Completeness in Two-Party Secure Computation: A Computational View View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-05-24

AUTHORS

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

ABSTRACT

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols. The previous study of these questions was mainly conducted from an information theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally. More... »

PAGES

521-552

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00145-006-0346-4

DOI

http://dx.doi.org/10.1007/s00145-006-0346-4

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harnik", 
        "givenName": "Danny", 
        "id": "sg:person.011037626541.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037626541.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reingold", 
        "givenName": "Omer", 
        "id": "sg:person.012547246003.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012547246003.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DEAS, Harvard University, Cambridge, MA 02138, USA", 
          "id": "http://www.grid.ac/institutes/grid.38142.3c", 
          "name": [
            "DEAS, Harvard University, Cambridge, MA 02138, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rosen", 
        "givenName": "Alon", 
        "id": "sg:person.016463202715.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016463202715.80"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006-05-24", 
    "datePublishedReg": "2006-05-24", 
    "description": "A Secure Function Evaluation (SFE) of a two-variable function f(\u00b7,\u00b7) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither  party learns \"more than is necessary\". A rich body of work deals with the study of completeness for secure two-party computation. A function f is  complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE,  which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols. The previous study of these questions was mainly conducted from an information theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization  of the complete functions in this model as well.  More precisely, we present a computational criterion (called  computational row non-transitivity) for a function f to be complete for the asymmetric\ncase. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all \"nice\" functions as either complete or having SFE unconditionally.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00145-006-0346-4", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136278", 
        "issn": [
          "0933-2790", 
          "1432-1378"
        ], 
        "name": "Journal of Cryptology", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "19"
      }
    ], 
    "keywords": [
      "secure function evaluation", 
      "SFE protocols", 
      "computational setting", 
      "two-party computation", 
      "two-party secure computation", 
      "information theoretic point", 
      "secure computation", 
      "secure evaluation", 
      "study of completeness", 
      "input x", 
      "computational criteria", 
      "computational view", 
      "function evaluations", 
      "theoretic point", 
      "complete function", 
      "computation", 
      "protocol", 
      "rich body", 
      "combinatorial criterion", 
      "completeness", 
      "combinatorial properties", 
      "information", 
      "strong answer", 
      "parties", 
      "function f", 
      "view", 
      "negation", 
      "evaluation", 
      "work deals", 
      "answers", 
      "transitivity", 
      "deal", 
      "criteria", 
      "model", 
      "fundamental questions", 
      "function", 
      "setting", 
      "point", 
      "manner", 
      "rows", 
      "computational study", 
      "questions", 
      "form", 
      "cases", 
      "full characterization", 
      "properties", 
      "study", 
      "previous studies", 
      "body", 
      "major differences", 
      "characterization", 
      "differences", 
      "two-variable function f", 
      "efficient SFE protocols", 
      "computational row transitivity", 
      "row transitivity", 
      "simple SFE", 
      "computational row"
    ], 
    "name": "Completeness in Two-Party Secure Computation: A Computational View", 
    "pagination": "521-552", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038812161"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00145-006-0346-4"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00145-006-0346-4", 
      "https://app.dimensions.ai/details/publication/pub.1038812161"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_424.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00145-006-0346-4"
  }
]
 

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/s00145-006-0346-4'

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/s00145-006-0346-4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-006-0346-4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-006-0346-4'


 

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

140 TRIPLES      21 PREDICATES      83 URIs      75 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00145-006-0346-4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2010286dee1145bdbd072e611e89fb9c
4 schema:datePublished 2006-05-24
5 schema:datePublishedReg 2006-05-24
6 schema:description A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols. The previous study of these questions was mainly conducted from an information theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N0e7a3dbf2bc74776a427d5259e6c07e2
11 N9b88ac301daf4dc69dc89460816ef685
12 sg:journal.1136278
13 schema:keywords SFE protocols
14 answers
15 body
16 cases
17 characterization
18 combinatorial criterion
19 combinatorial properties
20 complete function
21 completeness
22 computation
23 computational criteria
24 computational row
25 computational row transitivity
26 computational setting
27 computational study
28 computational view
29 criteria
30 deal
31 differences
32 efficient SFE protocols
33 evaluation
34 form
35 full characterization
36 function
37 function evaluations
38 function f
39 fundamental questions
40 information
41 information theoretic point
42 input x
43 major differences
44 manner
45 model
46 negation
47 parties
48 point
49 previous studies
50 properties
51 protocol
52 questions
53 rich body
54 row transitivity
55 rows
56 secure computation
57 secure evaluation
58 secure function evaluation
59 setting
60 simple SFE
61 strong answer
62 study
63 study of completeness
64 theoretic point
65 transitivity
66 two-party computation
67 two-party secure computation
68 two-variable function f
69 view
70 work deals
71 schema:name Completeness in Two-Party Secure Computation: A Computational View
72 schema:pagination 521-552
73 schema:productId N6f9d78c589a34a82ab7b0a5864c8921e
74 N8c73595d1ff147a780696e90a6bac76e
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038812161
76 https://doi.org/10.1007/s00145-006-0346-4
77 schema:sdDatePublished 2022-01-01T18:16
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher Na33e82f38cd64c658f7bcee24dbfb440
80 schema:url https://doi.org/10.1007/s00145-006-0346-4
81 sgo:license sg:explorer/license/
82 sgo:sdDataset articles
83 rdf:type schema:ScholarlyArticle
84 N0e7a3dbf2bc74776a427d5259e6c07e2 schema:volumeNumber 19
85 rdf:type schema:PublicationVolume
86 N2010286dee1145bdbd072e611e89fb9c rdf:first sg:person.011037626541.00
87 rdf:rest Nb75fcf28e0094b9a8ef959e86b40e8ea
88 N6f9d78c589a34a82ab7b0a5864c8921e schema:name dimensions_id
89 schema:value pub.1038812161
90 rdf:type schema:PropertyValue
91 N78bee7de07184096828afe51181e8276 rdf:first sg:person.016463202715.80
92 rdf:rest rdf:nil
93 N7e4846c7c9e841ab86c71f14d6ea6dce rdf:first sg:person.012547246003.78
94 rdf:rest N78bee7de07184096828afe51181e8276
95 N8c73595d1ff147a780696e90a6bac76e schema:name doi
96 schema:value 10.1007/s00145-006-0346-4
97 rdf:type schema:PropertyValue
98 N9b88ac301daf4dc69dc89460816ef685 schema:issueNumber 4
99 rdf:type schema:PublicationIssue
100 Na33e82f38cd64c658f7bcee24dbfb440 schema:name Springer Nature - SN SciGraph project
101 rdf:type schema:Organization
102 Nb75fcf28e0094b9a8ef959e86b40e8ea rdf:first sg:person.07776170271.83
103 rdf:rest N7e4846c7c9e841ab86c71f14d6ea6dce
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
108 schema:name Computation Theory and Mathematics
109 rdf:type schema:DefinedTerm
110 sg:journal.1136278 schema:issn 0933-2790
111 1432-1378
112 schema:name Journal of Cryptology
113 schema:publisher Springer Nature
114 rdf:type schema:Periodical
115 sg:person.011037626541.00 schema:affiliation grid-institutes:grid.13992.30
116 schema:familyName Harnik
117 schema:givenName Danny
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037626541.00
119 rdf:type schema:Person
120 sg:person.012547246003.78 schema:affiliation grid-institutes:grid.13992.30
121 schema:familyName Reingold
122 schema:givenName Omer
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012547246003.78
124 rdf:type schema:Person
125 sg:person.016463202715.80 schema:affiliation grid-institutes:grid.38142.3c
126 schema:familyName Rosen
127 schema:givenName Alon
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016463202715.80
129 rdf:type schema:Person
130 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
131 schema:familyName Naor
132 schema:givenName Moni
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
134 rdf:type schema:Person
135 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel
136 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, 76100, Israel
137 rdf:type schema:Organization
138 grid-institutes:grid.38142.3c schema:alternateName DEAS, Harvard University, Cambridge, MA 02138, USA
139 schema:name DEAS, Harvard University, Cambridge, MA 02138, USA
140 rdf:type schema:Organization
 




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


...