On the possibility of one-message weak zero-knowledge
2004 (English)In: THEORY OF CRYPTOGRAPHY, PROCEEDINGS / [ed] Naor, M, BERLIN: SPRINGER , 2004, Vol. 2951, 121-132 p.Conference paper (Refereed)
We investigate whether it is possible to obtain any meaningful type of zero-knowledge proofs using a one-message (i.e., noninteractive) proof system. We show that, under reasonable (although not standard) assumptions, there exists a one-message proof system for every language in NP that satisfies the following relaxed form of zero knowledge: 1. The soundness condition holds only against cheating provers that run in uniform (rather than non-uniform) probabilistic polynomial-time. 2. The zero-knowledge condition is obtained using a simulator that runs in quasi-polynomial (rather than polynomial) time. We note that it is necessary to introduce both relaxations to obtain a one-message system for a non-trivial language. We stress that our result is in the plain model, and in particular we do not assume any setup conditions (such as the existence of a shared random string). We also discuss the validity of our assumption, and show two conditions that imply it. In addition, we show that an assumption of a similar kind is necessary in order to obtain a one-message system that satisfies some sort of meaningful zero-knowledge and soundness conditions.
Place, publisher, year, edition, pages
BERLIN: SPRINGER , 2004. Vol. 2951, 121-132 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 2951
IdentifiersURN: urn:nbn:se:kth:diva-43985ISI: 000189415300007ScopusID: 2-s2.0-35048855117ISBN: 3-540-21000-8OAI: oai:DiVA.org:kth-43985DiVA: diva2:450876
1st Theory of Cryptography Conference (TCC 2004). MIT, Cambridge, MA. FEB 19-21, 2004
QC 201110242011-10-242011-10-192011-10-24Bibliographically approved