Shor算法对$F_{2^m}$椭圆曲线和GHASH的影响

Question

椭圆曲线的安全性取决于离散对数问题的难度。如果Shor算法被证明是可行的，那么椭圆曲线将不再提供任何有用的安全属性，因此需要后量子密码算法。

关于Shor算法的大多数讨论都是针对整数的，但它对多项式的适用性如何呢？

这是相关的，因为SEC2在F_{2^m}上定义了一组椭圆曲线，而不是F_P。

我也很好奇Shor的算法会如何影响在F_{2^m}中运行的GCM / GHASH。

Answer 1

关于Shor算法的大多数讨论都是针对整数的，但它对多项式的适用性如何呢？

相当适用；Shor的算法将组操作看作一个黑盒，因此它处理一个偶数特征曲线，就像处理素数曲线一样。唯一的实际差别是质数曲线和偶数特征曲线加法运算之间的成本差异(在量子位数、电路复杂度和深度方面)。

我也很好奇Shor的算法会如何影响在F_{2^m}中运行的GCM / GHASH。

这是一个不同的问题(因为GCM/GHASH有一个秘密对称密钥)；就标准CPA和CCA攻击而言，GCM/GHASH (正确使用)显然是安全的，只要您不能将AES (或您正在使用的任何底层分组密码)与随机排列区分开来；允许对手执行量子操作不会改变这一点(因此，除非他能够使用他的量子计算机破坏AES，否则他什么也做不了)。

一个例外是，如果您走出该模型，进入一个量子Oracle模型(在该模型中，攻击者可以请求纠缠查询并获得纠缠响应)，这就不同了--众所周知，GHASH (即GCM中的身份验证部分)很容易被破坏。这确实表明，白盒GCM实现不可能是量子安全的；然而，很难想出另一个实际的方案，在这种攻击是适用的。