International Association
for Cryptologic Research

The major objective of this paper is to present a theoretical model for an algorithm that has not been previously described in the literature, capable of generating a secret key through the transmission of data over a public channel. We explain how the method creates a shared secret key by attaining commutativity through the multiplication of the modular exponentiation of a minimum of two bases and an equal number of private exponents for each party involved in the exchange. In addition, we explore the relationship between CMME and the traditional Diffie-Hellman scheme. We just briefly discuss the algorithm's security, opting to leave the essential investigation to cryptanalysts, while we elucidate on the algorithm's mechanism by illustrating some cases.

Existing proofs of adaptive security (e.g., in settings in which decryption keys are adaptively revealed) often rely on guessing arguments. Such guessing arguments can be simple (and, e.g., just involve guessing which keys are revealed), or more complex "partitioning'' arguments. Since guessing directly and negatively impacts the loss of the corresponding security reduction, this leads to black-box lower bounds for a number of cryptographic scenarios that involve adaptive security.

In this work, we provide an alternative to such guessing arguments: instead of guessing in a security reduction which adaptive choices an adversary A makes, we rewind A many times until we can successfully embed a given computational challenge. The main benefit of using rewindings is that these rewindings can be arranged sequentially, and the corresponding reduction loss only accumulates additively (instead of multiplicatively, as with guessing). The main technical challenge is to show that A's success is not negatively affected after (potentially many) rewindings. To this end, we develop a machinery for "undirected'' rewindings that preserve A's success across (potentially many) rewindings.

We use this strategy to show - security of the "Logical Key Hierarchy'' protocol underlying the popular TreeKEM key management protocol, and - security of the Goldreich-Goldwasser-Micali (GGM) pseudorandom function (PRF) as a prefix-constrained PRF.

In both cases, we provide the first polynomial reductions to standard assumptions (i.e., to IND-CPA and PRG security, respectively), and in case of the GGM PRF, we also circumvent an existing lower bound.

Distributed broadcast encryption (DBE) [Boneh and Zhandry - CRYPTO 2014] improves on the traditional notion of broadcast encryption by eliminating the key-escrow problem: In a DBE system, users generate their own secret keys without the help of a trusted party. Then anyone can broadcast a message for a subset S of the users, in such a way that the resulting ciphertext size is sublinear in (and, ideally, independent of) |S|. Unfortunately, the only known construction of DBE requires heavy cryptographic machinery, such as general-purpose indistinguishability obfuscation. In this work, we show that obfuscation is not necessary for DBE, and we present two DBE schemes from standard assumptions in prime-order bilinear groups. Our constructions are conceptually simple, satisfy the strong notion of adaptive security, and are concretely efficient. In fact, their performance, in terms of number of group elements and efficiency of the algorithms, is comparable with that of traditional (non distributed) broadcast encryption schemes from bilinear groups.

We offer two very transparent digital signature schemes: one using non-square matrices and the other using scrap automorphisms. The former can be easily converted to a public key encryption scheme.

Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support conjunctive searches, or are practically inefficient. In particular, there exists no quantum-safe yet practically efficient conjunctive SSE scheme from lattice-based hardness assumptions. We solve this open question by proposing Oblivious Post-Quantum Secure Cross Tags (OQXT) – the first lattice-based practically efficient and highly scalable conjunctive SSE scheme. The technical centerpiece of OQXT is a novel oblivious cross-tag generation protocol with provable security guarantees derived from lattice-based hardness assumptions. We prove the post-quantum simulation security of OQXT with respect to a rigorously defined and thoroughly analyzed leakage profile. We then present a prototype implementation of OQXT and experimentally validate its practical efficiency and scalability over extremely large real-world databases. Our experiments show that OQXT has competitive end-to-end search latency when compared with the best (quantum-broken) conjunctive SSE schemes.

Proving security bounds in contexts with a large number of users is one of the central problems in symmetric-key cryptography today. This paper introduces a new method for information-theoretic multi-user security proofs, called ``the Squared-Ratio Method''. At its core, the method requires the expectation of the square of the ratio of observing the so-called good transcripts (from Patarin's H-coefficient technique) in the real and the ideal world. Central to the method is the observation that for information-theoretic adversaries, the KL-divergence for the multi-user security bound can be written as a summation of the KL-divergence of every single user. We showcase the Squared-Ratio Method on three examples: the Xor of two Permutations by Bellare et al. (EUROCRYPT '98) and Hall et al. (CRYPTO '98), the Encrypted Davies-Mayer by Cogliati and Seurin (CRYPTO '16), and the two permutation variant of the nEHtM MAC algorithm by Dutta et al. (EUROCRYPT '19). With this new tool, we provide improved bounds for the multi-user security of these constructions. Our approach is modular in the sense that the multi-user security can be obtained directly from single-user results.

Addition of $n$ inputs is often the easiest nontrivial function to compute securely. Motivated by several open questions, we ask what can be computed securely given only an oracle that computes the sum. Namely, what functions can be computed in a model where parties can only encode their input locally, then sum up the encodings over some Abelian group $\G$, and decode the result to get the function output.

An *additive randomized encoding* (ARE) of a function $f(x_1,\ldots,x_n)$ maps every input $x_i$ independently into a randomized encoding $\hat x_i$, such that $\sum_{i=1}^n$ $\hat x_i$ reveals $f(x_1,\ldots,x_n)$ and nothing else about the inputs. In a *robust* ARE, the sum of any subset of the $\hat x_i$ only reveals the residual function obtained by restricting the corresponding inputs.

We obtain positive and negative results on ARE. In particular:

* Information-theoretic ARE. We fully characterize the 2-party functions $f:X_1\times X_2\to\{0,1\}$ admitting a perfectly secure ARE. For $n\ge 3$ parties, we show a useful ``capped sum'' function that separates statistical security from perfect security.

* Computational ARE. We present a general feasibility result, showing that *all functions* can be computed in this model, under a standard hardness assumption in bilinear groups. We also describe a heuristic lattice-based construction.

* Robust ARE. We present a similar feasibility result for {\em robust} computational ARE based on ideal obfuscation along with standard cryptographic assumptions.

We then describe several applications of ARE and the above results.

* Under a standard cryptographic assumption, our computational ARE schemes imply the feasibility of general non-interactive secure computation in the shuffle model, where messages from different parties are shuffled. This implies a general utility-preserving compiler from differential privacy in the central model to computational differential privacy in the (non-robust) shuffle model.

* The existence of information-theoretic {\em robust} ARE implies "best-possible" information-theoretic MPC protocols (Halevi et al., TCC 2018) and degree-2 multiparty randomized encodings (Applebaum et al., TCC 2018). This yields new positive results for specific functions in the former model, as well as a simple unifying barrier for obtaining negative results in both models.

We propose UniPlonK, a modification of the PlonK protocol that uniformizes the Verifier’s work for families of circuits. Specifically, a single fixed-cost “Universal Verifier” can check proofs for circuits of different: sizes, public input lengths, selector polynomials, copy constraints, and even different custom gate sets. UniPlonK therefore extends the universality of PlonK beyond the SRS; it enables a single “Universal Verifier Circuit” capable of verifying proofs from different PlonK circuits.

The Universal Verifier’s marginal cost over the ordinary Plonk verifier is small: for circuits using only the vanilla Plonk gate, the Universal Verifier performs a number of additional field multiplications proportional to the logarithm of the maximum supported circuit size; it incurs no additional elliptic curve operations. For circuits using custom gates, the Universal Verifier incurs additional elliptic curve arithmetic only when verifying proofs from circuits that do not use all supported gate types. For circuits that use all supported gates, the Universal Verifier’s additional cost consists only of field multiplications proportional to the logarithm of the maximum supported circuit size, the number of custom gate types, and the number of witness variables used by these gates. In both settings (vanilla-only and custom gates) the marginal cost to the prover is a fixed-base MSM of size ℓ, the length of the public input vector.

Order manipulation attacks such as frontrunning and sandwiching have become an increasing concern in blockchain applications such as DeFi. To protect from such attacks, several recent works have designed order policy enforcement (OPE) protocols to order transactions fairly in a data-independent fashion. However, while the manipulation attacks are motivated by monetary profits, the defenses assume honesty among a significantly large set of participants. In existing protocols, if all participants are rational, they may be incentivized to collude and circumvent the order policy without incurring any penalty.

This work makes two key contributions. First, we explore whether the need for the honesty assumption is fundamental. Indeed, we show that it is impossible to design OPE protocols under some requirements when all parties are rational. Second, we explore the tradeoffs needed to circumvent the impossibility result. In the process, we propose a novel concept of rationally binding transactions that allows us to construct AnimaguSwap(A key design in AnimaguSwap is that user orders may transform to a different direction---like the fictional creatures Animagi in Harry Potter---in order to achieve the desired game theoretic properties) , the first content-oblivious Automated Market Makers (AMM) that is secure under rationality.

This paper presents a security analysis of forward secure log sealing in the journald logging system, which is part of systemd and used in modern Linux distributions. Forward secure log sealing is a cryptographic technique used to ensure the integrity of past log entries even in the event of a full system compromise. We analyze the implementation of this technique in journald, identifying multiple security vulnerabilities resulting from a gap between the model of the cryptographic primitives and their usage in a larger context. In particular one vulnerability allows to forge arbitrary logs for past entries without the validation tool noticing any problem. We demonstrate the found attacks on the journald implementation by providing a concrete security definition for the larger system, an implementation close to the security experiment and a corresponding attacker defeating it when used with a vulnerable version of journald. For the more serious vulnerabilities, we provide patch recommendations, which prevent the implemented attack. Our findings break the security guarantee from log sealing completely, without the error resulting from an inconsistency in the theoretical model nor being a simple implementation mistake. This provides a practical example of the problems that can occur when applying cryptographic primitives to a complex system in reality and that fall in between theory and practice.

Lossy trapdoor functions (LTFs) constitute a useful and versatile cryptographic building block. LTFs have found applications in various types of encryption schemes, are closely connected to statistically secure oblivious transfer protocols, and have led to the first constructions of group-based trapdoor functions. However, with one recent exception, all known group-based LTFs are comparatively inefficient, and in particular suffer from large images. In this work, we attempt to explain this inefficiency, and derive lower bounds for the image size of group-based LTFs. In essence, we find that purely algebraic group-based LTFs (i.e., LTFs that use the underlying group in a generic way, without considering group representations) must suffer from a large image size (of an at least super-constant number of group elements). Our results also help to explain the mentioned exceptional group-based LTF with compact images.

ASCON, a lightweight permutation-based primitive, has been selected as NIST’s lightweight cryptography standard. ASCON-HASH is one of the hash functions provided by the cipher suite ASCON. At ToSC 2021, the collision attack on 2-round ASCON-HASH with time complexity 2^{103} was proposed. Due to its small rate, it is always required to utilize at least 2 message blocks to mount a collision attack because each message block is only of size 64 bits. This significantly increases the difficulty of the analysis because one almost needs to analyze equivalently at least $2L$ rounds of ASCON in order to break $L$ rounds. In this paper, we make some critical observations on the round function of ASCON, especially a 2-round property. It is found that such properties can be exploited to reduce the time complexity of the 2-round collision attack to 2^{62.6}. Although the number of attacked rounds is not improved, we believe our techniques shed more insight into the properties of the ASCON permutation and we expect they can be useful for the future research. Following the same analysis method and with SMT technique, we practically find some semi-free-start collision attacks for 4-round ASCON-HASH and ASCON-Xof with STP solver.

Selective opening (SO) security is a security notion for public-key encryption schemes that captures security against adaptive corruptions of senders. SO security comes in chosen-plaintext (SO-CPA) and chosen-ciphertext (SO-CCA) variants, neither of which is implied by standard security notions like IND-CPA or IND-CCA security.

In this paper, we present the first SO-CCA secure encryption scheme that combines the following two properties: (1) it has a constant ciphertext expansion (i.e., ciphertexts are only larger than plaintexts by a constant factor), and (2) its security can be proven from a standard assumption. Previously, the only known SO-CCA secure encryption scheme achieving (1) was built from an ad-hoc assumption in the RSA regime.

Our construction builds upon LWE, and in particular on a new and surprisingly simple construction of compact lossy trapdoor functions (LTFs). Our LTF can be converted into an “all-but-many LTF” (or ABM-LTF), which is known to be sufficient to obtain SO-CCA security. Along the way, we fix a technical problem in that previous ABM-LTF-based construction of SO-CCA security.

Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the standard model, even with a CRS, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Secondly, we study the question of building distributed samplers in the party-dynamic setting, where parties can join in an ad-hoc manner, and the total number of parties is unbounded. Here, we obtain positive results. First, we build a special type of unbounded universal sampler, which after a trusted setup, allows sampling from any distributed with unbounded size. Our construction is in the shared randomness model, where the parties have access to a shared random string, and uses indistinguishability obfuscation and somewhere statistically binding hashing. Next, using our unbounded universal sampler, we construct distributed universal samplers in the party-dynamic setting. Our first construction satisfies one-time selective security in the shared randomness model. Our second construction is reusable and secure against a malicious adversary in the random oracle model. Finally, we show how to use party-dynamic, distributed universal samplers to produce ideal, correlated randomness in the party-dynamic setting, in a single round of interaction.

Hofheinz et al. (TCC 2017) proposed several key encapsulation mechanism (KEM) variants of Fujisaki-Okamoto (\textsf{FO}) transformation, including $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}_m^{\slashed{\bot}}$, $\textsf{QFO}_m^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^\bot$ and $\textsf{QFO}_m^\bot$, and they are widely used in the post-quantum cryptography standardization launched by NIST. These transformations are divided into two types, the implicit and explicit rejection type, including $\{\textsf{FO}^{\slashed{\bot}}, \textsf{FO}_m^{\slashed{\bot}}, \textsf{QFO}_m^{\slashed{\bot}}\}$ and $\textsf{FO}^{\bot}, \textsf{FO}_m^\bot, \textsf{QFO}_m^\bot$, respectively. The decapsulation algorithm of the implicit (resp. explicit) rejection type returns a pseudorandom value (resp. an abort symbol $\bot$) for an invalid ciphertext.

For the implicit rejection type, the \textsf{IND-CCA} security reduction of $\textsf{FO}^{\slashed{\bot}}$ in the quantum random oracle model (QROM) can avoid the quadratic security loss, as shown by Kuchta et al. (EUROCRYPT 2020). However, for the explicit rejection type, the best known \textsf{IND-CCA} security reduction in the QROM presented by Ho"velmanns et al. (ASIACRYPT 2022) for $\textsf{FO}_m^\bot$ still suffers from a quadratic security loss. Moreover, it is not clear until now whether the implicit rejection type is more secure than the explicit rejection type.

In this paper, a QROM security reduction of $\textsf{FO}_m^\bot$ without incurring a quadratic security loss is provided. Furthermore, our reduction achieves \textsf{IND-qCCA} security, which is stronger than the \textsf{IND-CCA} security. To achieve our result, two steps are taken: The first step is to prove that the \textsf{IND-qCCA} security of $\textsf{FO}_m^\bot$ can be tightly reduced to the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ by using the online extraction technique proposed by Don et al. (EUROCRYPT 2022). The second step is to prove that the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ can be reduced to the \textsf{IND-CPA} security of the underlying public key encryption (PKE) scheme without incurring quadratic security loss by using the Measure-Rewind-Measure One-Way to Hiding Lemma (EUROCRYPT 2020).

In addition, we prove that (at least from a theoretic point of view), security is independent of whether the rejection type is explicit ($\textsf{FO}_m^\bot$) or implicit ($\textsf{FO}_m^{\slashed{\bot}}$) if the underlying PKE scheme is weakly $\gamma$-spread.

In Internet security protocols including TLS 1.3, KEMTLS, MLS and Noise, HMAC is being assumed to be a dual-PRF, meaning a PRF not only when keyed conventionally (through its first input), but also when "swapped" and keyed (unconventionally) through its second (message) input. We give the first in-depth analysis of the dual-PRF assumption on HMAC.

For the swap case, we note that security does not hold in general, but completely characterize when it does; we show that HMAC is swap-PRF secure if and only if keys are restricted to sets satisfying a condition called feasibility, that we give, and that holds in applications. The sufficiency is shown by proof and the necessity by attacks. For the conventional PRF case, we fill a gap in the literature by proving PRF security of HMAC for keys of arbitrary length.

Our proofs are in the standard model, make assumptions only on the compression function underlying the hash function, and give good bounds in the multi-user setting. The positive results are strengthened through achieving a new notion of variable key-length PRF security that guarantees security even if different users use keys of different lengths, as happens in practice.

A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible. In this work, we provide new definitions for distributed samplers which we show achieve meaningful security guarantees in the standard model. In particular, our notion implies that the hardness of a wide range of security games is preserved when the CRS is replaced with a distributed sampler. We also show how to realize our notion of distributed samplers. A core technical tool enabling our construction is a new notion of single-message zero knowledge.

Group actions are fundamental mathematical tools, with a long history of use in cryptography. Indeed, the action of finite groups at the basis of the discrete logarithm problem is behind a very large portion of modern cryptographic systems. With the advent of post-quantum cryptography, however, the method for building protocols shifted towards a different paradigm, centered on the difficulty of discerning 'noisy' objects, as is the case for lattices, codes, and multivariate systems. This method yields promising results for 'core' primitives such as encryption or signature, but can be less than ideal in the case when more advanced functionalities are required. In this work, we show that isomorphism problems which stem from cryptographic group actions, can be viable building blocks for threshold signature schemes. In particular, we construct a full $N$-out-of-$N$ threshold signature scheme, and discuss the efficiency issues arising from extending it to the generic $T$-out-of-$N$ case. To give a practical outlook on our constructions, we instantiate them with the LESS and MEDS frameworks, which are two flavors of code-based cryptographic group actions. Finally, we highlight some ideas that would allow for a more efficient and compact $(T,N)$ threshold variant of LESS, whose security relies on new hardness assumptions.

Pairings are useful tools in isogeny-based cryptography and have been used in SIDH/SIKE and other protocols. As a general technique, pairings can be used to move problems about points on curves to elements in finite fields. However, until now, their applicability was limited to curves over fields with primes of a specific shape and pairings seemed too costly for the type of primes that are nowadays often used in isogeny-based cryptography. We remove this roadblock by optimizing pairings for highly-composite degrees such as those encountered in CSIDH and SQISign. This makes the general technique viable again: We apply our low-cost pairing to problems of general interest, such as supersingularity verification and finding full-torsion points, and show that we can outperform current methods, in some cases up to four times faster than the state-of-the-art. Furthermore, we analyze how parings can be used to improve deterministic and dummy-free CSIDH. Finally, we provide a constant-time implementation (in Rust) that shows the practicality of these algorithms.

A zero-knowledge proof is a cryptographic protocol where a prover can convince a verifier that a statement is true, without revealing any further information except for the truth of the statement. More precisely, if $x$ is a statement from an NP language verified by an efficient machine $M$, then a zero-knowledge proof aims to prove to the verifier that there exists a witness $w$ such that $M(x,w)=1$, without revealing any further information about $w$. The proof is a proof of knowledge, if the prover additionally convinces the verifier that it knows the witness $w$, rather than just of its existence.

This article is a survey of recent developments in building practical systems for zero-knowledge proofs of knowledge using vector oblivious linear evaluation (VOLE), a tool from secure two-party computation.