Ontology type: schema:Chapter Open Access: True

2005

Ran Canetti , Shai Halevi , Michael Steiner

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... »

17-33

Theory of Cryptography

978-3-540-24573-5

978-3-540-30576-7

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

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

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

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

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 | N07e41874fd76426aa26e88c99ad54f5b |

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 | N4ccdfb66ac13483581f846580e0184e5 |

8 | ″ | schema:genre | chapter |

9 | ″ | schema:isAccessibleForFree | true |

10 | ″ | schema:isPartOf | N86f2665750e3433e9118aa650b9efec4 |

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 | N1d96850cd6164242919fc6484a706348 |

59 | ″ | ″ | N9be6d808836146b08778a416be405e63 |

60 | ″ | schema:publisher | Nbaa86dd200314f8eafd67e8a138ebeda |

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 | Nab8fdc10ced54c86970d45a5a3585375 |

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 | N07e41874fd76426aa26e88c99ad54f5b | rdf:first | sg:person.012320111457.74 |

71 | ″ | rdf:rest | Nc8ad371102834d088bb3a4fcf3a76cd1 |

72 | N1d96850cd6164242919fc6484a706348 | schema:name | doi |

73 | ″ | schema:value | 10.1007/978-3-540-30576-7_2 |

74 | ″ | rdf:type | schema:PropertyValue |

75 | N3d7224a579324c8a845e0a8ecd540379 | rdf:first | sg:person.011437622154.42 |

76 | ″ | rdf:rest | rdf:nil |

77 | N4ccdfb66ac13483581f846580e0184e5 | rdf:first | Nf4a1b1ecae0444e5bf444feef16274e4 |

78 | ″ | rdf:rest | rdf:nil |

79 | N86f2665750e3433e9118aa650b9efec4 | 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 | N9be6d808836146b08778a416be405e63 | schema:name | dimensions_id |

84 | ″ | schema:value | pub.1047370291 |

85 | ″ | rdf:type | schema:PropertyValue |

86 | Nab8fdc10ced54c86970d45a5a3585375 | schema:name | Springer Nature - SN SciGraph project |

87 | ″ | rdf:type | schema:Organization |

88 | Nbaa86dd200314f8eafd67e8a138ebeda | schema:name | Springer Nature |

89 | ″ | rdf:type | schema:Organisation |

90 | Nc8ad371102834d088bb3a4fcf3a76cd1 | rdf:first | sg:person.015100320721.93 |

91 | ″ | rdf:rest | N3d7224a579324c8a845e0a8ecd540379 |

92 | Nf4a1b1ecae0444e5bf444feef16274e4 | schema:familyName | Kilian |

93 | ″ | schema:givenName | Joe |

94 | ″ | rdf:type | schema:Person |

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 |