International Association
for Cryptologic Research

We revisit the problem of finding B -block-long collisions in Merkle–Damgård 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\le B\le T$$ 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage $$\widetilde{\Omega }(STB/2^n+T^2/2^n)$$ Ω ~ ( S T 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\approx T$$ B ≈ T and $$B=2$$ B = 2 . Very recently, Ghoshal and Komargodski (CRYPTO 2022) confirmed the STB conjecture for all constant values of B and provided an $$\widetilde{O}(S^4TB^2/2^n+T^2/2^n)$$ O ~ ( S 4 T B 2 / 2 n + T 2 / 2 n ) bound for all choices of B . In this work, we prove an $$\widetilde{O}((STB/2^n)\cdot \max \{1,ST^2/2^n\}+ T^2/2^n)$$ O ~ ( ( S T B / 2 n ) · max { 1 , S T 2 / 2 n } + T 2 / 2 n ) bound for every $$2< B < T$$ 2 < B < T . Our bound confirms the STB conjecture for $$ST^2\le 2^n$$ S T 2 ≤ 2 n and is optimal up to a factor of S for $$ST^2>2^n$$ S T 2 > 2 n (note as $$T^2$$ T 2 is always at most $$2^n$$ 2 n , 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=\widetilde{O}(1)$$ B = O ~ ( 1 ) and $$ST^2>2^n$$ S T 2 > 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$$ B = 2 , recovering the main result of Akshima, Cash, Drucker and Wee.

We study the black-box function inversion problem, which is the problem of finding x \in [N] such that f(x) = y, given as input some challenge point y in the image of a function f : [N] \to [N], using T oracle queries to f \emph{and} preprocessed advice \sigma \in \{0,1\}^S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying T S^2 \cdot \max\{S,T\} = \widetilde{\Theta}(N^3) In the important setting when S < T, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires T S^3 \gtrsim N^3. E.g., Fiat and Naor's algorithm is only non-trivial for S \gg N^{2/3}, while our algorithm gives a non-trivial tradeoff for any S \gg N^{1/2}. (Our algorithm and analysis are quite simple. As a consequence of this, we also give a self-contained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We observe that there is a very simple \emph{non-adaptive} algorithm (i.e., an algorithm whose i-th query x_i is chosen based entirely on \sigma and y, and not on the f(x_1),\ldots, f(x_{i-1})) that improves slightly on the trivial algorithm. It works for any T and S satisfying S = \Theta(N \log(N/T)), for example, T = N /\polylog(N), S = \Theta(N/\log \log N). This answers a question due to Corrigan-Gibbs and Kogan [TCC, 2019], who asked whether non-trivial non-adaptive algorithms exist; namely, algorithms that work with parameters T and S satisfying T + S/\log N < o(N). We also observe that our non-adaptive algorithm is what we call a \emph{guess-and-check} algorithm, that is, it is non-adaptive \emph{and} its final output is always one of the oracle queries x_1,\ldots, x_T. For guess-and-check algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (S,T) for this natural class of algorithms. (Corrigan-Gibbs and Kogan showed that any such lower bound for \emph{arbitrary} non-adaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f : [N] \to [M] with different ranges. Some of these equivalence results are deferred to the full version [ECCC, 2022]. All of the above results are most naturally described in a model with \emph{shared randomness} (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not.

Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damg\r ard paradigm. We revisit the problem of finding $B$-block-long collisions in sponge hash functions in the auxiliary-input random permutation model, in which an attacker gets a piece of $S$-bit advice about the random permutation and makes $T$ (forward or inverse) oracle queries to the random permutation. Recently, significant progress has been made in the Merkle-Damg\r ard setting and optimal bounds are known for a large range of parameters, including all constant values of $B$. However, the sponge setting is widely open: there exist significant gaps between known attacks and security bounds even for $B=1$. Freitag, Ghoshal and Komargodski (CRYPTO 2022) showed a novel attack for $B=1$ that takes advantage of the inverse queries and achieves advantage $\Omega(\min(S^2T^2/2^{2c}$, $ (S^2T/2^{2c})^{2/3})+T^2/2^r)$, where $r$ is bit-rate and $c$ is the capacity of the random permutation. However, they only showed an $O(ST/2^c+T^2/2^r)$ security bound, leaving open an intriguing quadratic gap. For $B=2$, they beat the general security bound %$O(ST^2/2^c+T^2/2^r)$, by Coretti, Dodis, Guo (CRYPTO 2018) for arbitrary values of $B$. However, their highly non-trivial argument is quite laborious, and no better (than the general) bounds are known for $B\geq 3$. In this work, we study the possibility of proving better security bounds in the sponge setting. To this end, \begin{itemize} \item For $B=1$, we prove an improved $O(S^2T^2/2^{2c}+S/2^c+T/2^c+T^2/2^r)$ bound. Our bound strictly improves the bound by Freitag et al., %Ghoshal and Komargodski, and is optimal for $ST^2\leq 2^c$. %and is optimal up to a factor of $(ST^2/2^c)^{2/3}$ for $ST^2>2^c$. \item For $B=2$, we give a considerably simpler and more modular proof, recovering the bound obtained by Freitag et al. %, Ghoshal and Komargodski. \item We obtain our bounds by adapting the recent multi-instance technique of Akshima, Guo and Liu (CRYPTO 2022) which bypasses limitations of prior techniques in the Merkle-Damg\r ard setting. To complement our results, we provably show that the recent multi-instance technique cannot further improve our bounds for $B=1,2$, and the general %$O(ST^2/2^c+T^2/2^r)$ bound by Correti et al., for $B\geq 3$. \end{itemize} Overall, our results yield the state-of-the-art security bounds for finding short collisions, and fully characterize the power of the multi-instance technique in the sponge setting. \keywords{Collision \and hash functions \and Sponge \and multi-instance \and pre-computation \and auxiliary input}

We revisit the problem of finding B-block-long collisions in Merkle-Damgard 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\leq B\leq T (with respect to a random salt). The attack achieves advantage \Tilde{\Omega}(STB/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\approx T and B=2. Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of B, and provided an \Tilde{O}(S^4TB^2/2^n+T^2/2^n) bound for all choices of B. In this work, we prove an \Tilde{O}((STB/2^n)\cdot\max\{1,ST^2/2^n\}+ T^2/2^n) bound for every 2< B < T. Our bound confirms the STB conjecture for ST^2\leq 2^n, and is optimal up to a factor of S for ST^2>2^n (note as T^2 is always at most 2^n, 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=\Tilde{O}(1) and ST^2>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.

Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state R with a new entropic input X. Instead, they use ``super-efficient'' simple entropy-accumulation procedures, such as R <- rot_{alpha, n}(R) XOR X where rot_{alpha,n} rotates an n-bit state R by some fixed number alpha. For example, Microsoft's RNG uses alpha=5 for n=32 and alpha=19 for n=64. Where do these numbers come from? Are they good choices? Should rotation be replaced by a better permutation pi of the input bits? In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs X_1,X_2, ... as independent (but otherwise adversarial) samples from some natural distribution family D. We show a simple but surprisingly powerful connection between entropy accumulation and understanding the Fourier spectrum of distributions in D. Our contribution is as follows. - We define 2-monotone distributions as a rich family D that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results. - For any alpha with gcd(alpha,n)=1, we show that rotation accumulates Omega(n) bits of entropy from n independent samples X_1,...,X_n from any (unknown) 2-monotone distribution with entropy k > 1. - However, we also show some choices of alpha perform much better than others for a given n. E.g., we show alpha=19 is one of the best choices for n=64; in contrast, alpha=5 is good, but generally worse than alpha=7, for n=32. - More generally, given a permutation pi and k > 1, we define a simple parameter, the covering number C_{pi,k}, and show that it characterizes the number of steps before the rule (R_1,...,R_n) <- (R_{pi(1)},..., R_{pi(n)}) XOR X accumulates nearly n bits of entropy from independent, 2-monotone samples of min-entropy k each. - We build a simple permutation pi^*, which achieves nearly optimal C_{pi^*,k} \approx n/k for all values of k simultaneously, and experimentally validate that it compares favorably with all rotations rot_{alpha,n}.

Auxiliary-input (AI) idealized models, such as auxiliary-input random oracle model (AI-ROM) and auxiliary-input random permutation model (AI-PRM), play a critical role in assessing non-uniform security of symmetric key and hash function constructions. However, obtaining security bounds in these models is often much more challenging. The presampling technique, introduced by Unruh (CRYPTO' 07), generically reduces security proofs in the auxiliary-input models to much simpler bit-fixing models. This technique has been further optimized by Coretti, Dodis, Guo, Steinberger (EUROCRYPT' 18), and generalized by Coretti, Dodis, Guo (CRYPTO' 18), resulting in powerful tools for proving non-uniform security bounds in various idealized models. We study the possibility of leveraging the presampling technique to the quantum world. To this end, (*) We show that such leveraging will {resolve a major open problem in quantum computing, which is closely related to the famous Aaronson-Ambainis conjecture (ITCS' 11). (*) Faced with this barrier, we give a new but equivalent bit-fixing model and a simple proof of presampling techniques for arbitrary oracle distribution in the classical setting, including AI-ROM and AI-RPM. Our theorem matches the best-known security loss and unifies previous presampling techniques. (*) Finally, we leverage our new classical presampling techniques to a novel ``quantum bit-fixing'' version of presampling. It matches the optimal security loss of the classical presampling. Using our techniques, we give the first post-quantum non-uniform security for salted Merkle-Damgard hash functions and reprove the tight non-uniform security for function inversion by Chung et al. (FOCS' 20).

$$\mathsf {LWE}$$ LWE -based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie–Hellman key exchange or polynomial $$\mathsf {LWE}$$ LWE -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $$\mathsf {LWE}$$ LWE -based protocols with polynomial $$\mathsf {LWE}$$ LWE -modulus. To this end, we identify and formalize simple non-interactive and polynomial $$\mathsf {LWE}$$ LWE -modulus variants of the existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $$\mathsf {LWE}$$ LWE samples with polynomial $$\mathsf {LWE}$$ LWE -modulus and then run individual key reconciliation functions to obtain the shared key. We point out central barriers and show that such non-interactive key-exchange protocols are impossible in either of the following cases: (1) the reconciliation functions first compute the inner product of the received $$\mathsf {LWE}$$ LWE sample with their private $$\mathsf {LWE}$$ LWE secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $$\mathsf {LWE}$$ LWE sample. This impossibility assumes hardness of $$\mathsf {LWE}$$ LWE . We show that progress toward either a polynomial $$\mathsf {LWE}$$ LWE -modulus $$\text {NIKE}$$ NIKE construction or a general impossibility result has implications to the current understanding of lattice-based cryptographic constructions. Overall, our results show possibilities and challenges in designing simple (ring) $$\mathsf {LWE}$$ LWE -based non-interactive key-exchange protocols.

$$mathsf {LWE}$$ based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie-Hellman key-exchange or polynomial $$mathsf {LWE}$$ -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $$mathsf {LWE}$$ -based protocols with polynomial $$mathsf {LWE}$$ -modulus. To this end, We identify and formalize simple non-interactive and polynomial $$mathsf {LWE}$$ -modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $$mathsf {LWE}$$ samples with polynomial $$mathsf {LWE}$$ -modulus and then run individual key reconciliation functions to obtain the shared key. We point out central barriers and show that such non-interactive key-exchange protocols are impossible if: (1) the reconciliation functions first compute the inner product of the received $$mathsf {LWE}$$ sample with their private $$mathsf {LWE}$$ secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $$mathsf {LWE}$$ sample. This impossibility assumes hardness of $$mathsf {LWE}$$ . We give further evidence that progress in either direction, of giving an $$mathsf {LWE}$$ -based $$mathrm {NIKE}$$ protocol or proving impossibility of one will lead to progress on some other well-studied questions in cryptography. Overall, our results show possibilities and challenges in designing simple (ring) $$mathsf {LWE}$$ -based non-interactive key exchange protocols.

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by decision trees of depth $$d= n^{1/4-o(1)}$$ . In particular, each bit of the tampered codeword is set arbitrarily after adaptively reading up to d arbitrary locations within the original codeword. Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth $$O(\log ^2 n)$$ .Our result also yields efficient, unconditional non-malleable codes that are $$\exp (-n^{\varOmega (1)})$$ -secure against constant-depth circuits of $$\exp (n^{\varOmega (1)})$$ -size. Prior work of Chattopadhyay and Li (STOC 2017) and Ball et al. (FOCS 2018) only provide protection against $$\exp (O(\log ^2n))$$ -size circuits with $$\exp (-O(\log ^2n))$$ -security.We achieve our result through simple non-malleable reductions of decision tree tampering to split-state tampering. As an intermediary, we give a simple and generic reduction of leakage-resilient split-state tampering to split-state tampering with improved parameters. Prior work of Aggarwal et al. (TCC 2015) only provides a reduction to split-state non-malleable codes with decoders that exhibit particular properties.

The random-permutation model (RPM) and the ideal-cipher model (ICM) are idealized models that offer a simple and intuitive way to assess the conjectured standard-model security of many important symmetric-key and hash-function constructions. Similarly, the generic-group 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 well-known attacks, e.g., based on rainbow tables (Hellman, IEEE Transactions on Information Theory ’80), and more recent ones, e.g., against the discrete-logarithm problem (Corrigan-Gibbs and Kogan, EUROCRYPT ’18), suggest that the concrete security bounds one obtains from such idealized proofs are often completely inaccurate if one considers non-uniform or preprocessing attacks in the standard model. To remedy this situation, this workdefines the auxiliary-input (AI) RPM/ICM/GGM, which capture both non-uniform and preprocessing attacks by allowing an attacker to leak an arbitrary (bounded-output) function of the oracle’s function table;derives the first non-uniform bounds for a number of important practical applications in the AI-RPM/ICM, including constructions based on the Merkle-Damgård and sponge paradigms, which underly the SHA hashing standards, and for AI-RPM/ICM applications with computational security; andusing simpler proofs, recovers the AI-GGM security bounds obtained by Corrigan-Gibbs and Kogan against preprocessing attackers, for a number of assumptions related to cyclic groups, such as discrete logarithms and Diffie-Hellman problems, and provides new bounds for two assumptions. An important step in obtaining these results is to port the tools used in recent work by Coretti et al. (EUROCRYPT ’18) from the ROM to the RPM/ICM/GGM, resulting in very powerful and easy-to-use tools for proving security bounds against non-uniform and preprocessing attacks.