From Single-Bit to Multi-bit Public-Key Encryption via Non-malleable Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Sandro Coretti , Ueli Maurer , Björn Tackmann , Daniele Venturi

ABSTRACT

One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build “stronger” or more general schemes generically from “weaker” or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS ’09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt ’12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE.It is well-known that encrypting each bit of a plaintext string independently is not chosen-ciphertext secure—the resulting scheme is malleable. This paper analyzes the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS ’10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. An attacker’s ability to make multiple decryption queries requires that the underlying code be continuously non-malleable (Faust et al., TCC ’14). This flavor of non-malleable codes can only be achieved if the decoder is allowed to “self-destruct” when it processes an invalid encoding. The resulting PKE scheme inherits this property and therefore only achieves a weaker variant of chosen-ciphertext security, where the decryption becomes dysfunctional once the attacker submits an invalid ciphertext.We first show that the above approach based on non-malleable codes indeed yields a solution to the problem of domain extension for publickey encryption where the decryption may self-destruct, provided that the underlying code is continuously non-malleable against a reduced form of bit-wise tampering. This statement is shown by combining a simple information-theoretic argument with the constructive cryptography perspective on PKE (Coretti et al., Asiacrypt ’13). Then, we prove that the code of Dziembowski et al. is actually already continuously non-malleable against (full) bit-wise tampering; this constitutes the first informationtheoretically secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering. More... »

PAGES

532-560

Book

TITLE

Theory of Cryptography

ISBN

978-3-662-46493-9
978-3-662-46494-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-46494-6_22

DOI

http://dx.doi.org/10.1007/978-3-662-46494-6_22

DIMENSIONS

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


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": "ETH Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coretti", 
        "givenName": "Sandro", 
        "id": "sg:person.0756652750.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0756652750.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ETH Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maurer", 
        "givenName": "Ueli", 
        "id": "sg:person.01316567627.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC San Diego, USA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "UC San Diego, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tackmann", 
        "givenName": "Bj\u00f6rn", 
        "id": "sg:person.07617171521.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07617171521.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome, Italy", 
          "id": "http://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Sapienza University of Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Venturi", 
        "givenName": "Daniele", 
        "id": "sg:person.011520342003.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520342003.25"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build \u201cstronger\u201d or more general schemes generically from \u201cweaker\u201d or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS \u201909) and continued by Hohenberger, Lewko, and Waters (Eurocrypt \u201912), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE.It is well-known that encrypting each bit of a plaintext string independently is not chosen-ciphertext secure\u2014the resulting scheme is malleable. This paper analyzes the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS \u201910) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. An attacker\u2019s ability to make multiple decryption queries requires that the underlying code be continuously non-malleable (Faust et al., TCC \u201914). This flavor of non-malleable codes can only be achieved if the decoder is allowed to \u201cself-destruct\u201d when it processes an invalid encoding. The resulting PKE scheme inherits this property and therefore only achieves a weaker variant of chosen-ciphertext security, where the decryption becomes dysfunctional once the attacker submits an invalid ciphertext.We first show that the above approach based on non-malleable codes indeed yields a solution to the problem of domain extension for publickey encryption where the decryption may self-destruct, provided that the underlying code is continuously non-malleable against a reduced form of bit-wise tampering. This statement is shown by combining a simple information-theoretic argument with the constructive cryptography perspective on PKE (Coretti et al., Asiacrypt \u201913). Then, we prove that the code of Dziembowski et al. is actually already continuously non-malleable against (full) bit-wise tampering; this constitutes the first informationtheoretically secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering.", 
    "editor": [
      {
        "familyName": "Dodis", 
        "givenName": "Yevgeniy", 
        "type": "Person"
      }, 
      {
        "familyName": "Nielsen", 
        "givenName": "Jesper Buus", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-46494-6_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-46493-9", 
        "978-3-662-46494-6"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "non-malleable codes", 
      "CCA secure PKE", 
      "bit-wise tampering", 
      "public-key encryption scheme", 
      "chosen-ciphertext security", 
      "domain extension", 
      "chosen-ciphertext secure", 
      "memory tampering", 
      "key encryption", 
      "encryption scheme", 
      "CCA security", 
      "information-theoretic arguments", 
      "PKE scheme", 
      "attacker's ability", 
      "invalid ciphertexts", 
      "decryption queries", 
      "Dziembowski et al", 
      "codeword bits", 
      "technical contribution", 
      "tampering", 
      "previous approaches", 
      "encryption", 
      "decryption", 
      "single bit", 
      "PKE", 
      "security", 
      "code", 
      "independent interest", 
      "scheme", 
      "bits", 
      "above approach", 
      "more general schemes", 
      "queries", 
      "attacker", 
      "Secure", 
      "ciphertext", 
      "plaintext", 
      "Lewko", 
      "decoder", 
      "weak variant", 
      "Hohenberger", 
      "Shelat", 
      "general scheme", 
      "encoding", 
      "self-destruct", 
      "first application", 
      "simple approach", 
      "extension", 
      "context", 
      "applications", 
      "cost", 
      "strings", 
      "particular line", 
      "solution", 
      "work", 
      "construction", 
      "ability", 
      "interest", 
      "one", 
      "et al", 
      "assumption", 
      "perspective", 
      "results", 
      "variants", 
      "statements", 
      "credible assumptions", 
      "contribution", 
      "form", 
      "self", 
      "lines", 
      "argument", 
      "properties", 
      "Myers", 
      "al", 
      "flavor", 
      "approach", 
      "water", 
      "paper", 
      "problem"
    ], 
    "name": "From Single-Bit to Multi-bit Public-Key Encryption via Non-malleable Codes", 
    "pagination": "532-560", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006115284"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-46494-6_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-46494-6_22", 
      "https://app.dimensions.ai/details/publication/pub.1006115284"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_145.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-46494-6_22"
  }
]
 

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-662-46494-6_22'

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-662-46494-6_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-46494-6_22'

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-662-46494-6_22'


 

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

171 TRIPLES      23 PREDICATES      105 URIs      98 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-46494-6_22 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nbb2c194fc56e46c7a74c00c009f34662
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build “stronger” or more general schemes generically from “weaker” or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS ’09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt ’12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE.It is well-known that encrypting each bit of a plaintext string independently is not chosen-ciphertext secure—the resulting scheme is malleable. This paper analyzes the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS ’10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. An attacker’s ability to make multiple decryption queries requires that the underlying code be continuously non-malleable (Faust et al., TCC ’14). This flavor of non-malleable codes can only be achieved if the decoder is allowed to “self-destruct” when it processes an invalid encoding. The resulting PKE scheme inherits this property and therefore only achieves a weaker variant of chosen-ciphertext security, where the decryption becomes dysfunctional once the attacker submits an invalid ciphertext.We first show that the above approach based on non-malleable codes indeed yields a solution to the problem of domain extension for publickey encryption where the decryption may self-destruct, provided that the underlying code is continuously non-malleable against a reduced form of bit-wise tampering. This statement is shown by combining a simple information-theoretic argument with the constructive cryptography perspective on PKE (Coretti et al., Asiacrypt ’13). Then, we prove that the code of Dziembowski et al. is actually already continuously non-malleable against (full) bit-wise tampering; this constitutes the first informationtheoretically secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering.
7 schema:editor Ncf354c264ca840a780a09d2d66823fd0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N0a747f7754fe49d8bd9f8a4a0489a12b
12 schema:keywords CCA secure PKE
13 CCA security
14 Dziembowski et al
15 Hohenberger
16 Lewko
17 Myers
18 PKE
19 PKE scheme
20 Secure
21 Shelat
22 ability
23 above approach
24 al
25 applications
26 approach
27 argument
28 assumption
29 attacker
30 attacker's ability
31 bit-wise tampering
32 bits
33 chosen-ciphertext secure
34 chosen-ciphertext security
35 ciphertext
36 code
37 codeword bits
38 construction
39 context
40 contribution
41 cost
42 credible assumptions
43 decoder
44 decryption
45 decryption queries
46 domain extension
47 encoding
48 encryption
49 encryption scheme
50 et al
51 extension
52 first application
53 flavor
54 form
55 general scheme
56 independent interest
57 information-theoretic arguments
58 interest
59 invalid ciphertexts
60 key encryption
61 lines
62 memory tampering
63 more general schemes
64 non-malleable codes
65 one
66 paper
67 particular line
68 perspective
69 plaintext
70 previous approaches
71 problem
72 properties
73 public-key encryption scheme
74 queries
75 results
76 scheme
77 security
78 self
79 self-destruct
80 simple approach
81 single bit
82 solution
83 statements
84 strings
85 tampering
86 technical contribution
87 variants
88 water
89 weak variant
90 work
91 schema:name From Single-Bit to Multi-bit Public-Key Encryption via Non-malleable Codes
92 schema:pagination 532-560
93 schema:productId Ne0d7bfdcccd34b139b369dc723f621ed
94 Ne5f75deffea94c87a91fd2e4558539f1
95 schema:publisher Neb85833846c242b39777c36d7dcf2a32
96 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006115284
97 https://doi.org/10.1007/978-3-662-46494-6_22
98 schema:sdDatePublished 2022-05-20T07:42
99 schema:sdLicense https://scigraph.springernature.com/explorer/license/
100 schema:sdPublisher N7d1117e1e7144094a0fc8b92be4d3021
101 schema:url https://doi.org/10.1007/978-3-662-46494-6_22
102 sgo:license sg:explorer/license/
103 sgo:sdDataset chapters
104 rdf:type schema:Chapter
105 N0458daaef3e24c998099578a7f40b6df schema:familyName Dodis
106 schema:givenName Yevgeniy
107 rdf:type schema:Person
108 N0a747f7754fe49d8bd9f8a4a0489a12b schema:isbn 978-3-662-46493-9
109 978-3-662-46494-6
110 schema:name Theory of Cryptography
111 rdf:type schema:Book
112 N2f7200a32f1a4b639c07b0405207c455 rdf:first N751d62b62dbd4307b7fe5826acc9669a
113 rdf:rest rdf:nil
114 N566b0be5f69d4ccaa660e07418035607 rdf:first sg:person.07617171521.69
115 rdf:rest N5b72b7c9aa2249e0ac87402f1073db8b
116 N5b72b7c9aa2249e0ac87402f1073db8b rdf:first sg:person.011520342003.25
117 rdf:rest rdf:nil
118 N751d62b62dbd4307b7fe5826acc9669a schema:familyName Nielsen
119 schema:givenName Jesper Buus
120 rdf:type schema:Person
121 N7d1117e1e7144094a0fc8b92be4d3021 schema:name Springer Nature - SN SciGraph project
122 rdf:type schema:Organization
123 N9bda982cae5d429b87f3cd3ae1292945 rdf:first sg:person.01316567627.91
124 rdf:rest N566b0be5f69d4ccaa660e07418035607
125 Nbb2c194fc56e46c7a74c00c009f34662 rdf:first sg:person.0756652750.76
126 rdf:rest N9bda982cae5d429b87f3cd3ae1292945
127 Ncf354c264ca840a780a09d2d66823fd0 rdf:first N0458daaef3e24c998099578a7f40b6df
128 rdf:rest N2f7200a32f1a4b639c07b0405207c455
129 Ne0d7bfdcccd34b139b369dc723f621ed schema:name doi
130 schema:value 10.1007/978-3-662-46494-6_22
131 rdf:type schema:PropertyValue
132 Ne5f75deffea94c87a91fd2e4558539f1 schema:name dimensions_id
133 schema:value pub.1006115284
134 rdf:type schema:PropertyValue
135 Neb85833846c242b39777c36d7dcf2a32 schema:name Springer Nature
136 rdf:type schema:Organisation
137 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
138 schema:name Information and Computing Sciences
139 rdf:type schema:DefinedTerm
140 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
141 schema:name Data Format
142 rdf:type schema:DefinedTerm
143 sg:person.011520342003.25 schema:affiliation grid-institutes:grid.7841.a
144 schema:familyName Venturi
145 schema:givenName Daniele
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520342003.25
147 rdf:type schema:Person
148 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
149 schema:familyName Maurer
150 schema:givenName Ueli
151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
152 rdf:type schema:Person
153 sg:person.0756652750.76 schema:affiliation grid-institutes:grid.5801.c
154 schema:familyName Coretti
155 schema:givenName Sandro
156 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0756652750.76
157 rdf:type schema:Person
158 sg:person.07617171521.69 schema:affiliation grid-institutes:grid.266100.3
159 schema:familyName Tackmann
160 schema:givenName Björn
161 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07617171521.69
162 rdf:type schema:Person
163 grid-institutes:grid.266100.3 schema:alternateName UC San Diego, USA
164 schema:name UC San Diego, USA
165 rdf:type schema:Organization
166 grid-institutes:grid.5801.c schema:alternateName ETH Zurich, Switzerland
167 schema:name ETH Zurich, Switzerland
168 rdf:type schema:Organization
169 grid-institutes:grid.7841.a schema:alternateName Sapienza University of Rome, Italy
170 schema:name Sapienza University of Rome, Italy
171 rdf:type schema:Organization
 




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


...