## CryptoDB

### Siyao Guo

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Time-Space Lower Bounds for Finding Collisions in Merkle-Damgard Hash Functions
📺
Abstract

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.

2021

CRYPTO

No Time to Hash:On Super-Efficient Entropy Accumulation
📺
Abstract

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}.

2021

TCC

Unifying Presampling via Concentration Bounds
📺
Abstract

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).

2021

JOFC

Limits on the Efficiency of (Ring) LWE-Based Non-interactive Key Exchange
Abstract

$$\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.

2020

PKC

Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange
📺
Abstract

$$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.

2019

CRYPTO

Non-malleable Codes for Decision Trees
📺
Abstract

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.

2018

CRYPTO

Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models
📺
Abstract

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.

#### Program Committees

- Crypto 2021
- TCC 2021
- Crypto 2019
- Eurocrypt 2019
- TCC 2019

#### Coauthors

- Akshima (1)
- Marshall Ball (1)
- Andrej Bogdanov (2)
- Sandro Coretti (2)
- Yevgeniy Dodis (4)
- Pavel Hubáček (1)
- Pritish Kamath (2)
- Jonathan Katz (1)
- Ilan Komargodski (1)
- Qian Li (1)
- Qipeng Liu (2)
- Tal Malkin (1)
- Daniel Masny (1)
- Igor Carboni Oliveira (1)
- Silas Richelson (1)
- Alon Rosen (5)
- Katerina Sotiraki (2)
- John P. Steinberger (1)
- Noah Stephens-Davidowitz (1)
- Margarita Vald (1)
- Daniel Wichs (1)
- Zhiye Xie (1)
- Jiapeng Zhang (1)