Foundations of Cryptography

Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. We explore a new space of plausible PRF candidates that are obtained by mixing linear functions over different small moduli. Our candidates are motivated by the goals of maximizing simplicity and minimizing complexity measures that are relevant to cryptographic applications such as secure multiparty computation.

We present several concrete new PRF candidates that follow the above approach. Our main candidate is a weak PRF candidate (whose conjectured pseudorandomness only holds for uniformly random inputs) that first applies a secret mod-2 linear mapping to the input, and then a public mod-3 linear mapping to the result. This candidate can be implemented by depth-2 ACC⁰ circuits. We also put forward a similar depth-3 strong PRF candidate. Finally, we present a different weak PRF candidate that can be viewed as a deterministic variant of “Learning Parity with Noise” (LPN) where the noise is obtained via a mod-3 inner product of the input and the key.

The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw natural connections between their hardness and questions in complexity theory or learning theory (e.g., learnability of depth-2 ACC⁰ circuits and width-3 branching programs, interpolation and property testing for sparse polynomials, and natural proof barriers for showing super-linear circuit lower bounds). On the applied side, the “piecewise-linear” structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). Using our PRF candidates, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity (often both) compared to protocols obtained by combining standard MPC protocols with PRFs like AES, LowMC, or Rasta (the latter two are specialized MPC-friendly PRFs). Our advantage over competing approaches is maximized in the setting of MPC with an honest majority, or alternatively, MPC with preprocessing.

Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We conclude by showing that our main weak PRF candidate can plausibly be boosted to an encoded-input PRF by leveraging error-correcting codes.

Boneh, Bonneau, Bünz, and Fisch (CRYPTO 2018) recently introduced the notion of a verifiable delay function (VDF). VDFs are functions that take a long sequential time \( T \) to compute, but whose outputs \( y := \text{Eval}(x) \) can be efficiently verified (possibly given a proof \( \pi \)) in time \( t \ll T \) (e.g., \( t=\text{poly}(\lambda, \log T) \) where \( \lambda \) is the security parameter). The first security requirement on a VDF, called uniqueness, is that no polynomial-time algorithm can find a convincing proof \( \pi' \) that verifies for an input \( x \) and a different output \( y' \neq y \). The second security requirement, called sequentiality, is that no polynomial-time algorithm running in time \( \sigma\lt T \) for some parameter \( \sigma \) (e.g., \( \sigma=T^{1/10} \)) can compute \( y \), even with \( \text{poly}(T,\lambda) \) many parallel processors. Starting from the work of Boneh et al., there are now multiple constructions of VDFs from various algebraic assumptions.

In this work, we study whether VDFs can be constructed from ideal hash functions in a black-box way, as modeled in the random oracle model (ROM). In the ROM, we measure the running time by the number of oracle queries and the sequentiality by the number of rounds of oracle queries. We rule out two classes of constructions of VDFs in the ROM:

• We show that VDFs satisfying perfect uniqueness (i.e., no different convincing solution \( y' \neq y \) exists) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution \( y \) in \( \approx t \) rounds of queries, asking only \( \text{poly}(T) \) queries in total.

• We also rule out tight VDFs in the ROM. Tight VDFs were recently studied by Döttling, Garg, Malavolta, and Vasudevan (ePrint Report 2019) and require sequentiality \( \sigma \approx T-T^\rho \) for some constant \( 0 \lt \rho \lt 1 \). More generally, our lower bound also applies to proofs of sequential work (i.e., VDFs without the uniqueness property), even in the private verification setting, and sequentiality \( \sigma \gt T- T / (2t) \) for a concrete verification time \( t \).