论文标题
Farfalle和（广义）钥匙替代Feistel网络的量子密码分析
Quantum Cryptanalysis of Farfalle and (Generalised) Key-Alternating Feistel Networks
论文作者
论文摘要
Farfalle是一种基于置换的构建，用于构建伪随机函数，该函数由G. Bertoni等人提出。在2017年。在这项工作中，我们表明，通过观察Farfalle的合适输入，可以通过涉及秘密密钥的时期来得出周期性功能的各种构造。由于这在所谓的Q2攻击模型中接受了Simon算法的应用，因此我们进一步表明，在内部滚动函数是线性的情况下，可以在可行的假设下提取秘密密钥。此外，使用Farfalle的定期函数的提供的构造，我们表明可以在会话支持模式下进行伪造攻击，以进行身份验证的加密（Farfalle-SAE）和合成初始值AE模式（Farfalle-SIV）。此外，由于宽块密码模式FARFALLE-WBC是一个四轮Feistel方案，因此在输入分支在最后两个区块中包含一个块的情况下，构建了一个量子区分程序，其中一个块的长度对应于Farfalle中使用的置换量的大小（可以将类似的攻击安装到Farfalle-WBC-ae）。最后，我们考虑了从（广义）Feistel方案（GFN）获得的不同时期中提取秘密圆形密钥的问题，这在以前的任何作品中尚未解决，这些工作都考虑了Simon（或Simon-Grover）算法的应用，以使GFN的降低版本的圆形降低版本。通过应用两个不同的插值公式，我们表明可以通过利用与基础内部功能的多项式/代数密切相关的不同周期来提取圆形钥匙。
Farfalle is a permutation-based construction for building a pseudorandom function which has been proposed by G. Bertoni et al. in 2017. In this work, we show that by observing suitable inputs to Farfalle, one can derive various constructions of a periodic function with a period that involves a secret key. As this admits the application of Simon's algorithm in the so-called Q2 attack model, we further show that in the case when internal rolling function is linear, then the secret key can be extracted under feasible assumptions. Furthermore, using the provided constructions of periodic functions for Farfalle, we show that one can mount forgery attacks on the session-supporting mode for authenticated encryption (Farfalle-SAE) and the synthetic initial value AE mode (Farfalle-SIV). In addition, as the wide block cipher mode Farfalle-WBC is a 4-round Feistel scheme, a quantum distinguisher is constructed in the case when input branches are containing at last two blocks, where length of one block corresponds to the size of a permutation employed in Farfalle (a similar attack can be mounted to Farfalle-WBC-AE). And finally, we consider the problem of extracting a secret round key out of different periods obtained from a (Generalized) Feistel scheme (GFN), which has not been addressed in any of the previous works which consider the application of Simon's (or Simon-Grover) algorithm to round reduced versions of GFNs. By applying two different interpolation formulas, we show that one can extract the round key by utilizing amount of different periods which is closely related to the polynomial/algebraic degree of underlying inner function.
