Scrutinizing Black-Box Separations in (Quantum) Cryptography

仔细研究（量子）密码学中的黑盒分离

• 批准号: 185457243
• 负责人: Professor Dr. Marc Fischlin
• 金额: --
• 依托单位: Forschungsgruppe Kryptographie und Komplexitätstheorie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2010
• 资助国家: 德国
• 起止时间: 2009-12-31 至 2014-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/185457243?language=en
• 关键词: Scrutinizing; Black; Box; Separations; Quantum

The design of new cryptographic protocols nowadays entails (a) the description of the construction based on known primitives (like signature and encryption schemes), and (b) a security proof that that the construction meets the desired security goals, assuming the security of the underlying primitives. The second step (b) is often carried out by a reduction, showing that any adversary breaking the new construction could be used to break the underlying primitives. Assuming that the primitives are secure, this vice versa implies that there cannot be such an adversary and that the construction is secure.Cryptographic reductions are often of a special type, called black-box reductions. Such reductions do not take advantage of the internal properties of the potential adversary or the primitives, but merely consider them via their input/output behavior. Any impossibility result about the existence of such black-box reduction is called a black-box separation. The proposal FI 940/4-1 has clarified some important issues regarding the power and limitations of such black-box reductions, and yet left open some issues concerning the granularity of the distinction between black-box and non-black-box reductions.The objectives of the renewal proposal here are to clarify the power of black-box reductions regarding the ability to interfere with the internal properties of the adversary resp. the primitive. The first objective is to explore the reduction's possibilities to learn, or even to set, the adversary's random input tape; such reductions are somewhat in between the black-box and non-black-box type. This would potentially allow for bypassing previously given black-box separation results. The second objective is to diagram different types of black-box reductions in the non-uniform machine model and to relate them to the uniform model of computation. This would clarify the question if non-uniform reductions can be more powerful and if one could, by assuming non-uniformly secure primitives, still provide positive results. The third objective is to show the applicability of the so-called algebrization technique to provide stronger separation results concerning the use of the primitives. This would limit the possibility of non-black-box usages of primitives to circumvent black-box separations.

如今，新的加密协议的设计需要（a）基于已知基础（例如签名和加密方案）的构建描述，以及（b）安全证明，假设构造符合所需的安全目标，则假设基础原始原始原始原始原始原始原始符合所需的安全目标。第二步（b）通常是通过减少来进行的，表明任何对手都可以使用新结构来打破基础的原语。假设原语是安全的，反之亦然，这意味着不可能有这样的对手，并且结构是安全的。切碎的减少通常是特殊类型的，称为黑盒降低。这种降低并不能利用潜在对手或原语的内部特性，而只是通过其输入/输出行为来考虑它们。关于这种黑盒还原的存在的任何不可能结果称为黑盒分离。提案FI 940/4-1阐明了有关此类黑盒减少的功能和局限性的一些重要问题，但仍留下了有关黑盒和非黑盒减少的区别粒度的一些问题，此处的更新预言的目标是在此处降低授权的能力，以阐明置于式属性的能力的力量。原始。第一个目的是探索减少的学习可能性，甚至设置对手的随机输入胶带；这样的减少在黑框和非黑色框类型之间有些介入。这有可能允许绕过先前给定的黑盒分离结果。第二个目标是在非统一机器模型中绘制不同类型的黑盒减少，并将其与统一的计算模型相关联。这将阐明一个问题是否可以更强大，并且通过假设不均匀的固定原始素仍然可以提供积极的结果，并且可以通过不均匀的降低。第三个目标是显示所谓的代数技术的适用性，以提供有关使用原始物质的更强的分离结果。这将限制原始盒非黑色盒子使用以绕开黑盒分离的可能性。