International Association
for Cryptologic Research

Assume that distributions X_0,X_1 (respectively Y_0,Y_1) are d_X (respectively d_Y) indistinguishable for circuits of a given size. It is well known that the product distributions X_0Y_0,X_1Y_1 are d_X+d_Y indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in fact X_0Y_0 and X_1Y_1 are d_x+d_y-d_x*d_y indistinguishable, and also that this bound is tight. We formulate and prove the computational analog of this tight bound. Our proof is entirely different from the proof in the statistical case, which is non-constructive. As a corollary, we show that if X and Y are d indistinguishable, then k independent copies of X and k independent copies of Y are almost 1-(1-d)^k indistinguishable for smaller circuits, as against d*k using the looser bound. Our bounds are useful in settings where only weak (i.e. non-negligible) indistinguishability is guaranteed. We demonstrate this in the context of cryptography, showing that our bounds yield simple analysis for amplification of weak oblivious transfer protocols.

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing succinct arguments. In this work, we study the limitations of IOPs, as well as their relation to those of PCPs. We present a versatile toolbox of IOP-to-IOP transformations containing tools for: (i) length and round reduction; (ii) improving completeness; and (iii) derandomization. We use this toolbox to establish several barriers for IOPs: \begin{itemize} \item Low-error IOPs can be transformed into low-error PCPs. In other words, interaction can be used to construct low-error PCPs; alternatively, low-error IOPs are as hard to construct as low-error PCPs. This relates IOPs to PCPs in the regime of the sliding scale conjecture for inverse-polynomial soundness error. \item Limitations of quasilinear-size IOPs for 3SAT with small soundness error. \item Limitations of IOPs where query complexity is much smaller than round complexity. \item Limitations of binary-alphabet constant-query IOPs. \end{itemize} We believe that our toolbox will prove useful to establish additional barriers beyond our work.

An important theme in the research on attribute-based encryption (ABE) is minimizing the sizes of secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, i.e., the key size is independent of the sizes of policies or attributes and dependent only on the security parameter $\lambda$. - We construct the first key-policy ABE scheme for circuits with constant-size secret keys, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$, which concretely consist of only three group elements. The previous state-of-the-art scheme by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth $d$ of the policy circuits, ${|\mathsf{sk}_f|=\mathrm{poly}(d,\lambda)}$. Our new scheme removes this dependency of key size on $d$ while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, ${|\mathsf{ct}_{\mathbf{x}}|=|\mathbf{x}|\mathrm{poly}(d,\lambda)}$. - We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, namely, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$ and ${|\mathsf{ct}_{\mathbf{x}}|=\mathrm{poly}(|\mathbf{x}|,\lambda)}$. Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non-constant-size keys [Agrawal--Yamada, Eurocrypt '20, Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them. Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18], the constructions become adaptively secure.

Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers? We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called \emph{funcCPA}, that we prove is sufficient. Additionally, we show: - Homomorphic encryption schemes that have a certain type of circuit privacy -- for example, schemes in which ciphertexts can be ``sanitized" -- are funcCPA-secure. - In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure. - For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security -- i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption). Namely, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

We construct adaptively secure multiparty non-interactive key exchange (NIKE) from polynomially-hard indistinguishability obfuscation and other standard assumptions. This improves on all prior such protocols, which required sub-exponential hardness. Along the way, we establish several compilers which simplify the task of constructing new multiparty NIKE protocols, and also establish a close connection with a particular type of constrained PRF.

In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow up in query complexity for each oracle individually, and causes a very mild blow up only. In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure a KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure. Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in oder to deal with adaptivity.

The goal of anonymous whistleblowing is to publicly disclose a message while at the same time hiding the identity of the sender in a way that even if suspected of being the sender, this cannot be proven. While many solutions to this problem have been proposed over the years, they all require some form of interaction with trusted or non-colluding parties. In this work, we ask whether this is fundamentally inherent. We put forth the notion of anonymous transfer as a primitive allowing to solve this problem without relying on any participating trusted parties. We initiate the theoretical study of this question, and derive negative and positive results on the existence of such a protocol. We refute the feasibility of asymptotically secure anonymous transfer, where the message will be received with overwhelming probability while at the same time the identity of the sender remains hidden with overwhelming probability. On the other hand, resorting to fine-grained cryptography, we provide a heuristic instantiation (assuming ideal obfuscation) which guarantees that the message will be correctly received with overwhelming probability and the identity of the sender leaks with vanishing probability. Our results provide strong foundations for the study of the possibility of anonymous communications through authenticated channels, an intriguing goal which we believe to be of fundamental interest.

Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties $t$ is less than a third of the computing parties $n$), and with no setup or cryptographic assumptions. While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\bigO(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting. In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\bigO(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\bigO(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\bigO(n^2\log n)$ bits. As an independent interest, our broadcast is achieved by a \emph{packed verifiable secret sharing}, a new notion that we introduce. We show a protocol that verifies $\bigO(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.

A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set of elements from a universe. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any element not in the set, it might answer `Yes' but with a small (non-negligible) probability. When dealing with such data structures in adversarial settings, we need to define the correctness guarantee and formalize the requirement that bad events happen infrequently and those false positives are appropriately distributed. Recently, several papers investigated this topic, suggesting different robustness definitions. In this work, we try to unify this line of research and propose several robustness notions for Bloom filters that allow the adaptivity of queries. The goal is that a robust Bloom filter should behave like a random biased coin even against an adaptive adversary. The robustness definitions are formalized by the type of test the Bloom filter should withstand. We then explore the relationships between these notions and highlight the notion of Bet-or-Pass as capturing the desired properties of such a data structure.

The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is "uninstantiable," i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense "looks generic." We introduce a standard-model definition called pseudo-generic group (PGG), where we require exponentiations with base an (initially) unknown group generator to result in random-looking group elements. In essence, our framework delicately lifts the influential notion of Universal Computational Extractors of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group. The definition we obtain simultaneously generalizes the Uber assumption family, as group exponents no longer need to be polynomially induced. At the core of our definitional contribution is a new notion of algebraic unpredictability, which reinterprets the standard Schwartz-Zippel lemma as a restriction on sources. We prove the soundness of our definition in the GGM with auxiliary-input (AI-GGM). Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of Uber. We then present a number of applications in settings where exponents are not polynomially induced. In particular we prove that simple variants of ElGamal meet several advanced security goals previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for split sources, which in turn are sufficient in several applications. As corollaries of our AI-GGM feasibility, we obtain the security of all these applications in the presence of preprocessing attacks. Some of our implications utilize a novel type of hash function, which we call linear-dependence destroyers (LDDs) and use to convert standard into algebraic unpredictability. We give an LDD for low-degree sources, and establish their plausibility for all sources by showing, via a compression argument, that random functions meet this definition.

The recent work of Agrawal et al., [Crypto '21] and Goyal et al. [Eurocrypt '22] concurrently introduced the notion of dynamic bounded collusion security for functional encryption (FE) and showed a construction satisfying the notion from identity based encryption (IBE). Agrawal et al., [Crypto '21] further extended it to FE for Turing machines in non-adaptive simulation setting from the sub-exponential learining with errors assumption (LWE). Concurrently, the work of Goyal et al. [Asiacrypt '21] constructed attribute based encryption (ABE) for Turing machines achieving adaptive indistinguishability based security against bounded (static) collusions from IBE, in the random oracle model. In this work, we significantly improve the state of art for dynamic bounded collusion FE and ABE for Turing machines by achieving \emph{adaptive} simulation style security from a broad class of assumptions, in the standard model. In more detail, we obtain the following results: \begin{enumerate} \item We construct an adaptively secure (AD-SIM) FE for Turing machines, supporting dynamic bounded collusion, from sub-exponential LWE. This improves the result of Agrawal et al. which achieved only non-adaptive (NA-SIM) security in the dynamic bounded collusion model. \item Towards achieving the above goal, we construct a \emph{ciphertext policy} FE scheme (CPFE) for circuits of \emph{unbounded} size and depth, which achieves AD-SIM security in the dynamic bounded collusion model from IBE and \emph{laconic oblivious transfer} (LOT). Both IBE and LOT can be instantiated from a large number of mild assumptions such as the computational Diffie-Hellman assumption, the factoring assumption, and polynomial LWE. This improves the construction of Agrawal et al. which could only achieve NA-SIM security for CPFE supporting circuits of unbounded depth from IBE. \item We construct an AD-SIM secure FE for Turing machines, supporting dynamic bounded collusions, from LOT, ABE for NC1 (or NC) and private information retrieval (PIR) schemes which satisfy certain properties. This significantly expands the class of assumptions on which AD-SIM secure FE for Turing machines can be based. In particular, it leads to new constructions of FE for Turing machines including one based on polynomial LWE and one based on the combination of the bilinear decisional Diffie-Hellman assumption and the decisional Diffie-Hellman assumption on some specific groups. In contrast the only prior construction by Agrawal et al. achieved only NA-SIM security and relied on \emph{sub-exponential} LWE. To achieve the above result, we define the notion of CPFE for read only RAM programs and succinct FE for LOT, which may be of independent interest. \item We also construct an \emph{ABE} scheme for Turing machines which achieves AD-IND security in the \emph{standard model} supporting dynamic bounded collusions. Our scheme is based on IBE and LOT. Previously, the only known candidate that achieved AD-IND security from IBE by Goyal et al. relied on the random oracle model. \end{enumerate}

Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is computationally hard to find a claw, i.e., a colliding pair of inputs. TCFs have recently seen a surge of renewed interest due to new applications to quantum cryptography: as an example, TCFs enable a classical machine to verify that some quantum computation has been performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs based on conjectured hard problems on isogeny-based group actions. This is the first candidate construction that is not based on lattice-related problems and the first scheme (from any plausible post-quantum assumption) with a deterministic evaluation algorithm. To demonstrate the usefulness of our construction, we show that our TCF family can be used to devise a computational test of qubit, which is the basic building block used in general verification of quantum computations.

Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under "1 -> 2 attacks": the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion-resistant copy-protection in the plain model. Our results are twofold: * For the first time, we show that all major watermarkable functionalities can be copy-protected (including unclonable decryption, digital signatures, and PRFs). Among these, copy-protection of digital signature schemes is not known before. The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO' 21) * We make all the above schemes k bounded collusion-resistant for any polynomial k, giving the first bounded collusion-resistant copy-protection for various functionalities in the plain model.

We introduce the first proof system for layered arithmetic circuits over an arbitrary ring $R$ that is (possibly) non-commutative and (possibly) infinite, while only requiring black-box access to its arithmetic and a subset $A \subseteq R$. Our construction only requires limited commutativity and regularity properties from $A$, similar to recent work on efficient information theoretic multi-party computation over non-commutative rings by Escudero and Soria-Vazquez (\emph{CRYPTO 2021}), but furthermore covering infinite rings. We achieve our results through a generalization of GKR-style interactive proofs (Goldwasser, Kalai and Rothblum, \emph{Journal of the ACM}, 2015). When $A$ is a subset of the center of $R$, generalizations of the sum-check protocol and other building blocks are not too problematic. The case when the elements of $A$ only commute with each other, on the other hand, introduces a series of challenges. In order to overcome those, we need to introduce a new definition of polynomial ring over a non-commutative ring, the notion of \emph{left} (and \emph{right}) multi-linear extensions, modify the layer consistency equation and adapt the sum-check protocol. Despite these changes, our results are compatible with recent developments such as linear time provers. Moreover, for certain rings our construction achieves provers that run in \emph{sublinear} time in the circuit size. We obtain such result both for known cases, such as matrix and polynomial rings, as well as new ones, such as for some rings resulting from Clifford algebras. Besides efficiency improvements in computation and/or round complexity for several instantiations, the core conclusion of our results is that state of the art doubly efficient interactive proofs do not require much algebraic structure. This enables \emph{exact} rather than \emph{approximate} computation over infinite rings as well as ``agile" proof systems, where the black-box choice of the underlying ring can be easily switched through the software life cycle.

The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $\Sigma$-protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $(2\mu + 1)$-move protocol is, in general, approximately $Q^\mu$, where $Q$ is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $\mu$-fold sequential repetition of $\Sigma$-protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for $(k_1, \ldots, k_\mu)$-special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in $Q$, instead of $Q^\mu$. On the negative side, we show that for $t$-fold \emph{parallel repetitions} of typical $(k_1, \ldots, k_\mu)$-special-sound protocols with $t \geq \mu$ (and assuming for simplicity that $t$ and $Q$ are integer multiples of $\mu$), there is an attack that results in a security loss of approximately~$\frac12 Q^\mu /\mu^{\mu+t}$.

Forward-secure encryption (FSE) allows communicating parties to refresh their keys across epochs, in a way that compromising the current secret key leaves all prior encrypted communication secure. We investigate a novel dimension in the design of FSE schemes: fast-forwarding (FF). This refers to the ability of a stale communication party, that is "stuck" in an old epoch, to efficiently "catch up" to the newest state, and frequently arises in practice. While this dimension was not explicitly considered in prior work, we observe that one can augment prior FSEs -- both in symmetric- and public-key settings -- to support fast-forwarding which is sublinear in the number of epochs. However, the resulting schemes have disadvantages: the symmetric-key scheme is a security parameter slower than any conventional stream cipher, while the public-key scheme inherits the inefficiencies of the HIBE-based forward-secure PKE. To address these inefficiencies, we look at the common real-life situation which we call the bulletin board model, where communicating parties rely on some infrastructure -- such as an application provider -- to help them store and deliver ciphertexts to each other. We then define and construct FF-FSE in the bulletin board model, which addresses the above-mentioned disadvantages. In particular, * Our FF-stream-cipher in the bulletin-board model has: (a) constant state size; (b) constant normal (no fast-forward) operation; and (c) logarithmic fast-forward property. This essentially matches the efficiency of non-fast-forwardable stream ciphers, at the cost of constant communication complexity with the bulletin board per update. * Our public-key FF-FSE avoids HIBE-based techniques by instead using so-called updatable public-key encryption (UPKE), introduced in several recent works (and more efficient than public-key FSEs). Our UPKE-based scheme uses a novel type of "update graph" that we construct in this work. Our graph has constant in-degree, logarithmic diameter, and logarithmic "cut property" which is essential for the efficiency of our schemes. Combined with recent UPKE schemes, we get two FF-FSEs in the bulletin board model, under DDH and LWE.

We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR. The resulting protocol makes black-box use of one-to-one one-way functions.

Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances. In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances. In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically-binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.

The task of achieving full security (with guaranteed output delivery) in secure multiparty computation (MPC) is a long-studied problem with known impossibility results that rule out constructions in the dishonest majority setting. In this work, we investigate the question of constructing fully-secure MPC protocols in the dishonest majority setting with the help of an external trusted party (TP). It is well-known that the existence of such a trusted party is sufficient to bypass the impossibility results. As our goal is to study the minimal requirements needed from this trusted party, we restrict ourselves to the extreme setting where the size of the TP is independent of the size of the functionality to be computed (called "small" TP) and this TP is invoked only once during the protocol execution. We present several positive and negative results for fully-secure MPC in this setting. - For a natural class of protocols, specifically, those with a universal output decoder, we show that the size of the TP must necessarily be exponential in the number of parties. This result holds irrespective of the computational assumptions used in the protocol. This class is broad enough to capture the prior results and indicates that the prior techniques necessitate the use of an exponential-sized TP. We additionally rule out the possibility of achieving information-theoretic full security (without the restriction of using a universal output decoder) using a "small" TP in the plain model (i.e., without any setup). - In order to get around the above negative result, we consider protocols without a universal output decoder. The main positive result in our work is a construction of such a fully-secure MPC protocol assuming the existence of a succinct Functional Encryption scheme. We also give evidence that such an assumption is likely to be necessary for fully-secure MPC in certain restricted settings. - We also explore the possibility of achieving full-security with a semi-honest TP that could collude with the other malicious parties in the protocol (which are in a dishonest majority). In this setting, we show that fairness is impossible to achieve even if we allow the size of the TP to grow with the circuit-size of the function to be computed.

We introduce the idea of input obfuscation for secure two-party computation (io2PC). Sup- pose Alice holds a private value x and wants to allow clients to learn f (x, yi), for their choice of yi, via a secure computation protocol. The goal of io2PC is for Alice to encode x so that an adversary who compromises her storage gets only oracle access to the function f (x, ·). At the same time, there must be a 2PC protocol for computing f (x, y) that takes only this encoding (and not the plaintext x) as input. We show how to achieve io2PC for functions that have virtual black-box (VBB) obfuscation in either the random oracle model or generic group model. For functions that can be VBB- obfuscated in the random oracle model, we provide an io2PC protocol by replacing the random oracle with an oblivious PRF. For functions that can be VBB-obfuscated in the generic group model, we show how Alice can instantiate a “personalized” generic group. A personalized generic group is one where only Alice can perform the algebraic operations of the group, but where she can let others perform operations in that group via an oblivious interactive protocol.

The random oracle methodology is central to the design of many practical cryptosystems. A common challenge faced in several systems is the need to have a random oracle that outputs from a structured distribution D, even though most heuristic implementations such as SHA-3 are best suited for outputting bitstrings. Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We make the following contributions: - We provide a definitional framework for our results. We say that a sampling algorithm Sample() for a distribution is explainable if there exists an algorithm Explain(), where, for a x in the domain, we have that Explain(x) -> r \in {0,1}^n such that Sample(r)=x. Moreover, if x is sampled from D the explained distribution is statistically close to choosing r uniformly at random. We consider a variant of this definition that allows the statistical closeness to be a "precision parameter" given to the Explain() algorithm. We show that sampling algorithms which satisfy our `explainability' property can be programmed as a random oracle. - We provide a simple algorithm for explaining any sampling algorithm that works over distributions with polynomial sized ranges. This includes discrete Gaussians with small standard deviations. - We show how to transform a (not necessarily explainable) sampling algorithm Sample() for a distribution into a new Sample'() that is explainable. The requirements for doing this is that (1) the probability density function is efficiently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density above a given threshold p, showing the equivalence of random oracles to these distributions and random oracles to uniform bitstrings. This includes a large class of distributions, including all discrete Gaussians. - A potential drawback of the previous approach is that the transformation requires an additional computation of the density function. We provide a more customized approach that shows the Miccancio-Walter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.

Side-stepping the protection provided by cryptography, exfiltration attacks are becoming a considerable real-world threat. With the goal of mitigating the exfiltration of cryptographic keys, big-key cryptosystems have been developed over the past few years. These systems come with very large secret keys which are thus hard to exfiltrate. Typically, in such systems, the setup time must be large as it generates the large secret key. However, subsequently, the encryption and decryption operations, that must be performed repeatedly, are required to be efficient. Specifically, the encryption uses only a small public key and the decryption only accesses small ciphertext-dependent parts of the full secret key. Nonetheless, these schemes require decryption to have access to the entire secret key. Thus, using such big-key cryptosystems necessitate that users carry around large secret keys on their devices, which can be a hassle and in some cases might also render exfiltration easy. With the goal of removing this problem, in this work, we initiate the study of big-key identity-based encryption (bk-IBE). In such a system, the master secret key is allowed to be large but we require that the identity-based secret keys are short. This allows users to use the identity-based short keys as the ephemeral secret keys that can be more easily carried around and allow for decrypting ciphertexts matching a particular identity, e.g. messages that were encrypted on a particular date. In particular: -We build a new definitional framework for bk-IBE capturing a range of applications. In the case when the exfiltration is small our definition promises stronger security --- namely, an adversary can break semantic security for only a few identities, proportional to the amount of leakage it gets. In contrast, in the catastrophic case where a large fraction of the master secret key has been ex-filtrated, we can still resort to a guarantee that the ciphertexts generated for a randomly chosen identity (or, an identity with enough entropy) remain protected. We demonstrate how this framework captures the best possible security guarantees. -We show the first construction of such a bk-IBE offering strong security properties. Our construction is based on standard assumptions on groups with bilinear pairings and brings together techniques from seemingly different contexts such as leakage resilient cryptography, reusable two-round MPC, and laconic oblivious transfer. We expect our techniques to be of independent interest.

Motivated by leakage-resilient secure computation of circuits with addition and multiplication gates, this work studies the leakage-resilience of linear secret-sharing schemes with a small reconstruction threshold against any {\em bounded-size} family of joint leakage attacks, \ie, the leakage function can leak {\em global} information from all secret shares. We first prove that, with high probability, the Massey secret-sharing scheme corresponding to a random linear code over a finite field $F$ is leakage-resilient against any $\ell$-bit joint leakage family of size at most $\abs{F}^{k-2.01}/8^\ell $, where $k$ is the reconstruction threshold. Our result (1) bypasses the bottleneck due to the existing Fourier-analytic approach, (2) enables secure multiplication of secrets, and (3) is near-optimal. We use combinatorial and second-moment techniques to prove the result. Next, we show that the Shamir secret-sharing scheme over a prime-order field $F$ with randomly chosen evaluation places and with threshold $k$ is leakage-resilient to any $\ell$-bit joint leakage family of size at most $\abs{F}^{2k-n-2.01}/(k!\cdot 8^\ell)$ with high probability. We prove this result by marrying our proof techniques for the first result with the existing Fourier analytical approach. Moreover, it is unlikely that one can extend this result beyond $k/n\leq0.5$ due to the technical hurdle of the Fourier-analytic approach.

Registration-based encryption (Garg, Hajiabadi, Mahmoody, Rahimi, TCC'18) is a primitive that aims to offer what identity-based encryption offers without the key-escrow problem. In RBE, parties generate their secret keys, a key curator (KC) manages the public keys and updates the compact public parameter, and everyone can use the updated public parameter to securely encrypt messages for individuals. A major downside of RBE is that parties might need to periodically receive extra information from the KC, called decryption updates, that help them decrypt successfully. Current RBE schemes with n registered parties require \Omega(log n) number of updates while the public parameter is of length poly(log n). This leads to the following natural question: are so many decryption updates necessary for RBE schemes? Indeed, it would be desirable to have RBEs with only a constant number of updates. In this paper, we prove almost tight lowerbounds for the number of updates in RBE schemes. More generally, we prove a trade-off between the number of updates in RBEs and the length of the public parameter, as long as the update times are fixed, which is a natural property that holds for all known RBE constructions. In particular, we prove that for any RBE scheme for n \geq \binom{k+d}{d+1} identities and d updates that arrive at fixed times, the public parameter needs to be of length \Omega(k). In particular, our lower bound shows that RBE systems with public parameters of length poly(\log n) require almost logarithmic \Omega(log n / log log n) number of updates.

Attribute-based encryption (ABE) extends public-key encryption to enable fine-grained control to encrypted data. However, this comes at the cost of needing a central trusted authority to issue decryption keys. A multi-authority ABE (MA-ABE) scheme decentralizes ABE and allows anyone to serve as an authority. Existing constructions of MA-ABE only achieve security in the random oracle model. In this work, we develop new techniques for constructing MA-ABE for the class of subset policies (which captures policies such as conjunctions and DNF formulas) whose security can be based in the plain model without random oracles. We achieve this by relying on the recently-proposed "evasive" learning with errors (LWE) assumption by Wee (EUROCRYPT 2022) and Tsabury (CRYPTO 2022). Along the way, we also provide a modular view of the MA-ABE scheme for DNF formulas by Datta et al. (EUROCRYPT 2021) in the random oracle model. We formalize this via a general version of a related-trapdoor LWE assumption by Brakerski and Vaikuntanathan (ITCS 2022), which can in turn be reduced to the plain LWE assumption. As a corollary, we also obtain an MA-ABE scheme for subset policies from plain LWE with a polynomial modulus-to-noise ratio in the random oracle model. This improves upon the Datta et al. construction which relied on LWE with a sub-exponential modulus-to-noise ratio. Moreover, we are optimistic that the generalized related-trapdoor LWE assumption will also be useful for analyzing the security of other lattice-based constructions.

Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and broader functionality. • Stronger Security: In the typical formulation of MIFE security, an attacker is allowed to either corrupt all or none of the users who can encrypt the data. In this work, we study MIFE security in a stronger and more natural model where we allow an attacker to corrupt any subset of the users, instead of only permitting all-or-nothing corruption. We formalize the model by providing each user a unique encryption key, and letting the attacker corrupt all non-trivial subsets of the encryption keys, while still maintaining the MIFE security for ciphertexts generated using honest keys. We construct a secure MIFE system for quadratic functions in this fine-grained corruption model from bilinear maps. Our construction departs significantly from the existing MIFE schemes as we need to tackle a more general class of attackers. • Broader Functionality: The notion of multi-client functional encryption, MCFE, is a useful extension of MIFE. In MCFE, each encryptor can additionally tag each ciphertext with appropriate metadata such that ciphertexts with only matching metadata can be decrypted together. In more detail, each ciphertext is now annotated with a unique label such that ciphertexts encrypted for different slots can now only be combined together during decryption as long as the associated labels are an exact match for all individual ciphertexts. In this work, we upgrade our MIFE scheme to also support ciphertext labelling. While the functionality of our scheme matches that of MCFE for quadratic functions, our security guarantee falls short of the general corruption model studied for MCFE. In our model, all encryptors share a secret key, therefore this yields a secret-key version of quadratic MCFE, which we denote by SK-MCFE. We leave the problem of proving security in the general corruption model as an important open problem.

In $p$-noisy coin-tossing, Alice and Bob obtain fair coins which are of opposite values with probability $p$. Its Oblivious-Transfer (OT) complexity refers to the least number of OTs required by a semi-honest perfectly secure 2-party protocol for this task. We show a tight bound of $\Theta(\log 1/p)$ for the OT complexity of $p$-noisy coin-tossing. This is the first instance of a lower bound for OT complexity that is independent of the input/output length of the function. We obtain our result by providing a general connection between the OT complexity of randomized functions and the complexity of Secure Zero Communication Reductions (SZCR), as recently defined by Narayanan et al. (TCC 2020), and then showing a lower bound for the complexity of an SZCR from noisy coin-tossing to (a predicate corresponding to) OT.

Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space. In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We essentially resolve this question up to polylogarithmic factors. Namely, for every NP relation that can be verified in time T and space S, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\O(T)$ and space $\O(S)$, the verifier runs in time $\O(T/S+S)$ and space $\O(\kappa)$ and the communication is $\O(T/S)$, where $\kappa$ is the statistical security parameter. Using the Fiat-Shamir heuristic, our construction yields the first complexity-preserving ZK-SNARK based on CRH (via a black-box construction). Furthermore, we give evidence that reducing the proof length below $\O(T/S)$ will be hard using existing techniques by arguing the space-complexity of constant-distance error correcting codes.

A multi-party computation protocol is {\em perfectly secure} for some function $f$ if it perfectly emulates an ideal computation of $f$. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC '88] and Chaum et al. [STOC '88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can be corrupted. For two-party sender-receiver functionalities (where only one party receives an output), Ishai et al. [TCC '13] showed that any function can be computed in the correlated randomness model. Unfortunately, they also showed that perfect security cannot be achieved in general for two-party functions that give outputs to both parties (even in the correlated randomness model). We study the feasibility of obtaining perfect security for deterministic symmetric two-party functionalities (i.e., where both parties obtain the same output) in the face of malicious adversaries. We explore both the plain model as well as the correlated randomness model. We provide positive results in the plain model, and negative results in the correlated randomness model. As a corollary, we obtain the following results. \begin{enumerate} \item We provide a characterization of symmetric functionalities with (up to) four possible outputs that can be computed with perfect security. The characterization is further refined when restricted to three possible outputs and to Boolean functions. All characterizations are the same for both the plain model and the correlated randomness model. \item We show that if a functionality contains an embedded XOR or an embedded AND, then it cannot be computed with perfect security (even in the correlated randomness model). \end{enumerate}

Secret-sharing is one of the most fundamental primitives in cryptography, and has found several applications. All known constructions of secret sharing (with the exception of those with a pathological choice of parameters) require access to uniform randomness. However, in practice it is extremely challenging to generate a source of uniform randomness. This has led to a large body of research devoted to designing randomized algorithms and cryptographic primitives from imperfect sources of randomness. Motivated by this, Bosley and Dodis (TCC 2007) asked whether it is even possible to construct a $2$-out-of-$2$ secret sharing scheme without access to uniform randomness. In this work, we make significant progress towards answering this question. Namely, we resolve this question for secret sharing schemes with important additional properties: $1$-bit leakage-resilience and non-malleability. We prove that, for not too small secrets, it is impossible to construct any $2$-out-of-$2$ leakage-resilient or non-malleable secret sharing scheme without access to uniform randomness. Given that the problem of whether $2$-out-of-$2$ secret sharing requires uniform randomness has been open for more than a decade, it is reasonable to consider intermediate problems towards resolving the open question. In a spirit similar to NP-completeness, we also study how the existence of a $t$-out-of-$n$ secret sharing without access to uniform randomness is related to the existence of a $t'$-out-of-$n'$ secret sharing without access to uniform randomness for a different choice of the parameters $t,n,t',n'$.

Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, {\em algebraic} constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known. In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize. Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.

An $\ell$-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among $\ell$ servers while hiding the identity of the item. It is called $b$-error-correcting if a client can correctly compute the data item even in the presence of $b$ malicious servers. It is known that $b$-error correction is possible if and only if $\ell>2b$. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-2b)$-server PIR as a function of the database size $n$. Secondly, we formalize a relaxed notion of statistical $b$-error-correcting PIR, which allows non-zero failure probability. We show that as a function of $n$, the minimum communication cost of statistical $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-b)$-server one, which is at most that of $(\ell-2b)$-server one. Our main technical contribution is a generic construction of statistical $b$-error-correcting $\ell$-server PIR for any $\ell>2b$ from regular $(\ell-b)$-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any $\ell>2b$.

Continuous Group Key Agreement (CGKA) is the basis of modern Secure Group Messaging (SGM) protocols. At a high level, a CGKA protocol enables a group of users to continuously compute a shared (evolving) secret while members of the group add new members, remove other existing members, and perform state updates. The state updates allow CGKA to offer desirable security features such as forward secrecy and post-compromise security. CGKA is regarded as a practical primitive in the real-world. Indeed, there is an IETF Messaging Layer Security (MLS) working group devoted to developing a standard for SGM protocols, including the CGKA protocol at their core. Though known CGKA protocols seem to perform relatively well when considering natural sequences of performed group operations, there are no formal guarantees on their efficiency, other than the O(n) bound which can be achieved by trivial protocols, where n is the number of group numbers. In this context, we ask the following questions and provide negative answers. 1. Can we have CGKA protocols that are efficient in the worst case? We start by answering this basic question in the negative. First, we show that a natural primitive that we call Compact Key Exchange (CKE) is at the core of CGKA, and thus tightly captures CGKA’s worst-case communication cost. Intuitively, CKE requires that: first, n users non-interactively generate key pairs and broadcast their public keys, then, some other special user securely communicates to these n users a shared key. Next, we show that CKE with communication cost o(n) by the special user cannot be realized in a black-box manner from public-key encryption and one-way functions, thus implying the same for CGKA, where n is the corresponding number of group members. 2. Can we realize one CGKA protocol that works as well as possible in all cases? Here again, we present negative evidence showing that no such protocol based on black-box use of public-key encryption and one-way functions exists. Specifically, we show two distributions over sequences of group operations such that no CGKA protocol obtains optimal communication costs on both sequences.

One-time programs, originally formulated by Goldwasser et al.~\cite{goldwasser2008one}, are a powerful cryptographic primitive with compelling applications. Known solutions for one-time programs, however, require specialized secure hardware that is not widely available (or, alternatively, access to blockchains and very strong cryptographic tools). In this work we investigate the possibility of realizing one-time programs from a recent and now more commonly available hardware functionality: the {\em counter lockbox}. A counter lockbox is a stateful functionality that protects an encryption key under a user-specified password, and enforces a limited number of incorrect guesses. Counter lockboxes have become widely available in consumer devices and cloud platforms. We show that counter lockboxes can be used to realize one-time programs for general functionalities. We develop a number of techniques to reduce the number of counter lockboxes required for our constructions, that may be of independent interest.

We present the first non-interactive delegation scheme for P with time-tight parallel prover efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation scheme—which we refer to as a SPARG (succinct parallelizable argument)—the prover’s parallel running time is t + polylog(t), while using only polylog(t) processors and where t is the length of the computation. (In other words, the proof is computed essentially in parallel with the computation, with only some minimal additive overhead in terms of time). Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent delegation construction of Choudhuri, Jain, and Jin (FOCS’21) and combines it with techniques from Ephraim et al (EuroCrypt’20). We next demonstrate how to make our SPARG time-independent—where the prover and verifier do not need to known the running-time t in advance; as far as we know, this yields the first construction of a time-tight delegation scheme with time-independence based on any hardness assumption. We finally present applications of SPARGs to the constructions of VDFs (Boneh et al, Crypto’18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard function).

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates —possibly very widely— over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt ’21]. In this work, we present the first proof-of-work (PoW)-based permissionless clock synchro- nization protocol. Our construction relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.

Onion routing is a popular approach towards anonymous communication. Practical implementations are widely used (for example, Tor has millions of users daily), but are vulnerable to various traffic correlation attacks, and the theoretical foundations, despite recent progress, still lag behind. In particular, all works that model onion routing protocols and prove their security only address a single run, where each party sends and receives a single message of fixed length, once. Moreover, they all assume a static network setting, where the parties are stable throughout the lifetime of the protocol. In contrast, real networks have a high rate of churn (nodes joining and exiting the network), real users want to send multiple messages, and realistic adversaries may observe multiple runs of the protocol. We initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide definitions of both security and anonymity in this setting, and constructions that satisfy them. In particular, we define a new cryptographic primitive called \emph{Poly Onions} and show that it can be used to realize our definitions.

We show that for many fundamental cryptographic primitives, proving classical security under the learning-with-errors (LWE) assumption, does \emph{not} imply post-quantum security. This is despite the fact that LWE is widely believed to be post-quantum secure, and our work does not give any evidence otherwise. Instead, it shows that post-quantum insecurity can arise inside cryptographic constructions, even if the assumptions are post-quantum secure. Concretely, our work provides (contrived) constructions of pseudorandom functions, CPA-secure symmetric-key encryption, message-authentication codes, signatures, and CCA-secure public-key encryption schemes, all of which are proven to be classically secure under LWE via black-box reductions, but demonstrably fail to be post-quantum secure. All of these cryptosystems are stateless and non-interactive, but their security is defined via an interactive game that allows the attacker to make oracle queries to the cryptosystem. The polynomial-time quantum attacker can break these schemes by only making a few \emph{classical} queries to the cryptosystem, and in some cases, a single query suffices. Previously, we only had examples of post-quantum insecurity under post-quantum assumptions for stateful/interactive protocols. Moreover, there appears to be a folklore belief that for stateless/non-interactive cryptosystems with black-box proofs of security, a quantum attack against the scheme should translate into a quantum attack on the assumption. This work shows otherwise. Our main technique is to carefully embed interactive protocols inside the interactive security games of the above primitives. As a result of independent interest, we also show a 3-round \emph{quantum disclosure of secrets (QDS)} protocol between a classical sender and a receiver, where a quantum receiver learns a secret message in the third round but, assuming LWE, a classical receiver does not.

One of the most fundamental results in game theory is that every game has a Nash equilibrium, an assignment of (randomized) strategies to players with the stability property that no individual player can benefit from deviating from the assigned strategy. It is not known how to efficiently *compute* such a Nash equilibrium --- the computational complexity of this task is characterized by the class PPAD, but the relation of PPAD to other problems and well-known complexity classes is not precisely understood. In recent years there has been mounting evidence, based on cryptographic tools and techniques, showing the hardness of PPAD. We continue this line of research by showing that PPAD is as hard as *learning with errors* and the *iterated squaring* problem, two standard problems in cryptography. Our work improves over prior hardness results that relied either on (1) sub-exponential assumptions, or (2) relied on ``obfustopia,'' which can currently be based on a particular combination of three assumptions. Our work additionally establishes *public-coin* hardness for PPAD (computational hardness for a publicly sampleable distribution of instances) that seems out of reach of the obfustopia approach. Following the work of Choudhuri et al. (STOC 2019) and subsequent works, our hardness result is obtained by constructing an *unambiguous and incrementally-updateable* succinct non-interactive argument for IS, whose soundness relies on polynomial hardness of LWE. The result also implies a verifiable delay function with unique proofs, which may be of independent interest.

Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions and applications of pseudorandom states, and present the following contributions: - We study variants of pseudorandom \emph{function-like} state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show feasibility of these variants assuming the existence of post-quantum one-way functions. - We show that PRS generators with logarithmic output length imply commitment and encryption schemes with \emph{classical communication}. Previous constructions of such schemes from PRS generators required quantum communication. - We give a simpler proof of the Brakerski--Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states. - We also show that logarithmic output length is a sharp threshold where PRS generators start requiring computational assumptions.

The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.

We investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols, including those based on the recursive folding technique of Bulletproofs. To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.

We study the notion of {\em Random-index ORAM} (RORAM), which is a weak form of ORAM where the Client is limited to asking for random elements of the $N$-items memory rather than specific ones (and, possibly, modify them). That is, whenever the client issues a request, it gets in return a pair $(r,x_r)$ where $r\in_R[N]$ is a random index and $x_r$ is the content of the $r$-th memory item. Then, the client can also modify the content to some new value $x'_r$. We first argue that for certain applications the limited functionality of RORAM still suffices. These include various applications of sampling (or sub-sampling), and in particular the very-large-scale MPC application in the setting of~ Benhamouda et al. \cite{BGG+20}. Clearly, RORAM can be implemented using any ORAM scheme (by the Client selecting the random $r$'s by himself), but the hope is that the limited functionality of RORAM can make it faster and easier to implement than ORAM. Indeed, our main contributions are several RORAM schemes (both of the hierarchical-type and the tree-type) of lighter complexity than that of ORAM.

Incompressible encryption, recently proposed by Guan, Wichs and Zhandry (EUROCRYPT'22), is a novel encryption paradigm geared towards providing strong long-term security guarantees against adversaries with \emph{bounded long-term memory}. Given that the adversary forgets just a small fraction of a ciphertext, this notion provides strong security for the message encrypted therein, even if at some point in the future the entire secret key is exposed. This comes at the price of having potentially very large ciphertexts. Thus, an important efficiency measure for incompressible encryption is the message-to-ciphertext ratio (also called the rate). Guan et al. provided a low-rate instantiation of this notion from standard assumptions, and a rate-1 instantiation from indistinguishability obfuscation (iO). In this work, we propose a simple framework to build rate-1 incompressible encryption from standard assumptions. Our construction can be realized from e.g. the DDH and additionally the DCR or the LWE assumptions.

We give round-optimal {\em black-box} constructions of two-party and multiparty protocols in the common random/reference string (CRS) model, with security against malicious adversaries, based on any two-round oblivious transfer (OT) protocol in the same model. Specifically, we obtain two types of results. \smallskip \begin{enumerate} \item {\bf Two-party protocol.} We give a (two-round) {\it two-sided NISC} protocol that makes black-box use of two-round (malicious-secure) OT in the CRS model. In contrast to the standard setting of non-interactive secure computation (NISC), two-sided NISC allows communication from both parties in each round and delivers the output to both parties at the end of the protocol. Prior black-box constructions of two-sided NISC relied on idealized setup assumptions such as OT correlations, or were proven secure in the random oracle model. \item {\bf Multiparty protocol.} We give a three-round secure multiparty computation protocol for an arbitrary number of parties making black-box use of a two-round OT in the CRS model. The round optimality of this construction follows from a black-box impossibility proof of Applebaum et al. (ITCS 2020). Prior constructions either required the use of random oracles, or were based on two-round malicious-secure OT protocols that satisfied additional security properties. \end{enumerate}

We study the round complexity of secure multiparty computation (MPC) in the challenging model where full security, including guaranteed output delivery, should be achieved at the presence of an active rushing adversary who corrupts up to half of parties. It is known that 2 rounds are insufficient in this model (Gennaro et al., Crypto 2002), and that 3 round protocols can achieve computational security under public-key assumptions (Gordon et al., Crypto 2015; Ananth et al., Crypto 2018; and Badrinarayanan et al., Asiacrypt 2020). However, despite much effort, it is unknown whether public-key assumptions are inherently needed for such protocols, and whether one can achieve similar results with security against computationally-unbounded adversaries. In this paper, we use Minicrypt-type assumptions to realize 3-round MPC with full and active security. Our protocols come in two flavors: for a small (logarithmic) number of parties $n$, we achieve an optimal resiliency threshold of $t\leq \lfloor (n-1)/2\rfloor$, and for a large (polynomial) number of parties we achieve an almost-optimal resiliency threshold of $t\leq 0.5n(1-\epsilon)$ for an arbitrarily small constant $\epsilon > 0$. Both protocols can be based on sub-exponentially hard injective one-way functions in the plain model. If the parties have an access to a collision resistance hash function, we can derive \emph{statistical everlasting security} for every NC1 functionality, i.e., the protocol is secure against adversaries that are computationally bounded during the execution of the protocol and become computationally unlimited after the protocol execution. As a secondary contribution, we show that in the strong honest-majority setting ($t<n/3$), every NC1 functionality can be computed in 3 rounds with everlasting security and complexity polynomial in $n$ based on one-way functions. Previously, such a result was only known based on collision-resistance hash function.

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks. Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known to exist thus far only over a set of finite fields of negligible density, namely, over ``FFT-friendly'' fields that contain a sub-group of size $2^\rounds$. Our main result is to show that scalable IOPs can be constructed over \emph{any} sufficiently large finite field, of size that is at least quadratic in the length of computation whose integrity is proved by the IOP. This result has practical applications as well, because it reduces the proving and verification complexity of cryptographic statements that are naturally stated over pre-defined finite fields which are not ``FFT-friendly''. Prior state-of-the-art scalable IOPs relied heavily on arithmetization via univariate polynomials and Reed--Solomon codes over FFT-friendly fields. To prove our main result and extend scalability to all large finite fields, we generalize the prior techniques and use new algebraic geometry codes evaluated on sub-groups of elliptic curves (elliptic curve codes). We also show a new arithmetization scheme that uses the rich and well-understood group structure of elliptic curves to reduce statements of computational integrity to other statements about the proximity of functions evaluated on the elliptic curve to the new family of elliptic curve codes.

The recently proposed YOSO model is a groundbreaking approach to MPC, executable on a public blockchain, circumventing adaptive player corruption by hiding the corruption targets until they are worthless. Players are selected unpredictably from a large pool to perform MPC sub-tasks, in which each selected player sends a single message (and reveals their identity). While YOSO MPC has attractive asymptotic complexity, unfortunately, it is concretely prohibitively expensive due to the cost of its building blocks. We propose a modification to the YOSO model that preserves resilience to adaptive server corruption, but allows for much more efficient protocols. In SCALES (Small Clients And Larger Ephemeral Servers) only the servers facilitating the MPC computation are ephemeral (unpredictably selected and ``speak once''). Input providers (clients) publish problem instance and collect the output, but do not otherwise participate in computation. SCALES offers attractive features, and improves over YOSO in outsourcing MPC to a large pool of servers under adaptive corruption. We build SCALES from rerandomizable garbling schemes, which is a contribution of independent interest, with additional applications.

Secure Non-Interactive Reductions (SNIR) is a recently introduced, but fundamental cryp- tographic primitive. The basic question about SNIRs is how to determine if there is a SNIR from one 2-party correlation to another. While prior work provided answers for several pairs of correlations, the possibility that this is an undecidable problem in general was left open. In this work we show that the existence of a SNIR between any pair of correlations can be determined by an algorithm. At a high-level, our proof follows the blueprint of a similar (but restricted) result by Khorasgani et al. But combining the spectral analysis of SNIRs by Agrawal et al. (Eurocrypt 2022) with a new variant of a “junta theorem” by Kindler and Safra, we obtain a complete resolution of the decidability question for SNIRs. The new junta theorem that we identify and prove may be of independent interest.

{\em Secure non-interactive simulation} (SNIS), introduced in {EUROCRYPT} 2022, is the information-theoretic analog of {\em pseudo-correlation generators}. SNIS allows parties, starting with samples of a source correlated private randomness, to non-interactively and securely transform them into samples from a different correlated private randomness. Determining the feasibility, rate, and capacity of SNIS is natural and essential for the efficiency of secure computation. This work initiates the study of SNIS, where the target distribution $(U,V)$ is a random sample from the {\em binary symmetric or erasure channels}; however, the source distribution can be arbitrary. In this context, our work presents: \begin{enumerate} \item The characterization of all sources that facilitate such SNIS, \item An upper and lower bound on their maximum achievable rate, and \item Exemplar SNIS instances where non-linear reductions achieve optimal efficiency; however, any linear reduction is insecure. \end{enumerate} These results collectively yield the fascinating instances of {\em computer-assisted search} for secure computation protocols that identify ingenious protocols that are more efficient than all known constructions. Our work generalizes the algebraization of the simulation-based definition of SNIS as an approximate eigenvector problem. The following foundational and general technical contributions of ours are the underpinnings of the results mentioned above. \begin{enumerate} \item Characterization of Markov and adjoint Markov operators' effect on the Fourier spectrum of reduction functions. \item A new concentration phenomenon in the Fourier spectrum of reduction functions. \item A powerful statistical-to-perfect lemma with broad consequences for feasibility and rate characterization of SNIS. \end{enumerate} Our technical analysis relies on Fourier analysis over large alphabets with arbitrary measure, the orthogonal Efron-Stein decomposition, and junta theorems of Kindler-Safra and Friedgut. Our work establishes a fascinating connection between the rate of SNIS and the maximal correlation, a prominent information-theoretic property. Our technical approach motivates the new problem of ``security-preserving dimension reduction'' in harmonic analysis, which may be of independent and broader interest.

Random sampling from specified distributions is an important tool with wide applications for analysis of large-scale data. In this paper we study how to randomly sample when the distribution is partitioned among two parties' private inputs. Of course, a trivial solution is to have one party send a (possibly encrypted) description of its weights to the other party who can then sample over the entire distribution (possibly using homomorphic encryption). However, this approach requires communication that is linear in the input size which is prohibitively expensive in many settings. In this paper, we investigate secure 2-party sampling with sublinear communication for many standard distributions. We develop protocols for L_1, and L_2 sampling. Additionally, we investigate the feasibility of sublinear product sampling, showing impossibility for the general problem and showing a protocol for a restricted case of the problem. We additionally show how such product sampling can be used to instantiate a sublinear communication 2-party exponential mechanism for differentially-private data release.

We present a new framework for building round-optimal one-sided statistically secure two party computation (2PC) protocols in the plain model. We demonstrate that a relatively weak notion of oblivious transfer (OT), namely a three round elementary oblivious transfer (EOT) with statistical receiver privacy, along with a non-interactive commitment scheme suffices to build a one-sided statistically secure two party computation protocol with black-box simulation. Our framework enables the first instantiations of round-optimal one-sided statistically secure 2PC protocols from the CDH assumption and certain families of isogeny-based assumptions. As part of our compiler, we introduce the following new one-sided statistically secure primitives in the pre-processing model that might also be of independent interest: 1. Three round statistically sender private random-OT where only the last OT message depends on the receiver's choice bit and the sender receives random outputs generated by the protocol. 2. Four round delayed-input statistically sender private conditional disclosure of secrets where the first two rounds of the protocol are independent of the inputs of the parties. The above primitives are directly constructed from EOT and hence we obtain their instantiations from the same set of assumptions as our 2PC.

We revisit the well-studied problem of preventing steganographic communication in multi-party communications. While this is known to be a provably impossible task, we propose a new model that allows circumventing this impossibility. In our model, the parties first publish a single message during an honest \emph{non-interactive} pre-processing phase and then later interact in an execution phase. We show that in this model, it is indeed possible to prevent any steganographic communication in zero-knowledge protocols. Our solutions rely on standard cryptographic assumptions.

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size. We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings: 1) Circuit size. We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular ``decomposability'' property. In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility: from Quadratic Residuosity (QR) together with polynomial-noise-rate Learning Parity with Noise (LPN). Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing. 2) Input size. We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size n. Previous constructions from CDH required communication Omega(n). In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $O(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity --- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. Specifically, (1) we show that a line graph of size $N$ has reversible space-time complexity at most $O(N^{1+\frac{2}{\sqrt{\log N}}})$. (2) We show that any $(e,d)$-reducible DAG has reversible space-time complexity at most $O(Ne+dN2^d)$. In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most $O(N^2 \log \log N/\sqrt{\log N})$ and $O(N^2/\sqrt[3]{\log N})$, respectively. (3) We show that the reversible space-time complexity of DRSample is at most $O(N^2 \log \log N/\log N)$. We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs.

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions. In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.

We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a ``realistic model of computation is". In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable. Our notion of \emph{universal reductions} models attackers as PPT algorithms having access to some arbitrary unbounded \emph{stateful} Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of \emph{universal reductions w.r.t. time-evolving, $k$-window, Natures} that makes restrictions on Nature---roughly speaking, Nature's behavior may depend on number of messages it has received and the content of the last $k(\sec)$-messages (but not on ``older'' messages). We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.

Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable security in the general universal composition model (GUC model) of Canetti et al. is the best guarantee that nothing will go wrong when a system is part of a larger whole, even when all parties share a common random oracle. In this paper, we prove the minimal necessary properties of generally universally composable (GUC) NIZKPoK in any global random-oracle model, and show how to achieve efficient and GUC NIZKPoK in both the restricted programmable and restricted observable (non-programmable) global random-oracle models.

Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) presents an ``alternative'' to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing $\Sigma$-protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of ``plug \& play'' algorithmics. Unfortunately, their techniques are restricted to arithmetic circuits over \emph{prime} fields, which rules out the possibility of using more machine-friendly moduli such as powers of $2$, which have proven to improve efficiency in applications. In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo \emph{any} number. This enables the use of powers of $2$, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications. In order to achieve this, we first present an instantiation of the main building block of the theory of compressed $\Sigma$-protocols, namely compact vector commitments. Our construction, which may be of independent interest, is homomorphic modulo \emph{any} positive integer $m$, a result that was not known in the literature before. Second, we generalize Compressed $\Sigma$-Protocol Theory from finite fields to $\mathbb{Z}_m$. The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions. Our techniques have direct application for example to verifiable computation on homomorphically encrypted data.

A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate P is exactly n. We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message. Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.