Mar 21 2024
Published by
yl10038
A recent paper, first authored by Ye Yuping, an NYU Shanghai - ECNU Joint Graduate Training Program (N.E.T.) student majoring in software engineering, has been accepted by the ACM Theory of Computing Annual Conference (STOC), one of the most respected international conferences covering all areas of research within algorithms and computation theory.
The paper, titled “Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem,” was composed under the guidance of Assistant Professor of Computer Science Guo Siyao. The paper focused on the Decisional Diffie–Hellman (DDH) problem, which was introduced by Diffie and Hellman as the basis for their groundbreaking public-key cryptography revolution in 1976, and is still used to this day to secure our daily communication over the internet.
In the past decade, researchers have demonstrated surprisingly powerful preprocessing attacks on another foundational problem called the discrete-log problem, and suggested that a better attack may be possible for DDH. Preprocessing attacks are threatening the security of DDH, therefore many cryptographic systems based on DDH.
This paper shows that no better preprocessing attacks are possible, and confirms that DDH is as hard as the discrete-log problem even against preprocessing attacks. This answers one of the main open problems proposed by Corrigan-Gibbs and Kogan in their best young researcher award paper in Eurocrypt 2018 (one of the three flagship cryptography conferences).
The ACM Symposium on Theory of Computing (STOC) is a prestigious CS theory conference and will be held in Vancouver, Canada, in June 2024. This year, 188 papers were selected from 592 submissions for the conference, with a paper acceptance rate of 31.7%.
“After several years of being stuck and failing, we were extremely happy that we could eventually resolve this fundamental problem in a complete and elegant way. Being accepted by STOC as one of the <10 cryptography papers is definitely a remarkable recognition of this work,” said Guo. “More importantly, I am very happy that Yuping’s persistence, faith and growth along the way could be rewarded by such an achievement.”