Ontology type: schema:Chapter Open Access: True
2006
AUTHORSMoni Naor , Gil Segev , Adam Smith
ABSTRACTWe address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to “manually” authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any 0 < ε< 1 there exists a log*n-round protocol for authenticating n-bit messages, in which only 2 log(1 /ε) + O(1) bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most ε to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of 2 log(1/ ε) – 6 on the required length of the manually authenticated string.The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. Once again, we apply our proof technique, and prove a lower bound of 2 log(1/ ε) – 2 on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO ’93).Finally, we prove that one-way functions are essential (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting. More... »
PAGES214-231
Advances in Cryptology - CRYPTO 2006
ISBN
978-3-540-37432-9
978-3-540-37433-6
http://scigraph.springernature.com/pub.10.1007/11818175_13
DOIhttp://dx.doi.org/10.1007/11818175_13
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1040061033
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/0804",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Data Format",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, 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 of Science, 76100, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Segev",
"givenName": "Gil",
"id": "sg:person.016423726453.97",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Smith",
"givenName": "Adam",
"id": "sg:person.013307226666.21",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21"
],
"type": "Person"
}
],
"datePublished": "2006",
"datePublishedReg": "2006-01-01",
"description": "We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to \u201cmanually\u201d authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any 0 < \u03b5< 1 there exists a log*n-round protocol for authenticating n-bit messages, in which only 2 log(1 /\u03b5) + O(1) bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most \u03b5 to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of 2 log(1/ \u03b5) \u2013 6 on the required length of the manually authenticated string.The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. Once again, we apply our proof technique, and prove a lower bound of 2 log(1/ \u03b5) \u2013 2 on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO \u201993).Finally, we prove that one-way functions are essential (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.",
"editor": [
{
"familyName": "Dwork",
"givenName": "Cynthia",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11818175_13",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-37432-9",
"978-3-540-37433-6"
],
"name": "Advances in Cryptology - CRYPTO 2006",
"type": "Book"
},
"keywords": [
"proof technique",
"lower bounds",
"tight bounds",
"Shannon entropy",
"computational setting",
"above lower bounds",
"bounds",
"different communication models",
"second model",
"first model",
"computational assumptions",
"one-way functions",
"auxiliary channel",
"open question",
"short secret key",
"existence of protocols",
"model",
"entropy",
"round protocol",
"communication model",
"strings",
"key model",
"bit message",
"probability",
"problem",
"assumption",
"existence",
"channels",
"technique",
"receiver",
"insecure channel",
"secret key",
"Naor",
"authentication problem",
"function",
"sender",
"bits",
"adversary",
"length",
"authentication model",
"authentication protocol",
"messages",
"key",
"setting",
"protocol",
"questions",
"short messages",
"fraudulent messages",
"manual channel",
"Gemmell"
],
"name": "Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models",
"pagination": "214-231",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1040061033"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11818175_13"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11818175_13",
"https://app.dimensions.ai/details/publication/pub.1040061033"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:53",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_449.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11818175_13"
}
]
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/11818175_13'
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/11818175_13'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11818175_13'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11818175_13'
This table displays all metadata directly associated to this object as RDF triples.
124 TRIPLES
23 PREDICATES
76 URIs
69 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/11818175_13 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0804 |
3 | ″ | schema:author | N88496dfab1b045b6ba456f6e4e3d8ef1 |
4 | ″ | schema:datePublished | 2006 |
5 | ″ | schema:datePublishedReg | 2006-01-01 |
6 | ″ | schema:description | We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to “manually” authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any 0 < ε< 1 there exists a log*n-round protocol for authenticating n-bit messages, in which only 2 log(1 /ε) + O(1) bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most ε to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of 2 log(1/ ε) – 6 on the required length of the manually authenticated string.The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. Once again, we apply our proof technique, and prove a lower bound of 2 log(1/ ε) – 2 on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO ’93).Finally, we prove that one-way functions are essential (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting. |
7 | ″ | schema:editor | N80bc5bedc29a4e9fa1285ed3355d2535 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | true |
11 | ″ | schema:isPartOf | N716bbfbb353741dfaee92358f14c0d55 |
12 | ″ | schema:keywords | Gemmell |
13 | ″ | ″ | Naor |
14 | ″ | ″ | Shannon entropy |
15 | ″ | ″ | above lower bounds |
16 | ″ | ″ | adversary |
17 | ″ | ″ | assumption |
18 | ″ | ″ | authentication model |
19 | ″ | ″ | authentication problem |
20 | ″ | ″ | authentication protocol |
21 | ″ | ″ | auxiliary channel |
22 | ″ | ″ | bit message |
23 | ″ | ″ | bits |
24 | ″ | ″ | bounds |
25 | ″ | ″ | channels |
26 | ″ | ″ | communication model |
27 | ″ | ″ | computational assumptions |
28 | ″ | ″ | computational setting |
29 | ″ | ″ | different communication models |
30 | ″ | ″ | entropy |
31 | ″ | ″ | existence |
32 | ″ | ″ | existence of protocols |
33 | ″ | ″ | first model |
34 | ″ | ″ | fraudulent messages |
35 | ″ | ″ | function |
36 | ″ | ″ | insecure channel |
37 | ″ | ″ | key |
38 | ″ | ″ | key model |
39 | ″ | ″ | length |
40 | ″ | ″ | lower bounds |
41 | ″ | ″ | manual channel |
42 | ″ | ″ | messages |
43 | ″ | ″ | model |
44 | ″ | ″ | one-way functions |
45 | ″ | ″ | open question |
46 | ″ | ″ | probability |
47 | ″ | ″ | problem |
48 | ″ | ″ | proof technique |
49 | ″ | ″ | protocol |
50 | ″ | ″ | questions |
51 | ″ | ″ | receiver |
52 | ″ | ″ | round protocol |
53 | ″ | ″ | second model |
54 | ″ | ″ | secret key |
55 | ″ | ″ | sender |
56 | ″ | ″ | setting |
57 | ″ | ″ | short messages |
58 | ″ | ″ | short secret key |
59 | ″ | ″ | strings |
60 | ″ | ″ | technique |
61 | ″ | ″ | tight bounds |
62 | ″ | schema:name | Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models |
63 | ″ | schema:pagination | 214-231 |
64 | ″ | schema:productId | N9eeccfdc7ff74912940a88656b6e9dad |
65 | ″ | ″ | Nad6ba2986e4b47258289a0af0b03a2b0 |
66 | ″ | schema:publisher | Nf0cba87f424449ddb1c280dd6c3b092a |
67 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1040061033 |
68 | ″ | ″ | https://doi.org/10.1007/11818175_13 |
69 | ″ | schema:sdDatePublished | 2022-05-10T10:53 |
70 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
71 | ″ | schema:sdPublisher | Nb278d90e35b5431e84101099dcf3c318 |
72 | ″ | schema:url | https://doi.org/10.1007/11818175_13 |
73 | ″ | sgo:license | sg:explorer/license/ |
74 | ″ | sgo:sdDataset | chapters |
75 | ″ | rdf:type | schema:Chapter |
76 | N389f7f5d84ed4820972a01ac66d5f6c9 | rdf:first | sg:person.013307226666.21 |
77 | ″ | rdf:rest | rdf:nil |
78 | N6acbc1268fec4e5bb4c84d52a946c7bf | rdf:first | sg:person.016423726453.97 |
79 | ″ | rdf:rest | N389f7f5d84ed4820972a01ac66d5f6c9 |
80 | N716bbfbb353741dfaee92358f14c0d55 | schema:isbn | 978-3-540-37432-9 |
81 | ″ | ″ | 978-3-540-37433-6 |
82 | ″ | schema:name | Advances in Cryptology - CRYPTO 2006 |
83 | ″ | rdf:type | schema:Book |
84 | N80bc5bedc29a4e9fa1285ed3355d2535 | rdf:first | Nb65a6ccd479a4e96aa49fe2ac2f27883 |
85 | ″ | rdf:rest | rdf:nil |
86 | N88496dfab1b045b6ba456f6e4e3d8ef1 | rdf:first | sg:person.07776170271.83 |
87 | ″ | rdf:rest | N6acbc1268fec4e5bb4c84d52a946c7bf |
88 | N9eeccfdc7ff74912940a88656b6e9dad | schema:name | doi |
89 | ″ | schema:value | 10.1007/11818175_13 |
90 | ″ | rdf:type | schema:PropertyValue |
91 | Nad6ba2986e4b47258289a0af0b03a2b0 | schema:name | dimensions_id |
92 | ″ | schema:value | pub.1040061033 |
93 | ″ | rdf:type | schema:PropertyValue |
94 | Nb278d90e35b5431e84101099dcf3c318 | schema:name | Springer Nature - SN SciGraph project |
95 | ″ | rdf:type | schema:Organization |
96 | Nb65a6ccd479a4e96aa49fe2ac2f27883 | schema:familyName | Dwork |
97 | ″ | schema:givenName | Cynthia |
98 | ″ | rdf:type | schema:Person |
99 | Nf0cba87f424449ddb1c280dd6c3b092a | schema:name | Springer Nature |
100 | ″ | rdf:type | schema:Organisation |
101 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
102 | ″ | schema:name | Information and Computing Sciences |
103 | ″ | rdf:type | schema:DefinedTerm |
104 | anzsrc-for:0804 | schema:inDefinedTermSet | anzsrc-for: |
105 | ″ | schema:name | Data Format |
106 | ″ | rdf:type | schema:DefinedTerm |
107 | sg:person.013307226666.21 | schema:affiliation | grid-institutes:grid.13992.30 |
108 | ″ | schema:familyName | Smith |
109 | ″ | schema:givenName | Adam |
110 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21 |
111 | ″ | rdf:type | schema:Person |
112 | sg:person.016423726453.97 | schema:affiliation | grid-institutes:grid.13992.30 |
113 | ″ | schema:familyName | Segev |
114 | ″ | schema:givenName | Gil |
115 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97 |
116 | ″ | rdf:type | schema:Person |
117 | sg:person.07776170271.83 | schema:affiliation | grid-institutes:grid.13992.30 |
118 | ″ | schema:familyName | Naor |
119 | ″ | schema:givenName | Moni |
120 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83 |
121 | ″ | rdf:type | schema:Person |
122 | grid-institutes:grid.13992.30 | schema:alternateName | Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel |
123 | ″ | schema:name | Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel |
124 | ″ | rdf:type | schema:Organization |