International Association
for Cryptologic Research

Interactive oracle proofs (IOPs) (Ben-Sasson et al., TCC 2016) have emerged as a powerful model for proof systems which generalizes both Interactive Proofs (IPs) and Probabilistically Checkable Proofs (PCPs). While IOPs are not any more powerful than PCPs from a complexity theory perspective, their potential to create succinct proofs and arguments has been demonstrated by many recent constructions achieving better parameters such as total proof length, alphabet size, and query complexity. In this work, we establish new results on the relationship between various notions of soundness for IOPs. First, we formally generalize the notion of round-by-round soundness (Canetti et al., STOC 2019) and round-by-round knowledge soundness (Chiesa et al., TCC 2019). Given this generalization, we then examine its relationship to the notions of generalized special soundness (Attema et al., CRYPTO 2021) and generalized special unsoundness (Attema et al., TCC 2022). We show that: 1. generalized special soundness implies generalized round-by-round soundness; 2. generalized round-by-round knowledge soundness implies generalized special soundness; 3. generalized special soundness does not imply generalized round-by-round knowledge soundness; 4. generalized round-by-round soundness (resp., special unsoundness) is an upper bound (resp., a lower bound) on standard soundness, and that this relationship is tight when the round-by-round soundness and special unsoundness errors are equal; and 5. any special sound IOP can be transformed via (a variant of) the Fiat-Shamir transformation into a non-interactive proof that is adaptively sound in the Quantum Random Oracle Model.

We describe a pairing-based Snark with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1, BN254 and BLS12-381. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254 or BLS12-381.

The proof size is constant ($10$ $\mathbb{G}_1$, $20$ $\mathbb{F}_p$), as is the verification time, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the $10$ multi-scalar multiplications in $\mathbb{G}_1$ - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$- and, to a lesser extent, the computation of a single sum of polynomial products over the prime scalar field via multimodular FFTs.

The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$

Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple *univariate* custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed in the sense that $$\sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). $$ This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.

We initiate the study of lattice-based pseudo-random functions (PRFs) for use in multi-party computation protocols, motivated by their application to distributed key management. We show that the LWE-based PRF of Boneh et al. (CRYPTO'13) can be turned into a distributed PRF protocol that runs in only 8 online rounds, improving over the state-of-the-art by an order of magnitude. The resulting protocol can be used as a method for distributed key derivation and reduces the amount of managed key material in distributed key management systems from linear in the number of users to constant. Finally, we support our findings by implementing and evaluating our protocol using the MP-SPDZ framework (CCS'20).

An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a deep connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were investigated in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize the input transactions, a natural objective is to minimize the distance (in terms of injected number of transactions) between any pair of unfairly ordered transactions in the output ledger — a concept we call bounded unfairness. In state machine replication (SMR) parlance this asks for minimizing the number of unfair state updates occurring before the processing of any transaction. This unfairness minimization objective gives rise to a natural class of parametric order fairness definitions that has not been studied before. As we observe, previous realizable relaxations of order fairness do not yield good unfairness bounds.

Achieving optimal order fairness in the sense of bounded unfairness turns out to be connected to the graph theoretic properties of the underlying transaction dependency graph and specifically the bandwidth metric of strongly connected components in this graph. This gives rise to a specific instance of the definition that we call ``directed bandwidth order-fairness'' which we show that it captures the best possible that any protocol can achieve in terms of bounding unfairness. We prove ordering transactions in this fashion is NP-hard and non-approximable for any constant ratio. Towards realizing the property, we put forth a new distributed ledger protocol called Taxis that achieves directed bandwidth order-fairness in the permissionless setting. We present two variants of our protocol, one that matches the property perfectly but (necessarily) lacks in performance and liveness, and a second variant that achieves liveness and better complexity while offering a slightly relaxed version of the directed bandwidth definition. Finally, we comment on applications of our work to social choice theory, a direction which we believe to be of independent interest.

Side-channel analysis certification is a process designed to certify the resilience of cryptographic hardware and software implementations against side-channel attacks. In certain cases, third-party evaluations by external companies or departments are necessary due to limited budget, time, or even expertise with the penalty of a significant exchange of sensitive information during the evaluation process. In this work, we investigate the potential of Homomorphic Encryption (HE) in performing side-channel analysis on HE-encrypted measurements. With HE applied to side-channel analysis (SCA), a third party can perform SCA on encrypted measurement data and provide the outcome of the analysis without gaining insights about the actual cryptographic implementation under test. To this end, we evaluate its feasibility by analyzing the impact of AI-based side-channel analysis using HE (private SCA) on accuracy and execution time and compare the results with an ordinary AI-based side-channel analysis (plain SCA). Our work suggests that both unprotected and protected cryptographic implementations can be successfully attacked already today with standard server equipment and modern HE protocols/libraries, while the traces are HE-encrypted.

In this paper, we introduce the family $\mathsf{DeuringVRF}_{y,z}$ of Verifiable Random Function (VRF) protocols. Based on isogenies between supersingular curves, the random function at the heart of our scheme is the one that computes the codomain of an isogeny of big prime degree from its kernel.

In $\mathsf{DeuringVRF}_{y,z}$, the evaluation is done with algorithms for the Deuring correspondence that make use of isogenies in dimension $z$, and the verification is based on the isogeny representation obtained from isogenies in dimension $y$.

The main advantage of the $\mathsf{DeuringVRF}_{y,z}$ family is its compactness, with proof sizes of a few hundred bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF constructions.

We describe four variants of our scheme with $(y,z) \in \lbrace (2,1),(2,2),(4,1), (4,2) \rbrace$ each offering different tradeoffs between compactness, evaluation efficiency and verification efficiency.

In the process, we introduce several new algorithms that might be of independent interest. In particular, for the variants with $z=2$, we introduce the first algorithm to translate an ideal into the corresponding isogeny of dimension $1$ using isogenies between abelian variety of dimension $2$ as a tool. The main advantage of this new algorithm compared to existing solution is the relaxation of the constraints on the prime characteristic: our new algorithm can run efficiently with ``SIDH primes" that are very easy to generate unlike ``SQIsign primes" that are currently required by the state of the art appoach. We believe that this algorithm opens a promising research direction to speed-up other schemes based on the Deuring correspondence such as the SQIsign signature scheme.

A revealable functional commitment allows a prover to commit to a secret polynomial size function $f$. Later, the prover has the ability to (1) prove that $y = f(x)$ for public $x, y$ and (2) open a small window into $f$'s machinery, via an encoded set of constraints - all without divulging any other information about $f$. In this way, revealable functional commitments allow the operator of a proprietary function to prove desired predicate about the function. For example, a government can commit to a bail decision algorithm, and prove that the same algorithm is being used for all defendants. They can also quell concerns about bias, and increase transparency processes by revealing windows into what their function does - while keeping most of their function secret to prevent exploitation. To build a revealable functional commitment, we introduce a 'proof of reveal', to show that a set of constraints, combined with a set of guarantees about those constraints, is consistent with a committed secret function. We show that combining a algebraic holomorphic proof (AHP), a 'proof of function relation' (PFR), and a proof of reveal yields a secure revealable functional commitment scheme. Additionally, we construct proof of reveals for two popular PFR-equipped AHPs, and obtain two instantiations of revealable functional commitments. Towards that end, we also develop interactive protocols that prove properties of committed polynomials, which may have independent value.

From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general. However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model). The impossibility stems from the difference between the definitions of unforgeability. To the best of our knowledge, existing works demonstrating the constructions do not provide formal reduction from an MDVS scheme to a ring signature scheme, and thus the impossibility has been overlooked for a long time.

We show that the key agreement scheme [IEEE Trans. Veh. Technol. 71(4): 3470-3479, 2022] fails to keep user anonymity, not as claimed.

Cryptographic group actions provide a flexible framework that allows the instantiation of several primitives, ranging from key exchange protocols to PRFs and digital signatures. The security of such constructions is based on the intractability of some computational problems. For example, given the group action $(G,X,\star)$, the weak unpredictability assumption (Alamati et al., Asiacrypt 2020) requires that, given random $x_i$'s in $X$, no probabilistic polynomial-time algorithm can compute, on input $\{(x_i,g\star x_i)\}_{i=1,\dots,Q}$, the group element $g$. In this work, we study such assumptions, aided by the definition of group action representations and a new metric, the linear dimension, that estimates the "linearity" of a group action, or in other words, how much it is far from being linear. We show that under some hypotheses on the group action representation, and if the linear dimension is polynomial in the security parameter, then the weak unpredictability and other related assumptions cannot hold. This technique is applied to some actions from cryptography, like the ones arising from the equivalence of linear codes; as a result, we obtain the impossibility of using such actions for the instantiation of certain primitives. As an additional result, some bounds on the linear dimension are given for classical groups, such as $\mathcal{S}_n$, $\mathrm{GL}(\mathbb{F}^n)$ and the cyclic group $\mathbb{Z}_n$ acting on itself.

Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent protocol-level attacks exploit subtle behaviors that differ among real-world AEAD schemes. We provide the first automated analysis method for protocols that use AEADs that can systematically find attacks that exploit the subtleties of the specific type of AEAD used. This can then be used to analyze specific protocols with a fixed AEAD choice, or to provide guidance on which AEADs might be (in)sufficient to make a protocol design secure. We develop generic symbolic AEAD models, which we instantiate for the Tamarin prover. Our approach can automatically and efficiently discover protocol attacks that could previously only be found using manual inspection, such as the Salamander attack on Facebook’s message franking, and attacks on SFrame and YubiHSM. Furthermore, our analysis reveals undesirable behaviors of several other protocols.

The related-key statistical saturation (RKSS) attack is a cryptanalysis method proposed by Li et al. at FSE 2019. It can be seen as the extension of previous statistical saturation attacks under the related-key setting. The attack takes advantage of a set of plaintexts with some bits fixed, while the other bits take all possible values, and considers the relation between the value distributions of a part of the ciphertext bits generated under related keys. Usually, RKSS distinguishers exploit the property that the value distribution stays invariant under the modification of the key. However, this property can only be deterministically verified if the plaintexts cover all possible values of a selection of bits. In this paper, we propose the probabilistic RKSS cryptanalysis which avoids iterating over all non-fixed plaintext bits by applying a statistical method on top of the original RKSS distinguisher. Compared to the RKSS attack, this newly proposed attack has a significantly lower data complexity and has the potential of attacking more rounds. As an illustration, for reduced-round Piccolo, we obtain the best key recovery attacks (considering both pre- and post-whitening keys) on both versions in terms of the number of rounds. Note that these attacks do not threaten the full-round security of Piccolo.

Most of the current fully homomorphic encryption (FHE) schemes are based on either the learning-with-errors (LWE) problem or on its ring variant (RLWE) for storing plaintexts. During the homomorphic computation of FHE schemes, RLWE formats provide high throughput when considering several messages, and LWE formats provide a low latency when there are only a few messages. Efficient conversion can bridge the advantages of each format. However, converting LWE formats into RLWE format, which is called ring packing, has been a challenging problem.

We propose an efficient solution for ring packing for FHE. The main improvement of this work is twofold. First, we accelerate the existing ring packing methods by using bootstrapping and ring switching techniques, achieving practical runtimes. Second, we propose a new method for efficient ring packing, HERMES, by using ciphertexts in Module-LWE (MLWE) formats, to also reduce the memory. To this end, we generalize the tools of LWE and RLWE formats for MLWE formats.

On a single-thread implementation, HERMES consumes $10.2$s for the ring packing of $2^{15}$ LWE-format ciphertexts into an RLWE-format ciphertext. This gives $41$x higher throughput compared to the state-of-the-art ring packing for FHE, PEGASUS [S&P'21], which takes $51.7$s for packing $2^{12}$ LWE ciphertexts with similar homomorphic capacity. We also illustrate the efficiency of HERMES by using it for transciphering from LWE symmetric encryption to CKKS fully homomorphic encryption, significantly outperforming the recent proposals HERA [Asiacrypt'21] and Rubato [Eurocrypt'22].

Video conferencing apps like Zoom have hundreds of millions of daily users, making them a high-value target for surveillance and subversion. While such apps claim to achieve some forms of end-to-end encryption, they usually assume an incorruptible server that is able to identify and authenticate all the parties in a meeting. Concretely this means that, e.g., even when using the “end-to-end encrypted” setting, malicious Zoom servers could eavesdrop or impersonate in arbitrary groups.

In this work, we show how security against malicious servers can be improved by changing the way in which such protocols use passwords (known as passcodes in Zoom) and integrating a password-authenticated key exchange (PAKE) protocol.

To formally prove that our approach achieves its goals, we formalize a class of cryptographic protocols suitable for this setting, and define a basic security notion for them, in which group security can be achieved assuming the server is trusted to correctly authorize the group members. We prove that Zoom indeed meets this notion. We then propose a stronger security notion that can provide security against malicious servers, and propose a transformation that can achieve this notion. We show how we can apply our transformation to Zoom to provably achieve stronger security against malicious servers, notably without introducing new security elements.

In CRYPTO'02, Liskov et al. have introduced a new symmetric key primitive called tweakable block cipher. They have proposed two constructions of designing a tweakable block cipher from block ciphers. The first proposed construction is called $\mathsf{LRW1}$ and the second proposed construction is called $\mathsf{LRW2}$. Although, $\mathsf{LRW2}$ has been extended in later works to provide beyond birthday bound security (e.g., cascaded $\mathsf{LRW2}$ in CRYPTO'12 by Landecker et al.), but extension of the $\mathsf{LRW1}$ has received no attention until the work of Bao et al. in EUROCRYPT'20, where the authors have shown that one round extension of $\mathsf{LRW1}$, i.e., masking the output of $\mathsf{LRW1}$ with the given tweak and then re-encrypting it with the same block cipher, gives security up to $2^{2n/3}$ queries. Recently, Khairallah has shown a birthday bound distinguishing attack on the construction and hence invalidated the security claim of Bao et al. This has led to the open research question, that how many round are necessary for cascading $\mathsf{LRW1}$ to achieve beyond birthday bound security ?

In this paper, we have shown that cascading $\mathsf{LRW1}$ up to four rounds are necessary for ensuring beyond the birthday bound security. In particular, we have shown that $\mathsf{CLRW1}^4$ provides security up to $2^{2n/3}$ queries. Security analysis of our construction is based on the recent development of the mirror theory technique for tweakable random permutations under the H-Coefficient framework.

A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group.

In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.

Modern SNARK designs typically feature a frontend-backend paradigm: The frontend compiles a user's program into some equivalent circuit representation, while the backend calls for a SNARK specifically made for proving satisfiability of the circuit. While the circuit may be defined over small fields, the backend prover often needs to lift the computation to much larger fields for achieving soundness. This gap results in concrete overheads, for example, when representing a SHA-256 program as a circuit with pairing-based backend SNARKs.

For a class of computations that are $\textit{highly repetitive}$, we propose an improved frontend that partially bridges this gap. Compared with existing works, our frontend yields circuit representations defined over larger fields but of smaller size. Our implementation shows that for SIMD computation with $\approx 180$ SHA-256 instances, our improved frontend improves prover runtime by over $2.6 \times$ and reduces memory usage by over $1.3 \times$.

Central to our result and of independent interest, is an efficient technique for proving non-native modulo arithmetic.

In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct Schnorr-like blind signatures based on modules such as classical groups and lattices. Consequently, our scheme is provably-secure in the poly-logarithmic (in the number of security parameter) concurrent execution and does not seem susceptible to the recent efficient ROS attack exploiting the linear nature of the underlying mathematical tool.

In more detail, our blind signature exploits the "quadratic twist" of an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size $128$~B and signature size $8$~KB under the CSIDH-512 parameter sets---these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a new "ring" variant of the group action inverse problem rGAIP, we can halve the signature size to 4~KB while increasing the public key size to 512~B. We provide preliminary cryptanalysis of rGAIP and show that for certain parameter settings, it is essentially as secure as the standard GAIP. Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key---constructing such a hash function in the isogeny setting remains an open problem.

Ducas and Pulles in "Does the Dual-Sieve Attack on Learning with Errors even Work?" especially report on experiments they made comparing the distributions of scores for random targets and BDD targets. They discovered that the distribution of scores for BDD targets deviate from the predictions made under the independence heuristic. Here, we want to derive approximations for the distributions which take into account the dependency that occur in the scores. These approximations lead to new formulas that seem to describe the result in Table 1 of the article quite accurately.

The key step of the cube attack is to recover the special polynomial, the superpoly, of the target cipher. In particular, the balanced superpoly, in which there exists at least one secret variable as a single monomial and none of the other monomials contain this variable, can be exploited to reveal one-bit information about the key bits. However, as the number of rounds grows, it becomes increasingly difficult to find such balanced superpolies. Consequently, traditional methods of searching for balanced superpolies soon hit a bottleneck. Aiming at performing a cube attack on more rounds of Trivium with a practical complexity, in this paper, we present three techniques to obtain sufficient balanced polynomials. 1. Based on the structure of Trivium, we propose a variable substitution technique to simplify the superpoly. 2. Obtaining the additional balanced polynomial by combining two superpolies to cancel the two-degree terms. 3. We propose an experimental approach to construct high-quality large cubes which may contain more subcubes with balanced superpolies and a heuristic search strategy for their subcubes whose superpolies are balanced. To illustrate the power of our techniques, we search for balanced polynomials for 810- and 825-round Trivium. As a result, we can mount cube attacks against 810- and 825-round Trivium with the time complexity of $2^{44.17}$ and $2^{53.17}$ round-reduced Trivium initializations, respectively, which can be verified in 48 minutes and 18 days on a PC with one A100 GPU. For the same level of time complexity, this improves the previous best results by $2$ and $5$ rounds, respectively.