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.