论文标题
自适应与静态多门算法，以及分键PRF的量子安全性
Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of a Split-key PRF
论文作者
论文摘要
在本文的第一部分中，我们展示了一个通用编译器，该编译器将可以适应多个Oracles查询的任何Oracle算法，即可以决定哪种Oracle查询在什么方面取决于先前的Oracle响应，并将其转变为静态算法，从而在执行开始时解决了这些选择。与实现这一目标的天真方法相比，我们的编译器分别控制着每个Oracle的查询复杂性的爆炸，并且仅引起非常轻微的爆炸。 在本文的第二部分中，我们使用我们的编译器在量子随机 - 轨道模型中使用Giacon，Heuer and Poettering提出的非常有效的基于HASH的分键PRF的安全性（PKC 2018）。使用分键PRF作为密钥衍生功能会产生安全的KEM组合仪。因此，我们的结果表明Giacon等人的基于哈希的构建。可以在量子攻击的背景下安全地使用，例如将良好的但经典的KEM与据信是量子安全的候选KEM结合在一起。 我们对拆分PRF的安全证明至关重要的是我们的自适应到静态编译器，但我们希望我们的编译器在此特定应用程序之外有用。的确，我们讨论了文献中本来可以从我们的编译器中获利的其他几个已知的结果，因为这些作品必须经过严重的并发症才能处理适应性。
In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow-up in query complexity for each oracle individually, and causes a very mild blow-up only. In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure. Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in order to deal with adaptivity.
