Perfectly-Secure Multiplication for Any t < n/3 View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Gilad Asharov , Yehuda Lindell , Tal Rabin

ABSTRACT

In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. The most technically challenging part of this result is a protocol for multiplying two shared values, with perfect security in the presence of up to t < n/3 malicious adversaries.In this paper we provide a full specification of the BGW perfect multiplication protocol and prove its security. This includes one new step for the perfect multiplication protocol in the case of n/4 ≤ t < n/3. As in the original BGW protocol, this protocol works whenever the parties hold univariate (Shamir) shares of the input values. In addition, we present a new multiplication protocol that utilizes bivariate secret sharing in order to achieve higher efficiency while maintaining a round complexity that is constant per multiplication. Both of our protocols are presented with full proofs of security. More... »

PAGES

240-258

Book

TITLE

Advances in Cryptology – CRYPTO 2011

ISBN

978-3-642-22791-2
978-3-642-22792-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22792-9_14

DOI

http://dx.doi.org/10.1007/978-3-642-22792-9_14

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1051181479


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bar-Ilan University, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Bar-Ilan University, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Asharov", 
        "givenName": "Gilad", 
        "id": "sg:person.016347606461.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bar-Ilan University, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Bar-Ilan University, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lindell", 
        "givenName": "Yehuda", 
        "id": "sg:person.013115472057.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115472057.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J.\u00a0Watson Research, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM T.J.\u00a0Watson Research, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. The most technically challenging part of this result is a protocol for multiplying two shared values, with perfect security in the presence of up to t\u2009<\u2009n/3 malicious adversaries.In this paper we provide a full specification of the BGW perfect multiplication protocol and prove its security. This includes one new step for the perfect multiplication protocol in the case of n/4\u2009\u2264\u2009t\u2009<\u2009n/3. As in the original BGW protocol, this protocol works whenever the parties hold univariate (Shamir) shares of the input values. In addition, we present a new multiplication protocol that utilizes bivariate secret sharing in order to achieve higher efficiency while maintaining a round complexity that is constant per multiplication. Both of our protocols are presented with full proofs of security.", 
    "editor": [
      {
        "familyName": "Rogaway", 
        "givenName": "Phillip", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22792-9_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22791-2", 
        "978-3-642-22792-9"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "perfect security", 
      "multiplication protocol", 
      "secure multiparty computation", 
      "multiparty computation", 
      "secure computation", 
      "secure multiplication", 
      "malicious adversaries", 
      "secret sharing", 
      "private inputs", 
      "round complexity", 
      "Ben-Or", 
      "security", 
      "n parties", 
      "full specification", 
      "challenging part", 
      "input values", 
      "computation", 
      "full proof", 
      "functionality", 
      "protocol", 
      "channel model", 
      "adversary", 
      "Goldwasser", 
      "sharing", 
      "input", 
      "multiplication", 
      "Wigderson", 
      "specification", 
      "complexity", 
      "new step", 
      "information", 
      "set", 
      "parties", 
      "fundamental results", 
      "high efficiency", 
      "proof", 
      "efficiency", 
      "step", 
      "model", 
      "order", 
      "results", 
      "share", 
      "part", 
      "setting", 
      "values", 
      "cases", 
      "addition", 
      "presence", 
      "paper"
    ], 
    "name": "Perfectly-Secure Multiplication for Any t < n/3", 
    "pagination": "240-258", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051181479"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22792-9_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22792-9_14", 
      "https://app.dimensions.ai/details/publication/pub.1051181479"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_36.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22792-9_14"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22792-9_14'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22792-9_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22792-9_14'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22792-9_14'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      23 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22792-9_14 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Naea2d4082cdc45f6a2e8e62c831a5dcf
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. The most technically challenging part of this result is a protocol for multiplying two shared values, with perfect security in the presence of up to t < n/3 malicious adversaries.In this paper we provide a full specification of the BGW perfect multiplication protocol and prove its security. This includes one new step for the perfect multiplication protocol in the case of n/4 ≤ t < n/3. As in the original BGW protocol, this protocol works whenever the parties hold univariate (Shamir) shares of the input values. In addition, we present a new multiplication protocol that utilizes bivariate secret sharing in order to achieve higher efficiency while maintaining a round complexity that is constant per multiplication. Both of our protocols are presented with full proofs of security.
7 schema:editor Nfe54f213ba7f4e4f87e1776b0ae5a365
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf5fbe81b31f94f0aaa44a580205dd38e
12 schema:keywords Ben-Or
13 Goldwasser
14 Wigderson
15 addition
16 adversary
17 cases
18 challenging part
19 channel model
20 complexity
21 computation
22 efficiency
23 full proof
24 full specification
25 functionality
26 fundamental results
27 high efficiency
28 information
29 input
30 input values
31 malicious adversaries
32 model
33 multiparty computation
34 multiplication
35 multiplication protocol
36 n parties
37 new step
38 order
39 paper
40 part
41 parties
42 perfect security
43 presence
44 private inputs
45 proof
46 protocol
47 results
48 round complexity
49 secret sharing
50 secure computation
51 secure multiparty computation
52 secure multiplication
53 security
54 set
55 setting
56 share
57 sharing
58 specification
59 step
60 values
61 schema:name Perfectly-Secure Multiplication for Any t < n/3
62 schema:pagination 240-258
63 schema:productId N219d29735fe944bba6810de00e6848b8
64 N22d43244a028461fa5d8225e6d095e0d
65 schema:publisher N94956fb85e434043bf57a6c909565a3f
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051181479
67 https://doi.org/10.1007/978-3-642-22792-9_14
68 schema:sdDatePublished 2022-05-20T07:46
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N220eb9d76ce149108d0e60463ad24e8d
71 schema:url https://doi.org/10.1007/978-3-642-22792-9_14
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N14b8313a871a42ef8455aa63b509e50d rdf:first sg:person.013115472057.35
76 rdf:rest Nee1c742511a441f3a62091191fdece50
77 N219d29735fe944bba6810de00e6848b8 schema:name dimensions_id
78 schema:value pub.1051181479
79 rdf:type schema:PropertyValue
80 N220eb9d76ce149108d0e60463ad24e8d schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 N22d43244a028461fa5d8225e6d095e0d schema:name doi
83 schema:value 10.1007/978-3-642-22792-9_14
84 rdf:type schema:PropertyValue
85 N94956fb85e434043bf57a6c909565a3f schema:name Springer Nature
86 rdf:type schema:Organisation
87 Naea2d4082cdc45f6a2e8e62c831a5dcf rdf:first sg:person.016347606461.90
88 rdf:rest N14b8313a871a42ef8455aa63b509e50d
89 Nc5b2bf7d6bb64834bbd04c263d5522bd schema:familyName Rogaway
90 schema:givenName Phillip
91 rdf:type schema:Person
92 Nee1c742511a441f3a62091191fdece50 rdf:first sg:person.015473523512.58
93 rdf:rest rdf:nil
94 Nf5fbe81b31f94f0aaa44a580205dd38e schema:isbn 978-3-642-22791-2
95 978-3-642-22792-9
96 schema:name Advances in Cryptology – CRYPTO 2011
97 rdf:type schema:Book
98 Nfe54f213ba7f4e4f87e1776b0ae5a365 rdf:first Nc5b2bf7d6bb64834bbd04c263d5522bd
99 rdf:rest rdf:nil
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
104 schema:name Data Format
105 rdf:type schema:DefinedTerm
106 sg:person.013115472057.35 schema:affiliation grid-institutes:grid.22098.31
107 schema:familyName Lindell
108 schema:givenName Yehuda
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115472057.35
110 rdf:type schema:Person
111 sg:person.015473523512.58 schema:affiliation grid-institutes:None
112 schema:familyName Rabin
113 schema:givenName Tal
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
115 rdf:type schema:Person
116 sg:person.016347606461.90 schema:affiliation grid-institutes:grid.22098.31
117 schema:familyName Asharov
118 schema:givenName Gilad
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90
120 rdf:type schema:Person
121 grid-institutes:None schema:alternateName IBM T.J. Watson Research, USA
122 schema:name IBM T.J. Watson Research, USA
123 rdf:type schema:Organization
124 grid-institutes:grid.22098.31 schema:alternateName Bar-Ilan University, Israel
125 schema:name Bar-Ilan University, Israel
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...