#### QuICS Seminar

QuICS Seminar

Speaker:

Serge Fehr (CWI-Amsterdam)

Time:

Wednesday, March 27, 2019 - 11:00am

Location:

ATL 3100A

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.