Schnorr群中Shor算法作为模函数的困难性

Question

假设施诺尔群的阶数为质数q，用于针对当前计算机的安全性(如q为256位)；模数为素数p=q\,r+1，足够大(例如，3072至32768位)，用于求解组中的DLP的算法是波拉德氏肌或波拉德袋鼠，而不是指数演算、功能场筛或GNFS。

在经典计算机上，打破离散对数问题的预期代价是\sqrt q乘法模p的几倍，因此随着算法的不同(简单的\alpha\approx2，卡拉斯图巴的\alpha\approx\log_2(3)\approx1.585，更复杂的算法的\alpha稍低)，随着\alpha的增加，D13也随之增长。

在假设的量子计算中，Shor算法原则上可以用于离散对数问题(见这些 问题的答案)，包括这个组。根据一些有用的标准，p的大小如何影响这样做的难度？和所需的量子位数一样，它们的质量(错误率)？相干性时间？)，假设计算所需的持续时间或能量。

我的动机是评估，当速度和关键规模处于次要地位时，拥有中等q但规模很大的p (以今天的标准衡量)的Schnorr集团是否能提供一些保证，以抵御假想的第一波密码相关量子计算机。

Answer 1

根据一些有用的标准，p的大小如何影响这样做的难度？

好的，Shor算法的昂贵部分是在组中执行O(\log q)乘法(在纠缠量子位上)的必要性(在这种情况下，它是mod p)。

因此，要做到这一点，需要O(\log p)量子位，以及(假设您使用教科书式乘法算法) O(\log q (\log p)^2)量子操作。因此，增加p将增加所需的量子位数和操作总数(但两者都会增加一个低阶多项式因子)。

现在，我听到的一个建议(由Shamir提出)是做根本不平衡的RSA --我们使用一个非常大的素数p和一个中等素数的q (例如1024位)，我们的公钥是pq和一个小指数e > \log p / \log q；私钥是值q和d = e^{-1} \bmod q-1。为了加密密文m (要求小于q)，我们使用传统的加密c = m^e \bmod pq。要解密密文c，我们首先计算c \bmod q，然后计算m = (c \bmod q)^d \bmod q (忽略p部分)。在这里，加密和解密都没有那么昂贵，而且要打破这个方案，唯一明显的方法是考虑pq (因为p很大，对第一代CRQC来说可能不实用)。

我不能赞同这个想法(因为我们不知道CRQC的扩展速度有多快)--然而，它可能比您的Schnorr小组想法表现得更好.