Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case

By Jesper Buus Nielsen. Annual International Cryptology Conference, 2002

387 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/a2c51558eecc4ec2a0ce5b3520a2efbcb7bf019b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology (2004, result): “Other similar impossibility results are proposed in [ 12 ] and [1].”
ANONIZE: A Large-Scale Anonymous Survey System (2014, positive): “Let us remark that our definition of zero-knowledge in the oracle model is somewhat stronger than what is usually required (and also what we require in our definition of simulation extractability): our definition is “non-programmable” [35, 34] in that we do not allow the simulator to program the ora”
Merkle-Damgård Revisited: How to Construct a Hash Function (2005, background): “In fact, many recent “separation” results [11,26,19,2,12,15] illustrated various cryptographic systems secure in the random oracle model but completely insecure for any concrete instantiation of the random oracle (even by a family of hash functions).”
Interactive Oracle Proofs (2016, background): “…also outputs a function µ , but the distinguisher has access to the same oracle modiﬁed so that a query to an input x in the domain of µ is answered with µ ( x ) ; (iii) Non-programmable random oracle (NPRO) [Nie02, Pas03]: the simulator and the distinguisher have access to the same random oracle.”
Improved Garbled Circuit: Free XOR Gates and Applications (2008, neutral): “First, we use non-programmable RO [22], i.”
Functional Encryption: Definitions and Challenges (2011, methodology): “The overall idea of this proof is almost identical to the impossibility proof of Nielsen [ Nie02 ] for non-interactive non-committing encryption.”
A Forward-Secure Public-Key Encryption Scheme (2003, background): “Furthermore, Nielsen has recently shown that this property is essential for encryption schemes that are not key-evolving [ 29 ].”
Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures (2006, background): “It is well known that using the random oracle model sometimes results in insecure real life protocols [18,19,34,27,4].”
Relaxing Chosen-Ciphertext Security (2003, methodology): “Indeed, using the techniques of [22], it can be shown that no protocol πS can realize Frpke with respect to adaptive adversaries, for any scheme S.”
An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem (2004, methodology): “Further examples followed: Nielsen [19] presented an uninstantiable RO-model scheme for the goal of non-interactive, non-committing encryption [7], and Goldwasser and Taumann [17] showed the existence of a 3-move protocol which, when collapsed via a RO as per the Fiat-Shamir heuristic [14], yields a”
Extending Oblivious Transfers Efficiently (2003, methodology): “First, in our security proofs we treat the random oracle as being non-programmable [31], i.”
Short Pairing-Based Non-interactive Zero-Knowledge Arguments (2010, background): “Unfortunately, there are several examples of protocols that are secure in the random oracle model, but do not have any secure standard model instantiation no matter which hash-function is used [9,10,34,3,37].”
Foundations of garbled circuits (2012, background): “The only known way to achieve it is via non-committing encryption [24, 28, 32], which is only possible with keys as long as the total number of bits of message ever encrypted [79], making the outsourcing scheme fail to be non-trivial.”
How To Simulate It - A Tutorial on the Simulation Proof Technique (2016, methodology): “If we provide the distinguisher with the same randomly chosen oracle as the parties and the (real and ideal) adversary, then we obtain a non-programmable random oracle [32] which may not be strong enough.”