Scrutinizing Black-Box Separations in (Quantum) Cryptography

如今，新密码协议的设计需要(A)基于已知原语(如签名和加密方案)来描述构造，以及(B)假定底层原语的安全性，来证明构造满足期望的安全目标。第二步(B)通常是通过简化来执行的，这表明任何破坏新结构的对手都可以用来破坏底层原语。假设原语是安全的，反之亦然，这意味着不可能有这样的对手，并且构造是安全的。密码还原通常是一种特殊的类型，称为黑盒还原。这种约简没有利用潜在对手或原语的内部属性，而只是通过它们的输入/输出行为来考虑它们。关于这种黑盒归约存在的任何不可能结果称为黑盒分离。FI 940/4-1提案澄清了关于这种黑盒约简的权力和限制的一些重要问题，但关于黑盒约简和非黑盒约简的区分的粒度的一些问题仍然悬而未决。这里的更新提议的目的是澄清黑盒约简的权力关于干预对手的内部属性的能力。原始人。第一个目标是探索学习甚至设定对手的随机输入磁带的还原的可能性；这种还原在某种程度上介于黑盒和非黑盒类型之间。这可能允许绕过之前给出的黑盒分离结果。第二个目标是用图表表示非均匀机器模型中不同类型的黑盒简化，并将它们与统一计算模型联系起来。这将澄清这样一个问题，即非一致归约是否可以更有效，以及是否可以通过假设非一致安全基元来提供积极的结果。第三个目标是展示所谓的代数化技术的适用性，以提供与基元的使用有关的更强的分离结果。这将限制使用基元的非黑盒来绕过黑盒分隔的可能性。

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.