We revisit the problem of finding Bblocklong collisions in MerkleDamg˚ard Hash Functions in the auxiliaryinput random oracle model, in which an attacker gets a piece of Sbit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage Ω( e ST B/2 n + T 2/2 n) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this socalled STB conjecture was only proved for B ≈ T and B = 2. Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of B, and provided an Oe(S 4T B2/2 n + T 2/2 n) bound for all choices of B. In this work, we prove an Oe((ST B/2 n)· max{1, ST2/2 n}+T 2/2 n) bound for every 2 < B < T. Our bound confirms the STB conjecture for ST2 ≤ 2 n, and is optimal up to a factor of S for ST2 > 2 n (note asmore »
Towards Defeating Backdoored Random Oracles: Indifferentiability with Bounded Adaptivity
In the backdoored randomoracle (BRO) model, besides access to a random function H , adversaries are provided with a backdoor oracle that can compute arbitrary leakage functions f of the function table of H . Thus, an adversary would be able to invert points, find collisions, test for membership in certain sets, and more. This model was introduced in the work of Bauer, Farshim, and Mazaheri (Crypto 2018) and extends the auxiliaryinput idealized models of Unruh (Crypto 2007), Dodis, Guo, and Katz (Eurocrypt 2017), Coretti et al. (Eurocrypt 2018), and Coretti, Dodis, and Guo (Crypto 2018). It was shown that certain security properties, such as onewayness, pseudorandomness, and collision resistance can be reestablished by combining two independent BROs, even if the adversary has access to both backdoor oracles.
In this work we further develop the technique of combining two or more independent BROs to render their backdoors useless in a more general sense. More precisely, we study the question of building an indifferentiable and backdoorfree random function by combining multiple BROs. Achieving full indifferentiability in this model seems very challenging at the moment. We however make progress by showing that the xor combiner goes well beyond security against preprocessing attacks and more »
 Editors:
 Pass, Rafael; Pietrzak, Krzysztof
 Award ID(s):
 1815546
 Publication Date:
 NSFPAR ID:
 10208486
 Journal Name:
 Lecture notes in computer science
 Volume:
 12552
 Page Range or eLocationID:
 241273
 ISSN:
 03029743
 Sponsoring Org:
 National Science Foundation
More Like this


In a keyagreement protocol whose security is proven in the random oracle model (ROM), the parties and the eavesdropper can make bounded number of queries to a shared random function (an “oracle”). Such protocol are the alternative to keyagreement protocols whose security is based on “publickey assumptions”, assumptions that being more structured are presumingly more vulnerable to attacks. Barak and Mahmoody [Crypto ’09] (following Impagliazzo and Rudich [STOC ’89]) have shown the ROM keyagreement protocols can only guarantee limited secrecy: the key of any `lquery protocol can be revealed by an O(l^2 )query adversary, a bound that matches the gap obtained by the Merkle’s Puzzles twomessage protocol of Merkle [CACM ’78]. While this quadratic gap might not seem like much, if the honest parties are willing to work “hard enough” and given continuousness improvement in common hash functions evaluation time, this gap yields a good enough advantage (assuming the security of the protocol holds when initiating the random function with a fixed hash function). In this work we consider the communication complexity of ROM keyagreement protocols. In Merkle’s Puzzles, the honest parties need to exchange Ω(l) bits (ignoring logarithmic factors) to obtain secrecy against an eavesdropper that makes roughly l^2more »

Tessaro, Stefano (Ed.)A Proof of Sequential Work (PoSW) allows a prover to convince a resourcebounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including timestamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depthrobust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depthrobust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long ℋsequence and that any malicious party running in sequential time T1 will fail to produce an ℋsequence of length T except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T1 will fail to produce an ℋsequence except with negligible probability  even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry’s recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish postquantum securitymore »

The quantum random oracle model (QROM) has become the standard model in which to prove the postquantum security of randomoraclebased constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary’s queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this “recording barrier”. We do so by giving a new “compressed oracle” which allows for efficient onthefly simulation of random oracles, roughly analogous to the usual classical simulation. We then use this new technique to give the first proof of quantum indifferentiability for the MerkleDamgård domain extender for hash functions. We also give a proof of security for the FujisakiOkamoto transformation; previous proofs required modifying the scheme to include an additional hash term. Given the threat posed by quantum computers and the push toward quantumresistant cryptosystems, our work represents an important tool for efficient postquantum cryptosystems.

The randompermutation model (RPM) and the idealcipher model (ICM) are idealized models that offer a simple and intuitive way to assess the conjectured standardmodel security of many important symmetrickey and hashfunction constructions. Similarly, the genericgroup model (GGM) captures generic algorithms against assumptions in cyclic groups by modeling encodings of group elements as random injections and allows to derive simple bounds on the advantage of such algorithms. Unfortunately, both wellknown attacks, e.g., based on rainbow tables (Hellman, IEEE Transactions on Information Theory ’80), and more recent ones, e.g., against the discretelogarithm problem (CorriganGibbs and Kogan, EUROCRYPT ’18), suggest that the concrete security bounds one obtains from such idealized proofs are often completely inaccurate if one considers nonuniform or preprocessing attacks in the standard model. To remedy this situation, this work defines the auxiliaryinput (AI) RPM/ICM/GGM, which capture both nonuniform and preprocessing attacks by allowing an attacker to leak an arbitrary (boundedoutput) function of the oracle’s function table; derives the first nonuniform bounds for a number of important practical applications in the AIRPM/ICM, including constructions based on the MerkleDamgård and sponge paradigms, which underly the SHA hashing standards, and for AIRPM/ICM applications with computational security; and using simpler proofs, recovers the AIGGMmore »