Public-Key Cryptosystems Resilient to Key Leakage View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Moni Naor , Gil Segev

ABSTRACT

Most of the work in the analysis of cryptographic schemes is concentrated in abstract adversarial models that do not capture side-channel attacks. Such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. Inspired by recent side-channel attacks, especially the “cold boot attacks”, Akavia, Goldwasser and Vaikuntanathan (TCC ’09) formalized a realistic framework for modeling the security of encryption schemes against a wide class of side-channel attacks in which adversarially chosen functions of the secret key are leaked. In the setting of public-key encryption, Akavia et al. showed that Regev’s lattice-based scheme (STOC ’05) is resilient to any leakage of L / polylog(L) bits, where L is the length of the secret key.In this paper we revisit the above-mentioned framework and our main results are as follows:We present a generic construction of a public-key encryption scheme that is resilient to key leakage from any universal hash proof system. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. Existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional Diffie-Hellman assumption (and its progressively weaker d-Linear variants), the quadratic residuosity assumption, and Paillier’s composite residuosity assumption.We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-Linear variants), and show that the resulting scheme is resilient to any leakage of L(1 − o(1)) bits. In addition, we prove that the recent scheme of Boneh et al. (CRYPTO ’08), constructed to be a “circular-secure” encryption scheme, is resilient to any leakage of L(1 − o(1)) bits. These two proposed schemes complement each other in terms of efficiency.We extend the framework of key leakage to the setting of chosen-ciphertext attacks. On the theoretical side, we prove that the Naor-Yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are CCA2-secure with any leakage of L(1 − o(1)) bits. On the practical side, we prove that variants of the Cramer-Shoup cryptosystem (along the lines of our generic construction) are CCA1-secure with any leakage of L/4 bits, and CCA2-secure with any leakage of L/6 bits. More... »

PAGES

18-35

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_2

DOI

http://dx.doi.org/10.1007/978-3-642-03356-8_2

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Most of the work in the analysis of cryptographic schemes is concentrated in abstract adversarial models that do not capture side-channel attacks. Such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. Inspired by recent side-channel attacks, especially the \u201ccold boot attacks\u201d, Akavia, Goldwasser and Vaikuntanathan (TCC \u201909) formalized a realistic framework for modeling the security of encryption schemes against a wide class of side-channel attacks in which adversarially chosen functions of the secret key are leaked. In the setting of public-key encryption, Akavia et al. showed that Regev\u2019s lattice-based scheme (STOC \u201905) is resilient to any leakage of L / polylog(L) bits, where L is the length of the secret key.In this paper we revisit the above-mentioned framework and our main results are as follows:We present a generic construction of a public-key encryption scheme that is resilient to key leakage from any universal hash proof system. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. Existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional Diffie-Hellman assumption (and its progressively weaker d-Linear variants), the quadratic residuosity assumption, and Paillier\u2019s composite residuosity assumption.We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-Linear variants), and show that the resulting scheme is resilient to any leakage of L(1\u2009\u2212\u2009o(1)) bits. In addition, we prove that the recent scheme of Boneh et al. (CRYPTO \u201908), constructed to be a \u201ccircular-secure\u201d encryption scheme, is resilient to any leakage of L(1\u2009\u2212\u2009o(1)) bits. These two proposed schemes complement each other in terms of efficiency.We extend the framework of key leakage to the setting of chosen-ciphertext attacks. On the theoretical side, we prove that the Naor-Yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are CCA2-secure with any leakage of L(1\u2009\u2212\u2009o(1)) bits. On the practical side, we prove that variants of the Cramer-Shoup cryptosystem (along the lines of our generic construction) are CCA1-secure with any leakage of L/4 bits, and CCA2-secure with any leakage of L/6 bits.", 
    "editor": [
      {
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03356-8_2", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03355-1", 
        "978-3-642-03356-8"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "side-channel attacks", 
      "decisional Diffie-Hellman assumption", 
      "Diffie-Hellman assumption", 
      "encryption scheme", 
      "hash proof systems", 
      "lattice-based schemes", 
      "proof system", 
      "key leakage", 
      "secret key", 
      "residuosity assumption", 
      "Naor-Yung paradigm", 
      "Cramer-Shoup cryptosystem", 
      "chosen-ciphertext attacks", 
      "public-key encryption scheme", 
      "public-key encryption", 
      "number-theoretic assumptions", 
      "underlying proof system", 
      "unintended information leakage", 
      "such proof systems", 
      "cold boot attacks", 
      "Boneh et al", 
      "quadratic residuosity assumption", 
      "additional computational assumptions", 
      "Akavia et al", 
      "cryptographic schemes", 
      "computational assumptions", 
      "information leakage", 
      "key cryptosystem", 
      "such attacks", 
      "adversarial model", 
      "generic construction", 
      "terms of efficiency", 
      "recent schemes", 
      "physical implementation", 
      "cryptosystem", 
      "bits", 
      "attacks", 
      "scheme", 
      "practical side", 
      "framework", 
      "realistic framework", 
      "encryption", 
      "CCA2-secure", 
      "Akavia", 
      "CCA1-secure", 
      "Vaikuntanathan", 
      "Goldwasser", 
      "key", 
      "theoretical side", 
      "system", 
      "security", 
      "wide class", 
      "implementation", 
      "paradigm", 
      "construction", 
      "et al", 
      "assumption", 
      "efficiency", 
      "work", 
      "model", 
      "setting", 
      "class", 
      "terms", 
      "leakage", 
      "variety", 
      "main results", 
      "results", 
      "variants", 
      "function", 
      "analysis", 
      "side", 
      "form", 
      "addition", 
      "al", 
      "length", 
      "paper", 
      "abstract adversarial models", 
      "recent side-channel attacks", 
      "boot attacks", 
      "Regev\u2019s lattice-based scheme", 
      "universal hash proof system", 
      "Paillier\u2019s composite residuosity assumption", 
      "\u2019s composite residuosity assumption", 
      "new hash proof system", 
      "corollary encryption schemes", 
      "L/6 bits"
    ], 
    "name": "Public-Key Cryptosystems Resilient to Key Leakage", 
    "pagination": "18-35", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029717402"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03356-8_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03356-8_2", 
      "https://app.dimensions.ai/details/publication/pub.1029717402"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:17", 
    "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_300.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03356-8_2"
  }
]
 

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-03356-8_2'

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-03356-8_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_2'

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-03356-8_2'


 

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

157 TRIPLES      23 PREDICATES      113 URIs      105 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03356-8_2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author N6e4e4ce436fc4c3497ad733d6072b4a6
5 schema:datePublished 2009
6 schema:datePublishedReg 2009-01-01
7 schema:description Most of the work in the analysis of cryptographic schemes is concentrated in abstract adversarial models that do not capture side-channel attacks. Such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. Inspired by recent side-channel attacks, especially the “cold boot attacks”, Akavia, Goldwasser and Vaikuntanathan (TCC ’09) formalized a realistic framework for modeling the security of encryption schemes against a wide class of side-channel attacks in which adversarially chosen functions of the secret key are leaked. In the setting of public-key encryption, Akavia et al. showed that Regev’s lattice-based scheme (STOC ’05) is resilient to any leakage of L / polylog(L) bits, where L is the length of the secret key.In this paper we revisit the above-mentioned framework and our main results are as follows:We present a generic construction of a public-key encryption scheme that is resilient to key leakage from any universal hash proof system. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. Existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional Diffie-Hellman assumption (and its progressively weaker d-Linear variants), the quadratic residuosity assumption, and Paillier’s composite residuosity assumption.We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-Linear variants), and show that the resulting scheme is resilient to any leakage of L(1 − o(1)) bits. In addition, we prove that the recent scheme of Boneh et al. (CRYPTO ’08), constructed to be a “circular-secure” encryption scheme, is resilient to any leakage of L(1 − o(1)) bits. These two proposed schemes complement each other in terms of efficiency.We extend the framework of key leakage to the setting of chosen-ciphertext attacks. On the theoretical side, we prove that the Naor-Yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are CCA2-secure with any leakage of L(1 − o(1)) bits. On the practical side, we prove that variants of the Cramer-Shoup cryptosystem (along the lines of our generic construction) are CCA1-secure with any leakage of L/4 bits, and CCA2-secure with any leakage of L/6 bits.
8 schema:editor Ndfddc65695124665bdb0ee7a4debbb4d
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N2e7367902af24d668ece145c4411ed27
13 schema:keywords Akavia
14 Akavia et al
15 Boneh et al
16 CCA1-secure
17 CCA2-secure
18 Cramer-Shoup cryptosystem
19 Diffie-Hellman assumption
20 Goldwasser
21 L/6 bits
22 Naor-Yung paradigm
23 Paillier’s composite residuosity assumption
24 Regev’s lattice-based scheme
25 Vaikuntanathan
26 abstract adversarial models
27 addition
28 additional computational assumptions
29 adversarial model
30 al
31 analysis
32 assumption
33 attacks
34 bits
35 boot attacks
36 chosen-ciphertext attacks
37 class
38 cold boot attacks
39 computational assumptions
40 construction
41 corollary encryption schemes
42 cryptographic schemes
43 cryptosystem
44 decisional Diffie-Hellman assumption
45 efficiency
46 encryption
47 encryption scheme
48 et al
49 form
50 framework
51 function
52 generic construction
53 hash proof systems
54 implementation
55 information leakage
56 key
57 key cryptosystem
58 key leakage
59 lattice-based schemes
60 leakage
61 length
62 main results
63 model
64 new hash proof system
65 number-theoretic assumptions
66 paper
67 paradigm
68 physical implementation
69 practical side
70 proof system
71 public-key encryption
72 public-key encryption scheme
73 quadratic residuosity assumption
74 realistic framework
75 recent schemes
76 recent side-channel attacks
77 residuosity assumption
78 results
79 scheme
80 secret key
81 security
82 setting
83 side
84 side-channel attacks
85 such attacks
86 such proof systems
87 system
88 terms
89 terms of efficiency
90 theoretical side
91 underlying proof system
92 unintended information leakage
93 universal hash proof system
94 variants
95 variety
96 wide class
97 work
98 ’s composite residuosity assumption
99 schema:name Public-Key Cryptosystems Resilient to Key Leakage
100 schema:pagination 18-35
101 schema:productId N5992ed9449a644198371feddc5d59d92
102 Nfa1193acdf524e17ae14169bcb5771f0
103 schema:publisher N76e481a9d3704d6fbf0af95e268b71af
104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029717402
105 https://doi.org/10.1007/978-3-642-03356-8_2
106 schema:sdDatePublished 2022-01-01T19:17
107 schema:sdLicense https://scigraph.springernature.com/explorer/license/
108 schema:sdPublisher Nf5a0f472f23147868e502707c6243090
109 schema:url https://doi.org/10.1007/978-3-642-03356-8_2
110 sgo:license sg:explorer/license/
111 sgo:sdDataset chapters
112 rdf:type schema:Chapter
113 N2e7367902af24d668ece145c4411ed27 schema:isbn 978-3-642-03355-1
114 978-3-642-03356-8
115 schema:name Advances in Cryptology - CRYPTO 2009
116 rdf:type schema:Book
117 N5992ed9449a644198371feddc5d59d92 schema:name doi
118 schema:value 10.1007/978-3-642-03356-8_2
119 rdf:type schema:PropertyValue
120 N6e4e4ce436fc4c3497ad733d6072b4a6 rdf:first sg:person.07776170271.83
121 rdf:rest Nca5e2539f4154bdbbae3e56a0d552dba
122 N76e481a9d3704d6fbf0af95e268b71af schema:name Springer Nature
123 rdf:type schema:Organisation
124 Nca5e2539f4154bdbbae3e56a0d552dba rdf:first sg:person.016423726453.97
125 rdf:rest rdf:nil
126 Ndfddc65695124665bdb0ee7a4debbb4d rdf:first Nf904c629dd7641fc90340a9899cb48ec
127 rdf:rest rdf:nil
128 Nf5a0f472f23147868e502707c6243090 schema:name Springer Nature - SN SciGraph project
129 rdf:type schema:Organization
130 Nf904c629dd7641fc90340a9899cb48ec schema:familyName Halevi
131 schema:givenName Shai
132 rdf:type schema:Person
133 Nfa1193acdf524e17ae14169bcb5771f0 schema:name dimensions_id
134 schema:value pub.1029717402
135 rdf:type schema:PropertyValue
136 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
137 schema:name Information and Computing Sciences
138 rdf:type schema:DefinedTerm
139 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
140 schema:name Computation Theory and Mathematics
141 rdf:type schema:DefinedTerm
142 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
143 schema:name Data Format
144 rdf:type schema:DefinedTerm
145 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
146 schema:familyName Segev
147 schema:givenName Gil
148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
149 rdf:type schema:Person
150 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
151 schema:familyName Naor
152 schema:givenName Moni
153 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
154 rdf:type schema:Person
155 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
156 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
157 rdf:type schema:Organization
 




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


...