International Association
for Cryptologic Research

We present a theoretical framework for analyzing the efficiency of consensus protocols, and apply it to analyze the optimistic and pessimistic confirmation times of state-of-the-art partially-synchronous protocols in the so-called "rotating leader/random leader" model of consensus (recently popularized in the blockchain setting).

We next present a new and simple consensus protocol in the partially synchronous setting, tolerating $f \leq n/3$ byzantine faults; in our eyes, this protocol is essentially as simple to describe as the simplest known protocols, but it also enjoys an even simpler security proof, while matching and, even improving, the efficiency of the state-of-the-art (according to our theoretical framework).

As with the state-of-the-art protocols, our protocol assumes a (bare) PKI, a digital signature scheme, collision-resistant hash functions, and a random leader election oracle, which may be instantiated with a random oracle (or a CRS).

Some of the most efficient protocols for Multi-Party Computation (MPC) follow a two-phase approach where correlated randomness, in particular Beaver triples, is generated in the offline phase and then used to speed up the online phase. Recently, more complex correlations have been introduced to optimize certain operations even further, such as matrix triples for matrix multiplications. In this paper, our goal is to improve the efficiency of the triple generation in general and in particular for classical field values as well as matrix operations. To this end, we modify the Overdrive LowGear protocol to remove the costly sacrificing step and therewith reduce the round complexity and the bandwidth. We extend the state-of-the-art MP-SPDZ implementation with our new protocols and show that the new offline phase outperforms state-of-the-art protocols for the generation of Beaver triples and matrix triples. For example, we save 33 % in bandwidth compared to Overdrive LowGear.

Deep learning-based cryptanalysis is one of the emerging trends in recent times. Differential cryptanalysis is one of the most po- tent approaches to classical cryptanalysis. Researchers are now modeling classical differential cryptanalysis by applying deep learning-based tech- niques. In this paper, we report deep learning-based differential distin- guishers for block cipher PRIDE and RC5, utilizing deep learning models: CNN, LGBM and LSTM. We found distinguishers up to 23 rounds for PRIDE and nine rounds for RC5. To the best of our knowledge this is the first deep learning based differential classifier for cipher PRIDE and RC5.

At Eurocrypt 2016, Méaux et al. presented FLIP, a new family of stream ciphers {that aimed to enhance the efficiency of homomorphic encryption frameworks. Motivated by FLIP, recent research has focused on the study of Boolean functions with good cryptographic properties when restricted to subsets of the space $\mathbb{F}_2^n$. If an $n$-variable Boolean function has the property of balancedness when restricted to each set of vectors with fixed Hamming weight between $1$ and $n-1$, it is a weightwise perfectly balanced (WPB) Boolean function. In the literature, a few algebraic constructions of WPB functions are known, in which there are some constructions that use iterative method based on functions with low degrees of 1, 2, or 4. In this paper, we generalize the iterative method and contribute a unified construction of WPB functions based on functions with algebraic degrees that can} be any power of 2. For any given positive integer $d$ not larger than $m$, we first provide a class of $2^m$-variable Boolean functions with a degree of $2^{d-1}$. Utilizing these functions, we then present a construction of $2^m$-variable WPB functions $g_{m;d}$. In particular, $g_{m;d}$ includes four former classes of WPB functions as special cases when $d=1,2,3,m$. When $d$ takes other integer values, $g_{m;d}$ has never appeared before. In addition, we prove the algebraic degree of the constructed WPB functions and compare the weightwise nonlinearity of WPB functions known so far in 8 and 16 variables.

Side-channel analysis (SCA) attacks manifest a significant challenge to the security of cryptographic devices. In turn, it is generally quite expensive to protect from SCAs (energy, area, performance etc.). In this work we exhibit a significant change in paradigm for SCA attacks: our proposed attack is quite different from conventional SCA attacks and is able to filter out physical measurement noise, algorithmic noise, as well as thwart various countermeasures, and extract information from the entire leakage waveform as a whole and not only points-of-interest. We demonstrate on measured devices break of masking schemes of orders 2 and 3, supported by a model and also shuffling and dual-rail based countermeasures model; all performed efficiently with the same methodology, and with orders of magnitude less measurements and smaller computation time; underpinning the importance of this form of attack. In essence, in our attack we assume nothing different than a standard side-channel attack, i.e., a known plaintext scenario. However, we further group and classify leakages associated with specific subsets of plaintexts bits. The fact that we group specific (sub-)plaintexts associated leakages, and than in the next stage group or concatenate the associated leakages of these large groups in a predefined ordered sequence (modulation), enables far stronger attacks against SCA protected and unprotected designs. The evaluation-domain or the modulation-domain is the frequency domain in which per frequency it is possible to build a two feature constellation diagrams (amplitude and phase) and construct distinguishers over these diagrams. On top of the methodological contribution of this new SCA, the main observation we push forward is that practically such an attack is devastating for many countermeasures we were used to consider as secure to some level, such as masking or shuffling with large permutation size. As an example, leakage from a third order masked design can be detected with merely 100 leakage traces from the first statistical moment of the leakage as compared to $15\cdot10^6$ traces with conventional SCA leakage detection test from the third statistical order.

In 2002, Barak and Goldreich introduced the notion of a universal argument and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of non-interactive succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under sub-exponential assumptions. Assuming polynomially hard fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.

This paper introduces registered functional encryption (RFE) that eliminates trust on the central authority for handling secrets. Unlike standard functional encryption (FE), in an RFE scheme, users create their secret keys themselves and then register the associated public keys to a key curator along with the functions they wish to compute on the encrypted data. The key curator aggregates the public keys from the different users into a single compact master public key. To decrypt, users occasionally need to obtain helper decryption keys from the key curator which they combine with their own secret keys. We require that the size of the aggregated public key, the helper decryption keys, the ciphertexts, as well as the encryption/decryption time to be polylogarithmic in the number of registered users. Moreover, the key curator is entirely transparent and maintains no secrets. RFE generalizes the notions of registration-based encryption (RBE) introduced by Garg et al. (TCC 2018) and registered attribute-based encryption introduced by Hohenberger et al. (EUROCRYPT 2023) who dealt with the “all-or-nothing” variants of FE. We present an RFE scheme for general functions and an arbitrary number of users from indistinguishability obfuscation and somewhere statistically binding hash functions. Surprisingly, our construction is achieved via only a minor tweak applied to the registered ABE of Hohenberger et al.

Asynchronous Remote Key Generation (ARKG, introduced in ACM CCS 2020) allows for a party to create public keys for which corresponding private keys may be later computed by another intended party only. ARKG can be composed with standard public-key cryptosystems and has been used to construct a new class of privacy-preserving proxy signatures. The original construction of ARKG, however, generates discrete logarithm key pairs of the form $(x, g^x)$.

In this paper we define a generic approach for building ARKG schemes which can be applied to a wide range of pairing-based cryptosystems. This construction is based on a new building block which we introduce and call Asymmetric Key Generation (AKG) along with its extension $\phi$-AKG where $\phi$ is a suitable mapping for capturing different key structures and types of pairings. We show that appropriate choice of $\phi$ allows us to create a secure ARKG scheme compatible with any key pair that is secure under the Uber assumption (EUROCRYPT 2004).

To demonstrate the extensive range of our general approach, we construct ARKG schemes for a number of popular pairing-based primitives: Boneh-Lynn-Shacham (JoC 2004), Camenisch-Lysyanskaya (CRYPTO 2004), Pointcheval-Sanders (CT-RSA 2016), Waters (EUROCRYPT 2005) signatures and structure-preserving signatures on equivalence classes (ASIACRYPT 2014). For each scheme we give an implementation and provide benchmarks that show the feasibility of our techniques.

We introduce and formalize tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in the sense that they allow only three wire values ($0$,$1$, and undefined – $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in the sense that their statically placed gates fire (execute) eagerly as their inputs become defined, implying an order of execution that depends on the input. This dynamic behavior is sufficient to efficiently evaluate RAM programs.

We construct a TSC that emulates $T$ steps of any RAM program and that has only $O(T \cdot \log^3 T \cdot \log \log T )$ gates. Contrast this with the reduction to Boolean circuits, where the best known approach scans all of memory on each access, incurring quadratic cost. Thus, while simple, TSCs have expressive power that closely approximates the RAM model.

We connect TSCs with Garbled Computation (GC). TSCs capture the power of garbling far better than Boolean Circuits, offering a significantly more expressive model of computation while leaving the per-gate cost of evaluation essentially unchanged.

Our most exciting explicit result is authenticated Garbled RAM (GRAM), an approach to constant-round maliciously-secure 2PC of RAM programs. Let $\lambda$ denote the computational security parameter. We first extend authenticated garbling to TSCs; then, by simply plugging in our TSC-based RAM, we immediately obtain authenticated GRAM running at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming all prior work, including even GRAMs in the semi-honest setting. (Prior GRAMs measure per-access cost for a memory storing large $w = \Omega(\log^2 T)$-bit words; by this metric, our cost is $O(w\cdot \log T \cdot \log\log T \cdot \lambda)$.)

As another highlight of the power of TSCs, we give a simple semi-honest garbling of TSCs based only on one-way functions. This yields standard- assumption-based GRAM at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming the best prior GRAM in this setting by more than factor $\lambda$.

Wireless-channel key exchange (WiKE) protocols that leverage Physical Layer Security (PLS) techniques could become an alternative solution for secure communication establishment, such as vehicular ad-hoc networks, wireless IoT networks, or cross-layer protocols.

In this paper, we provide a novel abstraction of WiKE protocols and present the first game-based security model for WiKE. Our result enables the analysis of security guarantees offered by these cross-layer protocols and allows the study of WiKE's compositional aspects. Further, we address the potential problem of the slow-rate secret-key generation in WiKE due to inadequate environmental conditions that might render WiKE protocols impractical or undesirably slow. We explore a solution to such a problem by bootstrapping a low-entropy key coming as the output of WiKE using a Password Authenticated Key Exchange (PAKE). On top of the new security definition for WiKE and those which are well-established for PAKE, we build a compositional WiKE-then-PAKE model and define the minimum security requirements for the safe sequential composition of the two primitives in a black-box manner. Finally, we show the pitfalls of previous ad-hoc attempts to combine WiKE and PAKE.

We give an algebraic attack to forge the signature of a scheme called MPPK/DS, which can be achieved by solving a linear system in 5 variables with coefficients on $\mathbb{Z}/2^x q \mathbb{Z}$ for some odd prime $q$ and $x ≥ 1$.

We construct a sublinear-time single-server pre-processing Private Information Retrieval (PIR) scheme with optimal client storage and server computation (up to poly-logarithmic factors), only relying on the assumption of the existence of One Way Functions (OWF). Our scheme achieves amortized $\tilde{O}(\sqrt{n})$ online server computation and client computation and $O(\sqrt{n})$ online communication per query, and requires $\widetilde{O}_\lambda(\sqrt{n})$ client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme only utilizes lightweight cryptography such as PRFs, which is easily instantiated in practice. To our knowledge, this is the first practical implementation of a single-server sublinear-time PIR scheme. Compared to existing linear time single-server solutions, our schemes are faster by $10-300\times$ and are comparable to the fastest two-server schemes. In particular, for a 100GB database of 1.6 billion entries, our experiments show that our scheme has less than 40ms online computation time on a single core.

Verifiable secret sharing (VSS) allows a dealer to send shares of a secret value to parties such that each party receiving a share can verify (often interactively) if the received share was correctly generated. Non-interactive VSS (NI-VSS) allows the dealer to perform secret sharing such that every party (including an outsider) can verify their shares along with others’ without any interaction with the dealer as well as among themselves. Existing NI-VSS schemes employing either exponentiated ElGamal or lattice-based encryption schemes involve zero-knowledge range proofs, resulting in higher computational and communication complexities.

This preliminary report presents cgVSS, a NI-VSS protocol that uses class groups for encryption. In cgVSS, the dealer encrypts the secret shares in the exponent through a class group encryption such that the parties can directly decrypt their shares. The existence of a subgroup where a discrete logarithm is tractable in a class group allows the receiver to efficiently decrypt the share though it is available in the exponent. This yields a novel-yet-simple VSS protocol where the dealer publishes the encryptions of the shares and the zero-knowledge proof of the correctness of the dealing. The linear homomorphic nature of the employed encryption scheme allows for an efficient zero-knowledge proof of correct sharing. Given the rise in demand for VSS protocols in the blockchain space, especially for publicly verifiable distributed key generation (DKG), our NI-VSS construction can be particularly interesting. We implement our cgVSS protocol using the BICYCL library and compare its performance with the state-of-the-art NI-VSS by Groth. Our protocol reduces the message complexity and the bit length of the broadcast message by at least 5.6x for a 150 party system, with a 1.8x speed-up in the dealer’s computation time and with similar receiver computation times.

HID Global is a major vendor of physical access control systems. In 2012, it introduced Seos, its newest and most secure contactless RFID credential technology, successfully remediating known flaws in predecessors iCLASS and Prox. Seos has been widely deployed to secure sensitive assets and facilities. To date, no published research has demonstrated a security flaw in Seos. We present a relay attack developed with inexpensive COTS hardware, including the Proxmark 3 RDV4. Our attack is capable of operating over extremely long ranges as it uses the Internet as a communications backbone. We have tested multiple real-world attack scenarios and are able to unlock a door in our lab with a card approximately 1960 km away. Our attack is covert and does not require long-term access to the card. Further, our attack is generic and is potentially applicable to other protocols that, like Seos, use ISO/IEC 14443A to communicate. We discuss several mitigations capable of thwarting our attack that could be introduced in future credential systems or as an update to Seos-compatible readers' firmware; these rely on rejecting cards that take too long to reply.

Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in $\mathbb{R}^D$ as input. The honest parties are required to obtain very close outputs in $\mathbb{R}^D$ that lie inside the convex hull of their inputs.

Existing Multidimensional Approximate Agreement protocols achieve resilience against $t_s < n / (D + 1)$ corruptions under a synchronous network where messages are delivered within some time $\Delta$, but become completely insecure as soon as a single message is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to $t_a < n / (D + 2)$ corruptions.

We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate $t_s$ corruptions when the network is synchronous, and also tolerate $t_a \leq t_s$ corruptions when the network is asynchronous. We provide a protocol that works as long as $(D + 1) \cdot t_s + t_a < n$, and matches several existing lower bounds.

The generalized inverses of systematic non-square binary matrices have applications in mathematics, channel coding and decoding, navigation signals, machine learning, data storage and cryptography such as the McEliece and Niederreiter public-key cryptosystems. A systematic non-square $(n-k) \times k$ matrix $H$, $n > k$, has $2^{k\times(n-k)}$ different generalized inverse matrices. This paper presents an algorithm for generating these matrices and compares it with two well-known methods, i.e. Gauss-Jordan elimination and Moore-Penrose methods. A random generalized inverse matrix construction method is given which has a lower execution time than the Gauss-Jordan elimination and Moore-Penrose approaches.

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, a orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice $\mathbb Z^n$ is of particular interest ($\mathbb Z$LIP). Heuristic analysis suggests that the BKZ algorithm with blocksize $\beta = n/2 + o(n)$ solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022).

In this work, I propose a provable version of this statement, namely, that $\mathbb Z$LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem (SVP) oracle in dimension at most $n/2 + 1$.

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In this work we revisit the Micciancio-Peikert preimage sampling algorithm with different contributions. We first propose a finer analysis of this procedure which results in interesting efficiency gains of around 20% on the preimage sizes without affecting security. It can thus be used as a drop-in replacement in every construction resorting to it. We then reconsider the Lyubashevsky-Wichs sampler for Micciancio-Peikert trapdoors which leverages rejection sampling but suffered from strong parameter requirements that hampered performance. We propose an improved analysis which allows to obtain much more compact parameters. This leads to gains of up to 30% compared to the original Micciancio-Peikert sampling technique and opens promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. As an application of the latter, we give the first lattice-based aggregate signature supporting public aggregation and that achieves relevant compression compared to the concatenation of individual signatures. Our scheme is proven secure in the aggregate chosen-key model coined by Boneh et al. in 2003, based on the well-studied assumptions Module Learning With Errors and Module Short Integer Solution.

We prove adaptive security of a simple three-round threshold Schnorr signature scheme, which we call Sparkle. The standard notion of security for threshold signatures considers a static adversary – one who must declare which parties are corrupt at the beginning of the protocol. The stronger adaptive adversary can at any time corrupt parties and learn their state. This notion is natural and practical, yet not proven to be met by most schemes in the literature.

In this paper, we demonstrate that Sparkle achieves several levels of security based on different corruption models and assumptions. To begin with, Sparkle is statically secure under minimal assumptions: the discrete logarithm assumption (DL) and the random oracle model (ROM). If an adaptive adversary corrupts fewer than t/2 out of a threshold of t + 1 signers, then Sparkle is adaptively secure under a weaker variant of the one-more discrete logarithm assumption (AOMDL) in the ROM. Finally, we prove that Sparkle achieves full adaptive security, with a corruption threshold of t, under AOMDL in the algebraic group model (AGM) with random oracles. Importantly, we show adaptive security without requiring secure erasures. Ours is the first proof achieving full adaptive security without exponential tightness loss for any threshold Schnorr signature scheme; moreover, the reduction is tight.

Bounded-collusion identity-based encryption (BC-IBE) is a variant of identity-based encryption, where an adversary obtains user secrete keys corresponding to at most $d$ identities. From results of existing work, it is proven that BC-IBE can be constructed from public key encryption (PKE) with several properties. In particular, we focus on post-quantum PKE schemes submitted to the NIST PQC competition, as the underlying PKE of BC-IBE schemes. This is because post-quantum cryptography is one of active research areas, due to recent advancement of developing quantum computers. Hence, it is reasonable to consider converting such PKE schemes into encryption schemes with additional functionalities. By using existing generic constructions of BC-IBE, those post-quantum PKE schemes are transformed into BC-IBE with non-compact public parameter. In this paper, we propose generic constructions of BC-IBE whose public parameter-size is more compact, and it is possible to apply many post-quantum PKE schemes secure against chosen plaintext attacks, into our generic constructions. To this end, we construct BC-IBE schemes from a group testing perspective, while existing ones are constructed by employing error-correcting codes or cover-free families. As a result, we can obtain BC-IBE schemes with more compact public parameter, which are constructed from the NIST PQC PKE schemes.