Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Sebastian Faust , Tal Rabin , Leonid Reyzin , Eran Tromer , Vinod Vaikuntanathan

ABSTRACT

Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a new, functionally equivalent circuit which is resilient against well-defined classes of leakage. Our construction requires a small, stateless and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component.Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component) and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited either in its computational ability (namely, it lacks the ability to decode certain linear encodings and outputs a limited number of bits per iteration), or its precision (each observed bit is flipped with some probability). While our results apply in general to such leakage classes, in particular, we obtain security against:Constant depth circuits leakage, where the measurement apparatus can be implemented by an AC0 circuit (namely, a constant depth circuit composed of NOT gates and unbounded fan-in AND and OR gates), or an ACC0[p] circuit (which is the same as AC0, except that it also uses MODp gates) which outputs a limited number of bits.Noisy leakage, where the measurement apparatus reveals all the bits of the state of the circuit, perturbed by independent binomial noise. Namely, each bit of the computation is perturbed with probability p, and remains unchanged with probability 1 − p. More... »

PAGES

135-156

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_7

DOI

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

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "K.U.\u00a0Leuven ESAT-COSIC/IBBT", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "K.U.\u00a0Leuven ESAT-COSIC/IBBT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Faust", 
        "givenName": "Sebastian", 
        "id": "sg:person.012373070423.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012373070423.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM Research"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Boston University", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Boston University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reyzin", 
        "givenName": "Leonid", 
        "id": "sg:person.016627532062.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016627532062.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "MIT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tromer", 
        "givenName": "Eran", 
        "id": "sg:person.013627204443.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013627204443.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM Research"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vaikuntanathan", 
        "givenName": "Vinod", 
        "id": "sg:person.010511407257.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a new, functionally equivalent circuit which is resilient against well-defined classes of leakage. Our construction requires a small, stateless and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component.Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component) and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited either in its computational ability (namely, it lacks the ability to decode certain linear encodings and outputs a limited number of bits per iteration), or its precision (each observed bit is flipped with some probability). While our results apply in general to such leakage classes, in particular, we obtain security against:Constant depth circuits leakage, where the measurement apparatus can be implemented by an AC0 circuit (namely, a constant depth circuit composed of NOT gates and unbounded fan-in AND and OR gates), or an ACC0[p] circuit (which is the same as AC0, except that it also uses MODp gates) which outputs a limited number of bits.Noisy leakage, where the measurement apparatus reveals all the bits of the state of the circuit, perturbed by independent binomial noise. Namely, each bit of the computation is perturbed with probability p, and remains unchanged with probability 1\u2009\u2212\u2009p.", 
    "editor": [
      {
        "familyName": "Gilbert", 
        "givenName": "Henri", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13190-5_7", 
    "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": [
      "random elements", 
      "probability p", 
      "probability 1", 
      "measurement apparatus", 
      "noisy case", 
      "general transformation", 
      "computational devices", 
      "equivalent circuit", 
      "computational ability", 
      "circuit leakage", 
      "AC0 circuits", 
      "simple components", 
      "computation", 
      "internal states", 
      "complex circuits", 
      "problem", 
      "noisy leakage", 
      "class", 
      "circuit", 
      "observer", 
      "noise", 
      "bits", 
      "state", 
      "limited number", 
      "devices", 
      "side-channel information", 
      "distribution", 
      "transformation", 
      "approach", 
      "construction", 
      "number", 
      "information", 
      "components", 
      "essence", 
      "adversary", 
      "results", 
      "cases", 
      "elements", 
      "precision", 
      "apparatus", 
      "time", 
      "leakage", 
      "stateless", 
      "security", 
      "amount", 
      "ability", 
      "secret internal state"
    ], 
    "name": "Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases", 
    "pagination": "135-156", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040247219"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13190-5_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13190-5_7", 
      "https://app.dimensions.ai/details/publication/pub.1040247219"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "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_319.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13190-5_7"
  }
]
 

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_7'

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_7'

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_7'

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_7'


 

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

142 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13190-5_7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1d32f356b4fe41688f70dd3bc6d63d73
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a new, functionally equivalent circuit which is resilient against well-defined classes of leakage. Our construction requires a small, stateless and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component.Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component) and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited either in its computational ability (namely, it lacks the ability to decode certain linear encodings and outputs a limited number of bits per iteration), or its precision (each observed bit is flipped with some probability). While our results apply in general to such leakage classes, in particular, we obtain security against:Constant depth circuits leakage, where the measurement apparatus can be implemented by an AC0 circuit (namely, a constant depth circuit composed of NOT gates and unbounded fan-in AND and OR gates), or an ACC0[p] circuit (which is the same as AC0, except that it also uses MODp gates) which outputs a limited number of bits.Noisy leakage, where the measurement apparatus reveals all the bits of the state of the circuit, perturbed by independent binomial noise. Namely, each bit of the computation is perturbed with probability p, and remains unchanged with probability 1 − p.
7 schema:editor N11c7ecb905bf4aca9c3e2a1d8b798a4e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb3021c7eb09a4257b1a24796ffec5051
12 schema:keywords AC0 circuits
13 ability
14 adversary
15 amount
16 apparatus
17 approach
18 bits
19 cases
20 circuit
21 circuit leakage
22 class
23 complex circuits
24 components
25 computation
26 computational ability
27 computational devices
28 construction
29 devices
30 distribution
31 elements
32 equivalent circuit
33 essence
34 general transformation
35 information
36 internal states
37 leakage
38 limited number
39 measurement apparatus
40 noise
41 noisy case
42 noisy leakage
43 number
44 observer
45 precision
46 probability 1
47 probability p
48 problem
49 random elements
50 results
51 secret internal state
52 security
53 side-channel information
54 simple components
55 state
56 stateless
57 time
58 transformation
59 schema:name Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases
60 schema:pagination 135-156
61 schema:productId N049fe105937b48f19a0f272837eeaa25
62 N41a953445ed04cfdb834d276658fce09
63 schema:publisher N1bbcb8a8935040dd89035dd796821c68
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040247219
65 https://doi.org/10.1007/978-3-642-13190-5_7
66 schema:sdDatePublished 2022-05-20T07:45
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N9813d406d10c4fb297eed72d8f33fff0
69 schema:url https://doi.org/10.1007/978-3-642-13190-5_7
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N049fe105937b48f19a0f272837eeaa25 schema:name dimensions_id
74 schema:value pub.1040247219
75 rdf:type schema:PropertyValue
76 N11c7ecb905bf4aca9c3e2a1d8b798a4e rdf:first Ned33f4f292db4958b03564fd2b9773f4
77 rdf:rest rdf:nil
78 N1bbcb8a8935040dd89035dd796821c68 schema:name Springer Nature
79 rdf:type schema:Organisation
80 N1d32f356b4fe41688f70dd3bc6d63d73 rdf:first sg:person.012373070423.93
81 rdf:rest N91f777a60a394459a88e65931edd6394
82 N411f016939004174b654d851beefedcb rdf:first sg:person.013627204443.07
83 rdf:rest Nd8ec421349384d12b503f48fccbe1223
84 N41a953445ed04cfdb834d276658fce09 schema:name doi
85 schema:value 10.1007/978-3-642-13190-5_7
86 rdf:type schema:PropertyValue
87 N91f777a60a394459a88e65931edd6394 rdf:first sg:person.015473523512.58
88 rdf:rest N9c2985ff1f004d30ac38c8782b2c957a
89 N9813d406d10c4fb297eed72d8f33fff0 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 N9c2985ff1f004d30ac38c8782b2c957a rdf:first sg:person.016627532062.10
92 rdf:rest N411f016939004174b654d851beefedcb
93 Nb3021c7eb09a4257b1a24796ffec5051 schema:isbn 978-3-642-13189-9
94 978-3-642-13190-5
95 schema:name Advances in Cryptology – EUROCRYPT 2010
96 rdf:type schema:Book
97 Nd8ec421349384d12b503f48fccbe1223 rdf:first sg:person.010511407257.61
98 rdf:rest rdf:nil
99 Ned33f4f292db4958b03564fd2b9773f4 schema:familyName Gilbert
100 schema:givenName Henri
101 rdf:type schema:Person
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
106 schema:name Computation Theory and Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.010511407257.61 schema:affiliation grid-institutes:None
109 schema:familyName Vaikuntanathan
110 schema:givenName Vinod
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61
112 rdf:type schema:Person
113 sg:person.012373070423.93 schema:affiliation grid-institutes:None
114 schema:familyName Faust
115 schema:givenName Sebastian
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012373070423.93
117 rdf:type schema:Person
118 sg:person.013627204443.07 schema:affiliation grid-institutes:None
119 schema:familyName Tromer
120 schema:givenName Eran
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013627204443.07
122 rdf:type schema:Person
123 sg:person.015473523512.58 schema:affiliation grid-institutes:None
124 schema:familyName Rabin
125 schema:givenName Tal
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
127 rdf:type schema:Person
128 sg:person.016627532062.10 schema:affiliation grid-institutes:grid.189504.1
129 schema:familyName Reyzin
130 schema:givenName Leonid
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016627532062.10
132 rdf:type schema:Person
133 grid-institutes:None schema:alternateName IBM Research
134 K.U. Leuven ESAT-COSIC/IBBT
135 MIT
136 schema:name IBM Research
137 K.U. Leuven ESAT-COSIC/IBBT
138 MIT
139 rdf:type schema:Organization
140 grid-institutes:grid.189504.1 schema:alternateName Boston University
141 schema:name Boston University
142 rdf:type schema:Organization
 




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


...