IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function
Full text linkA trapdoor Memory-Hard Function is a function that is memory-hard to evaluate for any party who does not have a trapdoor, but is substantially less expensive to evaluate with the trapdoor. Biryukov and Perrin (Asiacrypt 2017) introduced the first candidate trapdoor Memory-Hard Function called Diodon, which modifies a Memory-Hard Function called Scrypt by replacing a hash chain with repeated squaring modulo a composite number N=pq. The trapdoor, which consists of the prime factors p and q, allows one to compute the function with significantly reduced cumulative memory cost (CMC) O(n*log n*(log N)^2) where n denotes the running time parameter, e.g., the length of the hash chain or repeated squaring chain. By contrast, the best-known algorithm to compute Diodon without the trapdoor has the CMC O(n^2*log N). Auerbach et al. (Eurocrypt 2024) provided the first provable lower bound on the CMC of TdScrypt — a specific instantiation of Diodon. In particular, in idealized models, they proved that the CMC of TdScrypt is Omega(n^2*log N/(log n)) which almost matches the upper bound O(n^2*log N) but is off by a multiplicative log n factor. In this work, we show how to tighten the analysis of Auerbach et al. (Eurocrypt 2024) and eliminate the gap. In particular, our results imply that TdScrypt has the CMC at least Omega(n^2*log N). </p
Relating Definitions of Computational Differential Privacy in Wider Parameter Regimes
Full text link The literature on computational differential privacy (CDP) has focused almost exclusively on definitions that are computational analogs of `pure\u27 (epsilon,0)-DP. We initiate the formal study of computational versions of approximate DP, i.e. (epsilon, delta)-DP with non-negligible delta and do this by revisiting results for computational pure DP and extend them to the approximate case. We focus on IND-CDP and SIM-forall-exists-CDP and show that the hierarchy between them when delta > 0 potentially differs substantially from when delta = 0. In one direction, we show that for delta < 1, any mechanism which is (epsilon,delta)-SIM-forall-exists-CDP also is (epsilon,delta)-IND-CDP, but only if epsilon is logarithmic in the security parameter. As a special case, this proves that the existing implication from (epsilon,0)-SIM-forall-exists-CDP to (epsilon,0)-IND-CDP does not hold for arbitrary epsilon, as previously claimed. Furthermore, we prove that when the parameters are the same in IND-CDP and SIM-forall-exists-CDP and epsilon is superlogarithmic, there exists a natural task that can be solved whilst satisfying SIM-forall-exists-CDP but which no IND-CDP mechanism can solve. This is the first separation in the CDP literature which is not due to using a task contrived specifically in order to give rise to the separation. In the other direction, we show that the techniques for establishing an implication from (epsilon,0)-IND-CDP to SIM-forall-exists-CDP extend only to that a mechanism being (epsilon,delta)-IND-CDP implies it is also (epsilon,delta\u27)-SIM-forall-exists-CDP with delta\u27 > delta. Finally, we show that the Groce-Katz-Yerukhimovich barrier results against separations between CDP and statistical DP hold for arbitrary values of delta. </p
Lower Bounds on the Bottleneck Complexity of Secure Multiparty Computation
Full text linkSecure multiparty computation (MPC) is a cryptographic primitive which enables multiple parties to jointly compute a function without revealing any extra information on their private inputs. Bottleneck complexity is an efficiency measure that captures the load-balancing aspect of MPC protocols, defined as the maximum amount of communication required by any party. In this work, we study the problem of establishing lower bounds on the bottleneck complexity of MPC protocols. While the previously known techniques for lower bounding total communication complexity can also be applied to bottleneck complexity, they do not provide nontrivial bounds in the correlated randomness model, which is commonly assumed by existing protocols achieving low bottleneck complexity, or they are applied only to functions of limited practical interest. We propose several novel techniques for lower bounding the bottleneck complexity of MPC protocols. Our methods derive nontrivial lower bounds even in the correlated randomness model and apply to practically relevant functions including the sum function and threshold functions. Furthermore, our lower bounds demonstrate the optimality of some existing MPC protocols in terms of bottleneck complexity or the amount of correlated randomness. </p
MSX: Lightweight Block Ciphers for Microcontrollers with High-assurance against Differential and Linear Attacks
Full text linkWe present MSX, a new family of 64/128-bit block ciphers. It aims to provide fast execution on microcontrollers and comes with a highly reliable argument on the resistance against basic differential/linear attacks, backed by the classical differential/linear probability analysis on Feistel ciphers and Vaudenay\u27s decorrelation theory. MSX are classical (generalized) Feistel ciphers with a round function. Similar to many existing ARX ciphers, its round function uses arithmetic operations and does not have an S-box. A unique feature of MSX is its use of 32-bit integer multiplication, which enables proving an ideally strong differential/linear property by design. It could be interpreted as an application of Vaudenay\u27s decorrelation theory. We provide a detailed security analysis on attacks beyond differential and linear ones and conduct a benchmark on a range of popular microcontrollers with a comparison to Speck, a top performer on microcontrollers. The results show MSX\u27s good performance on 32-bit microcontrollers, maintaining a sufficiently large security margin. MSX aims at security under single key, and related-key security is not the focus. </p
Post-Quantum Traceable Anonymous Credentials from Lattices
Full text linkTraceable Anonymous Credentials (TACs) are an important extension of Anonymous Credentials (ACs). TAC systems protect user privacy during credential verifications while also allowing for the de-anonymization of credentials in cases of misbehavior. Although TACs have been studied with several constructions based on number-theoretic assumptions, the formal security definitions of credential tracing and efficient constructions with post-quantum security remain absent. This work addresses both gaps by presenting the first formalization of TACs and the first post-quantum construction based on module lattices. We design a new trapdoor for a lattice-based commitment, which allows partial recovery of commitment randomness. We integrate our trapdoor commitment into the state-of-the-art lattice-based AC system by Jeudy et al. (Crypto 2023) to derive our efficient TAC system. </p
Highly Scalable Searchable Symmetric Encryption for Boolean Queries from NTRU Lattice Trapdoors
Full text linkSearchable symmetric encryption (SSE) enables query execution directly over symmetrically encrypted databases. To support realistic query executions over encrypted document collections, one needs SSE schemes capable of supporting both conjunctive and disjunctive keyword queries. Unfortunately, existing solutions are either practically inefficient (incur large storage overheads and/or high query processing latency) or are quantum-unsafe. In this paper, we present the first practically efficient SSE scheme with fast conjunctive and disjunctive keyword searches, compact storage, and security based on the (plausible) quantum-hardness of well-studied lattice-based assumptions. We present NTRU-OQXT – a highly compact NTRU lattice-based conjunctive SSE scheme that outperforms all existing conjunctive SSE schemes in terms of search latency. We then present an extension of NTRU-OQXT that additionally supports disjunctive queries, we call it NTRU-TWINSSE. Technically, both schemes rely on a novel oblivious search protocol based on highly optimized Fast-Fourier trapdoor sampling algorithms over NTRU lattices. While such techniques have been used to design other cryptographic primitives (such as digital signatures), they have not been applied before in the context of SSE. We present prototype implementations of both schemes, and experimentally validate their practical performance over a large real-world dataset. Our experiments demonstrate that NTRU-OQXT achieves faster conjunctive keyword searches as compared to all other conjunctive SSE schemes (including the best quantum-unsafe conjunctive SSE schemes), and substantially outperforms many of these schemes in terms of storage requirements. These efficiency benefits also translate to NTRU-TWINSSE, which is practically competitive with the best quantum-unsafe SSE schemes capable of supporting both conjunctive and disjunctive queries. </p
Incompressible Encryption Beyond CPA/CCA Security
Full text linkAn incompressible encryption scheme offers protection against adversaries who possess the entire secret key but can store only a portion of the ciphertext. In recent years, there has been growing interest in developing such primitives in both public-key and secret-key settings, as well as in the multi-user scenario.In this work, we extend the concept of incompressible encryption to incorporate anonymity and key-dependent message security. We introduce the following schemes: The first key-dependent message incompressible SKE scheme secure against unbounded adversaries. The first anonymous incompressible SKE scheme secure against unbounded encryption queries. Furthermore, we present the public key versions of these schemes. </p
Improved Constant-Sized Polynomial Commitment Schemes Without Trusted Setup
Full text link Argument systems are a fundamental ingredient in many cryptographic constructions. The best-performing argument systems to date largely rely on a trusted setup, which is undesirable in trust-minimized applications. While transparent argument systems avoid this trust assumption, they have historically been inefficient, typically exhibiting polylogarithmic proof sizes compared to their trusted counterparts. In 2023, Arun et al. (PKC 2023) constructed the first transparent constant-sized polynomial commitment scheme (PCS), leading to transparent constant-sized arguments. However, the evaluation proof still comprises 66 group elements in a group of unknown order (GUO), rendering it rather impractical. In this work, we address this challenge by presenting a set of novel batching and aggregation techniques tailored for proofs of knowledge of ranges in GUOs. These techniques may also be of independent interest and are readily applicable to enhance and shorten other existing schemes in GUOs. Consequently, by applying these techniques, we immediately achieve an improved PCS with an evaluation proof consisting of only 10 group elements—an impressive 85% reduction. To our knowledge, this represents the shortest PCS in the transparent setting. Thus compiling known information-theoretic proof systems using our improved PCS yields highly compact transparent argument systems when instantiated in a class group, which is more practical than prior constant-sized schemes. </p
Boomy: Batch Opening Of Multivariate polYnomial commitment
Full text linkWe present Boomy, a multivariate polynomial commitment scheme enabling the proof of the evaluation of multiple points, i.e., batch opening. Boomy is the natural extension of two popular protocols: the univariate polynomial commitment scheme of Kate, Zaverucha and Goldberg[KZG10] and its multivariate counterpart from Papamanthou, Shi and Tamassia[PST13]. Our construction is proven secure under the selective security model. In this paper, we present Boomy\u27s complexity and the applications on which it can have a significant impact. In fact, Boomy is perfectly suited to tackling blockchain problems by greatly improving data availability sampling and shrinking existing challenges. We also present special lower-complexity cases that occur frequently in practical situations. </p
Practical Persistent Fault Attacks on AES with Instruction Skip
Full text linkPersistent Fault Attacks (PFA) have emerged as an active research area in embedded cryptography. This attack exploits faults in one or multiple constants stored in memory, typically targeting S-box elements. In the literature, such persistent faults primarily induced by bit flips in storage, often achieved through laser fault injection techniques. In this paper, we demonstrate that persistent faults can also be induced through instruction skips, which can easily be achieved with almost any fault injection methods (e.g., voltage/clock glitching, electromagnetism). Specifically, we target AES implementations that dynamically generate the S-box table at runtime, during the initialization phase, before executing the first AES operation. We illustrate this with an attack on the AES implementation in the MbedTLS library, where a clock glitch is inserted during the S-box generation. Secondly, we introduce, to our knowledge, the first PFA that targets a constant other than the S-box elements. We show that faulting a round constant involved in the AES key schedule is sufficient to recover the key by a differential analysis. Compared to previous PFAs that rely on statistical analysis requiring hundreds to thousands of ciphertexts, our approach needs only three correct-faulty ciphertexts pairs. We showcase this attack with an experiment on the MbedTLS AES implementation, using a clock glitch in the round constant generation. </p