View in EDS

PERFECT SECURE COMPUTATION IN TWO ROUNDS.

Saved in:
Bibliographic Details
Title: PERFECT SECURE COMPUTATION IN TWO ROUNDS.
Authors: APPLEBAUM, BENNY1 bennyap@post.tau.ac.il, BRAKERSKI, ZVIKA2 zvika.brakerski@weizmann.ac.il, TSABARY, ROTEM2 rotem.tsabary@weizmann.ac.il
Source: SIAM Journal on Computing. 2021, Vol. 50 Issue 1, p68-97. 30p.
Subjects: IEEE Computer Society, Computer science, Information-theoretic security, Open-ended questions, Cybernetics, Polynomials
Abstract: We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the ma jority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The protocol is efficient for NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f. We further introduce a new notion of effective degree, and show that the round complexity of a functionality f is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics 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 Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 149427330
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: PERFECT SECURE COMPUTATION IN TWO ROUNDS.
– 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="%22BRAKERSKI%2C+ZVIKA%22">BRAKERSKI, ZVIKA</searchLink><relatesTo>2</relatesTo><i> zvika.brakerski@weizmann.ac.il</i><br /><searchLink fieldCode="AR" term="%22TSABARY%2C+ROTEM%22">TSABARY, ROTEM</searchLink><relatesTo>2</relatesTo><i> rotem.tsabary@weizmann.ac.il</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2021, Vol. 50 Issue 1, p68-97. 30p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22IEEE+Computer+Society%22">IEEE Computer Society</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+science%22">Computer science</searchLink><br /><searchLink fieldCode="DE" term="%22Information-theoretic+security%22">Information-theoretic security</searchLink><br /><searchLink fieldCode="DE" term="%22Open-ended+questions%22">Open-ended questions</searchLink><br /><searchLink fieldCode="DE" term="%22Cybernetics%22">Cybernetics</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the ma jority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The protocol is efficient for NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294-304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f. We further introduce a new notion of effective degree, and show that the round complexity of a functionality f is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics 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=149427330
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/19M1272044
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 30
        StartPage: 68
    Subjects:
      – SubjectFull: IEEE Computer Society
        Type: general
      – SubjectFull: Computer science
        Type: general
      – SubjectFull: Information-theoretic security
        Type: general
      – SubjectFull: Open-ended questions
        Type: general
      – SubjectFull: Cybernetics
        Type: general
      – SubjectFull: Polynomials
        Type: general
    Titles:
      – TitleFull: PERFECT SECURE COMPUTATION IN TWO ROUNDS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: APPLEBAUM, BENNY
      – PersonEntity:
          Name:
            NameFull: BRAKERSKI, ZVIKA
      – PersonEntity:
          Name:
            NameFull: TSABARY, ROTEM
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: 2021
              Type: published
              Y: 2021
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 50
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1