Lattices lead to promising practical post-quantum digital signatures, combining asymptotic efficiency with strong theoretical security guarantees. However, tuning their parameters into practical instantiations is a delicate task. On the one hand, NIST round 2 candidates based on Lyubashevsky's design (such as Dilithium and qTesla) allow several tradeoffs between security and efficiency, but at the expense of a large bandwidth consumption. On the other hand, the hash-and-sign falcon signature is much more compact and is still very efficient, but it allows only two security levels, with large compactness and security gaps between them. We introduce a new family of signature schemes based on the Falcon design, which relies on module lattices. Our concrete instantiation enjoys the compactness and efficiency of Falcon, and allows an intermediate security level. It leads to the most compact lattice-based signature achieving a quantum security above 128 bits.

In contemporary times, there are many situations where users need to verify that their information is correctly retained by servers. At the same time, servers need to maintain transparency logs. Many algorithms have been designed to address this problem. For example, Certificate Transparency (CT) helps track certificates issued by Certificate Authorities (CAs), while CONIKS aims to provide key transparency for end users. However, these algorithms often suffer from either high append time or imbalanced inclusion-proof cost and consistency-proof cost. To find an optimal solution, we constructed two different but similar authenticated data structures tailored to two different lookup protocols. We propose ATS (Advanced Transparency System), which uses only linear storage cost to reduce append time and balances the time costs for both servers and users. When addressing the value-lookup problem, this system allows servers to append user information in constant time and enables radical-level inclusion proof and consistency proof. For the key transparency problem, the system requires logarithmic time complexity for the append operation and offers acceptable inclusion proof and consistency proof.

Boolean functions play an important role in designing and analyzing many cryptographic systems, such as block ciphers, stream ciphers, and hash functions, due to their unique cryptographic properties such as nonlinearity, correlation immunity, and algebraic properties. The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is an important area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds applications in privacy-preserving protocols and secure multi-party computations. In this manuscript, we present an efficient and generic two-party protocol (namely $$) for the secure evaluation of Boolean functions by utilizing a 1-out-of-2 Oblivious Transfer (OT) as a building block. $$ only employs XOR operations as the core computational step, thus making it lightweight and fast. Unlike other lightweight state-of-the-art designs of SBE, $$ avoids the use of additional cryptographic primitives, such as hash functions and commitment schemes to reduce the computational overhead.

A Timed Commitment (TC) with time parameter $$ is hiding for time at most $$, that is, commitments can be force-opened by any third party within time $$. In addition to various cryptographic assumptions, the security of all known TC schemes relies on the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck. In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by additionally relying on one-way permutations and collision-resistant hashing. Currently, TLPs are known from (a) the specific repeated squaring assumption, (b) the general (necessary) assumption on the existence of worst-case non-parallelizing languages and indistinguishability obfuscation, and (c) any iteratively sequential function and the hardness of the circular small-secret LWE problem. The latter admits a plausibly post-quantum secure instantiation. Hence, thanks to the generality of our transform, we get i) the first TC whose timed security is based on the the existence of non-parallelizing languages and ii) the first TC that is plausibly post-quantum secure. We first define quasi publicly-verifiable TLPs (QPV-TLPs) and construct them from any standard TLP in a black-box manner without relying on any additional assumptions. Then, we devise a black-box commit-and-prove system to transform any QPV-TLPs into a TC.

Aaronson, Atia, and Susskind [Aaronson et al., 2020] established that efficiently mapping between quantum states $$ and $$ is computationally equivalent to distinguishing their superpositions $$ and $$. We generalize this insight into a broader duality principle in quantum computation, wherein manipulating quantum states in one basis is equivalent to extracting their value in a complementary basis. In its most general form, this duality principle states that for a given group, the ability to implement a unitary representation of the group is computationally equivalent to the ability to perform a Fourier subspace extraction from the invariant subspaces corresponding to its irreducible representations. Building on our duality principle, we present the following applications: * Quantum money, which captures quantum states that are verifiable but unclonable, and its stronger variant, quantum lightning, have long resisted constructions based on concrete cryptographic assumptions. While (public-key) quantum money has been constructed from indistinguishability obfuscation (iO)—an assumption widely considered too strong—quantum lightning has not been constructed from any such assumptions, with previous attempts based on assumptions that were later broken. We present the first construction of quantum lightning with a rigorous security proof, grounded in a plausible and well-founded cryptographic assumption. We extend Zhandry's construction from Abelian group actions [Zhandry, 2024] to non-Abelian group actions, and eliminate Zhandry's reliance on a black-box model for justifying security. Instead, we prove a direct reduction to a computational assumption—the pre-action security of cryptographic group actions. We show how these group actions can be realized with various instantiations, including with the group actions of the symmetric group implicit in the McEliece cryptosystem. * We provide an alternative quantum money and lightning construction from one-way homomorphisms, showing that security holds under specific conditions on the homomorphism. Notably, our scheme exhibits the remarkable property that four distinct security notions—quantum lightning security, security against both worst-case cloning and average-case cloning, and security against preparing a specific canonical state—are all equivalent. * Quantum fire captures the notion of a samplable distribution on quantum states that are efficiently clonable, but not efficiently telegraphable, meaning they cannot be efficiently encoded as classical information. These states can be spread like fire, provided they are kept alive quantumly and do not decohere. The only previously known construction relied on a unitary quantum oracle, whereas we present the first candidate construction of quantum fire in the plain model.

We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning With Errors (LWE) assumption whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et al. (EUROCRYPT 2014) -- we reduce the key size in the latter from $$ to $$. The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo (TCC 2022), which achieves $$ key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

Service discovery is essential in wireless communications. However, existing service discovery protocols provide no or very limited privacy protection for service providers and clients, and they often leak sensitive information (e.g., service type, client’s identity and mobility pattern), which leads to various network-based attacks (e.g., spoofing, man-in-the-middle, identification and tracking). In this paper, we propose a private service discovery protocol, called PriSrv, which allows a service provider and a client to respectively specify a fine-grained authentication policy that the other party must satisfy before a connection is established. PriSrv consists of a private service broadcast phase and an anonymous mutual authentication phase with bilateral control, where the private information of both parties is hidden beyond the fact that a mutual match to the respective authentication policy occurred. As a core component of PriSrv, we introduce the notion of anonymous credential-based matchmaking encryption (ACME), which exerts dual-layer matching in one step to simultaneously achieve bilateral flexible policy control, selective attribute disclosure and multi-show unlinkability. As a building block of ACME, we design a fast anonymous credential (FAC) scheme to provide constant size credentials and efficient show/verification mechanisms, which is suitable for privacy-enhanced and highly usable service discovery in wireless networks. We present a concrete PriSrv protocol that is interoperable with popular wireless communication protocols, such as Wi-Fi Extensible Authentication Protocol (EAP), mDNS, BLE and Airdrop, to offer privacy-enhanced protection. We present formal security proof of our protocol and evaluate its performance on multiple hardware platforms: desktop, laptop, mobile phone and Raspberry Pi. PriSrv accomplishes private discovery and secure connection in less than 0.973 s on the first three platforms, and in less than 2.712 s on Raspberry Pi 4B. We also implement PriSrv into IEEE 802.1X in the real network to demonstrate its practicality.

Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling-based quantum advantage and searching-based one. Previous work [Morimae and Yamakawa, Crypto 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs, which solves the open question of [Chung, Goldin, and Gray, Crypto 2024]. Moreover, it is the first quantum-computation-classical-communication (QCCC) application of OWPuzzs.

The succinct non-interactive argument of knowledge (SNARK) technique has been extensively utilized in blockchain systems to replace the costly on-chain computation with the verification of a succinct proof. However, most existing applications verify each proof independently, resulting in a heavy load on nodes and high transaction fees for users. Currently, the mainstream proof aggregation schemes are based on a generalized inner product argument, which has a logarithmic proof size and verification cost. To improve the efficiency of verifying multiple proofs, we introduce SnarkFold, a novel SNARK-proof aggregation scheme with constant verification time and proof size. SnarkFold is derived from incrementally verifiable computation (IVC) and is optimized further through the folding scheme. By folding multiple instance-proof pairs, SnarkFold defers the expensive SNARK verification (e.g., elliptic curve pairing) to the final step. Additionally, we propose a generic technique to enhance the verifier's efficiency by delegating instance aggregation tasks to the prover. The verifier only needs a simple preprocessing to check the validity of the delegation. We further introduce folding schemes for Groth16 and Plonk proofs. Experimental results demonstrate that SnarkFold offers significant advantages, with an aggregated Plonk proof size of just $$ KB and the verification time of only $$ ms for aggregating 4096 Plonk proofs.

Most existing MPC protocols consider the homogeneous setting, where all the MPC players are assumed to have identical communication and computation resources. In practice, the player with the least resources often becomes the bottleneck of the entire MPC protocol execution. In this work, we initiate the study of so-called \emph{load-balanced MPC} in heterogeneous computing. A load-balanced MPC protocol can adjust the workload of each player accordingly to maximize the overall resource utilization. In particular, we propose new notions called composite circuit and composite garbling scheme, and construct two efficient server-aided protocols with malicious security and semi-honest security, respectively. Our maliciously secure protocol is over 400$$ faster than the authenticated garbling protocol (CCS '17) and up to 4.3$$ faster than the state-of-the-art server-aided MPC protocol of Lu et al. (TDSC '23); our semi-honest protocol is up to 173$$ faster than the optimized BMR protocol (CCS '16) and is up to 3.8$$ faster than the protocol of Lu et al.

We say there is a share conversion from a secret sharing scheme $$ to another scheme $$ implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret sharing under $$ to a valid (but not necessarily random) secret sharing under $$ of the same secret. If such a conversion exists, we say that $$. This notion was introduced by Cramer et al. (TCC'05), where they particularly proved that for any access structure (AS), any linear secret sharing scheme over a given field $$, has a conversion from a CNF scheme, and is convertible to a DNF scheme. In this work, we initiate a systematic study of convertability between secret sharing schemes, and present a number of results with implications to the understanding of the convertibility landscape. - In the context of linear schemes, we present two key theorems providing necessary conditions for convertibility, proved using linear-algebraic tools. It has several implications, such as the fact that Shamir secret sharing scheme can be neither maximal or minimal. Another implication of it is that for a broad class of access structures, a linear scheme where some party has sufficiently small share complexity, may not be minimal. - Our second key result is a necessary condition for convertibility to CNF from a broad class of (not necessarily linear) schemes. This result is proved via information-theoretic techniques and implies non-maximality for schemes with share complexity smaller than that of CNF. We also provide a condition which is both necessary and sufficient for the existence of a share conversion to some linear scheme. The condition is stated as a system of linear equations, such that a conversion exists iff. a solution to the linear system exists. We note that the impossibility results for linear schemes may be viewed as identifying a subset of contradicting equations in the system. Another contribution of our paper, is in defining and studying share conversion for evolving secret sharing schemes. In such a schemes, recently introduced by Komargodski et al. (IEEE ToIT'18), the number of parties is not bounded apriori, and every party receives a share as it arrives, which never changes in the sequel. Our impossibility results have implications to the evolving setting as well. Interestingly, that unlike the standard setting, there is no maximum or minimum in a broad class of evolving schemes, even without any restriction on the share size. Finally, we show that, generally, there is no conversion between additive schemes over different fields, however by degrading to statistical security, it may be possible to create convertible schemes.

Numerous applications in homomorphic encryption require an operation that moves the slots of a ciphertext to the coefficients of a different ciphertext. For the BGV and BFV schemes, the only efficient algorithms to implement this slot-to-coefficient transformation were proposed in the setting of non-power-of-two cyclotomic rings. In this paper, we devise an FFT-like method to decompose the slot-to-coefficient transformation (and its inverse) for power-of-two cyclotomic rings. The proposed method can handle both fully and sparsely packed slots. Our algorithm brings down the computational complexity of the slot-to-coefficient transformation from a linear to a logarithmic number of FHE operations, which is shown via a detailed complexity analysis. The new procedures are implemented in Microsoft SEAL for BFV. The experiments report a speedup of up to $$ when packing $$ elements from $$. We also study a fully packed bootstrapping operation that refreshes $$ elements from $$ and obtain an amortized speedup of $$.

LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures — basis potential (Pot) and squared sum (SS) — both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold $$ for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350.

HAWK is a lattice-based signature scheme candidate to the fourth call of the NIST's Post-Quantum standardization campaign. Considered as a cousin of Falcon (one of the future NIST post-quantum standards) one can wonder whether HAWK shares the same drawbacks as Falcon in terms of side-channel attacks. Indeed, Falcon signature algorithm and particularly its Gaussian sampler, has shown to be highly vulnerable to power-analysis attacks. Besides, efficiently protecting Falcon's signature algorithm against these attacks seems a very challenging task. This work presents the first power analysis leakage review on HAWK signature scheme: it extensively assesses the vulnerabilities of a central and sensitive brick of the scheme, the discrete Gaussian sampler. Knowing the output x of the sampler for a given signature leads to linear information about the private key of the scheme. This paper includes several demonstrations of simple power analysis attacks targeting this sample x with various attacker strengths, all of them performed on the reference implementation on a ChipWhisperer Lite with STM32F3 target (ARM Cortex M4). We report being able to perform key recoveries with very low (to no) offline resources. As this reference implementation of HAWK is not claimed to be protected against side-channel attacks, the existence of such attacks is not surprising, but they still concretely warn about the use of this unprotected signature on physical devices. To go further, our study proposes a generic way of assessing the performance of a side-channel attack on x even when less information is recovered, in a setting where some protections are implemented or when the attacker has less measurement possibilities. While it is easy to see that x is a sensitive value, quantifying the residual complexity of the key recovery with some knowledge about x (like the parity or the sign of some coefficients) is not straightforward as the underlying hardness assumption is the newly introduced Module-LIP problem. We propose to adapt the existing methodology of leaky LWE estimation tools (Dachman-Soled et al. at Crypto 2020) to exploit the retrieved information and lower down the residual key recovery complexity. To finish, we propose an ad-hoc technique to lower down the leakage on the identified vulnerability points. These modifications prevent our attacks on our platform and come with essentially no cost in terms of performance. It could be seen as a temporary solution and encourages more analysis on proven side-channel protection of HAWK like masking.

Yu et al. described an algorithm for conducting computational searches for quadratic APN functions over the finite field $$, and used this algorithm to give a classification of all quadratic APN functions with coefficients in $$ for dimensions $$ up to 9. In this paper, we speed up the running time of that algorithm by a factor of approximately $$. Based on this result, we give a complete classification of all quadratic APN functions over $$ with coefficients in $$. We also perform some partial computations for quadratic APN functions over $$ with coefficients in $$ , and conjecture that they form 6 CCZ-inequivalent classes which also correspond to known APN functions.

Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including filtering traffic patterns that are characteristic of proxy or circumvention protocols and actively probing potential proxy servers. Circumvention practitioners have developed fully encrypted protocols (FEPs), intended to have traffic that appears indistinguishable from random. A FEP is typically composed of a key exchange protocol to establish shared secret keys, and then a secure channel protocol to encrypt application data; both must avoid revealing to observers that an obfuscated protocol is in use. We formalize the notion of obfuscated key exchange, capturing the requirement that a key exchange protocol's traffic "looks random" and that it resists active probing attacks, in addition to ensuring secure session keys and authentication. We show that the Tor network's obfs4 protocol satisfies this definition. We then show how to extend the obfs4 design to defend against stronger censorship attacks and present a quantum-safe obfuscated key exchange protocol. To instantiate our quantum-safe protocol using the ML-KEM (Kyber) standard, we present Kemeleon, a new mapping between ML-KEM public keys/ciphertexts and uniform byte strings.

Approximate nearest neighbor search (ANNS), also known as vector search, is an important building block for varies applications, such as databases, biometrics, and machine learning. In this work, we are interested in the private ANNS problem, where the client wants to learn (and can only learn) the ANNS results without revealing the query to the server. Previous private ANNS works either suffers from high communication cost (Chen et al., USENIX Security 2020) or works under a weaker security assumption of two non-colluding servers (Servan-Schreiber et al., SP 2022). We present Panther, an efficient private ANNS framework under the single server setting. Panther achieves its high performance via several novel co-designs of private information retrieval (PIR), secretsharing, garbled circuits, and homomorphic encryption. We made extensive experiments using Panther on four public datasets, results show that Panther could answer an ANNS query on 10 million points in 23 seconds with 318 MB of communication. This is more than 6× faster and 18× more compact than Chen et al..

ARADI is a low-latency block cipher proposed by the NSA (National Security Agency) in 2024 for memory encryption. Bellini et al. experimentally demonstrated that in specific cubes of 5-round ARADI, the cube sums are byte-wise equal, for example, to 0x9d9dc5c5. This paper modifies the MILP-based division property algorithm to prove this and observes that the rotation amount of 8 in ARADI causes cancellations of monomials, allowing us to extend the byte-wise equal property up to 8 rounds. As a result, we obtained distinguishers for rounds 6 and 7 with lower data complexities of $$ and $$, respectively, compared to previous methods.

We present a new compact and tightly secure (anonymous) identity-based encryption (IBE) scheme based on structured lattices. This is the first IBE scheme that is (asymptotically) as compact as the most practical NTRU-based schemes and tightly secure under the module learning with errors (MLWE) assumption, known as the standard lattice assumption, in the (quantum) random oracle model. In particular, our IBE scheme is the most compact lattice-based scheme (except for NTRU-based schemes). We design our IBE scheme by instantiating the framework of Gentry, Peikert, and Vaikuntanathan (STOC`08) using the compact trapdoor proposed by Yu, Jia, and Wang (CRYPTO'23). The tightness of our IBE scheme is achieved by extending the proof technique of Katsumata et al. (ASIACRYPT'18, JoC'21) to the hermit normal form setting. To achieve this, we developed some new results on module lattices that may be of independent interest.

Federated Learning (FL) enables multiple clients to collaboratively train a machine learning model while keeping their data private, eliminating the need for data sharing. Two common approaches to secure aggregation (SA) in FL are the single-aggregator and multiple-aggregator models. This work focuses on improving the multiple-aggregator model. Existing multiple-aggregator protocols such as Prio (NSDI 2017), Prio+ (SCN 2022), Elsa (S&P 2023) either offer robustness only in the presence of semi-honest servers or provide security without robustness and are limited to two aggregators. We introduce Mario, the first multiple-aggregator Secure Aggregation protocol that is both secure and robust in a malicious setting. Similar to prior work of Prio and Prio+, Mario provides secure aggregation in a setup of $$ servers and $$ clients. Unlike previous work, Mario removes the assumption of semi-honest servers, and provides a complete protocol with robustness under malicious clients and malicious servers. Our implementation shows that \system is $$ and $$ faster than Elsa and Prio+, respecitively.

Distributed mean estimation (DME) is a fundamental and important task as it serves as a subroutine in convex optimization, aggregate statistics, and, more generally, federated learning. The inputs for distributed mean estimation (DME) are provided by clients (such as mobile devices), and these inputs often contain sensitive information. Thus, protecting privacy and mitigating the influence of malicious adversaries are critical concerns in DME. A surge of recent works has focused on building multiparty computation (MPC) based protocols tailored for the task of secure aggregation. However, MPC fails to directly address these two issues: (i) the potential manipulation of input by adversaries, and (ii) the leakage of information from the underlying function. This paper presents a novel approach that addresses both these issues. We propose a secure aggregation protocol with a robustness guarantee, effectively protecting the system from "faulty" inputs introduced by malicious clients. Our protocol further ensures differential privacy, so that the underlying function will not leak significant information about individuals. Notably, this work represents the first comprehensive effort to combine robustness and differential privacy guarantees in the context of DME. In particular, we capture the security of the protocol via a notion of "usefulness" combined with differential privacy inspired by the work of Mironov et al. (CRYPTO 2009) and formally analyze this security guarantee for our protocol.

In this article, we derive the weight distribution of linear codes stemming from a subclass of (vectorial) $$-ary plateaued functions (for a prime $$), which includes all the explicitly known examples of weakly and non-weakly regular plateaued functions. This construction of linear codes is referred in the literature as the first generic construction. First, we partition the class of $$-ary plateaued functions into three classes $$ and $$, according to the behavior of their dual function $$. Using these classes, we refine the results presented in a series of articles \cite{Mesnager2017, MesOzSi,Pelen2020, RodPasZhaWei, WeiWangFu}. Namely, we derive the full weight distributions of codes stemming from all $$-plateaued functions for $$ odd (parametrized by the weight of the dual $$), whereas for $$ even, the weight distributions are derived from the class of $$-plateaued functions in $$ parametrized using two parameters (including $$ and a related parameter $$). Additionally, we provide more results on the different weight distributions of codes stemming from functions in subclasses of the three different classes. The exact derivation of such distributions is achieved by using some well-known equations over finite fields to count certain dual preimages. In order to improve the dimension of these codes, we then study the vectorial case, thus providing the weight distributions of a few codes associated to known vectorial plateaued functions and obtaining codes with parameters $$. For the first time, we provide the full weight distributions of codes from (a subclass of) vectorial $$-ary plateaued functions. This class includes all known explicit examples in the literature. The obtained codes are minimal and self-orthogonal virtually in all cases. Notably, we show that this is the best one can achieve---there are no $$-ary self-dual minimal codes for any prime power $$, except for the ternary tetracode and the binary repetition code.

RAM (random access memory) is an important primitive in verifiable computation. In this paper, we focus on realizing RAM with efficient batching property, i.e, proving a batch of $$ updates on a RAM of size $$ while incurring a cost that is sublinear in $$. Classical approaches based on Merkle-trees or address ordered transcripts to model RAM correctness are either concretely inefficient, or incur linear overhead in the size of the RAM. Recent works explore cryptographic accumulators based on unknown-order groups (RSA, class-groups) to model the RAM state. While recent RSA accumulator based approaches offer significant improvement over classical methods, they incur linear overhead in the size of the accumulated set to compute witnesses, as well as prohibitive constant overheads. We realize a batching-efficient RAM with superior asymptotic and concrete costs as compared to existing approaches. Towards this: (i) we build on recent constructions of lookup arguments to allow efficient lookups even in presence of table updates, and (ii) we realize a variant of sub-vector relation addressed in prior works, which we call committed index lookup. We combine the two building blocks to realize batching-efficient RAM with sublinear dependence on size of the RAM. Our construction incurs an amortized proving cost of $$ for a batch of $$ updates on a RAM of size $$. Our results also benefit the recent arguments for sub-vector relation, by enabling them to be efficient in presence of updates to the table. We believe that this is a contribution of independent interest. We implement our solution to evaluate its concrete efficiency. Our experiments show that it offers significant improvement over existing works on batching-efficient accumulators/RAMs, with a substantially reduced resource barrier.

Elliptic Curve Point Multiplication (ECPM) is a key component of the Elliptic Curve Cryptography (ECC) hierarchy protocol. However, the specific estimation of resources required for this process remains underexplored despite its significance in the cryptanalysis of ECC algorithms, particularly binary ECC in GF (2𝑚). Given the extensive use of ECC algorithms in various security protocols and devices, it is essential to conduct this examination to gain valuable insights into its cryptanalysis, specifically in terms of providing precise resource estimations, which serve as a solid basis for further investigation in solving the Elliptic Curve Discrete Logarithm Problem. Expanding on several significant prior research, in this work, we refer to as ECPM cryptanalysis, we estimate quantum resources, including qubits, gates, and circuit depth, by integrating point addition (PA) and point-doubling (PD) into the ECPM scheme, culminating in a Shor’s algorithm-based binary ECC cryptanalysis circuit. Focusing on optimizing depth, we elaborate on and implement the most efficient PD circuit and incorporate optimized Karatsuba multiplication and FLT-based inversion algorithms for PA and PD operations. Compared to the latest PA-only circuits, our preliminary results showcase significant resource optimization for various ECPM implementations, including single-step ECPM, ECPM with combined or selective PA/PD utilization, and total−step ECPM (2𝑛 PD+2 PA).

In many multi-round public-coin interactive proof systems, challenges in different rounds serve different roles, but a formulation that actively utilizes this aspect has not been studied extensively. In this paper, we propose new notions called critical-round special honest verifier zero-knowledge and critical-round special soundness. Our notions are simple, intuitive, easy to apply, and capture several practical multi-round proof protocols including, but not limited to, those from the MPC-in-the-Head paradigm. We demonstrate the usefulness of these notions with two fundamental applications where three-round protocols are known to be useful, but multi-round ones generally fail. First, we show that critical-round proofs yield trapdoor commitment schemes. This result also enables the instantiation of post-quantum secure adaptor signatures and threshold ring signatures from MPCitH, resolving open questions in (Haque and Scafuro, PKC 2020) and in (Liu et al., ASIACRYPT 2024). Second, we show that critical-round proofs can be securely composed using the Cramer-Schoenmakers-Damgård method. This solves an open question posed by Abe et al. in CRYPTO 2024. Overall, these results shed new light on the potential of multi-round proofs in both theoretical and practical cryptographic protocol design

We present an efficient Publicly Verifiable Fully Homomorphic Encryption scheme that, along with being able to evaluate arbitrary boolean circuits over ciphertexts, also generates a succinct proof of correct homomorphic computation. Our scheme is based on FHEW proposed by Ducas and Micciancio (Eurocrypt'15), and we incorporate the GINX homomorphic accumulator (Eurocrypt'16) for improved bootstrapping efficiency. In order to generate the proof efficiently, we generalize the widely used Rank-1 Constraint System (R1CS) to the ring setting and obtain Ring R1CS, to natively express homomorphic computation in FHEW. In particular, we develop techniques to efficiently express in our Ring R1CS the "non-arithmetic" operations, such as gadget decomposition and modulus switching used in the FHEW construction. We further construct a SNARG for Ring R1CS instances, by translating the Ring R1CS instance into a sum-check protocol over polynomials, and then compiling it into a succinct non-interactive proof by incorporating the lattice-based polynomial commitment scheme of Cini, Malavolta, Nguyen, and Wee (Crypto'24). Putting together, our Publicly Verifiable FHE scheme relies on standard hardness assumptions about lattice problems such that it generates a succinct proof of homomorphic computation of circuit $$ in time $$ and of size $$. Besides, our scheme achieves the recently proposed IND-SA (indistinguishability under semi-active attack) security by Walter (EPrint 2024/1207) that exactly captures client data privacy when a homomorphic computation can be verified.

Based on the CM method for primality testing (ECPP) by Atkin and Morain published in 1993, we present two algorithms: one to generate embedded elliptic curves of SNARK-friendly curves, with a variable discriminant D; and another to generate families (parameterized by polynomials) with a fixed discriminant D. When D = 3 mod 4, it is possible to obtain a prime-order curve, and form a cycle. We apply our technique first to generate more embedded curves like Bandersnatch with BLS12-381 and we propose a plain twist-secure cycle above BLS12-381 with D = 6673027. We also devise about the scarcity of Bandersnatch-like CM curves, and show that with our algorithm, it is only a question of core-hours to find them. Second, we obtain families of prime-order embedded curves of discriminant D = 3 for BLS and KSS18 curves. Our method obtains families of embedded curves above KSS16 and can work for any KSS family. Our work generalizes the work on Bandersnatch (Masson, Sanso, and Zhang, and Sanso and El Housni).

We construct lollipops of pairing-friendly elliptic curves, which combine pairing-friendly chains with pairing-friendly cycles. The cycles inside these lollipops allow for unbounded levels of recursive pairing-based proof system composition, while the chains leading into these cycles alleviate a significant drawback of using cycles on their own: the only known cycles of pairing-friendly elliptic curves force the initial part of the circuit to be arithmetised on suboptimal (much larger) finite fields. Lollipops allow this arithmetisation to instead be performed over finite fields of an optimal size, while preserving the unbounded recursion afforded by the cycle. The notion of pairing-friendly lollipops itself is not novel. In 2019 the Coda + Dekrypt ``SNARK challenge'' offered a $20k USD prize for the best lollipop construction, but to our knowledge no lollipops were submitted to the challenge or have since emerged in the literature. This paper therefore gives the first construction of such lollipops. The main technical ingredient we use is a new way of instantiating pairing-friendly cycles over supersingular curves whose characteristics correspond to those in MNT cycles. The vast majority of MNT cycles that exist are unable to be instantiated in practice, because the corresponding CM discriminant is too large to construct the MNT curves explicitly. Our method can be viewed as a workaround that allows cycles to be instantiated regardless of the CM discriminant of the MNT curves.

A crucial ingredient for many cryptographic primitives such as key exchange protocols and advanced signature schemes is a commutative group action where the structure of the underlying group can be computed efficiently. SCALLOP provides such a group action, based on oriented supersingular elliptic curves. We present PEARL-SCALLOP, a variant of SCALLOP that changes several parameter and design choices, thereby improving on both efficiency and security and enabling feasible parameter generation for larger security levels. Within the SCALLOP framework, our parameters are essentially optimal; the orientation is provided by a $$-isogeny, where $$ is roughly equal to the discriminant of the acting class group. As an important subroutine we present a practical algorithm for generating oriented supersingular elliptic curves. To demonstrate our improvements, we provide a proof-of-concept implementation which instantiates PEARL-SCALLOP at all relevant security levels. Our timings are more than an order of magnitude faster than any previous implementation.

Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $$ bits per AND gate (for $$-bit computational security and any statistical security) and one with total communication of $$ bits per AND gate (for $$-bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: 1. The recent compression technique by Dittmer et al. (Crypto 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $$ bits to $$ bits per AND gate for $$-bit statistical security. 2. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $$ bits per AND gate. We designed a new authenticated garbling that does not use information theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $$ bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $$ bits per AND gate. 3. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $$ bits down to $$ bits per AND gate. Combined with our first contribution, this yields total amortized communication of $$ bits.

Homomorphically encrypted matrix operations are extensively used in various privacy-preserving applications. Consequently, reducing the cost of encrypted matrix operations is a crucial topic on which numerous studies have been conducted. In this paper, we introduce a novel matrix encoding method, named bicyclic encoding, under which we propose two new algorithms BMM-I and BMM-II for encrypted matrix multiplication. BMM-II outperforms the stat-of-the-art algorithms in theory, while BMM-I, combined with the segmented strategy, performs well in practice, particularly for matrices with high dimensions. Another noteworthy advantage of bicyclic encoding is that it allows for transposing an encrypted matrix entirely free. A comprehensive experimental study based on our proof-of-concept implementation shows that each algorithm introduced in this paper has specific scenarios outperforming existing algorithms, achieving speedups ranging from 2x to 38x.

This work focuses on concrete cryptanalysis of the isogeny-based cryptosystems SIDH/SIKE under realistic memory/storage constraints. More precisely, we are solving the problem of finding an isogeny of a given smooth degree between two given supersingular elliptic curves. Recent works by Adj et al. (SAC 2018), Costello et al. (PKC 2020), Longa et al. (CRYPTO 2021) suggest that parallel "memoryless" golden collision search by van Oorschot-Wiener (JoC 1999) is the best realistic approach for the problem. We show instead that the classic meet-in-the-middle attack is still competitive due to its very low computational overhead, at least on small parameters. As a concrete application, we apply the meet-in-the-middle attack with optimizations to the $IKEp182 challenge posed by Microsoft Research. The attack was executed on a cluster and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB.

Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform consequent complexity analysis with pen and paper, compared to the computer-aided approach of the original work. Furthermore, we show how MiF can be combined with plaintext structures for linear key schedules, allowing to increase the number of attacked rounds or to reduce the data complexity. We illustrate our methods on block cipher families CHAM and KATAN and show best-to-date single-key differential attacks for these ciphers.

Shoup and Smart (SS24) recently introduced a lightweight asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience directly from cryptographic hash functions (JoC 2024), offering plausible quantum resilience and computational efficiency. However, SS24 AVSS only achieves standard secrecy to keep the secret confidential against $$ corrupted parties \textit{if no honest party publishes its share}. In contrast, from ``heavyweight'' public-key cryptography, one can realize so-called \textit{high-threshold} asynchronous verifiable secret sharing (HAVSS), with a stronger \textit{high-threshold} secrecy to tolerate $$ corrupted parties and additional leaked shares from $$ honest parties. This raises the following question: can we bridge the remaining gap to design an efficient HAVSS using only lightweight cryptography? We answer the question in the affirmative by presenting a lightweight HAVSS with optimal resilience. When executing across $$ parties to share a secret, it attains a worst-case communication complexity of $$ (where $$ is the cryptographic security parameter) and realizes high-threshold secrecy to tolerate a fully asynchronous adversary that can control $$ malicious parties and also learn $$ additional secret shares from some honest parties. The (worst-case) communication complexity of our lightweight HAVSS protocol matches that of SS24 AVSS---the state-of-the-art lightweight AVSS without high-threshold secrecy. Notably, our design is a direct and concretely efficient reduction to hash functions in the random oracle model, without extra setup assumptions like CRS/PKI or heavy intermediate steps like hash-based zk-STARK.

Side-Channel Analysis (SCA) is critical in evaluating the security of cryptographic implementations. The search for hyperparameters poses a significant challenge, especially when resources are limited. In this work, we explore the efficacy of a multifidelity optimization technique known as BOHB in SCA. In addition, we proposed a new objective function called $$, which could be incorporated into any Bayesian Optimization used in SCA. We show the capabilities of both BOHB and $$ on four different public datasets. Specifically, BOHB could obtain the least number of traces in CTF2018 when trained in the Hamming weight and identity leakage model. Notably, this marks the first reported successful recovery of the key for the identity leakage model in CTF2018.

Deep neural networks (DNNs) represent a powerful technique for assessing cryptographic security concerning side-channel analysis (SCA) due to their ability to aggregate leakages automatically, rendering attacks more efficient without preprocessing. Nevertheless, despite their effectiveness, DNNs employed in SCA are predominantly black-box algorithms, posing considerable interpretability challenges. In this paper, we propose a novel technique called Key Guessing Occlusion (KGO) that acquires a minimal set of sample points required by the DNN for key recovery, which we call OccPoIs. These OccPoIs provide information on which areas of the traces are important to the DNN for retrieving the key, enabling evaluators to know where to refine their cryptographic implementation. After obtaining the OccPoIs, we first explore the leakages found in these OccPoIs to understand what the DNN is learning with first-order Correlation Power Analysis (CPA). We show that KGO obtains relevant sample points that have a high correlation with the given leakage model but also acquires sample points that first-order CPA fails to capture. Furthermore, unlike the first-order CPA in the masking setting, KGO obtains these OccPoIs without the knowledge of the shares or mask. Next, we employ the template attack (TA) using the OccPoIs to investigate if KGO could be used as a feature selection tool. We show that using the OccPoIs with TA can recover the key for all the considered synchronized datasets and is consistent as a feature selection tool even on datasets protected by first-order masking. Furthermore, it also allows a more efficient attack than other feature selections on the first-order masking dataset called ASCADf.

With the advent of quantum computers, the security of cryptographic primitives, including digital signature schemes, has been compromised. To deal with this issue, some signature schemes have been introduced to resist against these computers. These schemes are known as post-quantum signature schemes. One group of these schemes is based on the hard problems of coding theory, called code-based cryptographic schemes. Several code-based signature schemes are inspired by the McEliece encryption scheme using three non-singular, parity-check, and permutation matrices as the only components of the private keys, and their product as the public key. In this paper, we focus on the analysis of a class of such signature schemes. For this purpose, we first prove that the linear relationships between the columns of the parity-check/generator matrix appear in the public key matrix, and by exploiting this feature we perform a forgery attack on one of the signature schemes of this class as an evidence. The complexity of this attack is of O(n^4).

We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO '23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.

We study those $$-permutations, and more generally those balanced $$-functions, whose component functions all admit a derivative equal to constant function 1 (this property itself implies balancedness). We call these functions quadratic-like permutations (resp. quadratic-like balanced functions) since all quadratic balanced functions have this property. We show that all Feistel permutations, all crooked permutations and (more generally) all balanced strongly plateaued functions have this same property and we observe that the notion is affine invariant. We also study in each of these classes and in the class of quadratic-like APN permutations the "reversed" property that every derivative in a nonzero direction has a component function equal to constant function 1, and we show that this property can be satisfied only if $$. We also show that all the quadratic-like power permutations $$, $$ must be quadratic, which generalizes a well-known similar result on power crooked functions. We give several constructions of quadratic-like permutations and balanced functions outside the three classes of quadratic balanced functions, permutations affine equivalent to Feistel permutations and crooked permutations. We characterize the property by the Walsh transform.

We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s SOS-decomposability. FLI takes two lookup instances $$, and expresses them as matrix equations $$ for $$, where each matrix $$ has rows which are elementary basis vectors in $$. Matrices that satisfy this condition are said to be in $$. Then, a folding scheme for $$ into a relaxed relation is used, which combines the matrices $$ as $$ for a random $$. Finally, the lookup equations are combined as $$. In FLI, only the property that a matrix is in $$ is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances. FLI+SOS builds upon FLI to enable folding of large SOS-decomposable tables. This is achieved through a variation of Lasso's approach to SOS-decomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar and Proofs for Deep Thought that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs, FLI+SOS can concretely be the cheapest folding solution.

In Side-Channel Analysis (SCA), statistical or machine learning methods are employed to extract secret information from power or electromagnetic (EM) traces. In many practical scenarios, raw power/EM traces can span hundreds of thousands of features, with relevant leakages occurring over only a few small segments. Consequently, existing SCAs often select a small number of features before launching the attack, making their success highly dependent on the feasibility of feature selection. However, feature selection may not always be possible, such as in the presence of countermeasures like masking or jitters. Several recent works have employed deep learning (DL) methods to conduct SCA directly on long raw traces, thereby reducing reliance on feature selection steps. However, these methods often perform poorly in the presence of various jitter-based countermeasures. While some methods, such as the one proposed by Hajra et al. (TCHES 2024), have shown high robustness to several jitter-based countermeasures on relatively short traces, we demonstrate in this work that their performance deteriorates as trace lengths increase. Consequently, existing DL models perform poorly on long traces or in the presence of various jitter-based countermeasures. To address these challenges, we propose HierNet, a hierarchical DL model designed for SCA on long traces. HierNet uses a two-level information assimilation process: at the base level, a shift-invariant DL model processes smaller trace segments; at the top level, another DL model aggregates the outputs from all segments to produce the final output. HierNet has been experimentally evaluated against various combinations of masking, random delay, and clock jitter countermeasures, using three publicly available SCA datasets with trace lengths up to 250K features. The results have been compared with four existing SCA benchmark models. They demonstrate HierNet's superiority, particularly on long traces or in the presence of clock jitter countermeasures, showcasing its ability to reach guessing entropy 1 with fewer than or around 10 attack traces, while the benchmark models fail to do so even using 5K attack traces. HierNet also exhibits significantly better results in low training data scenarios.

Cloud storage offers convenient data access and sharing, but security concerns remain. Existing secure cloud storage solutions often lack essential features like data integrity, multi-cloud support, user-friendly file sharing, and efficient search. This paper proposes a novel secure cloud storage system that addresses these limitations. Our system uses distributed storage and attribute-based encryption to enhance data availability, access control, and user experience. It also enables private and efficient file search and data retrievability verification. This approach overcomes the trade-offs present in prior work, offering a secure and user-friendly solution for cloud data management.

Privacy-preserving graph analysis allows performing computations on graphs that store sensitive information while ensuring all the information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden. The current work addresses this problem by designing a highly scalable framework, $$, that allows securely realising any graph algorithm. $$ relies on the technique of secure multiparty computation (MPC) to design a generic framework that improves over the state-of-the-art framework of GraphSC by Araki et al. (CCS'21). The key technical contribution is that $$ has round complexity independent of the graph size, which in turn allows attaining the desired scalability. Specifically, this is achieved by (i) decoupling the $$ primitive of GraphSC into separate operations of $$ and $$, (ii) designing a novel constant-round approach to realise $$, as well as (iii) designing a novel constant-round approach to realise the $$ primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of $$ for the application of contact tracing via BFS for 10 hops and observe that it takes less than 2 minutes when computing over a graph of size $$. Concretely it improves over the state-of-the-art up to a factor of $$ in online run time. Similar to GraphSC by Araki et al., since $$ relies on a secure protocol for shuffle, we additionally design a shuffle protocol secure against a semi-honest adversary in the 2-party with a helper setting. Given the versatility of shuffle protocol, the designed solution is of independent interest. Hence, we also benchmark the performance of the designed shuffle where we observe improvements of up to $$ in online run time when considering an input vector of size $$, in comparison to the state-of-the-art in the considered setting.

It is shown how bounds on exponential sums derived from modern algebraic geometry, and l-adic cohomology specifically, can be used to upper bound the absolute correlations of linear approximations for cryptographic constructions of low algebraic degree. This is illustrated by applying results of Deligne, Denef and Loeser, and Rojas-León, to obtain correlation bounds for a generalization of the Butterfly construction, three-round Feistel ciphers, and a generalization of the Flystel construction. For each of these constructions, bounds obtained using other methods are significantly weaker. In the case of the Flystel construction, our bounds resolve a conjecture by the designers. Correlation bounds of this type are relevant for the development of security arguments against linear cryptanalysis, especially in the weak-key setting or for primitives that do not involve a key. Since the methods used in this paper are applicable to constructions defined over arbitrary finite fields, the results are also relevant for arithmetization-oriented primitives such as Anemoi, which uses S-boxes based on the Flystel construction.

Homomorphic Encryption (HE) technology allows for processing encrypted data, breaking through data isolation barriers and providing a promising solution for privacy-preserving computation. The integration of HE technology into Convolutional Neural Network (CNN) inference shows potential in addressing privacy issues in identity verification, medical imaging diagnosis, and various other applications. The CKKS HE algorithm stands out as a popular option for homomorphic CNN inference due to its capability to handle real number computations. However, challenges such as computational delays and resource overhead present significant obstacles to the practical implementation of homomorphic CNN inference, largely due to the complex nature of HE operations. In addition, current methods for speeding up homomorphic CNN inference primarily address individual images or large batches of input images, lacking a solution for efficiently processing a moderate number of input images with fast homomorphic inference capabilities, which is more suitable for edge computing applications. In response to these challenges, we introduce a novel leveled homomorphic CNN inference scheme aimed at reducing latency and improving throughput using the CKKS scheme. Our proposed inference strategy involves mapping multiple inputs to a set of ciphertext by exploiting the sliding window properties of convolutions to utilize CKKS's inherent Single-Instruction-Multiple-Data (SIMD) capability. To mitigate the delay associated with homomorphic CNN inference, we introduce optimization techniques, including mask-weight merging, rotation multiplexing, stride convolution segmentation, and folding rotations. The efficacy of our homomorphic inference scheme is demonstrated through evaluations carried out on the MNIST and CIFAR-10 datasets. Specifically, results from the MNIST dataset on a single CPU thread show that inference for 163 images can be completed in 10.4 seconds with an accuracy of 98.9%, which is a 6.9 times throughput improvement over state-of-the-art works. Comparative analysis with existing methodologies highlights the superior performance of our proposed inference scheme in terms of latency, throughput, communication overhead, and memory utilization.

The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the security of a construction is captured by a ``single-stage'' security game, it may generally provide no meaningful guarantees when the security is captured by a ``multi-stage'' one. In particular, the indifferentiability framework does not capture offline-online games, where the adversary can perform an extensive offline computation to later speed up the online phase. Such security games are extremely common, both in practice and in theory. Over the past decade, there has been numerous attempts to meaningfully extend the indifferentiability framework to offline-online games, however, they all ultimately met with little success. In this work, our contribution is threefold. First, we propose an extension of the classical indifferentiability framework, we refer to as *offline-online-indifferentiability*, that applies in the context of attackers with an expensive offline phase (á la Ghoshal and Tessaro, CRYPTO '23). Second, we show that our notion lends itself to a natural and meaningful composition theorem for offline-online security games. Lastly, as our main technical contribution, we analyze the offline-online-indifferentiability of two classical variants of the Merkle-Damg\aa rd hashing mechanism, one where the key is fed only to the first block in the chain and the other where the key is fed to each block in the chain. For both constructions, we prove a *tight* bound on their offline-online-indifferentiability (i.e., an upper bound and an attack that matches it). Notably, our bound for the second variant shows that the construction satisfies *optimal* offline-online-indifferentiability.

In a zero-knowledge proof market, we have two sides. On one side, bidders with proofs of different sizes and some private value to have this proof computed. On the other side, we have distributors (also called sellers) which have compute available to process the proofs by the bidders, and these distributors have a certain private cost to process these proofs (dependent on the size). More broadly, this setting applies to any online resource allocation where we have bidders who desire a certain amount of a resource and distributors that can provide this resource. In this work, we study how to devise double auctions for this setting which are truthful for users, weak group strategy proof, weak budget balanced, computationally efficient, and achieve a good approximation of the maximum welfare possible by the set of bids. We denote such auctions as $$.

In 2018 Cai et al. proposed a multi-party quantum key agreement with five-qubit Brown states. They confirmed the security of their proposed scheme. However, Elhadad, Ahmed, et al. found the scheme cannot resist the collusion attack launched by legal participants. They suggested a modification and declared that their improved version is capable of resisting this type of attack. Nevertheless, after analysis, we found that the collusion attack still exists. Subsequently, we proposed a straightforward modification to prevent the attack. After analysis, we conclude that our modification meets the required security and collusion attack requirements, which are very important in the quantum key agreement scheme.

Proof-Carrying Data (PCD) is a foundational tool for ensuring the correctness of incremental distributed computations that has found numerous applications in theory and practice. The state-of-the-art PCD constructions are obtained via accumulation or folding schemes. Unfortunately, almost all known constructions of accumulation schemes rely on homomorphic vector commitments (VCs), which results in relatively high computational costs and insecurity in the face of quantum adversaries. A recent work of Bünz, Mishra, Nguyen, and Wang removes the dependence on homomorphic VCs by relying only on the random oracle model, but introduces a bound on the number of consecutive accumulation steps, which in turn bounds the depth of the PCD computation graph and greatly affects prover and verifier efficiency. In this work, we propose Arc, a novel hash-based accumulation scheme that overcomes this restriction and supports an unbounded number of accumulation steps. The core building block underlying Arc is a new accumulation scheme for claims about proximity of claimed codewords to the Reed--Solomon code. Our approach achieves near-optimal efficiency, requiring a small number of Merkle tree openings relative to the code rate, and avoids the efficiency loss associated with bounded accumulation depth. Unlike prior work, our scheme is also able to accumulate claims up to list-decoding radius, resulting in concrete efficiency improvements. We use this accumulation scheme to construct two distinct accumulation schemes, again relying solely on random oracles. The first approach accumulates RS proximity claims and can be used as an almost-drop-in replacement in existing PCD deployments based on IOP-based SNARKs. The second approach directly constructs an accumulation scheme for rank-1 constraint systems (and more generally polynomial constraint systems) that is simpler and more efficient than the former and prior approaches. We introduce the notion of Interactive Oracle Reductions (IORs) to enable a modular and simple security analysis. These extend prior notions of Reductions of Knowledge to the setting of IOPs.

We propose a group signature scheme with a function of designated traceability; each opener has attributes, and a signer of a group signature can be traced by only the openers whose attributes satisfy the boolean formula designated by the signer. We describe syntax and security definitions of the scheme. Then we give a generic construction of the scheme by employing a ciphertext-policy attribute-based encryption scheme.

Offline payments present an opportunity for central bank digital currency to address the lack of digital financial inclusion plaguing existing digital payment solutions. However, the design of secure offline payments is a complex undertaking; for example, the lack of connectivity during the payments renders double spending attacks trivial. While the identification of double spenders and penal sanctions may curb attacks by individuals, they may not be sufficient against concerted efforts by states or well-funded institutions. It is hence important to also rely on preventive measures that reduce the scale of such attacks. An example of such a measure is secure elements. These however are limited in compute and storage, making the design of solutions that offer comparable privacy guarantees to those of physical cash challenging. We address this with a protocol that offloads most of the payment computation to the user’s mobile device and restricts the computation on the secure element to deleting spent tokens, and generating a signature with a computation equivalent to that of ECDSA. We claim that the use of mobile devices or enhanced smart card-based devices are required for secure consumer-to-consumer payments. To further harden the protocol, we enable the efficient identification of double spenders on the off-chance an attacker successfully double spends. Finally, we prove its security in the ideal/real world paradigm, and evaluate its performance to demonstrate its practicality.

This short note describes an update to the sca25519 library, an ECC implementation computing the X25519 key-exchange protocol on the Arm Cortex-M4 microcontroller. The sca25519 software came with extensive mitigations against various side-channel and fault attacks and was, to our best knowledge, the first to claim affordable protection against multiple classes of attacks that are motivated by distinct real-world application scenarios. This library is protected against various passive and active side-channel threats. However, both classes of attacks were considered separately, i.e., combining the attacks is considered out-of-scope because to successfully execute such a combined attack, the adversary would need to be very powerful (e.g., a very well-equipped security laboratory). Protection against such powerful adversaries is considered infeasible without using dedicated protected hardware with which Arm Cortex-M4 is not equipped. However, there exists a particular class of easy and cheap active attacks: they are called tearing, and they are well known in the smartcard context. In this paper, we extend the scope of the library to also consider a combination of tearing and side-channel attacks. In this note, we show how we can mitigate such a combination by performing a small code update. The update does not affect the efficiency of the library.

We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following: • (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle. • We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle. • We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist. Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new ``path recording'' formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang.

The search for optimal differential trails for ARX ciphers is known to be difficult and scale poorly as the word size (and the branching through the carries of modular additions) increases.To overcome this problem, one may approximate the modular addition with the XOR operation, a process called linearization. The immediate drawback of this approach is that many valid and good trails are discarded. In this work, we explore different partial linearization trade-offs to model the modular addition through the \emph{window heuristic}, which restricts carry propagation to windows of $$ consecutive positions. This strategy enables the exploration of full linearization ($$), normal modelling ($$), and all the different trade-offs between completeness and speed in between. We give the corresponding SAT and MILP model and their parallel versions, and apply them to \chachacore, \speckfamily, \leafamily, and \hightfamily. Our method greatly outperforms all previous modeling of modular addition. In particular, we find the first differential path for 4 rounds of \chachacore with a probability greater than $$, and a corresponding 6 rounds boomerang distinguisher. This indicates that purely differential-based attacks have the potential to become competitive with differential-linear attacks, currently, the best-known attacks against \chachacore and other ARX ciphers. Finally, we exhibit an improved key recovery attack on reduced \leafamily.

We propose a new cryptographic primitive called "batched identity-based encryption" (Batched IBE) and its thresholdized version. The new primitive allows encrypting messages with specific identities and batch labels, where the latter can represent, for example, a block number on a blockchain. Given an arbitrary subset of identities for a particular batch, our primitive enables efficient issuance of a single decryption key that can be used to decrypt all ciphertexts having identities that are included in the subset while preserving the privacy of all ciphertexts having identities that are excluded from the subset. At the heart of our construction is a new technique that enables public aggregation (i.e. without knowledge of any secrets) of any subset of identities, into a succinct digest. This digest is used to derive, via a master secret key, a single succinct decryption key for all the identities that were digested in this batch. In a threshold system, where the master key is distributed as secret shares among multiple authorities, our method significantly reduces the communication (and in some cases, computation) overhead for the authorities. It achieves this by making their costs for key issuance independent of the batch size. We present a concrete instantiation of a Batched IBE scheme based on the KZG polynomial commitment scheme by Kate et al. (Asiacrypt'10) and a modified form of the BLS signature scheme by Boneh et al. (Asiacrypt'01). The construction is proven secure in the generic group model (GGM). In a blockchain setting, the new construction can be used for achieving mempool privacy by encrypting transactions to a block, opening only the transactions included in a given block and hiding the transactions that are not included in it. With the thresholdized version, multiple authorities (validators) can collaboratively manage the decryption process. Other possible applications include scalable support via blockchain for fairness of dishonest majority MPC, and conditional batched threshold decryption that can be used for implementing secure Dutch auctions and privacy preserving options trading.

The recent explosion of high-quality language models has necessitated new methods for identifying AI-generated text. Watermarking is a leading solution and could prove to be an essential tool in the age of generative AI. Existing approaches embed watermarks at inference and crucially rely on the large language model (LLM) specification and parameters being secret, which makes them inapplicable to the open-source setting. In this work, we introduce the first watermarking scheme for open-source LLMs. Our scheme works by modifying the parameters of the model, but the watermark can be detected from just the outputs of the model. Perhaps surprisingly, we prove that our watermarks are unremovable under certain assumptions about the adversary's knowledge. To demonstrate the behavior of our construction under concrete parameter instantiations, we present experimental results with OPT-6.7B and OPT-1.3B. We demonstrate robustness to both token substitution and perturbation of the model parameters. We find that the stronger of these attacks, the model-perturbation attack, requires deteriorating the quality score to 0 out of 100 in order to bring the detection rate down to 50%.

We construct a quantum oracle relative to which $$ but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to which $$, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which $$ but pseudorandom state generators (a quantum variant of pseudorandom generators) exist. We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of "quantum samplable" one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if $$. Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if $$, but are broken if $$. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".

The Brakerski/Fan-Vercauteren (BFV) scheme is a state-of-the-art scheme in Fully Homomorphic Encryption based on the Ring Learning with Errors (RLWE) problem. Thus, ciphertexts contain an error that increases with each homomorphic operation and has to stay below a certain threshold for correctness. This can be achieved by setting the ciphertext modulus big enough. On the other hand, a larger ciphertext modulus decreases the level of security and computational efficiency, making parameter selection challenging. Our work aims to improve the bound on the ciphertext modulus, minimizing it. Our main contributions are the following. Primarily, we perform the first average-case analysis of the error growth for the BFV scheme, significantly improving its estimation. For a circuit with a multiplicative depth of only 5, our bounds are up to 25.2 bits tighter than previous analyses and within 1.2 bits of the experimentally observed values. % Secondly, we give a general way to bound the ciphertext modulus for correct decryption that allows closed formulas. % Finally, we use our theoretical advances and propose the first parameter generation tool for the BFV scheme. Here, we add support for arbitrary but use-case-specific circuits, as well as the ability to generate easy-to-use code snippets, making our theoretical work accessible to both researchers and practitioners.

The theory of compressed $$-protocols [AC20, ACF21] provides a standardized framework for creating efficient $$-protocols. This method involves two main phases: first, amortization, which combines multiple instances that satisfy a homomorphic relation into a single instance; and second, Bulletproofs compression [BBB+18], which minimizes communication overhead to a logarithmic scale during the verification of the combined instance. For high-degree polynomial (non-homomorphic) relations, a circuit-based linearization technique is used to transform each instance into a linear relation, resulting in a protocol with at least linear complexity. In this paper, we provide a direct method to extend the compressed $$-protocol theory to polynomial relations, named $$-Check. One major contribution of $$-Check is to eliminate the linear cost associated with linearization in amortization. To achieve this, we employ a sum-check during this phase to ensure a logarithmic communication cost. To the best of our knowledge, $$-Check is the first work to achieve a logarithmic amortization for polynomial relations. Nevertheless, without linearization, the amortized relation may not be linear, which hinders us from using Bulletproofs compression. To overcome this problem, we employ another sum-check during the compression phase to effectively manage high-degree relations. Additionally, we propose several variants of our techniques and adapt them for arithmetic circuit relations. We also demonstrate the practicality of our compressed $$-protocol theory through applications such as binary proofs, range proofs, and partial knowledge proofs. Our basic protocols are initially based on the Discrete Logarithm (DL) assumption, and we have further extended these to incorporate the Strong-RSA assumption and the Generalized Discrete Logarithm Representation (GDLR) assumption. Our work expands the scope of compressed $$-protocol theory and provides a robust foundation for real-world cryptographic applications.

Convex Consensus (CC) allows a set of parties to agree on a value $$ inside the convex hull of their inputs with respect to a predefined abstract convexity notion, even in the presence of byzantine parties. In this work, we focus on achieving CC in the best-of-both-worlds paradigm, i.e., simultaneously tolerating at most $$ corruptions if communication is synchronous, and at most $$ corruptions if it is asynchronous. Our protocol is randomized, which is a requirement under asynchrony, and we prove that it achieves optimal resilience. In the process, we introduce communication primitives tailored to the network-agnostic model. These are a deterministic primitive allowing parties to obtain intersecting views (Gather), and a randomized primitive leading to identical views (Agreement on a Core-Set). Our primitives provide stronger guarantees than previous counterparts, making them of independent interest.

We present experimental findings on the decoding failure rate (DFR) of BIKE, a fourth-round candidate in the NIST Post-Quantum Standardization process, at the 20-bit security level using graph-theoretic approaches. We select parameters according to BIKE design principles and conduct a series of experiments using Rust to generate significantly more decoding failure instances than in prior work using SageMath. For each decoding failure, we study the internal state of the decoder at each iteration and find that for 97% of decoding failures at block size $$, the decoder reaches a fixed point within 7 iterations. We then consider the corresponding Tanner graphs of each decoding failure instance to determine whether the decoding failures are due to absorbing sets. We find that 81% of decoding failures at $$ were caused by absorbing sets, and of these the majority were $$-near codewords.

Evaluation of cryptographic implementations with respect to side-channels has been mandated at high security levels nowadays. Typically, the evaluation involves four stages: detection, modeling, certification and secret recovery. In pursuit of specific goal at each stage, inherently different techniques used to be considered necessary. However, since the recent works of Eurocrypt2022 and Eurocrypt2024, linear regression analysis (LRA) has uniquely become the technique that is well-applied throughout all the stages. In this paper, we concentrate on this silver bullet technique within the field of side-channel. First, we address the fundamental problems of why and how to use LRA. The discussion of nominal and binary nature explains its strong applicability. To sustain effective outcomes, we provide in-depth analyses about the design matrix, regarding the sample distribution of plaintext and the chosen polynomial degree. We summarize ideal conditions that totally avoid multicollinearity problem, and explore the novel evaluator-advantageous property of LRA by means of model diagnosis. Then, we trace the roots where we theoretically elaborate its connections with traditional side-channel techniques, including Correlation Power Analysis (CPA), Distance-of-Means analysis (DoM) and Partition Power Analysis (PPA), in terms of regression coefficients, regression model and coefficient of determination. Finally, we probe into the state-of-the-art combined LRA with the so-called collapse function, demonstrating its relationship with another refined technique, G-DoM. We argue that properly relaxing the definition of bit groups equally satisfies our conclusions. Experimental results are in line with the theory, confirming its correctness.

This paper explores advancements in the Gentry-Sahai-Waters (GSW) fully homomorphic encryption scheme, addressing challenges related to message data range limitations and ciphertext size constraints. We introduce a novel approach utilizing the Chinese Remainder Theorem (CRT) for message decomposition, significantly expanding the allowable message range to the entire plaintext space. This method enables unrestricted message selection and supports parallel homomorphic operations without intermediate decryption. Additionally, we adapt existing ciphertext compression techniques, such as the PVW-like scheme, to reduce memory overhead associated with ciphertexts. Our experimental results demonstrate the effectiveness of the CRT-based decomposition in increasing the upper bound of message values and improving the scheme's capacity for consecutive homomorphic operations. However, compression introduces a trade-off, necessitating a reduced message range due to error accumulation. This research contributes to enhancing the practicality and efficiency of the GSW encryption scheme for complex computational scenarios while managing the balance between expanded message range, computational complexity, and storage requirements.

This is a survey on the One Time Pad (OTP) and its derivatives, from its origins to modern times. OTP, if used correctly, is (the only) cryptographic code that no computing power, present or future, can break. Naturally, the discussion shifts to the creation of long random sequences, starting from short ones, which can be easily shared. We could call it the Short Key Dream. Many problems inevitably arise, which affect many fields of computer science, mathematics and knowledge in general. This work presents a vast bibliography that includes fundamental classical works and current papers on randomness, pseudorandom number generators, compressibility, unpredictability and more.

Fully Homomorphic Encryption (FHE) is a promising privacy-enhancing technique that enables secure and private data processing on untrusted servers, such as privacy-preserving neural network (NN) evaluations. However, its practical application presents significant challenges. Limitations in how data is stored within homomorphic ciphertexts and restrictions on the types of operations that can be performed create computational bottlenecks. As a result, a growing body of research focuses on optimizing existing evaluation techniques for efficient execution in the homomorphic domain. One key operation in this space is matrix multiplication, which forms the foundation of most neural networks. Several studies have even proposed new FHE schemes specifically to accelerate this operation. The optimization of matrix multiplication is also the primary goal of our work. We leverage the Single Instruction Multiple Data (SIMD) capabilities of FHE to increase data packing and significantly reduce the KeySwitch operation count— an expensive low-level routine in homomorphic encryption. By minimizing KeySwitching, we surpass current state-of-the-art solutions, requiring only a minimal multiplicative depth of two. The best-known complexity for matrix multiplication at this depth is $$ for matrices of size $$. Remarkably, even the leading techniques that require a multiplicative depth of three still incur a KeySwitch complexity of $$. In contrast, our method reduces this complexity to $$ while maintaining the same level of data packing. Our solution broadly applies to all FHE schemes supporting Single Instruction Multiple Data (SIMD) operations. We further generalize the technique in two directions: allowing arbitrary packing availability and extending it to rectangular matrices. This versatile approach offers significant improvements in matrix multiplication performance and enables faster evaluation of privacy-preserving neural network applications.

Over the last two decades, microarchitectural side channels have been the focus of a large body of research on the development of new attack techniques, exploiting them to attack various classes of targets and designing mitigations. One line of work focuses on increasing the speed of the attacks, achieving higher levels of temporal resolution that can allow attackers to learn finer-grained information. The most recent addition to this line of work is Prime+Scope [CCS '21], which only requires a single access to the L1 cache to confirm the absence of victim activity in a cache set. While significantly faster than prior attacks, Prime+Scope is still an order of magnitude slower than cache access. In this work, we set out to close this gap. We draw on techniques from research into microarchitectural weird gates, software constructs that exploit transient execution to perform arbitrary computation on cache state. We design the Spec-o-Scope gate, a new weird gate that performs 10 cache probes in quick succession, and forms the basis for our eponymous attack. Our Spec-o-Scope attack achieves an order of magnitude improvement in temporal resolution compared to the previous state-of-the-art of Prime+Scope, reducing the measurement time from ~70 cycles to only 5 --- only one cycle more than an L1 cache access. We experimentally verify that our attack can detect timing differences in a 5 cycle resolution. Finally, using our Spec-o-Scope attack, we show the first microarchitectural side-channel attack on an unmodified AES S-box-based implementation, which uses generic CPU features and does not require manipulation of the operating system's scheduler.

Large polynomial multiplication is one of the computational bottlenecks in fully homomorphic encryption implementations. Usually, these multiplications are implemented using the number-theoretic transformation to speed up the computation. State-of-the-art GPU-based implementation of fully homomorphic encryption computes the number theoretic transformation in two different kernels, due to the necessary synchronization between GPU blocks to ensure correctness in computation. This can be a serious limitation in embedded systems that only have constrained computational resources to support the time-consuming homomorphic encryption. In this paper, we proposed a series of techniques to improve the performance of number theoretic transform targeting homomorphic encryption on a GPU device. Firstly, we proposed to arrange the polynomials in a transposed manner and skip the last two levels of radix-4 number theoretic transformation, allowing us to completely avoid the block synchronization in NTT implementation. This technique improved the performance of homomorphic encryption by 1.37× and 1.34× on RTX 4060 and Jetson Orin Nano respectively, compared to the conventional approach that uses full NTT without skipping any levels. However, such an approach also introduces extra overhead in the subsequent point-wise multiplication, which slows down the homomorphic multiplication. To reduce this negative impact, a fast 16 × 16 point-wise multiplication implementation was proposed, which relies on the heavily optimized Toom-Cook 4-way algorithm. Experimental results show that our proposed homomorphic multiplication can achieve similar latency compared to Jung et al. and Yang et al., which are the best results to date. This shows that the proposed cuTraNTT is able to reduce the latency of homomorphic encryption without sacrificing the performance in homomorphic multiplication.

We provide the first construction of compact Functional Encryption (FE) for pseudorandom functionalities from the evasive LWE and LWE assumptions. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from uniform for every input seen by the adversary. This yields the first compact FE for a nontrivial class of functions which does not rely on pairings. We demonstrate the power of our new tool by using it to achieve optimal parameters for both key-policy and ciphertext-policy Attribute Based Encryption (ABE) schemes for circuits of unbounded depth, from just the LWE and evasive LWE assumptions. This improves prior work along the twin axes of assumptions and performance. In more detail, this allows to: (i) replace the assumption of circular evasive LWE used in the work of Hseih, Lin and Luo (FOCS 2023) by plain evasive LWE, (ii) remove the need for the circular tensor LWE assumption in the work of Agrawal, Kumari and Yamada (CRYPTO, 2024), (iii) improve parameters obtained by both aforementioned works to achieve asymptotic optimality. Previously, optimal parameters for ABE schemes were only achieved using compact FE for P (Jain, Lin and Luo, Eurocrypt 2023) – we show that compact FE for a much weaker class (albeit with incomparable security) suffices. Thus we obtain the first optimal ABE schemes for unbounded depth circuits which can be conjectured post-quantum secure. Along the way, we define and construct a new primitive which we term laconic pseudorandom obfuscation from the same assumptions – this may be of independent interest.

When we use signature schemes in practice, we sometimes should consider security beyond unforgeability. This paper considers security against key substitution attacks of multi-signer signatures (i.e., aggregate signatures and multi-signatures). Intuitively, this security property ensures that a malicious party cannot claim the ownership of a signature that is created by an honest signer. We investigate security against key substitution attacks of a wide range of aggregate signature schemes and multi-signature schemes: the Boneh-Gentry-Lynn-Shacham aggregate signature scheme, the sequential aggregate signature scheme by Lysyanskaya et al., the multi-signature scheme by Bellare and Neven, MuSig2, and the ordered multi-signature scheme by Boldyreva et al. Furthermore, if the scheme does not provide security against key substitution attacks, then we modify the scheme to become secure against the attacks.

For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup). However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is impossible to construct UC-secure PAKE protocols with a straightforward CoR-setup (i.e., either the CRS is functional but the RO is compromised, or the RO is functional but the CRS is compromised). To circumvent this impossibility result, we investigate how to design UC-secure PAKE protocols with a fine-grained CoR-setup, where either the CRS is functional but the RO is non-functional, or vice versa. Different from the straightforward CoR-setup, a fine-grained non-functional setup is not necessarily completely compromised and fully controlled by the adversary; Instead, we consider this non-functional setup may still offer certain security properties. Certainly, the non-functional setup alone should be useless for achieving UC-security. We present a UC-secure PAKE protocol under two conditions: either the CRS is functional while the RO is non-functional (falling back to a collision-resistant hash function), or the RO is functional while the CRS is non-functional (falling back to a global CRS). Before presenting our construction, we first prove that a global CRS setup alone is insufficient for achieving UC-secure PAKE. This impossibility result highlights the non-triviality of our approach. To obtain our construction, we introduce several techniques as follows: (1) We propose a new variant of Non-Interactive Key Exchange (NIKE), called homomorphic NIKE with associated functions, which captures key properties of existing RO-based PAKE protocols. This new primitive serves as an important component in our construction. (2) We develop a ``Brute Force'' extraction strategy which allows us to provide security analysis for our UC-secure PAKE with a fine-grained CoR-setup for polynomial-sized password spaces. (3) We introduce a novel password space extension technique that enables the expansion of PAKE protocols from polynomial-sized to arbitrary-sized password spaces. (4) Finally, to ensure provable security for our password space extension in UC-secure PAKEs, we modify existing PAKE functionalities to prevent responses that reveal the correctness of password guesses. This is a reasonable adjustment, as our protocol provides only implicit authentication. We further present a PAKE protocol in the BPR framework (Bellare, Pointcheval, Rogaway, EuroCrypt 2000), assuming either the CRS is functional while the RO falls back to a collision-resistant hash function, or the RO is functional but the CRS trapdoor is allowed to be learned by the adversary.

A mixnet developed by Hébant et al. (PKC '20) employs certified ciphertexts that carry homomorphic signatures from an authority, reducing the complexity of the shuffling proof, and thereby enabling efficient large-scale deployment. However, their privacy relies on trusting the authority, making it unsuitable for voting, the primary application of mixnets. Building on the prior work, we leverage recent advances in equivalence class signatures by replacing homomorphic signatures with newly developed two-party mercurial signatures on randomizable ciphertexts. This allows users and the authority to jointly sign ciphertexts and randomize keys, ciphertexts, and signatures, all while preserving the embedded messages. We demonstrate that our mixnet is suitable for receipt-free voting without requiring trust in the signing authority for privacy. To assess scalability, we compare our approach to other scalable mixnet solutions, implement our protocols, and provide concrete performance benchmarks. Our results show that our mixnet significantly outperforms existing alternatives in both computation and communication efficiency. Specifically, verifying the mixing process for 50,000 ciphertexts takes just 135 seconds on a commodity laptop using ten mixers, illustrating the practical viability of our approach.

Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects---both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processin} attacks in which the adversary gains access to (classical or quantum) advice that is relevant to the particular construction. In this work, we show that indifferentiability is (generically) insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable (with pre-computation) from a random oracle. This yields the first (and tight) classical/quantum space-time trade-off for one-round sponge inversion.

Liu et al. (ITCS22) initiated the study of designing a secure position verification protocol based on a specific proof of quantumness protocol and classical communication. In this paper, we study this interesting topic further and answer some of the open questions that are left in that paper. We provide a new generic compiler that can convert any single round proof of quantumness-based certified randomness protocol to a secure classical communication-based position verification scheme. Later, we extend our compiler to different kinds of multi-round proof of quantumness-based certified randomness protocols. Moreover, we instantiate our compiler with a random circuit sampling (RCS)-based certified randomness protocol proposed by Aaronson and Hung (STOC 23). RCS-based techniques are within reach of today's NISQ devices; therefore, our design overcomes the limitation of the Liu et al. protocol that would require a fault-tolerant quantum computer to realize. Moreover, this is one of the first cryptographic applications of RCS-based techniques other than certified randomness.

In recent years, urban areas have experienced a rapid increase in vehicle numbers, while the availability of parking spaces has remained largely static, leading to a significant shortage of parking spots. This shortage creates considerable inconvenience for drivers and contributes to traffic congestion. A viable solution is the temporary use of private parking spaces by homeowners during their absence, providing a means to alleviate the parking problem and generate additional income for the owners. However, current systems for sharing parking spaces often neglect security and privacy concerns, exposing users to potential risks. This paper presents PISA, a novel Privacy-Preserving Smart Parking scheme designed to address these issues through a cryptographically secure protocol. PISA enables the anonymous sharing of parking spots and allows vehicle owners to park without revealing any personal identifiers. Our primary contributions include the development of a comprehensive bi-directional anonymity framework that ensures neither party can identify the other, and the use of formal verification methods to substantiate the soundness and reliability of our security measures. Unlike existing solutions, which often lack a security focus, fail to provide formal validation, or are computationally intensive, PISA is designed to be both secure and efficient.

Since designing a dedicated secure symmetric PRF is difficult, various works studied optimally secure PRFs from the sum of independent permutations (SoP). At CRYPTO'20, Gunsing and Mennink proposed the Summation-Truncation Hybrid (STH). While based on SoP, STH releases additional $$ bits of the permutation calls and sums $$ bits of them. Thus, it produces $$ bits at $$-bit PRF security. Both SoP or STH can be used directly in encryption schemes or MACs in place of permutation calls for higher security. However, simply replacing every call as in GCM-SIV$$ would demand more calls. For encryption schemes, Iwata's XORP scheme is long known to provide a better trade-off between efficiency and security. It extends SoP to variable-length-outputs by using $$ calls to a block cipher where the output of one call is added to each of the other $$ outputs. A similar extension can be conducted for STH that we call XTH, the XORP-Truncation Hybrid. Such an extension was already suggested in the final discussion by Gunsing and Mennink, but left as an open problem. This work fills the gap by formalizing and proving the security of XTH. For a rate of $$ as in XORP, we show $$-bit security for XTH.

We present a distributed ECDSA protocol, for any number of signatories. The protocol improves on that of the authors (CCS'20), which in turn builds on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18). Specifically: ** Only the last round of the protocol requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. ** The protocol withstands adaptive corruption of signatories. Furthermore, it includes a periodic refresh mechanism and guarantees proactive security. ** The protocol achieves accountability by identifying corrupted signatories in case of failure to generate a valid signature. (Identifiable abort) Furthermore, we formulate a distributed signature ideal functionality within the UC framework that guarantees unforgeability, proactive security, and identifiable abort, and show that the protocol realizes this functionality in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. This combination of properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and universally composable security) make our protocol a good fit for threshold wallets for ECDSA-based cryptocurrencies.

With the recent standardization of post-quantum cryptographic algorithms, research efforts have largely remained centered on public key exchange and encryption schemes. Argument systems, which allow a party to efficiently argue the correctness of a computation, have received comparatively little attention regarding their quantum-resilient design. These computational integrity frameworks often rely on cryptographic assumptions, such as pairings or group operations, which are vulnerable to quantum attacks. In this work, we present a fully implemented post-quantum secure argument system that compresses unbounded computation into a constant-sized space. We present a fully implemented prover which can argue the truth of any size computation, and verifier which can verify correctness in constant time. This work shows an extension of utility for computational integrity statements into the quantum domain. We provide real-world performance metrics demonstrating that post-quantum secure argument systems not only exist but can outperform classical systems in both efficiency and scalability, making such systems an attractive choice for practical deployment.

This report presents the security protocols and general trust architecture of the SMARTEDGE swarm computing platform. Part 1 describes the coordination protocols for use in a swarm production environment, e.g. a smart factory, and Part 2 deals with crowd-sensing scenarios characteristic of traffic-control swarms.

Non-Interactive Timed Commitment schemes (NITC) allow to open any commitment after a specified delay $$. This is useful for sealed bid auctions and as primitive for more complex protocols. We present the first NITC without repeated squaring or theoretical black box algorithms like NIZK proofs or one-way functions. It has fast verification, almost arbitrary delay and satisfies IND-CCA hiding and perfect binding. Our protocol is based on isogenies between supersingular elliptic curves making it presumably quantum secure, and all algorithms have been implemented as part of SQISign or other well-known isogeny-based cryptosystems. Additionally, it needs no trusted setup and can use known primes for SIKE or SQISign.

HFE (that stands for Hidden Field Equations) belongs to multivariate cryptography and was designed by Jacques Patarin in 1996 as a public key trapdoor suitable for encryption or signature. This original basic version is unfortunately known to have a super-polynomial attack, but as imagined since the beginning, it comes with various variants, one can describe as combinations of “modifiers”. In this work, we first present the state of the art of these HFE modifiers, along with their effect on the complexity of the main cryptanalysis techniques against HFE-based schemes. This allows us, in a second time, to identify a combination of two modifiers that has not yet been explored and may still be secure with efficient parameters. Based on our analysis, we propose a new signature scheme that offers extremely short signature sizes, with reasonable public key sizes and performance. In particular, we rely on the classical Feistel-Patarin technique to reduce signature sizes below two times the security parameter.

This paper addresses the problem of factoring composite numbers by introducing a novel approach to represent their prime divisors. We develop a method to efficiently identify smaller divisors based on the difference between the primes involved in forming the composite number. Building on these insights, we propose an algorithm that significantly reduces the computational complexity of factoring, requiring half as many iterations as traditional quadratic residue-based methods. The presented algorithm offers a more efficient solution for factoring composite numbers, with potential applications in fields such as cryptography and computational number theory.

Local Differential Privacy (LDP) provides a formal guarantee of privacy that enables the collection and analysis of sensitive data without revealing any individual's data. While LDP methods have been extensively studied, there is a lack of a systematic and empirical comparison of LDP methods for descriptive statistics. In this paper, we first provide a systematization of LDP methods for descriptive statistics, comparing their properties and requirements. We demonstrate that several mean estimation methods based on sampling from a Bernoulli distribution are equivalent in the one-dimensional case and introduce methods for variance estimation. We then empirically compare methods for mean, variance, and frequency estimation. Finally, we provide recommendations for the use of LDP methods for descriptive statistics and discuss their limitations and open questions.

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared to standard NTRU. To our knowledge, DiTRU (Africacrypt 2024) is the first noncommutative analog of NTRU provided as a complete package. Although DiTRU is practical, it operates at two times slower than NTRU with no decryption failure. Additionally, key generation, encryption, and decryption are 1.2, 1.7, and 1.7 times slower, respectively, with negligible decryption failure. In this work, we introduce a noncommutative version of NTRU that offers comparable performance and key sizes to NTRU while improving upon DiTRU. Our cryptosystem is based on the GR-NTRU framework, utilizing the group ring of a semidirect product of cyclic groups over the ring of Eisenstein integers. This design allows for an efficient construction with key generation speeds approximately two (three) times faster than NTRU (DiTRU). Further, the proposed scheme provides roughly a speed-up by a factor of 1.2 (2) while encrypting/decrypting messages of the same length over NTRU (DiTRU). We provide a reference implementation in C for the proposed cryptosystem to prove our claims.

We construct the first multi-input functional encryption (MIFE) and indistinguishability obfuscation (iO) schemes for pseudorandom functionalities, where the output of the functionality is pseudorandom for every input seen by the adversary. Our MIFE scheme relies on LWE and evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) for constant arity functions, and a strengthening of evasive LWE for polynomial arity. Thus, we obtain the first MIFE and iO schemes for a nontrivial functionality from conjectured post-quantum assumptions. Along the way, we identify subtle issues in the proof of witness encryption from evasive LWE by prior work and believe that a similar strengthening of evasive LWE should also be required for their proof, for the same reasons as ours. We demonstrate the power of our new tools via the following applications: 1. Multi Input Predicate Encryption for Constant Arity. Assuming evasive LWE and LWE, we construct a multi-input predicate encryption scheme (MIPE) for P, supporting constant arity. The only prior work to support MIPE for P with constant arity by Agrawal et al. (Crypto, 2023) relies on a strengthening of Tensor LWE in addition to LWE and evasive LWE. 2. Multi Input Predicate Encryption for Polynomial Arity. Assuming a stronger variant of evasive LWE and LWE, we construct MIPE for P for polynomial arity. MIPE for polynomial arity supporting P was not known before, to the best of our knowledge. 3. Two Party ID Based Key Exchange. Assuming a stronger variant of evasive LWE and LWE, along with Decision Bilinear Diffie-Hellman, we provide the first two-party ID based Non-Interactive Key Exchange (ID-NIKE) scheme in the standard model. This leads to the first ID-NIKE in the standard model without using multilinear maps or indistinguishability obfuscation. 4. Instantiating the Random Oracle. We use our pseudorandom iO to instantiate the random oracle in several applications that previously used iO (Hohenberger, Sahai and Waters, Eurocrypt 2014) such as full-domain hash signature based on trapdoor permutations and more. Our tools of MIFE and iO for pseudorandom functionalities appear quite powerful and yield extremely simple constructions when used in applications. We believe they provide a new pathway for basing “extreme” cryptography, which has so far required full fledged iO, on the presumably weaker evasive LWE in the post quantum regime.

There are two security notions for FHE schemes the traditional notion of IND-CPA, and a more stringent notion of IND-CPA$$. The notions are equivalent if the FHE schemes are perfectly correct, however for schemes with negligible failure probability the FHE parameters needed to obtain IND-CPA$$ security can be much larger than those needed to obtain IND-CPA security. This paper uses the notion of ciphertext drift in order to understand the practical difference between IND-CPA and IND-CPA$$ security in schemes such as FHEW, TFHE and FINAL. This notion allows us to define a modulus switching operation (the main culprit for the difference in parameters) such that one does not require adapting IND-CPA cryptographic parameters to meet the IND-CPA$$ security level. Further, the extra cost incurred by the new techniques has no noticeable performance impact in practical applications. The paper also formally defines a stronger version for IND-CPA$$ security called sIND-CPA$$, which is proved to be strictly separated from the IND-CPA$$ notion. Criterion for turning an IND-CPA$$ secure public-key encryption into an sIND-CPA$$ one is also provided.

With the rapid advance in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry's compressed quantum random oracle ($$), called compressed quantum random oracle with adaptive special points ({\bf CStO}$$). Then, we extend the on-line extraction technique of Don et al (EUROCRYPT'22) from {\bf CStO} to $$. We also extend the random experiment technique of Liu and Zhandry (CRYPTO'19) for extracting the $$ query that witnesses the future adversarial output. With these preparations, a systematic security proof in the quantum random oracle model can start with a random {\bf CStO} experiment (that extracts the witness for the future adversarial output) and then convert this game to one involving $$. Next, the on-line extraction technique for $$ can be applied to extract the witness for any on-line commitment. With this strategy, we give a security proof of our recent compact multi-signature framework that is converted from any weakly secure linear ID scheme. We also prove the quantum security of our recent lattice realization of this linear ID scheme, by iteratively applying the weakly collapsing protocol technique of Liu and Zhandry (CRYPTO 2019). Combining these two results, we obtain the first quantum security proof for a compact multi-signature.

We present an asynchronous secure multi-party computation (MPC) protocol that is practically efficient. Our protocol can evaluate any arithmetic circuit with linear communication in the number of parties per multiplication gate, while relying solely on computationally lightweight cryptography such as hash function and symmetric encryption. Our protocol is optimally resilient and tolerates $$ malicious parties among $$ parties. At the technical level, we manage to apply the \emph{player-elimination} paradigm to asynchronous MPC. This framework enables the detection and eviction of cheating parties by repeatedly attempting to generate Beaver triples. Once all malicious parties are eliminated, honest parties can proceed with efficient Beaver triple generation. While this approach is standard in synchronous MPC, it presents several technical challenges when adopted in an asynchronous network, which we address in this work.

We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the $$ language, our construction achieves a proof length of $$ where $$ denotes the witness, $$ is the security parameter, $$ is a small constant less than 1, and $$ is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from either the LWE assumption, or the $$-$$ assumption on prime-order groups with efficiently computable bilinear maps, or the sub-exponential DDH assumption. Previously, Gentry et al. (Journal of Cryptology, 2015) achieved NIZKs with statistical soundness and computational zero-knowledge with the aforementioned proof length by relying on the Learning with Errors (LWE) assumption.

In this paper, we introduce OT-PCA, a novel approach for conducting Plaintext-Checking (PC) oracle based side-channel attacks, specifically designed for Hamming Quasi-Cyclic (HQC). By calling the publicly accessible HQC decoder, we build offline templates that enable efficient extraction of soft information for hundreds of secret positions with just a single PC oracle call. Our method addresses critical challenges in optimizing key-related information extraction, including maximizing decryption output entropy and ensuring error pattern independence, through the use of genetic-style algorithms. Extensive simulations demonstrate that our new attack method significantly reduces the required number of oracle calls, achieving a 2.4-fold decrease for hqc-128 and even greater reductions for hqc-192 and hqc-256 compared to current state-of-the-art methods. Notably, the attack shows strong resilience against inaccuracy in the PC oracle—when the oracle accuracy decreases to 95%, the reduction factor in oracle call requirements increases to 7.6 for hqc-128. Lastly, a real-world evaluation conducted using power analysis on a platform with an ARM Cortex-M4 microcontroller validates the practical applicability and effectiveness of our approach.

Privacy-preserving blueprint schemes (Kohlweiss et al., EUROCRYPT'23) offer a mechanism for safeguarding user's privacy while allowing for specific legitimate controls by a designated auditor agent. These schemes enable users to create escrows encrypting the result of evaluating a function $$, with $$ being publicly known, $$ a secret used during the auditor's key generation, and $$ the user's private input. Crucially, escrows only disclose the blueprinting result $$ to the designated auditor, even in cases where the auditor is fully compromised. The original definition and construction only support the evaluation of functions $$ on an input $$ provided by a single user. We address this limitation by introducing updatable privacy-preserving blueprint schemes (UPPB), which enhance the original notion with the ability for multiple users to non-interactively update the private user input $$ while blueprinting. Moreover, UPPBs contain a proof that $$ is the result of a sequence of valid updates, while revealing nothing else about the private inputs $$ of updates. As in the case of privacy-preserving blueprints, we first observe that UPPBs can be realized via a generic construction for arbitrary predicates $$ based on FHE and NIZKs. Our main result is UBlu, an efficient instantiation for a specific predicate comparing the values $$ and $$, where $$ is the cumulative sum of users' private inputs and $$ is a fixed private value provided by the auditor in the setup phase. This rather specific setting already finds interesting applications such as privacy-preserving anti-money laundering and location tracking, and can be extended to support more generic predicates. From the technical perspective, we devise a novel technique to keep the escrow size concise, independent of the number of updates, and reasonable for practical applications. We achieve this via a novel characterization of malleability for the algebraic NIZK by Couteau and Hartmann (CRYPTO’20) that allows for an additive update function.

In verifiable outsourcing, an untrusted server runs an expensive computation and produces a succinct proof (called a SNARK) of the results. In many scenarios, the computation accesses a RAM that the server maintains a commitment to (persistent RAM) or that is initially zero (volatile RAM). But, SNARKs for such scenarios are limited by the high overheads associated with existing techniques for RAM checking. We develop new proofs about volatile, persistent, and sparse persistent RAM that reduce SNARK proving times. Our results include both asymptotic and concrete improvements---including a proving time reduction of up to 51.3$$ for persistent RAM. Along the way, we apply two tools that may be of independent interest. First, we generalize an existing construction to convert any algebraic interactive proof (AIP) into a SNARK. An AIP is a public-coin, non-succinct, interactive proof with a verifier that is an arithmetic circuit. Second, we apply Bézout's identity for polynomials to construct new AIPs for uniqueness and disjointness. These are useful for showing the independence of accesses to different addresses.

We propose a dynamic, low-latency encrypted multi-map (EMM) that operates in two modes: low-leakage mode, which reveals minimal information such as data size, expected response length, and query arrival rate; and subliminal mode, which reveals only the data size while hiding metadata including query and update times, the number of operations executed, and even whether an operation was executed at all---albeit at the cost of full correctness. We achieve this by exploiting a tradeoff between leakage and latency, a previously underexplored resource in EMM design. In low-leakage mode, our construction improves upon existing work both asymptotically and empirically: it achieves optimal server-side storage, as well as communication and computational complexity that is independent of the maximum response length. In subliminal mode, it is the first construction to hide metadata. To analyze the latency and client-side storage of our construction, we utilize queuing theory and introduce a new queuing model, which may be of independent interest. To examine its metadata-hiding properties, we extend standard security definitions to account for metadata and prove a surprising result: if a scheme is subliminal in that it hides the execution of its operations, then it absorbs the leakage of any scheme that makes black-box use of it without sending additional messages. In other words, if a scheme is subliminal, then any scheme that makes black-box use of it will also be subliminal. We implement and evaluate our construction, demonstrating that our empirical results align with our theoretical analysis and that the scheme achieves a median query latency below $$ milliseconds, making it practical for some applications.

Provable privacy typically requires involved analysis and is often associated with unacceptable accuracy loss. While many empirical verification or approximation methods, such as Membership Inference Attacks (MIA) and Differential Privacy Auditing (DPA), have been proposed, these do not offer rigorous privacy guarantees. In this paper, we apply recently-proposed Probably Approximately Correct (PAC) Privacy to give formal, mechanized, simulation-based proofs for a range of practical, black-box algorithms: K-Means, Support Vector Machines (SVM), Principal Component Analysis (PCA) and Random Forests. To provide these proofs, we present a new simulation algorithm that efficiently determines anisotropic noise perturbation required for any given level of privacy. We provide a proof of correctness for this algorithm and demonstrate that anisotropic noise has substantive benefits over isotropic noise. Stable algorithms are easier to privatize, and we demonstrate privacy amplification resulting from introducing regularization in these algorithms; meaningful privacy guarantees are obtained with small losses in accuracy. We propose new techniques in order to reduce instability in algorithmic output and convert intractable geometric stability verification into efficient deterministic stability verification. Thorough experiments are included, and we validate our provable adversarial inference hardness against state-of-the-art empirical attacks.

Machine-learning systems continue to advance at a rapid pace, demonstrating remarkable utility in various fields and disciplines. As these systems continue to grow in size and complexity, a nascent industry is emerging which aims to bring machine-learning-as-a-service (MLaaS) to market. Outsourcing the operation and training of these systems to powerful hardware carries numerous advantages, but challenges arise when privacy and the correctness of work carried out must be ensured. Recent advancements in the field of zero-knowledge cryptography have led to a means of generating arguments of integrity for any computation, which in turn can be efficiently verified by any party, in any place, at any time. In this work we prove the correct training of a differentially-private (DP) linear regression over a dataset of 50,000 samples on a single machine in less than 6 minutes, verifying the entire computation in 0.17 seconds. To our knowledge, this result represents the fastest known instance in the literature of provable-DP over a dataset of this size. We believe this result constitutes a key stepping-stone towards end-to-end private MLaaS.

Several cryptographic primitives, especially succinct proofs of various forms, transform the satisfaction of high-level properties to the existence of a polynomial quotient between a polynomial that interpolates a set of values with a cleverly arranged divisor. Some examples are SNARKs, like Groth16, and polynomial commitments, such as KZG. Such a polynomial division naively takes $$ time with Fast Fourier Transforms, and is usually the asymptotic bottleneck for these computations. Several works have targeted specific constructions to optimize these computations and trade-off one-time setup costs with faster online computation times. In this paper, we present a unified approach to polynomial division related computations for a diverse set of schemes. We show how our approach provides a common abstract lens which recasts and improves existing approaches. Additionally, we present benchmarks for the Groth16 and the KZG systems, illustrating the significant practical benefits of our approach in terms of speed, memory, and parallelizability. We get a speedup of $$ over the state-of-the-art in computing all openings for KZG commitments and a speed-up of about $$ for Groth16 proofs when compared against the Rust Arkworks implementation. Although our Groth16 speedup is modest, our approach supports twice the number of gates as Arkworks and SnarkJS as it avoids computations at higher roots of unity. Conversely this reduces the need for employing larger groups for bigger circuits. For example, our approach can support $$ gates with BN254, as compared to $$ for coset-based approaches, without sacrificing computational advantages. Our core technical contributions are novel conjugate representations and compositions of the derivative operator and point-wise division under the Discrete Fourier Transform. These allow us to leverage l'Hôpital's rule to efficiently compute polynomial division, where in the evaluation basis such divisions maybe of the form $$. Our techniques are generic with potential applicability to many existing protocols.

We provide optimized range proofs, called $$, in discrete logarithm and hidden order groups, based on square decomposition. In the former setting, we build on the paradigm of Couteau et al. (Eurocrypt '21) and optimize their range proof (from now on, CKLR) in several ways: (1) We introduce batching via vector commitments and an adapted $$-protocol. (2) We introduce a new group switching strategy to reduce communication. (3) As repetitions are necessary to instantiate CKLR in standard groups, we provide a novel batch shortness test that allows for cheaper repetitions. The analysis of our test is nontrivial and forms a core technical contribution of our work. For example, for $$ bit security and $$ bit ranges for $$ (resp. $$) proof(s), we reduce the proof size by $$ (resp. $$) in arbitrary groups, and by $$ (resp. $$ in groups of order $$-bit, compared to CKLR. As $$ and CKLR proofs satisfy a “relaxed” notion of security, we show how to enhance their security with one additional hidden order group element. In RSA groups, this reduces the size of state of the art range proofs (Couteau et al., Eurocrypt '17) by $$ ($$). Finally, we implement our most optimized range proof. Compared to the state of the art Bulletproofs (Bünz et al., S&P 2018), our benchmarks show a very significant runtime improvement. Eventually, we sketch some applications of our new range proofs.

We extend the usual ideal action on oriented elliptic curves to a (Hermitian) module action on oriented (polarised) abelian varieties. Oriented abelian varieties are naturally enriched in $$-modules, and our module action comes from the canonical power object construction on categories enriched in a closed symmetric monoidal category. In particular our action is canonical and gives a fully fledged symmetric monoidal action. Furthermore, we give algorithms to compute this action in practice, generalising the usual algorithms in rank~$$. The action allows us to unify in the same framework, on the one hand isogeny based cryptography based on ordinary or oriented elliptic curves, and on the other hand the one based on supersingular elliptic curves defined over $$. In particular, from our point of view, supersingular elliptic curves over $$ are given by a rank~$$ module action, while (the Weil restriction) of those defined over $$ are given by a rank~$$ module action. As a consequence, rank~$$ module action inversion is at least as hard as the supersingular isogeny path problem. We thus propose to use Hermitian modules as an avatar of a cryptographic symmetric monoidal action framework. This generalizes the more standard cryptographic group action framework, and still allows for a NIKE (Non Interactive Key Exchange). The main advantage of our action is that, presumably, Kuperberg's algorithm does not apply. Compared to CSIDH, this allows for more compact keys and much better scaling properties. In practice, we propose the key exchange scheme $$-MIKE (Tensor Module Isogeny Key Exchange). Alice and Bob start from a supersingular elliptic curve $$ and both compute a $$-isogeny over $$. They each send the $$-invariant of their curve. Crucially, unlike SIDH, no torsion information at all is required. Their common secret, given by the module action, is then a dimension~$$ principally polarised abelian variety. We obtain a very compact post-quantum NIKE: only 64B for NIST level~$$ security.

Fully asynchronous multi-party computation (AMPC) has superior robustness in realizing privacy and guaranteed output delivery (G.O.D.) against asynchronous adversaries that can arbitrarily delay communications. However, none of these protocols are truly practical, as they either have sub-optimal resilience, incur cumbersome communication cost, or suffer from an online phase with extra cryptographic overhead. The only attempting implementation---HoneyBadgerMPC (hbMPC)---merely ensures G.O.D. in some implausible optimistic cases due to a non-robust offline pre-processing phase. We propose Dumbo-MPC a concretely efficient AMPC-as-a-service design with all phases G.O.D. and optimal resilience against $$ malicious parties (where $$ is the total number of parties). Same to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. While for achieving all phases G.O.D., we design a novel dual-mode offline protocol that can robustly pre-process multiplication triples in asynchrony. The offline phase features $$ per-triple communication in the optimistic case, followed by a fully asynchronous fallback to a pessimistic path to securely restore G.O.D. in the bad case. To efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for product relationship of secret shares over compact KZG polynomial commitments, which enables us to reduce the degree of two secret shares' product from $$ to $$ and could be of independent interest. We also implement and extensively evaluate Dumbo-MPC (particularly its offline phase) in varying network settings with up to 31 AWS servers. To our knowledge, we provide the first implementation of AMPC with all-phase G.O.D. A recent asynchronous triple generation protocol from Groth and Shoup (GS23) is also implemented and experimentally compared. When $$, Dumbo-MPC generates 94 triples/sec (almost twice of GS23) in the pessimistic case and 349 triples/sec (6X of GS23) in the good case, such that 31 parties require only 2-8 min to prepare a private Vickrey auction of 100 bidders or 10-36 min for a mixing network of $$ inputs.

Multi-signature schemes are gaining significant interest due to their blockchain applications. Of particular interest are two-round schemes in the plain public-key model that offer key aggregation, and whose security is based on the hardness of the DLOG problem. Unfortunately, despite substantial recent progress, the security proofs of the proposed schemes provide rather insufficient concrete guarantees (especially for 256-bit groups). This frustrating situation has so far been approached either by relying on the security of seemingly stronger assumptions or by considering restricted classes of attackers (e.g., algebraic attackers, which are assumed to provide an algebraic justification of each group element that they produce). We present a complementing approach by constructing multi-signature schemes that satisfy two relaxed notions of security, whose applicability nevertheless ranges from serving as drop-in replacements to enabling expressive smart contract validation procedures. Our first notion, one-time unforgeability, extends the analogous single-signer notion by considering attackers that obtain a single signature for some message and set of signers of their choice. We construct a non-interactive one-time scheme based on any ring-homomorphic one-way function, admitting efficient instantiations based on the DLOG and RSA assumptions. Aggregated verification keys and signatures consist of two group elements and a single group element, respectively, and our security proof consists of a single application of the forking lemma (thus avoiding the substantial security loss exhibited by the proposed two-round schemes). Additionally, we demonstrate that our scheme naturally extends to a $$-time scheme, where aggregated verification keys consist of $$ group elements, while aggregated signatures still consist of a single group element. Our second notion, single-set unforgeability, considers attackers that obtain any polynomial number of signatures but are restricted to a single set of signers of their choice. We transform any non-interactive one-time scheme into a two-round single-set scheme via a novel forking-free construction that extends the seminal Naor-Yung tree-based approach to the multi-signer setting. Aggregated verification keys are essentially identical to those of the underlying one-time scheme, and the length of aggregated signatures is determined by that of the underlying scheme while scaling linearly with the length of messages (noting that long messages can always be hashed using a collision-resistant function). Instantiated with our one-time scheme, we obtain aggregated verification keys and signatures whose lengths are completely independent of the number of signers.

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es- tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al., INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes just 3.9 ms to transcipher 4 bit messages, being significantly faster than the state of the art in terms of latency.