View in EDS PDF Full Text

On the Amortized Complexity of Zero-Knowledge Protocols.

Saved in:
Bibliographic Details
Title: On the Amortized Complexity of Zero-Knowledge Protocols.
Authors: Cramer, Ronald cramer@cwi.nl, Damgård, Ivan1 ivan@cs.au.dk, Keller, Marcel2 m.keller@bristol.ac.uk
Source: Journal of Cryptology. Spring2014, Vol. 27 Issue 2, p284-316. 33p.
Subjects: Zero-knowledge proofs, Computer network protocols, Computational complexity, Probability theory, Logarithms, Error analysis in mathematics
Abstract: We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance x and error probability 2 was O(| x| n) bits. By using our technique to prove n instances simultaneously, we can bring down the proof size per instance to O(| x|+ n) bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols as Σ-protocols and extend them later to zero-knowledge proofs of knowledge. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Cryptology is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 94834344
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Amortized Complexity of Zero-Knowledge Protocols.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Cramer%2C+Ronald%22">Cramer, Ronald</searchLink><i> cramer@cwi.nl</i><br /><searchLink fieldCode="AR" term="%22Damgård%2C+Ivan%22">Damgård, Ivan</searchLink><relatesTo>1</relatesTo><i> ivan@cs.au.dk</i><br /><searchLink fieldCode="AR" term="%22Keller%2C+Marcel%22">Keller, Marcel</searchLink><relatesTo>2</relatesTo><i> m.keller@bristol.ac.uk</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Cryptology%22">Journal of Cryptology</searchLink>. Spring2014, Vol. 27 Issue 2, p284-316. 33p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Zero-knowledge+proofs%22">Zero-knowledge proofs</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+network+protocols%22">Computer network protocols</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+theory%22">Probability theory</searchLink><br /><searchLink fieldCode="DE" term="%22Logarithms%22">Logarithms</searchLink><br /><searchLink fieldCode="DE" term="%22Error+analysis+in+mathematics%22">Error analysis in mathematics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance x and error probability 2 was O(| x| n) bits. By using our technique to prove n instances simultaneously, we can bring down the proof size per instance to O(| x|+ n) bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols as Σ-protocols and extend them later to zero-knowledge proofs of knowledge. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Cryptology is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=94834344
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00145-013-9145-x
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 33
        StartPage: 284
    Subjects:
      – SubjectFull: Zero-knowledge proofs
        Type: general
      – SubjectFull: Computer network protocols
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Probability theory
        Type: general
      – SubjectFull: Logarithms
        Type: general
      – SubjectFull: Error analysis in mathematics
        Type: general
    Titles:
      – TitleFull: On the Amortized Complexity of Zero-Knowledge Protocols.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Cramer, Ronald
      – PersonEntity:
          Name:
            NameFull: Damgård, Ivan
      – PersonEntity:
          Name:
            NameFull: Keller, Marcel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Spring2014
              Type: published
              Y: 2014
          Identifiers:
            – Type: issn-print
              Value: 09332790
          Numbering:
            – Type: volume
              Value: 27
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Journal of Cryptology
              Type: main
ResultId 1