Quantum Indistinguishability of Random Sponges
Quantum Indistinguishability of Random Sponges
复制标题
DOI：
10.1007/978-3-030-26951-7_11
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
J. Czajkowski;Andreas Hülsing;Christian Schaffner
中科院分区：
文献类型：
--
作者：
J. Czajkowski;Andreas Hülsing;Christian Schaffner
在这项工作中，我们表明，海绵建设可以用来构建量子安全的伪随机函数。作为我们的主要结果，我们证明了随机海绵是量子不可区分的随机功能。在这种情况下，对手可以叠加访问结构的输入输出行为，但不能访问内部功能。我们的证明在内部函数是随机函数或置换的假设下成立。然后，我们使用该结果来获得Andreeva、Daemen、Mennink和货车Assche（FSE'15）的结果的量子安全版本，该结果表明使用安全PRP或PRF作为内部函数的海绵是安全PRF。这一结果也证明了Kaplan，Leurent，Leverrier，and Naya-Plasstrom（Crypto'16）和Santoli，and Schaffner（QIC'16）最近对量子访问模型中CBC-MAC的攻击可以通过引入一个具有非平凡内部部分的状态来防止。我们的方法非常详细地分析了所考虑的建筑的统计行为。所使用的技术可能证明是有用的，在未来的分析不同的密码原语考虑量子对手。利用Zhandry的PRF/PRP开关引理，我们得到了当内部块函数是随机排列时，量子不变性也成立。
In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a quantum-security version of a result by Andreeva, Daemen, Mennink, and Van Assche (FSE’15) which shows that a sponge that uses a secure PRP or PRF as internal function is a secure PRF. This result also proves that the recent attacks against CBC-MAC in the quantum-access model by Kaplan, Leurent, Leverrier, and Naya-Plasencia (Crypto’16) and Santoli, and Schaffner (QIC’16) can be prevented by introducing a state with a non-trivial inner part.The proof of our main result is derived by analyzing the joint distribution of anyqinput-output pairs. Our method analyzes the statistical behavior of the considered construction in great detail. The used techniques might prove useful in future analysis of different cryptographic primitives considering quantum adversaries. Using Zhandry’s PRF/PRP switching lemma we then obtain that quantum indistinguishability also holds if the internal block function is a random permutation.