近日，由华东师范大学—上海纽约大学联合培养硕士生项目软件工程硕士研究生叶玉萍作为第一完成人、上海纽约大学助理教授郭斯瑶作为指导教师的《Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem》论文，被ACM计算理论年会（ACM Symposium on Theory of Computing，STOC）录用。

软件工程学院硕士研究生叶玉萍

成果介绍

决策Diffie-Hellman问题是许多广泛使用的密码方案的基础，其安全性备受关注。在不带预处理的通用群模型上，决策Diffie-Hellman问题的上下界是紧致的。然而在预处理的通用群模型上，决策Diffie-Hellman问题的上界为由Corrigan-Gibbs和Kogan在2018年的欧洲密码学会议上提出的sqrt(ST^2/N)，下界为ST^2/N，其上下界的差距较大。

此前，大众普遍认为，决策Diffie-Hellman问题是比离散对数问题更容易的。然而，本研究通过将其下界收紧到与离散对数问题下界同一量级证明了在带预处理的通用群模型下决策Diffie-Hellman问题与离散对数问题是一样安全的。

本研究成果首次提出了一种将决策问题多实例化后利用其代数结构来解决的新思路，构建了一系列从带预处理的通用群模型的决策问题到通用群模型的S-XOR决策问题，再到超平面查询模型中的S-XOR决策问题的安全规约，成功将带预处理的通用群模型上决策Diffie-Hellman问题的安全性上界收紧为ST^2/N。这个安全性上界在忽略多项式对数因子时完全消除了上下界之间的差距。本论文还首次分析了Yun模型中的决策问题，回答了Auerbach、Hoffman和Pascual-Perez在2023年理论计算机会议上提出的开放问题。

关于STOC

ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。该会议由ACM中的算法和计算理论兴趣小组（Special Interest Group in Algorithms and Computation Theory，SIGACT）提供资助，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。

内容来自论文作者

编辑丨俞思远

审核丨曹桂涛 陈铭松 邓玉欣