Theory of Cryptography

Table of Contents

1. Frontmatter

2. Secure Computation I

   1. Frontmatter

   2. Honest Majority Constant-Round MPC with Linear Communication from One-Way Functions

      Junru Li, Yifan Song

      Abstract

      Secure multiparty computation (MPC) faces a fundamental efficiency trade-off between round complexity and communication complexity: without fully homomorphic encryption, protocols with constant round complexity (e.g., protocols based on garbled circuits) incur high communication cost, while communication-efficient approaches (e.g., protocols based on secret sharing) have round complexity linear in the depth of the circuit. In this work, we focus on reducing the communication complexity of constant-round MPC protocols in the honest majority setting. Existing results either rely on strong assumptions (e.g., random oracles, DDH, LPN) or incur high communication of \(\varOmega (|C|n^2\kappa )\) bits under one-way functions (OWFs). However, non-constant-round MPC protocols can achieve linear communication in the number of parties even with information-theoretic security.

      We resolve this gap by presenting the first constant-round honest majority MPC protocol with linear communication complexity of \(O(|C|n\kappa + n^2\kappa ^2+n^4\kappa )\) only from OWFs. We introduce novel techniques for computing garbled circuits via party virtualization and efficient local computation of virtual parties, which optimize the existing protocols on multiparty garbling. These allow us to overcome the \(O(n^2\kappa )\) bit of communication per-gate bottleneck of prior protocols, matching the scalability of the best non-constant-round protocols in the same setting.

   3. Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols

      Ran Cohen, Pouyan Forghani, Juan Garay, Rutvik Patel, Vassilis Zikas

      Abstract

      Despite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other.

      In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition.

      We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question:

      Is asynchronous parallel composition even a realistic goal?

      To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions.

   4. Efficient Garbled Pseudorandom Functions and Lookup Tables from Minimal Assumption

      Wei-Kai Lin, Zhenghao Lu, Hong-Sheng Zhou

      Abstract

      Yao’s garbled circuits have received huge attention in both theory and practice. While garbled circuits can be constructed using minimal assumption (i.e., the existence of pseudorandom functions or one-way functions), the state-of-the-art constructions (e.g., Rosulek-Roy, Crypto 2021) are based on stronger assumptions. In particular, the “Free-XOR” technique (Kolesnikov-Schneider, ICALP 2008) is essential in these state-of-the-art constructions, and their security can only be proven in the random oracle model, or rely on the “circular-correlation robust hash” assumption.

      In this paper, we aim to develop new techniques to construct efficient garbling schemes using minimal assumptions. Instead of generically replacing the Free-XOR technique, we focus on garbling schemes for specific functionalities. We successfully eliminated the need for Free-XOR in several state-of-the-art schemes, including the one-hot garbling (Heath and Kolesnikov, CCS 2021) and the garbled pseudorandom functions, and the garbled lookup tables (Heath, Kolesnikov and Ng, Eurocrypt 2024). Our schemes are based on minimal assumptions, i.e., standard pseudorandom functions (PRFs)—we resolved the need for circular security. The performance of our scheme is almost as efficient as the best results except for a small constant factor. Namely, for any lookup table \(\{0,1\}^n \rightarrow \{0,1\}^m\), our scheme takes \(n + (5n+9)m{\lambda } + 2^n \cdot m\) bits of communication, where \(\lambda \) is the security parameter of PRF.

   5. Practical Secure Delegated Linear Algebra with Trapdoored Matrices

      Mark Braverman, Stephen Newman

      Abstract

      Most heavy computation occurs on servers owned by a second party. This reduces data privacy, resulting in interest in data-oblivious computation, which typically severely degrades performance. Secure and fast delegated computation is particularly important for linear algebra, which comprises a large fraction of total computation and is best run on highly specialized hardware often accessible only through the cloud.

      We state the natural efficiency and security desiderata for fast and data-oblivious delegated linear algebra. We demonstrate the existence of Trapdoored-Matrix families based on an LPN assumption, and provide a scheme for secure delegated matrix-matrix and matrix-vector multiplication based on the existence of trapdoored matrices. We achieve sublinear overhead for the server, dramatically reduced computation for the client, and various practical advantages over previous protocols.

   6. On Achieving “Best-in-the-Multiverse” MPC

      Anasuya Acharya, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam

      Abstract

      The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees: guaranteed output delivery against an honest majority and security with abort against a dishonest majority and provided tight upper and lower bounds in the presence of computationally bounded, i.e., PPT adversaries. Another line of works starting from the work of Chaum (CRYPTO 1989) considered protocols that simultaneously achieved security against an unbounded adversary corrupting a minority of the parties and security against arbitrary corruption by a PPT adversary.

      In this work, we generalize previous work to investigate a fundamental challenge of designing an MPC in a multiverse where security is specified with respect to (1) GOD, (2) fairness, (3) security w.r.t. unbounded adversaries, and (4) security with abort. The work of Lucas et al. (PODC 2010) resolved this question when considering threshold adversaries; however, the case of general adversary structures remains open. Our main result completely characterizes when a protocol can simultaneously achieve all properties. Namely, given adversary structures \(\mathcal{Z}_{\textsf{GOD}}, \mathcal{Z}_{\textsf{fair}},\mathcal{Z}_{\textsf{S}}\) and \(\mathcal{Z}_{\textsf{C}}\), we provide tight upper and lower bounds for when an MPC protocol can provide GOD, fairness, and security with abort respectively for unbounded and PPT adversaries w.r.t. these adversary structures.

   7. Information-Theoretic Broadcast-Optimal MPC

      Michele Ciampi, Ivan Damgárd, Divya Ravi, Luisa Siniscalchi, Sophia Yakoubov

      Abstract

      Broadcast, though often used as a black box in cryptographic protocols, is expensive to realize in terms of rounds and communication complexity. We investigate the minimal use of broadcast in round-optimal information-theoretic MPC, with statistical security. For information-theoretic MPC with guaranteed output delivery, four rounds of communication are necessary and sufficient (Applebaum, Kachlon and Patra, FOCS 2020; Applebaum, Kachlon and Patra, STOC 2023). We show that broadcast is unavoidable in the second and third rounds of statistical MPC protocols. To complement our lower bounds, we modify the protocol of Applebaum, Kachlon and Patra (STOC 2023) to make use of broadcast only in the second and third round. Along the way, we show that the sharing phase of any three-round information-theoretic VSS protocol must also make use of broadcast in the second and third rounds.

3. Homomorphic Primitives

   1. Frontmatter

   2. Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE

      Chris Peikert, Zachary Pepin

      Abstract

      The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption (FHE), has relied on cyclotomic number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on “packed” plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext “slots,” while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency.

      This work provides a suite of tools for instantiating ring-based lattice cryptography to work over subfields of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with optimal plaintext packing and homomorphic SIMD parallelism for any plaintext characteristic, along with efficient packed bootstrapping that fully exploits this parallelism.

      Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory:

      • For sampling and decoding errors in encryption and decryption (respectively), we construct geometrically short, structured bases for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well).
      • For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem (CRT) bases in abelian number rings, and give specialized fast transforms that map between CRT bases and any similarly structured bases.
      • For packed bootstrapping and homomorphic linear algebra, we give a general framework for homomorphic evaluation of structured linear transforms in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations.

   3. Fully-Homomorphic Encryption from Lattice Isomorphism

      Pedro Branco, Giulio Malavolta, Zayd Maradni

      Abstract

      The lattice isomorphism problem (LIP) asks, given two lattices \(\varLambda _0\) and \(\varLambda _1\), to decide whether there exists an orthogonal linear map from \(\varLambda _0\) to \(\varLambda _1\). In this work, we show that the hardness of (a circular variant of) LIP implies the existence of a fully-homomorphic encryption scheme for all classical and quantum circuits. Prior to our work, LIP was only known to imply the existence of basic cryptographic primitives, such as public-key encryption or digital signatures.

   4. Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys

      Kuiyuan Duan, Hongbo Li, Dengfa Liu, Guangsheng Ma

      Abstract

      Functional bootstrapping is a core technique in Fully Homomorphic Encryption(FHE). For large plaintext, to evaluate a general function homomorphically over a ciphertext, in the FHEW/TFHE approach, since the function in look-up table form is encoded in the coefficients of a test polynomial, the degree of the polynomial must be high enough to hold the entire table. This increases the bootstrapping time complexity and memory cost, as the size of bootstrapping keys and keyswitching keys need to be large accordingly.

      In this paper, we propose to encode the look-up table of any function in a polynomial vector, whose coefficients can hold more data. The corresponding representation of the additive group \({\mathbb Z}_q\) used in the RGSW-based bootstrapping is the group of monic monomial permutation matrices, which integrates the permutation matrix representation used by Alperin-Sheriff and Peikert in 2014, and the monic monomial representation used in the FHEW/TFHE scheme. We make comprehensive investigation of the new representation, and propose a new bootstrapping algorithm based on it.

      The new algorithm supports functional bootstrapping of large-plaintexts, and achieves polynomial reduction in key sizes and a constant-factor improvement in run-time cost.

   5. Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN

      Damiano Abram, Giulio Malavolta, Lawrence Roy

      Abstract

      Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given an encoding key for a function f, a hash on x together with a (small) input encoding allow one to recover f(x). TDHs are a versatile tool and a useful building block for more complex cryptographic protocols.

      In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate \(\varepsilon = O(\log ^{1+\beta } n / n)\) for \(\beta >0\), i.e., in the so-called low-noise regime. The construction achieves \(2^{\varTheta (\log ^{1-\beta } \lambda )}\) compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity \(L / 2^{\varTheta (\log ^{1-\beta } L)}\), for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than L) from any code-based assumption.

   6. Privately Constrained PRFs from DCR: Puncturing and Bounded Waring Rank

      Amik Raj Behera, Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl

      Abstract

      A privately constrained pseudorandom function (pCPRF) is a PRF with the additional property that one can derive a constrained key that allows evaluating the PRF only on inputs satisfying a constraint predicate C, without revealing C itself or leaking information about the PRF’s output on inputs that do not satisfy the constraint.

      Existing privately constrained PRFs face significant limitations: either (1) they rely on assumptions known to imply fully-homomorphic encryption or indistinguishability obfuscation, (2) they support only highly restricted classes of constraints—notably, no known group-based pCPRF even supports the simple class of puncturing constraints (where the constrained key permits evaluation on all but one point while hiding the punctured point), or (3) they are limited to polynomial-size input domains. A long-standing open question has been whether one can construct a privately constrained PRF from group-based assumptions for more expressive classes of constraints. In this work, we present a pCPRF based on the decisional composite residuosity (DCR) assumption that supports a highly expressive class of predicates, namely constraints whose degree and Waring rank are both polynomially bounded, which includes puncturing.

      From a technical perspective, our work follows the general template of Couteau, Meyer, Passelègue, and Riahinia (Eurocrypt’23), who constructed a pCPRF from group-based homomorphic secret-sharing but were limited to inner-product constraints in the constraint-hiding setting. Leveraging novel techniques for computing with distributed discrete logarithms (DDLog), we enable the non-interactive authentication of powers of linear combinations of shares of some value. This, in turn, allows us to express constraints with polynomially bounded Waring rank.

      Our construction is single-key, selectively secure, and supports an exponential-size domain.

4. Proofs I

   1. Frontmatter

   2. Linear Prover IOPs in Log Star Rounds

      Noor Athamnah, Noga Ron-Zewi, Ron D. Rothblum

      Abstract

      Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols.

      State-of-the-art IOPs achieve a linear-size prover and a poly-logarithmic time verifier but require a relatively large, logarithmic, number of rounds. While the Fiat-Shamir heuristic can be used to eliminate the need for actual interaction, in modern highly-parallelizable computer architectures such as GPUs, the large number of rounds still translates into a major bottleneck for the prover, since it needs to alternate between computing the IOP messages and the Fiat-Shamir hashes. Motivated by this fact, in this work we study the round complexity of linear-prover IOPs.

      Our main result is an IOP for a large class of Boolean circuits, with only \(O(\log ^*(S))\) rounds, where \(\log ^*\) denotes the iterated logarithm function (and S is the circuit size). The prover has linear size O(S) and the verifier runs in time \(\textrm{polylog}(S)\) and has query complexity \(O(\log ^*(S))\). The protocol is both conceptually simpler, and strictly more efficient, than prior linear prover IOPs for Boolean circuits.

   3. Linear-Time Accumulation Schemes

      Benedikt Bünz, Alessandro Chiesa, Giacomo Fenzi, William Wang

      Abstract

      Proof-carrying data (PCD) is a powerful cryptographic primitive for computational integrity in a distributed setting. State-of-the-art constructions of PCD are based on accumulation schemes (and, closely related, folding schemes).

      We present WARP, the first accumulation scheme with linear prover time and logarithmic verifier time. Our scheme is hash-based (secure in the random oracle model), plausibly post-quantum secure, and supports unbounded accumulation depth.

      We achieve our result by constructing an interactive oracle reduction of proximity that works with any linear code over a sufficiently large field. We take a novel approach by constructing a straightline extractor that relies on erasure correction, rather than error-tolerant decoding like prior extractors. Along the way, we introduce a variant of straightline round-by-round knowledge soundness that is compatible with our extraction strategy.

   4. Relativized Succinct Arguments in the ROM do not Exist

      Annalisa Barbara, Alessandro Chiesa, Ziyi Guan

      Abstract

      A relativized succinct argument in the random oracle model (ROM) is a succinct argument in the ROM that can prove/verify the correctness of computations that involve queries to the random oracle. We prove that relativized succinct arguments in the ROM do not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical).

      This impossibility puts on a formal footing the commonly-held belief that succinct arguments in the ROM require non-relativizing techniques. Moreover, our results stand in sharp contrast with other oracle models, for which a recent line of work has constructed relativized succinct non-interactive arguments (SNARGs). Indeed, relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable cryptographic assumptions. Our results rule out this approach for IVC and PCD in the ROM.

   5. SNARK Lower Bounds via Communication Complexity

      Rishabh Bhadauria, Alexander R. Block, Prantar Ghosh, Justin Thaler

      Abstract

      We initiate the study of lower bounding the verification time of Succinct Non-interactive ARguments of Knowledge (SNARKs) built in the Polynomial Interactive Oracle Proof + Polynomial Commitment Scheme paradigm. The verification time of these SNARKs is generally dominated by the polynomial commitment scheme, and so we want to understand if polynomial commitment schemes admit lower bounds on the verification time. By recognizing that polynomial commitment schemes are also often built by applying cryptography to some information-theoretic core protocol, we seek to separate this core from the cryptography in a way that meaningfully captures the verification time required by the polynomial commitment scheme verifier.

      We provide strong evidence that several polynomial commitment schemes have (nearly) optimal verifier times. Our evidence comes from connecting polynomial commitment schemes to certain information-theoretic protocols known as communication protocols from the field of communication complexity, a link which we believe to be of independent interest. Through this lens, we model the verifier work in the cryptographic protocols as information (i.e., number of bits) exchanged between parties in the communication protocols, allowing us to leverage lower bounds from communication complexity. These lower bounds give strong evidence that the verifier time in these polynomial commitment schemes must be at least the number of bits exchanged in the communication protocol.

      We extract the communication protocol cores of three polynomial commitment schemes and lower bound the bits exchanged in these cores. The lower bounds we obtain match (up to poly-logarithmic factors) the best-known (asymptotic) verification times of the polynomial commitment schemes we examine in this work. Specifically, we show that for univariate/multilinear polynomials of size \(N = 2^n\):

      • the communication core of Hyrax PCS (Wahby et al., S&P 2016) requires \(\Omega (\sqrt{N})\) bits to be exchanged;
      • the communication core of Bulletproofs PCS (Bootle et al., EUROCRYPT 2016; Bünz et al., S&P 2018) requires \(\Omega (N)\) bits to be exchanged; and
      • the communication core of Dory PCS (Lee, TCC 2021) requires \(\Omega (\log (N))\) bits to be exchanged.

      Our results strongly suggest a negative answer to a longstanding open question on whether the Bulletproofs verifier can run in sublinear time.

   6. A Fiat–Shamir Transformation from Duplex Sponges

      Alessandro Chiesa, Michele Orrù

      Abstract

      We analyze a variant of the Fiat–Shamir transformation based on an ideal permutation. The transformation relies on the popular duplex sponge paradigm, and minimizes the number of calls to the permutation (given the information to absorb/squeeze). This closely models deployed variants of the Fiat–Shamir transformation, and our analysis provides concrete security bounds to guide security parameters in practice. Our results contribute to the ongoing community-wide effort to achieve rigorous, and ultimately formally verified, security proofs for deployed cryptographic proofs. Along the way, we find that indifferentiability (a property proven for many modes of operation, including the duplex sponge) is ill-suited for establishing the knowledge soundness and zero knowledge of a non-interactive argument.

      We additionally contribute spongefish, an open-source Rust library implementing our Fiat–Shamir transformation. The library is interoperable across multiple cryptographic frameworks, and works with any choice of permutation. The library comes equipped with Keccak and Poseidon permutations, as well as several “codecs” for re-mapping prover and verifier messages to the permutation’s domain.

5. Backmatter