问公钥密码学中的Grover算法- FrodoKEM

EN

我想知道是否可以在密钥封装机制上应用Grover算法来破解共享密钥。

以下是Grover算法的工作原理(简化)：您使用一个“健身”函数(如果猜测正确，则对搜索的值进行猜测，并计算为“1”；如果猜测不正确，则计算为“0”--对于AES，适合度函数可能是‘使用猜测作为AES密钥，加密已知的明文块，并检查结果是否是已知的密文块)。

然后，将这个适应度函数(和一些其他量子运算)进行大量迭代--如果您迭代它的次数是正确的，那么当您测量结果时，它很可能是一个值，它的适应度函数计算为1。

现在，如果我们考虑攻击佛罗多，有两种方法可以攻击它。我们可以尝试直接从公钥共享中恢复共享秘密；在这种情况下，我们可以使用适合度函数--公钥共享，以及我们对共享秘密的猜测。但是，我们没有一种有效的方法来检查这个猜测是否正确(基于公钥共享)，因此我们不知道如何构建这个适应度函数(因此Grover的方法似乎不适用)。

另一方面，我们可以尝试恢复Frodo用来派生公钥1的秘密种子。对于Frodo-640 (NIST第1级)，这个秘密种子是128位；因为可以定义这个128位值(和公共数据，即公共种子)和公钥之间的映射，所以我们可以使用它来生成适应度函数。

现在，这种攻击并不是后量子密码所固有的；它的工作方式不是直接攻击128位共享秘密，而是使用128位随机值作为“秘密种子”，而不是Frodo的这个参数集如何生成其密钥共享。Frodo所做的就是使用那个128位的秘密种子，并使用握手来扩展它，生成更长的共享和错误向量；Frodo设计人员本来可以使用一个更长的秘密种子，并对其进行扩展--这将使Grover的秘密种子更难恢复(因为恢复的秘密种子要长得多，并且试图恢复内部抖动状态或抖动输出序列也需要太长时间)。弗罗多的设计者没有这样做，可能是因为它实际上不会提高安全性。

第三，我们通常使用共享密钥执行一些操作；我们可以将其输入KDF (可能还包括一些公共数据，如nonces)，然后将其用作AES密钥。我们可以在此基础上构建适应度函数，因此Grover的函数将适用于该系统--最有可能的是，这种KDF/AES结构在量子计算机中比Frodo公钥(或封装)过程更容易实现；因此，在那里攻击系统可能会更容易(如果只使用常数因子)。

第四，有理由问Grover's是否真的是对128位秘密的威胁--所有这些适应度功能评估都是连续进行的，并且连续评估任何函数的2^{64}时间都是不切实际的。而且，尽管你可以尝试通过在大量的量子计算机上运行Grover，通过划分秘密空间来解决这个问题，但是如果我们这样做，我们就失去了Grover的部分优势，所以我们最终使用了大量的量子计算机。

1：请注意，Frodo有两个种子；一个是公开的，它定义要使用的格，另一个是秘密的，用于生成样本和错误矩阵；由于公共种子在公钥中，攻击者不需要猜测；他所需要做的就是恢复这个秘密种子。