Parallel and Concurrent Security of the HB and HB + Protocols View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Jonathan Katz , Ji Sun Shin

ABSTRACT

Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB + - whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB + protocol is proven secure against active attacks.Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB + protocol to be parallelized, thereby substantially reducing its round complexity.Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially simpler security proofs for these protocols which are more complete in that they explicitly address the dependence of the soundness error on the number of iterations. More... »

PAGES

73-87

Book

TITLE

Advances in Cryptology - EUROCRYPT 2006

ISBN

978-3-540-34546-6
978-3-540-34547-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11761679_6

DOI

http://dx.doi.org/10.1007/11761679_6

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "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": "Dept. of Computer Science, University of Maryland, USA", 
          "id": "http://www.grid.ac/institutes/grid.410443.6", 
          "name": [
            "Dept. of Computer Science, University of Maryland, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "id": "sg:person.01354261156.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Maryland, USA", 
          "id": "http://www.grid.ac/institutes/grid.410443.6", 
          "name": [
            "Dept. of Computer Science, University of Maryland, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shin", 
        "givenName": "Ji Sun", 
        "id": "sg:person.015326027245.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015326027245.79"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB\u2009+\u2009 - whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the \u201clearning parity with noise\u201d (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB\u2009+\u2009 protocol is proven secure against active attacks.Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB\u2009+\u2009 protocol to be parallelized, thereby substantially reducing its round complexity.Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially simpler security proofs for these protocols which are more complete in that they explicitly address the dependence of the soundness error on the number of iterations.", 
    "editor": [
      {
        "familyName": "Vaudenay", 
        "givenName": "Serge", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11761679_6", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34546-6", 
        "978-3-540-34547-3"
      ], 
      "name": "Advances in Cryptology - EUROCRYPT 2006", 
      "type": "Book"
    }, 
    "keywords": [
      "concurrent execution", 
      "low computational cost", 
      "radio frequency identification (RFID) tags", 
      "simple security proof", 
      "active attacks", 
      "concurrent security", 
      "security proof", 
      "Learning Parity", 
      "passive adversary", 
      "HB protocol", 
      "sequential execution", 
      "round complexity", 
      "number of iterations", 
      "low-cost devices", 
      "soundness error", 
      "computational cost", 
      "security", 
      "conjectured hardness", 
      "execution", 
      "adversary", 
      "identification tags", 
      "protocol", 
      "Juels", 
      "aforementioned questions", 
      "attacks", 
      "complexity", 
      "iteration", 
      "strong class", 
      "tags", 
      "cost", 
      "devices", 
      "proof", 
      "error", 
      "Regev", 
      "noise", 
      "positive answer", 
      "answers", 
      "class", 
      "number", 
      "questions", 
      "recent results", 
      "results", 
      "cases", 
      "addition", 
      "Wei", 
      "parity", 
      "hardness", 
      "dependence", 
      "problem", 
      "Hb"
    ], 
    "name": "Parallel and Concurrent Security of the HB and HB + Protocols", 
    "pagination": "73-87", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037494651"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11761679_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11761679_6", 
      "https://app.dimensions.ai/details/publication/pub.1037494651"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "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_85.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11761679_6"
  }
]
 

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/11761679_6'

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/11761679_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11761679_6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11761679_6'


 

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

120 TRIPLES      22 PREDICATES      76 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11761679_6 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 anzsrc-for:0804
4 schema:author Nbf70c865cee44a1cbf7bb437663ece61
5 schema:datePublished 2006
6 schema:datePublishedReg 2006-01-01
7 schema:description Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB +  - whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB +  protocol is proven secure against active attacks.Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB +  protocol to be parallelized, thereby substantially reducing its round complexity.Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially simpler security proofs for these protocols which are more complete in that they explicitly address the dependence of the soundness error on the number of iterations.
8 schema:editor Neeb612c51823458ea8f33ccf97588f3b
9 schema:genre chapter
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne1b62e8354e440f9b2086bef17775812
12 schema:keywords HB protocol
13 Hb
14 Juels
15 Learning Parity
16 Regev
17 Wei
18 active attacks
19 addition
20 adversary
21 aforementioned questions
22 answers
23 attacks
24 cases
25 class
26 complexity
27 computational cost
28 concurrent execution
29 concurrent security
30 conjectured hardness
31 cost
32 dependence
33 devices
34 error
35 execution
36 hardness
37 identification tags
38 iteration
39 low computational cost
40 low-cost devices
41 noise
42 number
43 number of iterations
44 parity
45 passive adversary
46 positive answer
47 problem
48 proof
49 protocol
50 questions
51 radio frequency identification (RFID) tags
52 recent results
53 results
54 round complexity
55 security
56 security proof
57 sequential execution
58 simple security proof
59 soundness error
60 strong class
61 tags
62 schema:name Parallel and Concurrent Security of the HB and HB + Protocols
63 schema:pagination 73-87
64 schema:productId N47356ea273e14ca79f23e7e6750d7ff0
65 N68e1470f718d4d939e80cbb7fdca4e75
66 schema:publisher N903868f180f64a69a9e613c57f724b13
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037494651
68 https://doi.org/10.1007/11761679_6
69 schema:sdDatePublished 2022-08-04T17:22
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N3f1a765c4cd245a888ca70b24e02f67a
72 schema:url https://doi.org/10.1007/11761679_6
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N3f1a765c4cd245a888ca70b24e02f67a schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N47356ea273e14ca79f23e7e6750d7ff0 schema:name doi
79 schema:value 10.1007/11761679_6
80 rdf:type schema:PropertyValue
81 N68e1470f718d4d939e80cbb7fdca4e75 schema:name dimensions_id
82 schema:value pub.1037494651
83 rdf:type schema:PropertyValue
84 N903868f180f64a69a9e613c57f724b13 schema:name Springer Nature
85 rdf:type schema:Organisation
86 Na20106a77aba41cdb42612835f4b8171 schema:familyName Vaudenay
87 schema:givenName Serge
88 rdf:type schema:Person
89 Nbf70c865cee44a1cbf7bb437663ece61 rdf:first sg:person.01354261156.67
90 rdf:rest Ncb35265ebc0f4a7082bf26b4f9aac528
91 Ncb35265ebc0f4a7082bf26b4f9aac528 rdf:first sg:person.015326027245.79
92 rdf:rest rdf:nil
93 Ne1b62e8354e440f9b2086bef17775812 schema:isbn 978-3-540-34546-6
94 978-3-540-34547-3
95 schema:name Advances in Cryptology - EUROCRYPT 2006
96 rdf:type schema:Book
97 Neeb612c51823458ea8f33ccf97588f3b rdf:first Na20106a77aba41cdb42612835f4b8171
98 rdf:rest rdf:nil
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computer Software
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
106 schema:name Data Format
107 rdf:type schema:DefinedTerm
108 sg:person.01354261156.67 schema:affiliation grid-institutes:grid.410443.6
109 schema:familyName Katz
110 schema:givenName Jonathan
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67
112 rdf:type schema:Person
113 sg:person.015326027245.79 schema:affiliation grid-institutes:grid.410443.6
114 schema:familyName Shin
115 schema:givenName Ji Sun
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015326027245.79
117 rdf:type schema:Person
118 grid-institutes:grid.410443.6 schema:alternateName Dept. of Computer Science, University of Maryland, USA
119 schema:name Dept. of Computer Science, University of Maryland, USA
120 rdf:type schema:Organization
 




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


...