Degradation and Amplification of Computational Hardness View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Shai Halevi , Tal Rabin

ABSTRACT

What happens when you use a partially defective bit- commitment protocol to commit to the same bit many times? For example, suppose that the protocol allows the receiver to guess the committed bit with advantage , and that you used that protocol to commit to the same bit more than times. Or suppose that you encrypted some message many times (to many people), only to discover later that the encryption scheme that you were using is partially defective, and an eavesdropper has some noticeable advantage in guessing the encrypted message from the ciphertext. Can we at least show that even after many such encryptions, the eavesdropper could not have learned the message with certainty?In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for n times, the receiver’s advantage in guessing the encrypted bit is negligibly close to .Our results for hardness amplification follow just by observing that some of the known proofs for Yao’s lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch. More... »

PAGES

626-643

Book

TITLE

Theory of Cryptography

ISBN

978-3-540-78523-1
978-3-540-78524-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-78524-8_34

DOI

http://dx.doi.org/10.1007/978-3-540-78524-8_34

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, Hawthorne, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, Hawthorne, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "id": "sg:person.015100320721.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015100320721.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, Hawthorne, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, Hawthorne, NY, 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": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "What happens when you use a partially defective bit- commitment protocol to commit to the same bit many times? For example, suppose that the protocol allows the receiver to guess the committed bit with advantage , and that you used that protocol to commit to the same bit more than  times. Or suppose that you encrypted some message many times (to many people), only to discover later that the encryption scheme that you were using is partially defective, and an eavesdropper has some noticeable advantage in guessing the encrypted message from the ciphertext. Can we at least show that even after many such encryptions, the eavesdropper could not have learned the message with certainty?In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for n times, the receiver\u2019s advantage in guessing the encrypted bit is negligibly close to .Our results for hardness amplification follow just by observing that some of the known proofs for Yao\u2019s lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch.", 
    "editor": [
      {
        "familyName": "Canetti", 
        "givenName": "Ran", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-78524-8_34", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-78523-1", 
        "978-3-540-78524-8"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "computational hardness", 
      "interactive protocol", 
      "same bit", 
      "information-theoretic bounds", 
      "such encryption", 
      "encryption scheme", 
      "theoretic bounds", 
      "bit commitment protocol", 
      "messages", 
      "bits", 
      "hardness amplification", 
      "eavesdropper", 
      "generic setting", 
      "Yao\u2019s Lemma", 
      "noticeable advantages", 
      "protocol", 
      "encryption", 
      "ciphertext", 
      "advantages", 
      "scratch", 
      "scheme", 
      "example", 
      "proof", 
      "time", 
      "bounds", 
      "lemma", 
      "work", 
      "receiver", 
      "results", 
      "sequential repetition", 
      "look", 
      "hand", 
      "setting", 
      "hardness degradation", 
      "certainty", 
      "questions", 
      "repetition", 
      "cases", 
      "degradation", 
      "hardness", 
      "amplification"
    ], 
    "name": "Degradation and Amplification of Computational Hardness", 
    "pagination": "626-643", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022842874"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-78524-8_34"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-78524-8_34", 
      "https://app.dimensions.ai/details/publication/pub.1022842874"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "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_115.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-78524-8_34"
  }
]
 

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-540-78524-8_34'

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-540-78524-8_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-78524-8_34'

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-540-78524-8_34'


 

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

108 TRIPLES      23 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-78524-8_34 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nb75358123cd14b55af7d81b15d1b3199
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description What happens when you use a partially defective bit- commitment protocol to commit to the same bit many times? For example, suppose that the protocol allows the receiver to guess the committed bit with advantage , and that you used that protocol to commit to the same bit more than times. Or suppose that you encrypted some message many times (to many people), only to discover later that the encryption scheme that you were using is partially defective, and an eavesdropper has some noticeable advantage in guessing the encrypted message from the ciphertext. Can we at least show that even after many such encryptions, the eavesdropper could not have learned the message with certainty?In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for n times, the receiver’s advantage in guessing the encrypted bit is negligibly close to .Our results for hardness amplification follow just by observing that some of the known proofs for Yao’s lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch.
7 schema:editor N36bc0a67c3b549f3ba0f703a201d92c0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne45d918826c24884ae0dd24ba194fc53
12 schema:keywords Yao’s Lemma
13 advantages
14 amplification
15 bit commitment protocol
16 bits
17 bounds
18 cases
19 certainty
20 ciphertext
21 computational hardness
22 degradation
23 eavesdropper
24 encryption
25 encryption scheme
26 example
27 generic setting
28 hand
29 hardness
30 hardness amplification
31 hardness degradation
32 information-theoretic bounds
33 interactive protocol
34 lemma
35 look
36 messages
37 noticeable advantages
38 proof
39 protocol
40 questions
41 receiver
42 repetition
43 results
44 same bit
45 scheme
46 scratch
47 sequential repetition
48 setting
49 such encryption
50 theoretic bounds
51 time
52 work
53 schema:name Degradation and Amplification of Computational Hardness
54 schema:pagination 626-643
55 schema:productId N171acc34964744eba966624f37d7f53c
56 N2b01c3133e374bafb6796f9f37681323
57 schema:publisher Nf61628e334a44382a200290e41e150f7
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022842874
59 https://doi.org/10.1007/978-3-540-78524-8_34
60 schema:sdDatePublished 2022-05-20T07:41
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher Na0db334b026447d2854fbb3e9f1d2202
63 schema:url https://doi.org/10.1007/978-3-540-78524-8_34
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N171acc34964744eba966624f37d7f53c schema:name dimensions_id
68 schema:value pub.1022842874
69 rdf:type schema:PropertyValue
70 N2b01c3133e374bafb6796f9f37681323 schema:name doi
71 schema:value 10.1007/978-3-540-78524-8_34
72 rdf:type schema:PropertyValue
73 N36bc0a67c3b549f3ba0f703a201d92c0 rdf:first N8e69cb05d8624cd6a9be7c752e3eda56
74 rdf:rest rdf:nil
75 N8e69cb05d8624cd6a9be7c752e3eda56 schema:familyName Canetti
76 schema:givenName Ran
77 rdf:type schema:Person
78 Na0db334b026447d2854fbb3e9f1d2202 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 Nb75358123cd14b55af7d81b15d1b3199 rdf:first sg:person.015100320721.93
81 rdf:rest Nff0345e7576743e2937c817fe7718cc0
82 Ne45d918826c24884ae0dd24ba194fc53 schema:isbn 978-3-540-78523-1
83 978-3-540-78524-8
84 schema:name Theory of Cryptography
85 rdf:type schema:Book
86 Nf61628e334a44382a200290e41e150f7 schema:name Springer Nature
87 rdf:type schema:Organisation
88 Nff0345e7576743e2937c817fe7718cc0 rdf:first sg:person.015473523512.58
89 rdf:rest rdf:nil
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
94 schema:name Artificial Intelligence and Image Processing
95 rdf:type schema:DefinedTerm
96 sg:person.015100320721.93 schema:affiliation grid-institutes:grid.481554.9
97 schema:familyName Halevi
98 schema:givenName Shai
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015100320721.93
100 rdf:type schema:Person
101 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
102 schema:familyName Rabin
103 schema:givenName Tal
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
105 rdf:type schema:Person
106 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, Hawthorne, NY, USA
107 schema:name IBM T.J. Watson Research Center, Hawthorne, NY, USA
108 rdf:type schema:Organization
 




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


...