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": [
      "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

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.

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
 




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


...