International Association
for Cryptologic Research

Commitments are fundamental in cryptography. In the classical world, commitments are equivalent to the existence of one-way functions. It is also known that the most desired form of commitments in terms of their round complexity, i.e., non-interactive commitments, cannot be built from one-way functions in a black-box way [Mahmoody-Pass, Crypto’12]. However, if one allows the parties to use quantum computation and communication, it is known that non-interactive commitments (to classical bits) are in fact possible [Koshiba-Odaira, Arxiv’11 and Bitansky-Brakerski, TCC’21]. We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation and classical communication based on a black-box use of one-way functions. We prove that doing so is impossible, unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto’22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC’21], as they only required a classical decommitment message. Because non-interactive commitments can be based injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science’21] in which they only allowed the security reduction to be quantum. At a technical level, prove that sampling oracles at random from “sufficiently large” sets (of oracles) will make them one-way against polynomial-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al. [Asiacrypt’19] and Chung et al. [FOCS’20].

In 1974, Merkle showed that an ideal hash function (modeled as a random oracle) can be used between two parties to agree on a key that remains \emph{mildly} secure against adversaries whose running time is quadratic in those of honest parties. Shortly after, Diffie and Hellman improved this idea to a full-fledged key exchange protocol that is conjectured to be secure against super-polynomial adversaries. Both of these protocols have a crucial aspect in common: they are \emph{non-interactive}, as parties send their single message in parallel, and then they use their secret randomness and the public messages to derive the common key. Constructing $K$-NIKE protocols on well-founded assumptions turned out to be much challenging for $K>2$. For $K=3$ one can do this based on pairing-based assumptions, and for $K>3$ even stronger assumptions such as indistinguishability obfuscations have been used. In this work, we initiate a study of $K$-NIKE protocols in the \emph{fine-grained} setting, in which there is a \emph{polynomial} gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of $K$-NIKE protocols for $K \geq 3$. Our contribution is threefold. 1. We show that random oracles can be used to obtain fine-grained $K$-NIKE protocols for \emph{every} constant $K$. In particular, we show how to generalize Merkle's two-party protocol to $K$ parties in such a way that the honest parties ask $n$ queries each, while the adversary needs $n^{K/(K-1)}$ queries to the random oracle to find the key. 2. We then improve the security by further using algebraic structure, while avoiding pairing. In particular, we show that there is a 4-party NIKE in Shoup's generic group model with a \emph{quadratic} gap between the number of queries by the honest parties vs. that of the adversary. 3. Finally, we show a limitation of using purely algebraic methods for obtaining $3$-NIKE. In particular, we show that any $n$-query $3$-NIKE protocol in Maurer's generic group model can be broken by a $O(n^2)$-query attacker. Maurer's GGM is more limited compared with Shoup's both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break $3$-NIKE protocols in Maurer's model with \emph{any} polynomial number of queries. Our work leaves open to understand the optimality of our $K$-NIKE protocol in the random oracle model, which we conjecture to be optimal, and also to close the gap between our positive result in Shoup's model and the negative result in Maurer's model.

Time-lock puzzles wrap a solution s inside a puzzle P in such a way that “solving” P to find s requires significantly more time than generating the pair (s, P), even if the adversary has access to parallel computing; hence it can be thought of as sending a message s to the future. It is known [Mahmoody, Moran, Vadhan, Crypto’11] that when the source of hardness is only a random oracle, then any puzzle generator with n queries can be (efficiently) broken by an adversary in O(n) rounds of queries to the oracle. In this work, we revisit time-lock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum-powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of time-lock puzzles solely from quantum (accessible) random oracles. In particular, for any n-query classical puzzle generator, our attack only asks O(n) (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing. Assuming perfect completeness, we also show how to make the above attack run in exactly n rounds while asking a total of m · n queries where m is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask n−1 rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from O(mn log n) to mn. Finally, assuming perfect completeness, we present an attack in the “dual” setting in which the puzzle generator is quantum while the solver is classical. We then ask whether one can extend our classical-query attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv’2009] is false, then there is indeed a time-lock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto’22] about key agreements (that can have interactions in both directions) to time-lock puzzles (that only include unidirectional communication).

Registration-based encryption (RBE) is a primitive that aims to offer what identity-based encryption (IBE) offers without the so-called key-escrow problem. In RBE parties who wish to join the system will generate their own secret and public keys and register their public keys to a transparent party called key curator (KC) who does not have any secret state. The initial constructions of RBE made \emph{non-black-box} use of building block primitives, due to their use of either indistinguishability obfuscation or some garbling scheme. More recently, it was shown how to achieve \emph{black-box} constructions of (variants of) RBE and even stronger primitives based on \emph{bilinear maps} in which the RBE is relaxed to have a CRS whose length can \emph{grow} with the number of registered identities. Making cryptographic constructions in general, and RBE in particular, black-box is an important step as it can play a significant role in its efficiency and potential deployment. Hence, in this work we ask: \emph{what are the minimal assumptions for black-box constructions of RBE?} Particularly, can we black-box construct RBE schemes from the same assumptions used for public-key encryption or simpler algebraic assumptions that hold in the generic group model? In this work, we prove the first black-box separation results for RBE beyond the separations that follow from the observation that RBE black-box implies public-key encryption. In particular, we answer both of the questions above negatively and prove that neither trapdoor permutations nor (even Shoup's) generic group model can be used as the sole source of hardness for building RBE schemes. More generally, we prove that a relaxation of RBE in which all the keys are registered and compressed at the same time is already too complex to be built from either of the above-mentioned primitives in a black-box way. At a technical level, using compression techniques, we prove lemmas in the TDP and GGM oracle settings that prove the following intuitive yet useful fact: that compact strings cannot signal too many trapdoors, even if their generation algorithm takes exponential time. Due to their generality, our lemmas could be of independent interest and find more applications.

We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties A, B with local quantum computing power rely (only) on a random oracle and classical communication to agree on a key? (Note that A, B can now query the random oracle at quantum superpositions.) We make the first progress on the question above and prove the following. – When only one of the parties A is classical and the other party B is quantum powered, as long as they ask a total of d oracle queries and agree on a key with probability 1, then there is always a way to break the key agreement by asking O(d^2) number of classical oracle queries. – When both parties can make quantum queries to the random oracle, we introduce a natural conjecture, which if true would imply attacks with poly(d) classical queries to the random oracle. Our conjecture, roughly speaking, states that the multiplication of any two degree-d real-valued polynomials over the Boolean hypercube of influence at most δ = 1/ poly(d) is nonzero. We then prove our conjecture for exponentially small influences, which leads to an (unconditional) classical 2^O(md)-query attack on any such key agreement protocol, where m is the random oracle’s output length. – Since our attacks are classical, we then ask whether it is possible to find such classical attacks in general. We prove a barrier for this approach, by showing that if the folklore “simulation conjecture” about the possibility of simulating efficient-query quantum algorithms classically is false, then that implies a possible quantum protocol that cannot be broken by classical adversaries.

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.

Consider a coin tossing protocol in which n processors P_1,...,P_n agree on a random bit b in n rounds, where in round i P_i sends a single message w_i. Imagine a full-information adversary who prefers the output 1, and in every round i it knows all the finalized messages w_1,...,w_{i-1} so far as well as the prepared message w_i. A k-replacing attack will have a chance to replace the prepared w_i with its own choice w'_i \neq w_i in up to k rounds. Taking majority protocol over uniformly random bits w_i = b_i is robust in the following strong sense. Any k-replacing adversary can only increase the probability of outputting 1 by at most O(k/\sqrt{n}). In this work, we ask if the above simple protocol is tight. For the same setting, but restricted to uniformly random bit messages, Lichtenstein, Linial, and Saks [Combinatorica'89] showed how to achieve bias \Omega(k/\sqrt{n}) for any k \in [n]. Kalai, Komargodski, and Raz [DISC'18, Combinatorica'21] gave an alternative polynomial-time attack when k \geq \Theta(\sqrt{n}). Etesami, Mahloujifar, and Mahmoody [ALT'19, SODA'20] extended the result of KKR18 to arbitrary long messages. In this work, we resolve both of these problems. - For arbitrary length messages, we show that k-replacing polynomial-time attacks can indeed increase the probability of outputting 1 by \Omega(k/\sqrt{n}) for any k, which is optimal up to a constant factor. By plugging in our attack into the framework of Mahloujifar Mahmoody [TCC'17] we obtain similar data poisoning attacks against deterministic learners when adversary is limited to changing k=o(\sqrt{n}) of the n training examples. - For uniformly random bits b_1,...,b_n, we show that whenever Pr[b=1]=Pr[\sum b_i \geq t]=\beta[t]_n for t \in [n] is the probability of a Hamming ball, then online polynomial-time k-replacing attacks can increase Pr[b=1] from \beta[t]_n to \beta[t-k]_n , which is optimal due to the majority protocol. In comparison, the (information-theoretic) attack of LLS89 increased Pr[b=1] to \beta[t-k]_{n-k}, which is optimal for adaptive adversaries who cannot see the message before changing it. Thus, we obtain a computational variant of Harper's celebrated vertex isoperimetric inequality.

The notion of Registration-Based Encryption (RBE) was recently introduced by Garg, Hajiabadi, Mahmoody, and Rahimi [TCC’18] with the goal of removing the private-key generator (PKG) from IBE. Specifically, RBE allows encrypting to identities using a (compact) master public key, like how IBE is used, with the benefit that the PKG is substituted with a weaker entity called “key curator” who has no knowledge of any secret keys. Here individuals generate their secret keys on their own and then publicly register their identities and their corresponding public keys to the key curator. Finally, individuals obtain “rare” decryption-key updates from the key curator as the population grows. In their work, they gave a construction of RBE schemes based on the combination of indistinguishability obfuscation and somewhere statistically binding hash functions. However, they left open the problem of constructing RBE schemes based on standard assumptions.In this work, we resolve the above problem and construct RBE schemes based on standard assumptions (e.g., CDH or LWE). Furthermore, we show a new application of RBE in a novel context. In particular, we show that anonymous variants of RBE (which we also construct under standard assumptions) can be used for realizing abstracts forms of anonymous messaging tasks in simple scenarios in which the parties communicate by writing messages on a shared board in a synchronized way.

Understanding whether public-key encryption can be based on one-way functions is a fundamental open problem in cryptography. The seminal work of Impagliazzo and Rudich [STOC’89] shows that black-box constructions of public-key encryption from one-way functions are impossible. However, this impossibility result leaves open the possibility of using non-black-box techniques for achieving this goal.One of the most powerful classes of non-black-box techniques, which can be based on one-way functions (OWFs) alone, is Yao’s garbled circuit technique [FOCS’86]. As for the non-black-box power of this technique, the recent work of Döttling and Garg [CRYPTO’17] shows that the use of garbling allows us to circumvent known black-box barriers in the context of identity-based encryption.We prove that garbling of circuits that have OWF (or even random oracle) gates in them are insufficient for obtaining public-key encryption. Additionally, we show that this model also captures (non-interactive) zero-knowledge proofs for relations with OWF gates. This indicates that currently known OWF-based non-black-box techniques are perhaps insufficient for realizing public-key encryption.

We show that any OT extension protocol based on one-way functions (or more generally any symmetric-key primitive) either requires an additional round compared to the base OTs or must make a non-black-box use of one-way functions. This result also holds in the semi-honest setting or in the case of certain setup models such as the common random string model. This implies that OT extension in any secure computation protocol must come at the price of an additional round of communication or the non-black-box use of symmetric key primitives. Moreover, we observe that our result is tight in the sense that positive results can indeed be obtained using non-black-box techniques or at the cost of one additional round of communication.

In this work, we introduce the notion of registration-based encryption (RBE for short) with the goal of removing the trust parties need to place in the private-key generator in an IBE scheme. In an RBE scheme, users sample their own public and secret keys. There will also be a “key curator” whose job is only to aggregate the public keys of all the registered users and update the “short” public parameter whenever a new user joins the system. Encryption can still be performed to a particular recipient using the recipient’s identity and any public parameters released subsequent to the recipient’s registration. Decryption requires some auxiliary information connecting users’ public (and secret) keys to the public parameters. Because of this, as the public parameters get updated, a decryptor may need to obtain “a few” additional auxiliary information for decryption. More formally, if n is the total number of identities and $$\mathrm {\kappa }$$κ is the security parameter, we require the following.Efficiency requirements: (1) A decryptor only needs to obtain updated auxiliary information for decryption at most $$O(\log n)$$O(logn) times in its lifetime, (2) each of these updates are computed by the key curator in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn), and (3) the key curator updates the public parameter upon the registration of a new party in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn). Properties (2) and (3) require the key curator to have random access to its data.Compactness requirements: (1) Public parameters are always at most $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) bit, and (2) the total size of updates a user ever needs for decryption is also at most $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) bits.We present feasibility results for constructions of RBE based on indistinguishably obfuscation. We further provide constructions of weakly efficient RBE, in which the registration step is done in $${\text {poly}}(\mathrm {\kappa },n)$$poly(κ,n), based on CDH, Factoring or LWE assumptions. Note that registration is done only once per identity, and the more frequent operation of generating updates for a user, which can happen more times, still runs in time $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn). We leave open the problem of obtaining standard RBE (with $${\text {poly}}(\mathrm {\kappa },\log n)$$poly(κ,logn) registration time) from standard assumptions.