Paper 2008/240
LeakageResilient Cryptography in the Standard Model
Stefan Dziembowski and Krzysztof Pietrzak
Abstract
We construct a streamcipher $\SC$ whose \emph{implementation} is secure even if arbitrary (adversely chosen) information on the internal state of $\SC$ is leaked during computation. This captures \emph{all} possible sidechannel attacks on $\SC$ where the amount of information leaked in a given period is bounded, but overall can be arbitrary large, in particular much larger than the internal state of $\SC$. The only other assumption we make on the \emph{implementation} of $\SC$ is that only data that is accessed during computation leaks information. The construction can be based on any pseudorandom generator, and the only computational assumption we make is that this PRG is secure against nonuniform adversaries in the classical sense (i.e. when there are no sidechannels). The streamcipher $\SC$ generates its output in chunks $K_1,K_2,\ldots$, and arbitrary but bounded information leakage is modeled by allowing the adversary to adaptively chose a function $f_\ell:\bin^*\rightarrow\bin^\lambda$ before $K_\ell$ is computed, she then gets $f_\ell(\tau_\ell)$ where $\tau_\ell$ is the internal state of $\SC$ that is accessed during the computation of $K_\ell$. One notion of security we prove for $\SC$ is that $K_\ell$ is indistinguishable from random when given $K_1,\ldots,K_{\ell1}$, $f_1(\tau_1),\ldots, f_{\ell1}(\tau_{\ell1})$ and also the complete internal state of $\SC$ after $K_{\ell}$ has been computed (i.e. our cipher is forwardsecure). The construction is based on alternating extraction (previously used in the intrusionresilient secretsharing 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 HILL pseudoentropy (i.e. is indistinguishable from some distribution with high minentropy) even if arbitrary information about the seed is leaked. The amount of leakage $\leak$ 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 $\SC$ if the PRG is exponentially hard.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 stream cipherssidechannel attackspseudoentropyextractors
 Contact author(s)
 pietrzak @ cwi nl
 History
 20080602: received
 Short URL
 https://ia.cr/2008/240
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/240, author = {Stefan Dziembowski and Krzysztof Pietrzak}, title = {LeakageResilient Cryptography in the Standard Model}, howpublished = {Cryptology ePrint Archive, Paper 2008/240}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/240}}, url = {https://eprint.iacr.org/2008/240} }