Hardness Amplification of Weakly Verifiable Puzzles View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Ran Canetti , Shai Halevi , Michael Steiner

ABSTRACT

Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than ε, then no efficient algorithm can solve n independent puzzles simultaneously with probability more than εn. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single one.Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error. More... »

PAGES

17-33

Book

TITLE

Theory of Cryptography

ISBN

978-3-540-24573-5
978-3-540-30576-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30576-7_2

DOI

http://dx.doi.org/10.1007/978-3-540-30576-7_2

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "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": "Canetti", 
        "givenName": "Ran", 
        "id": "sg:person.012320111457.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74"
        ], 
        "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": "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": "Steiner", 
        "givenName": "Michael", 
        "id": "sg:person.011437622154.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011437622154.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than \u03b5, then no efficient algorithm can solve n independent puzzles simultaneously with probability more than \u03b5n. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single\u00a0one.Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error.", 
    "editor": [
      {
        "familyName": "Kilian", 
        "givenName": "Joe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30576-7_2", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24573-5", 
        "978-3-540-30576-7"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "one-way functions", 
      "verifiable puzzles", 
      "soundness error", 
      "efficient algorithm", 
      "parallel repetition", 
      "hardness amplification", 
      "candidate solutions", 
      "argument system", 
      "single instance", 
      "independent puzzles", 
      "independent instances", 
      "algorithm", 
      "Bellare", 
      "instances", 
      "proof", 
      "error", 
      "Naor", 
      "essential way", 
      "system", 
      "single puzzle", 
      "first results", 
      "solution", 
      "Impagliazzo", 
      "Yao", 
      "such puzzles", 
      "probability", 
      "second result", 
      "results", 
      "different answers", 
      "answers", 
      "way", 
      "parties", 
      "worse parameters", 
      "puzzle", 
      "adaptation", 
      "repetition", 
      "function", 
      "fact", 
      "cases", 
      "parameters", 
      "sound arguments", 
      "questions", 
      "reduction", 
      "argument", 
      "amplification"
    ], 
    "name": "Hardness Amplification of Weakly Verifiable Puzzles", 
    "pagination": "17-33", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047370291"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30576-7_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30576-7_2", 
      "https://app.dimensions.ai/details/publication/pub.1047370291"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_359.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30576-7_2"
  }
]
 

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-30576-7_2'

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-30576-7_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30576-7_2'

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-30576-7_2'


 

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

118 TRIPLES      22 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30576-7_2 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N5fcd20c367ad4ec5bcf1de756c8bc872
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than ε, then no efficient algorithm can solve n independent puzzles simultaneously with probability more than εn. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single one.Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error.
7 schema:editor N87d47bd087ff4fb48b9e2456454414b1
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N8f4fb810956545888877363fdc81ad4e
11 schema:keywords Bellare
12 Impagliazzo
13 Naor
14 Yao
15 adaptation
16 algorithm
17 amplification
18 answers
19 argument
20 argument system
21 candidate solutions
22 cases
23 different answers
24 efficient algorithm
25 error
26 essential way
27 fact
28 first results
29 function
30 hardness amplification
31 independent instances
32 independent puzzles
33 instances
34 one-way functions
35 parallel repetition
36 parameters
37 parties
38 probability
39 proof
40 puzzle
41 questions
42 reduction
43 repetition
44 results
45 second result
46 single instance
47 single puzzle
48 solution
49 sound arguments
50 soundness error
51 such puzzles
52 system
53 verifiable puzzles
54 way
55 worse parameters
56 schema:name Hardness Amplification of Weakly Verifiable Puzzles
57 schema:pagination 17-33
58 schema:productId Nb783b4881c894565b44e96e9de8cbcc7
59 Nee680c2b272b44638b6d2d2e4a317b19
60 schema:publisher N618de82c5ea34f5fa43c17650edaa72c
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047370291
62 https://doi.org/10.1007/978-3-540-30576-7_2
63 schema:sdDatePublished 2022-08-04T17:20
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N988040575fb9476580fda870b16b407b
66 schema:url https://doi.org/10.1007/978-3-540-30576-7_2
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N0be755487b3a448c8a63f1e1348e5d8b schema:familyName Kilian
71 schema:givenName Joe
72 rdf:type schema:Person
73 N5fcd20c367ad4ec5bcf1de756c8bc872 rdf:first sg:person.012320111457.74
74 rdf:rest Nd5c4280170664a6f8444498f74b39bbf
75 N618de82c5ea34f5fa43c17650edaa72c schema:name Springer Nature
76 rdf:type schema:Organisation
77 N87d47bd087ff4fb48b9e2456454414b1 rdf:first N0be755487b3a448c8a63f1e1348e5d8b
78 rdf:rest rdf:nil
79 N8f4fb810956545888877363fdc81ad4e schema:isbn 978-3-540-24573-5
80 978-3-540-30576-7
81 schema:name Theory of Cryptography
82 rdf:type schema:Book
83 N979542ff3e964592a67ef4d51ac2c1cd rdf:first sg:person.011437622154.42
84 rdf:rest rdf:nil
85 N988040575fb9476580fda870b16b407b schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 Nb783b4881c894565b44e96e9de8cbcc7 schema:name doi
88 schema:value 10.1007/978-3-540-30576-7_2
89 rdf:type schema:PropertyValue
90 Nd5c4280170664a6f8444498f74b39bbf rdf:first sg:person.015100320721.93
91 rdf:rest N979542ff3e964592a67ef4d51ac2c1cd
92 Nee680c2b272b44638b6d2d2e4a317b19 schema:name dimensions_id
93 schema:value pub.1047370291
94 rdf:type schema:PropertyValue
95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
96 schema:name Mathematical Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
99 schema:name Numerical and Computational Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.011437622154.42 schema:affiliation grid-institutes:grid.481554.9
102 schema:familyName Steiner
103 schema:givenName Michael
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011437622154.42
105 rdf:type schema:Person
106 sg:person.012320111457.74 schema:affiliation grid-institutes:grid.481554.9
107 schema:familyName Canetti
108 schema:givenName Ran
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74
110 rdf:type schema:Person
111 sg:person.015100320721.93 schema:affiliation grid-institutes:grid.481554.9
112 schema:familyName Halevi
113 schema:givenName Shai
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015100320721.93
115 rdf:type schema:Person
116 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, Hawthorne, NY, USA
117 schema:name IBM T.J. Watson Research Center, Hawthorne, NY, USA
118 rdf:type schema:Organization
 




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


...