More Like this

1. Time-Space Lower Bounds for Finding Collisions in Merkle-Damgard Hash Functions

   Akshima ; Guo, Siyao ; Lie, Qipeng ( July 2022 , IACR CRYPTO 2022)

   We revisit the problem of finding B-block-long collisions in Merkle-Damg˚ard Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of S-bit 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 so-called 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 as T 2 is always at most 2n, otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for B = Oe(1) and ST2 > 2 n. We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating proof for B = 2, recovering the main result of Akshima, Cash, Drucker and Wee. 

   more » « less
2. On the Communication Complexity of Key-Agreement Protocols

   Haitner, Iftach ; Mazor, Noam ; Oshman, Rotem ; Reingold, Omer ; Yehudayoff, Amir ( January 2019 , Innovations in Theoretical Computer Science Conference)

   In a key-agreement 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 key-agreement protocols whose security is based on “public-key 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 key-agreement protocols can only guarantee limited secrecy: the key of any `l-query protocol can be revealed by an O(l^2 )-query adversary, a bound that matches the gap obtained by the Merkle’s Puzzles two-message 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 key-agreement 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^2 queries, which makes the protocol unrealizable in many settings. We show that for protocols with certain natural properties, such high communication is unavoidable. Specifically, this is the case if the honest parties’ queries are independent and uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Since two-round key-agreement protocol are equivalent to public-key encryption scheme (seeing the first message as the public-key), the latter result bounds the public-key and encryption size of public-key encryption scheme whose security is proven in the ROM. 

   more » « less
3. Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model

   Apon, Daniel ; Cachet, Chloe ; Fuller, Benjamin ; Hall, Peter ; Liu, Feng-Hao ( January 2023 , Advances in Cryptology - Asiacrypt)

   We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). Along the way, we define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is public but protected from all tampering. We use the same paradigm to then extend this to digital lockers. Our constructions achieve nonmalleability over the output point by placing a CRS into the associated data and using an appropriate non-interactive zero-knowledge proof. Tampering is protected against the input point over low-degree polynomials and over any tampering to the output point and associated data. Our constructions achieve virtual black box security. These constructions are then used to create robust fuzzy extractors that can support low-entropy sources in the plain model. By using the geometric structure of a syndrome secure sketch (Dodis et al., SIAM Journal on Computing 2008), the adversary’s tampering function can always be expressed as a low-degree polynomial; thus, the protection provided by the constructed nonmalleable objects suffices. 

   more » « less
4. Sustained Space and Cumulative Complexity Trade-Offs for Data-Dependent Memory-Hard Functions

   Blocki, Jeremiah ; Holman, Blake ( October 2022 , Dodis, Y., Shrimpton, T. (eds) Advances in Cryptology – CRYPTO 2022)

   Dodis, Y. (Ed.)

   Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product of running time and the maximum space usage over the entire execution of an algorithm. Alwen and Serbinenko (STOC 2015) observed that the space-time cost of evaluating a function multiple times may not scale linearly in the number of instances being evaluated and introduced the stricter requirement that a memory-hard function has high cumulative memory complexity (CMC) to ensure that an attacker’s amortized space-time costs remain large even if the attacker evaluates the function on multiple different inputs in parallel. Alwen et al. (EUROCRYPT 2018) observed that the notion of CMC still gives the attacker undesirable flexibility in selecting space-time tradeoffs e.g., while the MHF Scrypt has maximal CMC Ω(N^2), an attacker could evaluate the function with constant O(1) memory in time O(N^2). Alwen et al. introduced an even stricter notion of Sustained Space complexity and designed an MHF which has s=Ω(N/logN) sustained complexity t=Ω(N) i.e., any algorithm evaluating the function in the parallel random oracle model must have at least t=Ω(N) steps where the memory usage is at least Ω(N/logN). In this work, we use dynamic pebbling games and dynamic graphs to explore tradeoffs between sustained space complexity and cumulative memory complexity for data-dependent memory-hard functions such as Argon2id and Scrypt. We design our own dynamic graph (dMHF) with the property that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N) space, or (2) has CMC Ω(N^{3−ϵ})—substantially larger than N^2. For Argon2id we show that any dynamic pebbling strategy either(1) has Ω(N) rounds with Ω(N^{1−ϵ}) space, or (2) has CMC ω(N^2). We also present a dynamic version of DRSample (Alwen et al. 2017) for which any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N/log N) space, or (2) has CMC Ω(N^3/log N). 

   more » « less
5. On the Security of Proofs of Sequential Work in a Post-Quantum World

   https://doi.org/10.4230/LIPIcs.ITC.2021.22  

   Blocki, J ; Lee, S ; Zhou, S. ( January 2021 , 2nd Conference on Information-Theoretic Cryptography (ITC 2021))

   Tessaro, Stefano (Ed.)

   A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, 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 depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust 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 T-1 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 T-1 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 post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018). 

   more » « less