Scrutinizing Black-Box Separations in (Quantum) Cryptography

• Applicant: Professor Dr. Marc Fischlin
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 185457243

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.

• DFG Programme: Research Grants