On the Impossibility of Tight Cryptographic Reductions
On the Impossibility of Tight Cryptographic Reductions
复制标题
DOI：
10.1007/978-3-662-49896-5_10
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Christoph Bader;Tibor Jager;Yong Li;Sven Schäge
中科院分区：
文献类型：
--
作者：
Christoph Bader;Tibor Jager;Yong Li;Sven Schäge
密码学安全证明中存在紧密约化问题是一个重要的问题，其动机是对安全保证真正独立于对抗行为的密码系统的理论探索，以及理论上合理的密码学参数选择的具体安全界的实际必要性。在2002年的Eurocrypt会议上，Coron描述了一种元约简技术，该技术可以证明某些数字签名方案不可能严格约简。这一开创性的结果发现了许多进一步有趣的应用。然而，由于争论中技术上的微妙之处，这种技术在单用户设置中除了数字签名之外的适用性是相当有限的。我们描述了一种新的元约简技术来证明这种不可能结果，它在几个方面改进了已知的结果。它支持有趣的新颖应用程序，包括正式证明，对于某些加密原语（包括公钥加密/密钥封装机制和数字签名），当原语从理想的单用户设置转移到更现实的多用户设置时，所产生的安全损失是不可避免的，并且非交互式密钥交换协议的较低密实度约束。此外，该技术允许从非常一般的非交互复杂性假设类别中排除紧密缩减。此外，证明和界限比Coron的技术及其扩展更简单。
The existence oftightreductions in cryptographic security proofs is an important question, motivated by the theoretical search for cryptosystems whose security guarantees are truly independent of adversarial behavior and the practical necessity of concrete security bounds for the theoretically-sound selection of cryptographic parameters. At Eurocrypt 2002, Coron described ameta-reductiontechnique that allows to prove theimpossibilityof tight reductions for certain digital signature schemes. This seminal result has found many further interesting applications. However, due to a technical subtlety in the argument, the applicability of this technique beyond digital signatures in thesingle-usersetting has turned out to be rather limited. We describe a new meta-reduction technique for proving such impossibility results, which improves on known ones in several ways. It enables interesting novel applications, including a formal proof that for certain cryptographic primitives (including public-key encryption/key encapsulation mechanisms and digital signatures), the security loss incurred when the primitive is transferred from an idealized single-user setting to the more realistic multi-user setting isimpossibleto avoid, and a lower tightness bound for non-interactive key exchange protocols. Moreover, the technique allows to rule out tight reductions from a very general class of non-interactive complexity assumptions. Furthermore, the proofs and bounds are simpler than in Coron’s technique and its extensions.