【密码学百科】离散对数与配对密码学：从 DLP 到 BLS 签名
💡
原文中文，约20200字，阅读约需48分钟。
📝
内容提要
离散对数问题（DLP）是公钥密码学的基础，广泛应用于加密和签名方案，其安全性依赖于群的结构，尤其在椭圆曲线中表现突出。通过双线性配对，DLP催生了BLS签名和身份基加密等新构造。尽管量子计算对DLP构成威胁，但其在当前密码学中仍然不可或缺。
🎯
关键要点
- 离散对数问题（DLP）是公钥密码学的基础，广泛应用于加密和签名方案。
- DLP的安全性依赖于群的结构，尤其在椭圆曲线中表现突出。
- 双线性配对催生了BLS签名和身份基加密等新构造。
- DLP的形式化定义涉及在有限循环群中求解离散对数问题。
- 椭圆曲线离散对数问题（ECDLP）是DLP在椭圆曲线加法群上的特化形式，具有更高的安全性。
- 计算性Diffie-Hellman假设（CDH）和判定性Diffie-Hellman假设（DDH）是DLP的衍生假设。
- 通用攻击算法如Baby-step Giant-step、Pohlig-Hellman和Pollard's rho算法用于求解DLP。
- Index Calculus是攻击有限域乘法群DLP的有效方法，但不适用于椭圆曲线群。
- 量子计算对DLP构成威胁，Shor算法可以在多项式时间内解决DLP。
- BLS签名方案是配对密码学的成功应用，具有短签名和高效聚合的优点。
- 身份基加密（IBE）和属性基加密（ABE）是基于配对的高级构造。
- 后量子计算的威胁促使密码学界考虑混合部署策略，以确保安全性。
- DLP及其衍生假设在当前密码学中仍然不可或缺，理解其攻击算法的演进是密码学从业者的必修课题。
❓
延伸问答
离散对数问题（DLP）在密码学中的重要性是什么？
离散对数问题是公钥密码学的基础，广泛应用于加密和签名方案，其安全性依赖于群的结构。
什么是椭圆曲线离散对数问题（ECDLP）？
椭圆曲线离散对数问题是DLP在椭圆曲线加法群上的特化形式，具有更高的安全性。
双线性配对如何影响密码学构造？
双线性配对催生了BLS签名和身份基加密等新构造，增强了密码学的功能和安全性。
量子计算对离散对数问题的威胁是什么？
量子计算通过Shor算法可以在多项式时间内解决离散对数问题，威胁到基于DLP的密码方案的安全性。
BLS签名方案的主要优点是什么？
BLS签名方案的主要优点是签名短且支持高效聚合，适合大规模应用。
Index Calculus算法为何不适用于椭圆曲线群？
Index Calculus算法依赖于群元素的因子分解结构，而椭圆曲线群运算不保持这种结构，因此不适用。
➡️
