Optimal Parameters for Efficient Two-Party Computation Protocols View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Chaya Ganesh , C. Pandu Rangan

ABSTRACT

We study the optimal parameters to minimize the cheating probability and communication complexity in protocols for two party computation secure against malicious adversaries. In cut-and-choose protocols for two party computation, we analyze the optimal parameters to keep the probability of undetected cheating minimum. We first study this for a constant number of circuits, and then generalize it to the case of constant bandwidth. More generally, the communication cost of opening a circuit is different from retaining the circuit for evaluation and we analyze the optimal parameters in this case, by fixing the total bits of communication. In the second part of our analysis, we minimize the communication complexity for a given probability of undetected cheating. We study, what should be the parameters to achieve a given cheating probability in minimum amount of communication in a given cut-and-choose protocol. While still keeping the security guarantees, that is, the cheating probability negligible, we achieve a concrete improvement in communication complexity by using optimal parameters in existing cut-and-choose protocols. More... »

PAGES

128-143

References to SciGraph publications

  • 2009-04. A Proof of Security of Yao’s Protocol for Two-Party Computation in JOURNAL OF CRYPTOLOGY
  • 2008. Efficient Two Party and Multi Party Computation Against Covert Adversaries in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2008
  • 2006. Efficiency Tradeoffs for Malicious Two-Party Computation in PUBLIC KEY CRYPTOGRAPHY - PKC 2006
  • 2007. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2007
  • 2007. Revisiting the Efficiency of Malicious Two-Party Computation in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2007
  • 2011. Two-Output Secure Computation with Malicious Adversaries in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2011
  • 2011. Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer in THEORY OF CRYPTOGRAPHY
  • Book

    TITLE

    Information Security Theory and Practice. Security, Privacy and Trust in Computing Systems and Ambient Intelligent Ecosystems

    ISBN

    978-3-642-30954-0
    978-3-642-30955-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-30955-7_12

    DOI

    http://dx.doi.org/10.1007/978-3-642-30955-7_12

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Madras", 
              "id": "https://www.grid.ac/institutes/grid.417969.4", 
              "name": [
                "Indian Institute of Technology, Madras, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ganesh", 
            "givenName": "Chaya", 
            "id": "sg:person.013404310066.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013404310066.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Madras", 
              "id": "https://www.grid.ac/institutes/grid.417969.4", 
              "name": [
                "Indian Institute of Technology, Madras, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rangan", 
            "givenName": "C. Pandu", 
            "id": "sg:person.016366027737.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-72540-4_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002329385", 
              "https://doi.org/10.1007/978-3-540-72540-4_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-008-9036-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009948846", 
              "https://doi.org/10.1007/s00145-008-9036-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-008-9036-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009948846", 
              "https://doi.org/10.1007/s00145-008-9036-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19571-6_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016941481", 
              "https://doi.org/10.1007/978-3-642-19571-6_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19571-6_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016941481", 
              "https://doi.org/10.1007/978-3-642-19571-6_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/28395.28420", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019059647"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019543573", 
              "https://doi.org/10.1007/978-3-540-78967-3_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019543573", 
              "https://doi.org/10.1007/978-3-540-78967-3_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11745853_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032239271", 
              "https://doi.org/10.1007/11745853_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11745853_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032239271", 
              "https://doi.org/10.1007/11745853_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-20465-4_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036943620", 
              "https://doi.org/10.1007/978-3-642-20465-4_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-20465-4_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036943620", 
              "https://doi.org/10.1007/978-3-642-20465-4_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-72540-4_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047728925", 
              "https://doi.org/10.1007/978-3-540-72540-4_5"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012", 
        "datePublishedReg": "2012-01-01", 
        "description": "We study the optimal parameters to minimize the cheating probability and communication complexity in protocols for two party computation secure against malicious adversaries. In cut-and-choose protocols for two party computation, we analyze the optimal parameters to keep the probability of undetected cheating minimum. We first study this for a constant number of circuits, and then generalize it to the case of constant bandwidth. More generally, the communication cost of opening a circuit is different from retaining the circuit for evaluation and we analyze the optimal parameters in this case, by fixing the total bits of communication. In the second part of our analysis, we minimize the communication complexity for a given probability of undetected cheating. We study, what should be the parameters to achieve a given cheating probability in minimum amount of communication in a given cut-and-choose protocol. While still keeping the security guarantees, that is, the cheating probability negligible, we achieve a concrete improvement in communication complexity by using optimal parameters in existing cut-and-choose protocols.", 
        "editor": [
          {
            "familyName": "Askoxylakis", 
            "givenName": "Ioannis", 
            "type": "Person"
          }, 
          {
            "familyName": "P\u00f6hls", 
            "givenName": "Henrich C.", 
            "type": "Person"
          }, 
          {
            "familyName": "Posegga", 
            "givenName": "Joachim", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-30955-7_12", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-30954-0", 
            "978-3-642-30955-7"
          ], 
          "name": "Information Security Theory and Practice. Security, Privacy and Trust in Computing Systems and Ambient Intelligent Ecosystems", 
          "type": "Book"
        }, 
        "name": "Optimal Parameters for Efficient Two-Party Computation Protocols", 
        "pagination": "128-143", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-30955-7_12"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b79ba8b6518352c295fdeccd5f1111dc6b038caa894da5689540e0a97ecbf03f"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1038544172"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-30955-7_12", 
          "https://app.dimensions.ai/details/publication/pub.1038544172"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T19:11", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8684_00000267.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-30955-7_12"
      }
    ]
     

    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-30955-7_12'

    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-30955-7_12'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-30955-7_12'

    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-30955-7_12'


     

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

    113 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-30955-7_12 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N7c3e473d0cf0458ea02c1e09063faaba
    4 schema:citation sg:pub.10.1007/11745853_30
    5 sg:pub.10.1007/978-3-540-72540-4_4
    6 sg:pub.10.1007/978-3-540-72540-4_5
    7 sg:pub.10.1007/978-3-540-78967-3_17
    8 sg:pub.10.1007/978-3-642-19571-6_20
    9 sg:pub.10.1007/978-3-642-20465-4_22
    10 sg:pub.10.1007/s00145-008-9036-8
    11 https://doi.org/10.1145/28395.28420
    12 schema:datePublished 2012
    13 schema:datePublishedReg 2012-01-01
    14 schema:description We study the optimal parameters to minimize the cheating probability and communication complexity in protocols for two party computation secure against malicious adversaries. In cut-and-choose protocols for two party computation, we analyze the optimal parameters to keep the probability of undetected cheating minimum. We first study this for a constant number of circuits, and then generalize it to the case of constant bandwidth. More generally, the communication cost of opening a circuit is different from retaining the circuit for evaluation and we analyze the optimal parameters in this case, by fixing the total bits of communication. In the second part of our analysis, we minimize the communication complexity for a given probability of undetected cheating. We study, what should be the parameters to achieve a given cheating probability in minimum amount of communication in a given cut-and-choose protocol. While still keeping the security guarantees, that is, the cheating probability negligible, we achieve a concrete improvement in communication complexity by using optimal parameters in existing cut-and-choose protocols.
    15 schema:editor N5701ab8334f041a59b49b8c7d31270cb
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf Ne472dd689e7047ba9d7a4092609f13fa
    20 schema:name Optimal Parameters for Efficient Two-Party Computation Protocols
    21 schema:pagination 128-143
    22 schema:productId N6fb04c279c2b4df4b3dfabf51f1f44f0
    23 Ne63cfbec1e0346e6b1938297a7ff744e
    24 Nfae3c2e8eb444d26bed163268616d52f
    25 schema:publisher N07bcff5eab414d488a0b7d517bb46cc8
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038544172
    27 https://doi.org/10.1007/978-3-642-30955-7_12
    28 schema:sdDatePublished 2019-04-15T19:11
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N642c05542616469ebf60eefec8a22d48
    31 schema:url http://link.springer.com/10.1007/978-3-642-30955-7_12
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N07bcff5eab414d488a0b7d517bb46cc8 schema:location Berlin, Heidelberg
    36 schema:name Springer Berlin Heidelberg
    37 rdf:type schema:Organisation
    38 N30f69c9fa89d4015bd6c738d742cdde0 schema:familyName Askoxylakis
    39 schema:givenName Ioannis
    40 rdf:type schema:Person
    41 N3327c219a29f4e8d8a6cbf5a4b9c33d9 schema:familyName Pöhls
    42 schema:givenName Henrich C.
    43 rdf:type schema:Person
    44 N5701ab8334f041a59b49b8c7d31270cb rdf:first N30f69c9fa89d4015bd6c738d742cdde0
    45 rdf:rest N7b4cd1d7e34e4b53a6e64662414ade79
    46 N642c05542616469ebf60eefec8a22d48 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N6fb04c279c2b4df4b3dfabf51f1f44f0 schema:name doi
    49 schema:value 10.1007/978-3-642-30955-7_12
    50 rdf:type schema:PropertyValue
    51 N76bb3e91d976444d9567fba92ee7f6f6 rdf:first sg:person.016366027737.61
    52 rdf:rest rdf:nil
    53 N7b4cd1d7e34e4b53a6e64662414ade79 rdf:first N3327c219a29f4e8d8a6cbf5a4b9c33d9
    54 rdf:rest Nd520a3f262114cdb9d840c6f21663cd8
    55 N7c3e473d0cf0458ea02c1e09063faaba rdf:first sg:person.013404310066.02
    56 rdf:rest N76bb3e91d976444d9567fba92ee7f6f6
    57 Nc4e50f17b1ae4486973cb5e97ed7ad5d schema:familyName Posegga
    58 schema:givenName Joachim
    59 rdf:type schema:Person
    60 Nd520a3f262114cdb9d840c6f21663cd8 rdf:first Nc4e50f17b1ae4486973cb5e97ed7ad5d
    61 rdf:rest rdf:nil
    62 Ne472dd689e7047ba9d7a4092609f13fa schema:isbn 978-3-642-30954-0
    63 978-3-642-30955-7
    64 schema:name Information Security Theory and Practice. Security, Privacy and Trust in Computing Systems and Ambient Intelligent Ecosystems
    65 rdf:type schema:Book
    66 Ne63cfbec1e0346e6b1938297a7ff744e schema:name readcube_id
    67 schema:value b79ba8b6518352c295fdeccd5f1111dc6b038caa894da5689540e0a97ecbf03f
    68 rdf:type schema:PropertyValue
    69 Nfae3c2e8eb444d26bed163268616d52f schema:name dimensions_id
    70 schema:value pub.1038544172
    71 rdf:type schema:PropertyValue
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Data Format
    77 rdf:type schema:DefinedTerm
    78 sg:person.013404310066.02 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
    79 schema:familyName Ganesh
    80 schema:givenName Chaya
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013404310066.02
    82 rdf:type schema:Person
    83 sg:person.016366027737.61 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
    84 schema:familyName Rangan
    85 schema:givenName C. Pandu
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61
    87 rdf:type schema:Person
    88 sg:pub.10.1007/11745853_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032239271
    89 https://doi.org/10.1007/11745853_30
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/978-3-540-72540-4_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002329385
    92 https://doi.org/10.1007/978-3-540-72540-4_4
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-540-72540-4_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047728925
    95 https://doi.org/10.1007/978-3-540-72540-4_5
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-540-78967-3_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019543573
    98 https://doi.org/10.1007/978-3-540-78967-3_17
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-642-19571-6_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016941481
    101 https://doi.org/10.1007/978-3-642-19571-6_20
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-3-642-20465-4_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036943620
    104 https://doi.org/10.1007/978-3-642-20465-4_22
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/s00145-008-9036-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009948846
    107 https://doi.org/10.1007/s00145-008-9036-8
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/28395.28420 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019059647
    110 rdf:type schema:CreativeWork
    111 https://www.grid.ac/institutes/grid.417969.4 schema:alternateName Indian Institute of Technology Madras
    112 schema:name Indian Institute of Technology, Madras, India
    113 rdf:type schema:Organization
     




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


    ...