Change search
ReferencesLink to record
Permanent link

Direct link
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)
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-43985ISI: 000189415300007ScopusID: 2-s2.0-35048855117ISBN: 3-540-21000-8OAI: diva2:450876
1st Theory of Cryptography Conference (TCC 2004). MIT, Cambridge, MA. FEB 19-21, 2004
QC 20111024Available from: 2011-10-24 Created: 2011-10-19 Last updated: 2011-10-24Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Pass, Rafael
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 6 hits
ReferencesLink to record
Permanent link

Direct link