---
_id: '3229'
abstract:
- lang: eng
  text: 'We construct a stream-cipher S whose implementation is secure even if a bounded
    amount of arbitrary (adversarially chosen) information on the internal state ofS
    is leaked during computation. This captures all possible side-channel attacks
    on S where the amount of information leaked in a given period is bounded, but
    overall can be arbitrary large. The only other assumption we make on the implementation
    of S is that only data that is accessed during computation leaks information.
    The stream-cipher S generates its output in chunks K1, K2, . . . and arbitrary
    but bounded information leakage is modeled by allowing the adversary to adaptively
    chose a function fl : {0,1}* rarr {0, 1}lambda before Kl is computed, she then
    gets fl(taul) where taul is the internal state ofS that is accessed during the
    computation of Kg. One notion of security we prove for S is that Kg is indistinguishable
    from random when given K1,..., K1-1,f1(tau1 ),..., fl-1(taul-1) and also the complete
    internal state of S after Kg has been computed (i.e. S is forward-secure). The
    construction is based on alternating extraction (used in the intrusion-resilient
    secret-sharing scheme from FOCS''07). We move this concept to the computational
    setting by proving a lemma that states that the output of any PRG has high HILLpseudoentropy
    (i.e. is indistinguishable from some distribution with high min-entropy) even
    if arbitrary information about the seed is leaked. The amount of leakage lambda
    that we can tolerate in each step depends on the strength of the underlying PRG,
    it is at least logarithmic, but can be as large as a constant fraction of the
    internal state of S if the PRG is exponentially hard.'
author:
- first_name: Stefan
  full_name: Dziembowski, Stefan
  last_name: Dziembowski
- first_name: Krzysztof Z
  full_name: Krzysztof Pietrzak
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Dziembowski S, Pietrzak KZ. Leakage resilient cryptography. In: IEEE; 2008:293-302.
    doi:<a href="https://doi.org/10.1109/FOCS.2008.56">10.1109/FOCS.2008.56</a>'
  apa: 'Dziembowski, S., &#38; Pietrzak, K. Z. (2008). Leakage resilient cryptography
    (pp. 293–302). Presented at the FOCS: Foundations of Computer Science, IEEE. <a
    href="https://doi.org/10.1109/FOCS.2008.56">https://doi.org/10.1109/FOCS.2008.56</a>'
  chicago: Dziembowski, Stefan, and Krzysztof Z Pietrzak. “Leakage Resilient Cryptography,”
    293–302. IEEE, 2008. <a href="https://doi.org/10.1109/FOCS.2008.56">https://doi.org/10.1109/FOCS.2008.56</a>.
  ieee: 'S. Dziembowski and K. Z. Pietrzak, “Leakage resilient cryptography,” presented
    at the FOCS: Foundations of Computer Science, 2008, pp. 293–302.'
  ista: 'Dziembowski S, Pietrzak KZ. 2008. Leakage resilient cryptography. FOCS: Foundations
    of Computer Science, 293–302.'
  mla: Dziembowski, Stefan, and Krzysztof Z. Pietrzak. <i>Leakage Resilient Cryptography</i>.
    IEEE, 2008, pp. 293–302, doi:<a href="https://doi.org/10.1109/FOCS.2008.56">10.1109/FOCS.2008.56</a>.
  short: S. Dziembowski, K.Z. Pietrzak, in:, IEEE, 2008, pp. 293–302.
conference:
  name: 'FOCS: Foundations of Computer Science'
date_created: 2018-12-11T12:02:08Z
date_published: 2008-10-28T00:00:00Z
date_updated: 2021-01-12T07:41:57Z
day: '28'
doi: 10.1109/FOCS.2008.56
extern: 1
fulldoi: https://doi.org/10.1109/FOCS.2008.56
month: '10'
page: 293 - 302
publication_status: published
publisher: IEEE
publist_id: '3451'
quality_controlled: 0
status: public
title: Leakage resilient cryptography
type: conference
year: '2008'
...