View in EDS PDF Full Text

From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back.

Saved in:
Bibliographic Details
Title: From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back.
Authors: Applebaum, Benny1 bennyap@post.tau.ac.il, Raykov, Pavel1 pavelraykov@post.tau.ac.il
Source: Journal of Cryptology. Oct2017, Vol. 30 Issue 4, p961-988. 28p.
Subjects: Zero-knowledge proofs, Technological complexity, Communication complexity (Information theory), Cryptography, Mathematics
Abstract: Göös et al. (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols ( $$\mathsf {ZAM}$$ ). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs x and y, respectively, and Merlin, the prover, attempts to convince them that some public function f evaluates to 1 on ( x, y). In addition to standard completeness and soundness, Göös et al., require a 'zero-knowledge' property which asserts that on each yes-input, the distribution of Merlin's proof leaks no information about the inputs ( x, y) to an external observer. In this paper, we relate this new notion to the well-studied model of Private Simultaneous Messages ( $$\mathsf {PSM}$$ ) that was originally suggested by Feige et al. (STOC, 1994). Roughly speaking, we show that the randomness complexity of $$\mathsf {ZAM}$$ corresponds to the communication complexity of $$\mathsf {PSM}$$ and that the communication complexity of $$\mathsf {ZAM}$$ corresponds to the randomness complexity of $$\mathsf {PSM}$$ . This relation works in both directions where different variants of $$\mathsf {PSM}$$ are being used. As a secondary contribution, we reveal new connections between different variants of $$\mathsf {PSM} $$ protocols which we believe to be of independent interest. Our results give rise to better $$\mathsf {ZAM}$$ protocols based on existing $$\mathsf {PSM}$$ protocols, and to better protocols for conditional disclosure of secrets (a variant of $$\mathsf {PSM}$$ ) from existing $$\mathsf {ZAM} $$ s. [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: 125186685
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Applebaum%2C+Benny%22">Applebaum, Benny</searchLink><relatesTo>1</relatesTo><i> bennyap@post.tau.ac.il</i><br /><searchLink fieldCode="AR" term="%22Raykov%2C+Pavel%22">Raykov, Pavel</searchLink><relatesTo>1</relatesTo><i> pavelraykov@post.tau.ac.il</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Cryptology%22">Journal of Cryptology</searchLink>. Oct2017, Vol. 30 Issue 4, p961-988. 28p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Zero-knowledge+proofs%22">Zero-knowledge proofs</searchLink><br /><searchLink fieldCode="DE" term="%22Technological+complexity%22">Technological complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Communication+complexity+%28Information+theory%29%22">Communication complexity (Information theory)</searchLink><br /><searchLink fieldCode="DE" term="%22Cryptography%22">Cryptography</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics%22">Mathematics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Göös et al. (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols ( $$\mathsf {ZAM}$$ ). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs x and y, respectively, and Merlin, the prover, attempts to convince them that some public function f evaluates to 1 on ( x, y). In addition to standard completeness and soundness, Göös et al., require a 'zero-knowledge' property which asserts that on each yes-input, the distribution of Merlin's proof leaks no information about the inputs ( x, y) to an external observer. In this paper, we relate this new notion to the well-studied model of Private Simultaneous Messages ( $$\mathsf {PSM}$$ ) that was originally suggested by Feige et al. (STOC, 1994). Roughly speaking, we show that the randomness complexity of $$\mathsf {ZAM}$$ corresponds to the communication complexity of $$\mathsf {PSM}$$ and that the communication complexity of $$\mathsf {ZAM}$$ corresponds to the randomness complexity of $$\mathsf {PSM}$$ . This relation works in both directions where different variants of $$\mathsf {PSM}$$ are being used. As a secondary contribution, we reveal new connections between different variants of $$\mathsf {PSM} $$ protocols which we believe to be of independent interest. Our results give rise to better $$\mathsf {ZAM}$$ protocols based on existing $$\mathsf {PSM}$$ protocols, and to better protocols for conditional disclosure of secrets (a variant of $$\mathsf {PSM}$$ ) from existing $$\mathsf {ZAM} $$ s. [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=125186685
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00145-016-9239-3
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 961
    Subjects:
      – SubjectFull: Zero-knowledge proofs
        Type: general
      – SubjectFull: Technological complexity
        Type: general
      – SubjectFull: Communication complexity (Information theory)
        Type: general
      – SubjectFull: Cryptography
        Type: general
      – SubjectFull: Mathematics
        Type: general
    Titles:
      – TitleFull: From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Applebaum, Benny
      – PersonEntity:
          Name:
            NameFull: Raykov, Pavel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 09332790
          Numbering:
            – Type: volume
              Value: 30
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Journal of Cryptology
              Type: main
ResultId 1