Welcome to the resource topic for 2024/1171
Title:
Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
Authors: Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, Yuping Ye
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.
ePrint: https://eprint.iacr.org/2024/1171
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .