椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究

Research on the Bit Security of Elliptic Curve Diffie-Hellman

椭圆曲线Diffie-Hellman密钥交换协议与其他公钥密码体制相比,能够以较小的密钥尺寸来达到相同的安全强度,因此在实际应用中对带宽和存储的要求较低,从而在很多计算资源受限的环境中有更多应用价值。该文从理论和应用角度,评估该类型协议共享密钥建立过程中的部分信息泄漏对安全性的威胁至关重要。基于隐藏数问题和格分析技术,该文讨论了椭圆曲线Diffie-Hellman密钥交换协议的比特安全性,启发式地证明了椭圆曲线Diffie-Hellman共享密钥的x坐标的中间11/12 bit的计算困难性近似于恢复整个密钥。进一步地,给出了信息泄露量与泄漏位置的显式关系式。该文的研究结果放松了对泄露比特位置的限制,更加符合应用场景,显著改进了以往工作中得出的结论。

The elliptic curve Diffie-Hellman key exchange protocol enjoys great advantages since it could achieve the same security level with significantly smaller size of parameters compared with other public key cryptosystems.In real-world scenarios,this type of protocol requires less bandwidth and storage which leads to more application especially to computing resource constrained environments.Hence,it is important to evaluate the threat aroused by the partial information leakage during the establishment of shared keys.In this paper,the bit security of elliptic curve Diffie-Hellman with knowledge of partial inner bits based on the combination of hidden number problem and lattice-based cryptanalysis technique is recisited.11/12 of the inner bits of the x-coordinate of the elliptic curve Diffie-Hellman key are approximately as hard to compute as the entire key.Moreover,the explicit relationship between the leakage fraction and the leakage position is elaborated.This result which relaxes the restriction on the location of leakage position dramatically improves the trivial one which stemmed from prior work.