Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the possibility of one-message weak zero-knowledge
KTH.
2004 (English)In: THEORY OF CRYPTOGRAPHY, PROCEEDINGS / [ed] Naor, M, BERLIN: SPRINGER , 2004, Vol. 2951, 121-132 p.Conference paper, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 2951
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-43985ISI: 000189415300007Scopus ID: 2-s2.0-35048855117ISBN: 3-540-21000-8 (print)OAI: oai:DiVA.org:kth-43985DiVA: diva2:450876
Conference
1st Theory of Cryptography Conference (TCC 2004). MIT, Cambridge, MA. FEB 19-21, 2004
Note
QC 20111024Available from: 2011-10-24 Created: 2011-10-19 Last updated: 2011-10-24Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Pass, Rafael
By organisation
KTH
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf