We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions". The main result of this paper is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible definitions for the notion of a "good implementation" of a random oracle, pointing out limitations and challenges.
Following the preliminary version of the current work @cite_25 , Hada and Tanaka observed that the existence of even restricted correlation intractable functions (in the non uniform model) would be enough to prove that 3-round auxiliary-input zero-knowledge AM proof systems only exist for languages in BPP @cite_0 . (Recall that auxiliary-input zero-knowledge is seemingly weaker than black-box zero-knowledge, and so the result of @cite_0 is incomparable to prior work of Goldreich and Krawczyk @cite_3 that showed that constant-round auxiliary-input zero-knowledge AM proof systems only exist for languages in BPP.)
@cite_0 @cite_25 @cite_3
1590334370 1987890787 2962993321 2023675273
Correlation intractable function ensembles were introduced in an attempt to capture the "unpredictability" property of a random oracle: It is assumed that if R is a random oracle then it is infeasible to find an input x such that the input-output pair (x,R(x)) has some desired property. Since this property is often useful to design many cryptographic applications in the random oracle model, it is desirable that a plausible construction of correlation intractable function ensembles will be provided. However, no plausibility result has been proposed. In this paper, we show that proving the implication, "if one-way functions exist then correlation intractable function ensembles exist", is as hard as proving that "3-round auxiliary-input zero-knowledge Arthur-Merlin proofs exist only for trivial languages such as BPP languages." As far as we know, proving the latter claim is a fundamental open problem in the theory of zero-knowledge proofs. Therefore, our result can be viewed as strong evidence that the construction based solely on one-way functions will be impossible, i.e., that any plausibility result will require stronger cryptographic primitives. The wide applicability of zero-knowledge interactive proofs comes from the possibility of using these proofs as subroutines in cryptographic protocols. A basic question concerning this use is whether the (sequential and or parallel) composition of zero-knowledge protocols is zero-knowledge too. We demonstrate the limitations of the composition of zero-knowledge protocols by proving that the original definition of zero-knowledge is not closed under sequential composition; and that even the strong formulations of zero-knowledge (e.g., black-box simulation) are not closed under parallel execution. We present lower bounds on the round complexity of zero-knowledge proofs, with significant implications for the parallelization of zero-knowledge protocols. We prove that three-round interactive proofs and constant-round Arthur--Merlin proofs that are black-box simulation zero-knowledge exist only for languages in BPP. In particular, it follows that the "parallel versions" of the first interactive proofs systems presented for quadratic residuosity, graph isomorphism, and any language in NP, are not black-box simulation zero-knowledge, unless the corresponding languages are in BPP. Whether these parallel versions constitute zero-knowledge proofs was an intriguing open questions arising from the early works on zero-knowledge. Other consequences are a proof of optimality for the round complexity of various known zero-knowledge protocols and the necessity of using secret coins in the design of "parallelizable" constant-round zero-knowledge proofs. Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben- (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable *physical assumption*: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP^* model captures this setting. In this work we study the following question: does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover *zero knowledge* interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP^*. Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP^* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory. We construct a 1-round delegation scheme (i.e., argument system) for every language computable in time t = t(n), where the running time of the prover is poly(t) and the running time of the verifier is n · polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n · polylog(t). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by (ICALP, 2000). This method relies on the existence of a sub-exponentially secure PIR scheme, and was proved secure by (STOC, 2013) assuming the underlying MIP is secure against no-signaling provers.