| Title | : | Tight Time-Space Tradeoffs for Decisional Diffie-Hellman Problem |
| Speaker | : | Dr. Akshima (NYU Shanghai) |
| Details | : | Thu, 20 Nov, 2025 11:00 AM @ SSB 334 |
| Abstract: | : | In the preprocessing Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group G with a generator g and of prime order N. 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 Z_N. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes, such as the Diffie-Hellman Key exchange protocol. Corrigan-Gibbs and Kogan [CK18] and then Coretti et al. [CDG18] studied lower bounds for this problem for generic algorithms. However, both the works left a gap from the best known (generic) attack for the problem. In our STOC24 paper, we close this gap up to poly-log factors and consequently show that DDH is asymptotically as hard as Discrete Logarithm problem for preprocessing algorithms. The talk will include some preliminary definitions, detailed description of the models, results and a high level idea of the techniques from the joint work with Tyler Besselman, Siyao Guo, Zhiye Xie and Yuping Ye, available at https://eprint.iacr.org/2024/1171.pdf. |
