On the Difficulty of Perfect NIZK with Adaptive Security
Speaker: Masayuki Abe , NTT
Date: April 21 2006
Time: 10:30AM to 12:00PM
Location: 32-G449 (Patil/Kiva)
Contact: Be Blackburn, 3-6098, imbe@mit.edu
The notion of non-interactive zero-knowledge (NIZK), introduced by
Blum, Feldman and Micali, is of fundamental importance in
cryptography. Despite the vast attention the concept of NIZK has
attracted since its introduction in the late 80's, one question has
remained open until recently: Is it possible to construct NIZK schemes
for any $\np$-language with {\em statistical} (or even {\em perfect})
ZK? Groth, Ostrovsky and Sahai recently proposed two elegant
constructions for perfect NIZK arguments for any $\np$-language
$L$.
However, their schemes achieve non-adaptive security, meaning security
against a dishonest prover that chooses the target instance \mbox{$x^*
\not\in L$} (for which he wants to fake a proof) {\em independent} of
the common reference string (CRS), or need strong non-standard
assumption to achieve adaptive security. But is such a strong
assumption inevitable in general?
In this talk, we show that using ``standard techniques'' it is not
possible to construct a statistical NIZK argument for an
$\np$-complete language with adaptive security unless \mbox{$\np \in
\ppoly$}. This is a joint work with Serge Fehr (CWI).
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in April 2006
