Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Moni Naor , Gil Segev , Adam Smith

ABSTRACT

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

PAGES

214-231

Book

TITLE

Advances in Cryptology - CRYPTO 2006

ISBN

978-3-540-37432-9
978-3-540-37433-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11818175_13

DOI

http://dx.doi.org/10.1007/11818175_13

DIMENSIONS

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


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/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": [
      "different communication models", 
      "first model", 
      "insecure channel", 
      "proof technique", 
      "second model", 
      "Shannon entropy", 
      "existence of protocols", 
      "above lower bounds", 
      "lower bounds", 
      "bounds", 
      "computational setting", 
      "tight bounds", 
      "message authentication problem", 
      "authentication problem", 
      "problem", 
      "communication model", 
      "model", 
      "sender", 
      "receiver", 
      "channels", 
      "auxiliary channel", 
      "short messages", 
      "messages", 
      "computational assumptions", 
      "assumption", 
      "round protocol", 
      "bit message", 
      "probability", 
      "fraudulent messages", 
      "technique", 
      "strings", 
      "authentication model", 
      "short secret key", 
      "secret key", 
      "entropy", 
      "open question", 
      "one-way functions", 
      "existence", 
      "authentication protocol", 
      "key model", 
      "setting", 
      "protocol", 
      "bits", 
      "adversary", 
      "length", 
      "key", 
      "questions", 
      "Gemmell", 
      "Naor", 
      "function", 
      "manual channel", 
      "low-bandwidth auxiliary channel", 
      "traditional message authentication model", 
      "message authentication model", 
      "Unconditional Authentication Protocols"
    ], 
    "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-01-01T19:06", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_108.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11818175_13"
  }
]
 

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

129 TRIPLES      23 PREDICATES      81 URIs      74 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 Ndd5d92f4ca2e451197e43266399b67be
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 N8e56b6cee3b847d88130366382e2dc9c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N811c4c42376e47ae989d2f6f5392d026
12 schema:keywords Gemmell
13 Naor
14 Shannon entropy
15 Unconditional Authentication Protocols
16 above lower bounds
17 adversary
18 assumption
19 authentication model
20 authentication problem
21 authentication protocol
22 auxiliary channel
23 bit message
24 bits
25 bounds
26 channels
27 communication model
28 computational assumptions
29 computational setting
30 different communication models
31 entropy
32 existence
33 existence of protocols
34 first model
35 fraudulent messages
36 function
37 insecure channel
38 key
39 key model
40 length
41 low-bandwidth auxiliary channel
42 lower bounds
43 manual channel
44 message authentication model
45 message authentication problem
46 messages
47 model
48 one-way functions
49 open question
50 probability
51 problem
52 proof technique
53 protocol
54 questions
55 receiver
56 round protocol
57 second model
58 secret key
59 sender
60 setting
61 short messages
62 short secret key
63 strings
64 technique
65 tight bounds
66 traditional message authentication model
67 schema:name Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models
68 schema:pagination 214-231
69 schema:productId N764a99ecf73743e3a521f21c85e04397
70 N93abe8dd0e614a18bff58d2caab09a0b
71 schema:publisher N59ea99a9b2cf4a7eba371a0629b0f0d2
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040061033
73 https://doi.org/10.1007/11818175_13
74 schema:sdDatePublished 2022-01-01T19:06
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N83dfe41757324370b840ad6c8e1286f3
77 schema:url https://doi.org/10.1007/11818175_13
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N59ea99a9b2cf4a7eba371a0629b0f0d2 schema:name Springer Nature
82 rdf:type schema:Organisation
83 N68ceacc9bd8a4056ac6d1edadeb55bd9 rdf:first sg:person.013307226666.21
84 rdf:rest rdf:nil
85 N764a99ecf73743e3a521f21c85e04397 schema:name dimensions_id
86 schema:value pub.1040061033
87 rdf:type schema:PropertyValue
88 N811c4c42376e47ae989d2f6f5392d026 schema:isbn 978-3-540-37432-9
89 978-3-540-37433-6
90 schema:name Advances in Cryptology - CRYPTO 2006
91 rdf:type schema:Book
92 N83dfe41757324370b840ad6c8e1286f3 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 N8e56b6cee3b847d88130366382e2dc9c rdf:first Nff5ce100acf14709b440f4c428b8df0f
95 rdf:rest rdf:nil
96 N93abe8dd0e614a18bff58d2caab09a0b schema:name doi
97 schema:value 10.1007/11818175_13
98 rdf:type schema:PropertyValue
99 Ndd5d92f4ca2e451197e43266399b67be rdf:first sg:person.07776170271.83
100 rdf:rest Ne991ee99b123419db497aa8e2524a414
101 Ne991ee99b123419db497aa8e2524a414 rdf:first sg:person.016423726453.97
102 rdf:rest N68ceacc9bd8a4056ac6d1edadeb55bd9
103 Nff5ce100acf14709b440f4c428b8df0f schema:familyName Dwork
104 schema:givenName Cynthia
105 rdf:type schema:Person
106 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
107 schema:name Information and Computing Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
110 schema:name Data Format
111 rdf:type schema:DefinedTerm
112 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.13992.30
113 schema:familyName Smith
114 schema:givenName Adam
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
116 rdf:type schema:Person
117 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
118 schema:familyName Segev
119 schema:givenName Gil
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
121 rdf:type schema:Person
122 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
123 schema:familyName Naor
124 schema:givenName Moni
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
126 rdf:type schema:Person
127 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
128 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
129 rdf:type schema:Organization
 




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


...