Public-Key Encryption in the Bounded-Retrieval Model View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Joël Alwen , Yevgeniy Dodis , Moni Naor , Gil Segev , Shabsi Walfish , Daniel Wichs

ABSTRACT

We construct the first public-key encryption scheme in the Bounded-Retrieval Model (BRM), providing security against various forms of adversarial “key leakage” attacks. In this model, the adversary is allowed to learn arbitrary information about the decryption key, subject only to the constraint that the overall amount of “leakage” is bounded by at most ℓ bits. The goal of the BRM is to design cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds ℓ (few bits or many Gigabytes), by only increasing the size of secret key proportionally, but keeping all the other parameters — including the size of the public key, ciphertext, encryption/decryption time, and the number of secret-key bits accessed during decryption — small and independent of ℓ.As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity’s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model. More... »

PAGES

113-134

Book

TITLE

Advances in Cryptology – EUROCRYPT 2010

ISBN

978-3-642-13189-9
978-3-642-13190-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13190-5_6

DOI

http://dx.doi.org/10.1007/978-3-642-13190-5_6

DIMENSIONS

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


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": "New York University (NYU), New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.137628.9", 
          "name": [
            "New York University (NYU), New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alwen", 
        "givenName": "Jo\u00ebl", 
        "id": "sg:person.012071501373.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012071501373.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "New York University (NYU), New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.137628.9", 
          "name": [
            "New York University (NYU), New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dodis", 
        "givenName": "Yevgeniy", 
        "id": "sg:person.015074130645.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, 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": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, 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": "Google Inc., Mountain View, USA", 
          "id": "http://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Inc., Mountain View, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Walfish", 
        "givenName": "Shabsi", 
        "id": "sg:person.016060746353.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016060746353.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "New York University (NYU), New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.137628.9", 
          "name": [
            "New York University (NYU), New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wichs", 
        "givenName": "Daniel", 
        "id": "sg:person.016071322513.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071322513.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We construct the first public-key encryption scheme in the Bounded-Retrieval Model (BRM), providing security against various forms of adversarial \u201ckey leakage\u201d attacks. In this model, the adversary is allowed to learn arbitrary information about the decryption key, subject only to the constraint that the overall amount of \u201cleakage\u201d is bounded by at most \u2113 bits. The goal of the BRM is to design cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds \u2113 (few bits or many Gigabytes), by only increasing the size of secret key proportionally, but keeping all the other parameters \u2014 including the size of the public key, ciphertext, encryption/decryption time, and the number of secret-key bits accessed during decryption \u2014 small and independent of \u2113.As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup\u00a0[CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity\u2019s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model.", 
    "editor": [
      {
        "familyName": "Gilbert", 
        "givenName": "Henri", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13190-5_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13189-9", 
        "978-3-642-13190-5"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2010", 
      "type": "Book"
    }, 
    "keywords": [
      "Bounded-Retrieval Model", 
      "public-key encryption scheme", 
      "hash proof systems", 
      "encryption scheme", 
      "decryption key", 
      "IB-HPS", 
      "proof system", 
      "encryption/decryption time", 
      "first public-key encryption scheme", 
      "identity-based setting", 
      "decryption time", 
      "key encryption", 
      "quadratic residuosity", 
      "cryptographic schemes", 
      "key leakage", 
      "public key", 
      "bilinear groups", 
      "secret-key bits", 
      "secret key", 
      "leakage bounds", 
      "arbitrary information", 
      "independent interest", 
      "scheme", 
      "key", 
      "bits", 
      "technical tools", 
      "partial leakage", 
      "encryption", 
      "ciphertext", 
      "primitives", 
      "adversary", 
      "security", 
      "main technical tool", 
      "Shoup", 
      "system", 
      "attacks", 
      "constraints", 
      "model", 
      "information", 
      "tool", 
      "bounds", 
      "goal", 
      "concept", 
      "Cramer", 
      "construction", 
      "results", 
      "notion", 
      "overall amount", 
      "interest", 
      "number", 
      "time", 
      "leakage", 
      "main results", 
      "size", 
      "amount", 
      "different constructions", 
      "setting", 
      "identity", 
      "form", 
      "lattice", 
      "group", 
      "residuosity", 
      "target identity\u2019s decryption key", 
      "identity\u2019s decryption key"
    ], 
    "name": "Public-Key Encryption in the Bounded-Retrieval Model", 
    "pagination": "113-134", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000769520"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13190-5_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13190-5_6", 
      "https://app.dimensions.ai/details/publication/pub.1000769520"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:23", 
    "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_401.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13190-5_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/978-3-642-13190-5_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/978-3-642-13190-5_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13190-5_6'

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-642-13190-5_6'


 

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

165 TRIPLES      23 PREDICATES      90 URIs      83 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13190-5_6 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N449e1e825f3e49dc8ead78fb6d8538ec
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We construct the first public-key encryption scheme in the Bounded-Retrieval Model (BRM), providing security against various forms of adversarial “key leakage” attacks. In this model, the adversary is allowed to learn arbitrary information about the decryption key, subject only to the constraint that the overall amount of “leakage” is bounded by at most ℓ bits. The goal of the BRM is to design cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds ℓ (few bits or many Gigabytes), by only increasing the size of secret key proportionally, but keeping all the other parameters — including the size of the public key, ciphertext, encryption/decryption time, and the number of secret-key bits accessed during decryption — small and independent of ℓ.As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity’s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model.
7 schema:editor N98287253966d4435b80360340ad79456
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8aa36125923c4cdcb1f9897ab63069ab
12 schema:keywords Bounded-Retrieval Model
13 Cramer
14 IB-HPS
15 Shoup
16 adversary
17 amount
18 arbitrary information
19 attacks
20 bilinear groups
21 bits
22 bounds
23 ciphertext
24 concept
25 constraints
26 construction
27 cryptographic schemes
28 decryption key
29 decryption time
30 different constructions
31 encryption
32 encryption scheme
33 encryption/decryption time
34 first public-key encryption scheme
35 form
36 goal
37 group
38 hash proof systems
39 identity
40 identity-based setting
41 identity’s decryption key
42 independent interest
43 information
44 interest
45 key
46 key encryption
47 key leakage
48 lattice
49 leakage
50 leakage bounds
51 main results
52 main technical tool
53 model
54 notion
55 number
56 overall amount
57 partial leakage
58 primitives
59 proof system
60 public key
61 public-key encryption scheme
62 quadratic residuosity
63 residuosity
64 results
65 scheme
66 secret key
67 secret-key bits
68 security
69 setting
70 size
71 system
72 target identity’s decryption key
73 technical tools
74 time
75 tool
76 schema:name Public-Key Encryption in the Bounded-Retrieval Model
77 schema:pagination 113-134
78 schema:productId Nc5dc5643342d476b9ac14fb48caaae6f
79 Nf391fbdb21374ffca03751aad14361a8
80 schema:publisher Nd3f28eb584024431a6226194bd9abd1c
81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000769520
82 https://doi.org/10.1007/978-3-642-13190-5_6
83 schema:sdDatePublished 2022-01-01T19:23
84 schema:sdLicense https://scigraph.springernature.com/explorer/license/
85 schema:sdPublisher N7899c4f98a89462e908575dbe2ccfc96
86 schema:url https://doi.org/10.1007/978-3-642-13190-5_6
87 sgo:license sg:explorer/license/
88 sgo:sdDataset chapters
89 rdf:type schema:Chapter
90 N13fde86ad2ee456cbe3f10d9281f5e13 rdf:first sg:person.016071322513.42
91 rdf:rest rdf:nil
92 N2c295c425b2840979c602ee0ab31dfb2 schema:familyName Gilbert
93 schema:givenName Henri
94 rdf:type schema:Person
95 N449e1e825f3e49dc8ead78fb6d8538ec rdf:first sg:person.012071501373.41
96 rdf:rest N84cef00e9457445bb074da5ae3abdd27
97 N7899c4f98a89462e908575dbe2ccfc96 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 N7fb69e4a5e9e424a84f04c52533d9bb8 rdf:first sg:person.016423726453.97
100 rdf:rest Nf4ce6e9904a04004a1d39dda107a8581
101 N84cef00e9457445bb074da5ae3abdd27 rdf:first sg:person.015074130645.34
102 rdf:rest Ndb2d5f00c61140a6bbb92b4ccdc5366c
103 N8aa36125923c4cdcb1f9897ab63069ab schema:isbn 978-3-642-13189-9
104 978-3-642-13190-5
105 schema:name Advances in Cryptology – EUROCRYPT 2010
106 rdf:type schema:Book
107 N98287253966d4435b80360340ad79456 rdf:first N2c295c425b2840979c602ee0ab31dfb2
108 rdf:rest rdf:nil
109 Nc5dc5643342d476b9ac14fb48caaae6f schema:name dimensions_id
110 schema:value pub.1000769520
111 rdf:type schema:PropertyValue
112 Nd3f28eb584024431a6226194bd9abd1c schema:name Springer Nature
113 rdf:type schema:Organisation
114 Ndb2d5f00c61140a6bbb92b4ccdc5366c rdf:first sg:person.07776170271.83
115 rdf:rest N7fb69e4a5e9e424a84f04c52533d9bb8
116 Nf391fbdb21374ffca03751aad14361a8 schema:name doi
117 schema:value 10.1007/978-3-642-13190-5_6
118 rdf:type schema:PropertyValue
119 Nf4ce6e9904a04004a1d39dda107a8581 rdf:first sg:person.016060746353.72
120 rdf:rest N13fde86ad2ee456cbe3f10d9281f5e13
121 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
122 schema:name Information and Computing Sciences
123 rdf:type schema:DefinedTerm
124 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
125 schema:name Data Format
126 rdf:type schema:DefinedTerm
127 sg:person.012071501373.41 schema:affiliation grid-institutes:grid.137628.9
128 schema:familyName Alwen
129 schema:givenName Joël
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012071501373.41
131 rdf:type schema:Person
132 sg:person.015074130645.34 schema:affiliation grid-institutes:grid.137628.9
133 schema:familyName Dodis
134 schema:givenName Yevgeniy
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34
136 rdf:type schema:Person
137 sg:person.016060746353.72 schema:affiliation grid-institutes:grid.420451.6
138 schema:familyName Walfish
139 schema:givenName Shabsi
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016060746353.72
141 rdf:type schema:Person
142 sg:person.016071322513.42 schema:affiliation grid-institutes:grid.137628.9
143 schema:familyName Wichs
144 schema:givenName Daniel
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071322513.42
146 rdf:type schema:Person
147 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
148 schema:familyName Segev
149 schema:givenName Gil
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
151 rdf:type schema:Person
152 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
153 schema:familyName Naor
154 schema:givenName Moni
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
156 rdf:type schema:Person
157 grid-institutes:grid.137628.9 schema:alternateName New York University (NYU), New York, USA
158 schema:name New York University (NYU), New York, USA
159 rdf:type schema:Organization
160 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
161 schema:name Weizmann Institute of Science, Rehovot, Israel
162 rdf:type schema:Organization
163 grid-institutes:grid.420451.6 schema:alternateName Google Inc., Mountain View, USA
164 schema:name Google Inc., Mountain View, USA
165 rdf:type schema:Organization
 




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


...