Serge Fehr: Security of the Fiat-Shamir Transformation in the Quantum Random Oracle Model
0Security of the Fiat-Shamir Transformation in the Quantum Random Oracle Model
In this presentation, I will first recall the Fiat-Shamir transformation, which is an important design principle for non-interactive zero-knowledge proofs and for digital signature schemes. In order to rigorously analyze the security of this transformation, one typically considers an idealized model, the so-called random oracle model (ROM), which treats cryptographic hash functions as ideal objects. It is well known that (in the ROM) the Fiat-Shamir transformation preserves the security properties one cares about. However, the proof for this result breaks down in the quantum setting where the attacker is allowed to make superposition queries to the random oracle. Indeed, the security of the Fiat-Shamir transformation against a quantum attack was largely open; only some limited results were know, and some negative claims were actually made in the literature. Having set up the stage, I will then discuss our recent result, which shows full-fledged security of the Fiat-Shamir transformation against quantum attacks, i.e., in the so-called quantum ROM. I will give some high-level intuition for our result, but will also go through the technical proof, which after all is quite simple. In the last part, I will briefly introduce a modification to a security definition for interactive proofs, which allows us to relativize a certain negative result, and which then makes our result on the Fiat-Shamir transformation relevant for a larger class of schemes.