Nothing Special   »   [go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?

Paper 2024/1171

Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem

Akshima, NYU Shanghai
Tyler Besselman, NYU Shanghai
Siyao Guo, NYU Shanghai
Zhiye Xie, NYU Shanghai
Yuping Ye, East China Normal University, NYU Shanghai
Abstract

In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group $G$ with a generator $g$ and a prime order $N$, and we want to prepare some advice of size $S$, such that we can efficiently distinguish $(g^{x},g^{y},g^{xy})$ from $(g^{x},g^{y},g^{z})$ in time $T$ for uniformly and independently chosen $x,y,z$ from $\mathbb{Z}_N$. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes, such as the Diffie–Hellman key exchange protocol. We prove that any generic preprocessing DDH algorithm (operating in any cyclic group) achieves advantage at most $O(ST^2 / N)$. This bound matches the best known attack up to poly-log factors, and confirms that DDH is as secure as the (seemingly harder) discrete logarithm problem against preprocessing attacks. Our result resolves an open question by Corrigan-Gibbs and Kogan (EUROCRYPT 2018), who proved optimal bounds for many variants of discrete logarithm problems except DDH (with an $\tilde{O}(\sqrt{ST^2/N})$ bound). We obtain our results by adopting and refining the approach by Gravin, Guo, Kwok, Lu (SODA 2021) and by Yun (EUROCRYPT 2015). Along the way, we significantly simplified and extended the above techniques which may be of independent interest. The highlights of our techniques are as follows: (1) We obtain a simpler reduction from decisional problems against $S$-bit advice to their $S$-wise XOR lemmas against zero-advice, recovering the reduction by Gravin, Guo, Kwok and Lu (SODA 2021). (2) We show how to reduce generic hardness of decisional problems to their variants in the simpler hyperplane query model proposed by Yun (EUROCRYPT 2015). This is the first work analyzing a decisional problem in Yun's model, answering an open problem proposed by Auerbach, Hoffman, and Pascual-Perez (TCC 2023). (3) We prove an $S$-wise XOR lemma of DDH in Yun's model. As a corollary, we obtain the generic hardness of the $S$-XOR DDH problem.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. STOC 2024
DOI
10.1145/3618260.3649752
Keywords
Decisional Diffie-HellmanTime-Space Tradeoffs in CryptographyGeneric Group ModelHyperplane Query Model
Contact author(s)
akshima @ nyu edu
tyler william b @ nyu edu
siyao guo @ nyu edu
zhiye xie @ nyu edu
yy3813 @ nyu edu
History
2024-07-22: approved
2024-07-19: received
See all versions
Short URL
https://ia.cr/2024/1171
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1171,
      author = {Akshima and Tyler Besselman and Siyao Guo and Zhiye Xie and Yuping Ye},
      title = {Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1171},
      year = {2024},
      doi = {10.1145/3618260.3649752},
      url = {https://eprint.iacr.org/2024/1171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.