Results 1 to 10 of about 90,649 (207)
A Machine-Checked Formalization of the Generic Model and the Random Oracle Model [PDF]
, 2004 Most approaches to the formal analyses of cryptographic protocols make the perfect cryptography assumption, i.e. the hypothese that there is no way to obtain knowledge about the plaintext pertaining to a ciphertext without knowing the key. Ideally, one would prefer to rely on a weaker hypothesis on the computational cost of gaining information about ...
Gilles Barthe +2 more
core +10 more sources
Adaptive Proofs of Knowledge in the Random Oracle Model [PDF]
IET Information Security, 2015 We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA ...
David Bernhard +2 more
core +10 more sources
Delegating Quantum Computation in the Quantum Random Oracle Model [PDF]
, 2019 A delegation scheme allows a computationally weak client to use a server's resources to help it evaluate a complex circuit without leaking any information about the input (other than its length) to the server. In this paper, we consider delegation schemes for quantum circuits, where we try to minimize the quantum operations needed by the client.
Jiayu Zhang
core +5 more sources
Online-Extractability in the Quantum Random-Oracle Model
, 2021 We show the following generic result. Whenever a quantum query algorithm in the quantum random-oracle model outputs a classical value $t$ that is promised to be in some tight relation with $H(x)$ for some $x$, then $x$ can be efficiently extracted with almost certainty.
Jelle Don +3 more
openalex +7 more sources
Quantum Depth in the Random Oracle Model
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023 We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle: (a) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{BQP}$.
Atul Singh Arora +5 more
openalex +4 more sources
Weakened Random Oracle Models with Target Prefix [PDF]
, 2021 Weakened random oracle models (WROMs) are variants of the random oracle model (ROM). The WROMs have the random oracle and the additional oracle which breaks some property of a hash function. Analyzing the security of cryptographic schemes in WROMs, we can specify the property of a hash function on which the security of cryptographic schemes depends ...
Masayuki Tezuka +2 more
openalex +5 more sources
How Risky Is the Random-Oracle Model? [PDF]
, 2009 RSA-FDH and many other schemes secure in the Random-Oracle Model (ROM) require a hash function with output size larger than standard sizes. We show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by Bellare and Rogaway from 1993 and 1996, and the ones implicit in ...
Gaëtan Leurent, Phong Q. Nguyễn
openalex +4 more sources
Uselessness for an Oracle model with internal randomness [PDF]
Quantum Information and Computation, 2014 We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between ...
Aram W. Harrow, David J. Rosenbaum
openalex +6 more sources
Short Signatures in the Random Oracle Model [PDF]
, 2002 We study how digital signature schemes can generate signatures as short as possible, in particular in the case where partial message recovery is allowed. We give a concrete proposition named OPSSR that achieves the lower bound for message expansion, and give an exact security proof of the scheme in the ideal cipher model.
Louis Granboulan
openalex +2 more sources
A Machine-Checked Formalization of the Random Oracle Model [PDF]
, 2006 Most approaches to the formal analysis of cryptography protocols make the perfect cryptographic assumption, which entails for example that there is no way to obtain knowledge about the plaintext pertaining to a ciphertext without knowing the key. Ideally, one would prefer to abandon the perfect cryptography hypothesis and reason about the computational
Gilles Barthe, Sabrina Tarento
openalex +3 more sources