International Association
for Cryptologic Research

While in classical cryptography one-way functions (OWFs) are widely regarded as the “minimal assumption”, the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One- way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC’24; Batra and Jain FOCS’24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID). As a consequence, we separate, via our oracle, QEFID and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto’24]. Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs. One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography.

We present new Non-Interactive Zero-Knowledge argument systems (NIZK), based on standard assumptions that were previously not known to imply it. In particular, we rely on the hardness of both the learning parity with noise (LPN) assumption, and the existence of trapdoor hash functions (TDH, defined by Döttling et al., Crypto 2019). TDH can be based on a number of standard assumptions, including DDH, QR, DCR, and LWE. We rely on the Correlation Intractability (CI) framework for converting \Sigma-protocols into NIZK, but deviate from prior works in considering CI for searchable relations where the search function has a probabilistic representation by a simple function class (linear or constant degree in our instantiations). Namely, there is a distribution over simple functions that computes each output bit of the search function with all but small (constant) probability. We present a new tool for proving CI for such function classes via a notion that we call Approximate-Correlation Intractability. This notion requires that CI holds even against approximations of a given function class. We show that approximate-correlation intractability for just constant degree functions suffices if the underlying \Sigma-protocol is implemented using an extractable commitment scheme with approximately low-degree extraction, and that such a commitment scheme can be constructed based on LPN. We then show how to construct approximate CI hash functions for this class from any suitable rate-1 TDH (with an enhanced correctness property that is satisfied by all existing constructions).

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to securely execute RAM programs over data that is stored in an untrusted server. Distributed Oblivious RAM is a variant of ORAM, where the data is stored in $$m>1$$ servers. Extensive research over the last few decades have succeeded to reduce the bandwidth overhead of ORAM schemes, both in the single-server and the multi-server setting, from $$O(\sqrt{N})$$ to O(1). However, all known protocols that achieve a sub-logarithmic overhead either require heavy server-side computation (e.g. homomorphic encryption), or a large block size of at least $$\varOmega (\log ^3 N)$$.In this paper, we present a family of distributed ORAM constructions that follow the hierarchical approach of Goldreich and Ostrovsky [17]. We enhance known techniques, and develop new ones, to take better advantage of the existence of multiple servers. By plugging efficient known hashing schemes in our constructions, we get the following results:1.For any number $$m\ge 2$$ of servers, we show an m-server ORAM scheme with $$O(\log N/\log \log N)$$ overhead, and block size $$\varOmega (\log ^2 N)$$. This scheme is private even against an $$(m-1)$$-server collusion.2.A three-server ORAM construction with $$O(\omega (1)\cdot \log N/\log \log N)$$ overhead and a block size almost logarithmic, i.e. $$\varOmega (\log ^{1+\epsilon }N)$$. We also investigate a model where the servers are allowed to perform a linear amount of light local computations, and show that constant overhead is achievable in this model, through a simple four-server ORAM protocol. From theoretical viewpoint, this is the first ORAM scheme with asymptotic constant overhead, and polylogarithmic block size, that does not use homomorphic encryption. Practically speaking, although we do not provide an implementation of the suggested construction, evidence from related work (e.g. [12]) confirms that despite the linear computational overhead, our construction is practical, in particular when applied to secure computation.

We introduce a new primitive, called trapdoor hash functions (TDH), which are hash functions $$\mathsf {H}: \{0,1\}^n \rightarrow \{0,1\}^\lambda $$ with additional trapdoor function-like properties. Specifically, given an index $$i\in [n]$$, TDHs allow for sampling an encoding key $$\mathsf {ek}$$ (that hides i) along with a corresponding trapdoor. Furthermore, given $$\mathsf {H}(x)$$, a hint value $$\mathsf {E}(\mathsf {ek},x)$$, and the trapdoor corresponding to $$\mathsf {ek}$$, the $$i^{th}$$ bit of x can be efficiently recovered. In this setting, one of our main questions is: How small can the hint value $$\mathsf {E}(\mathsf {ek},x)$$ be? We obtain constructions where the hint is only one bit long based on DDH, QR, DCR, or LWE.This primitive opens a floodgate of applications for low-communication secure computation. We mainly focus on two-message protocols between a receiver and a sender, with private inputs x and y, resp., where the receiver should learn f(x, y). We wish to optimize the (download) rate of such protocols, namely the asymptotic ratio between the size of the output and the sender’s message. Using TDHs, we obtain:1.The first protocols for (two-message) rate-1 string OT based on DDH, QR, or LWE. This has several useful consequences, such as:(a)The first constructions of PIR with communication cost poly-logarithmic in the database size based on DDH or QR. These protocols are in fact rate-1 when considering block PIR.(b)The first constructions of a semi-compact homomorphic encryption scheme for branching programs, where the encrypted output grows only with the program length, based on DDH or QR.(c)The first constructions of lossy trapdoor functions with input to output ratio approaching 1 based on DDH, QR or LWE.(d)The first constant-rate LWE-based construction of a 2-message “statistically sender-private” OT protocol in the plain model.2.The first rate-1 protocols (under any assumption) for n parallel OTs and matrix-vector products from DDH, QR or LWE. We further consider the setting where f evaluates a RAM program y with running time $$T\ll |x|$$ on x. We obtain the first protocols with communication sublinear in the size of x, namely $$T\cdot \sqrt{|x|}$$ or $$T\cdot \root 3 \of {|x|}$$, based on DDH or, resp., pairings (and correlated-input secure hash functions).