Paper 2011/530
KeyEvolution Schemes Resilient to SpaceBounded Leakage
Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs
Abstract
Much recent work in cryptography attempts to build secure schemes in the presence of \emph{sidechannel leakage} or leakage caused by malicious software, like computer viruses. In this setting, the adversary may obtain some additional information (beyond the control of the scheme designer) about the internal secret state of a cryptographic scheme. Here, we consider keyevolution schemes that allow a user to evolve a secretkey $K_1$ via a \emph{deterministic} function $f$, to get updated keys $K_2 = f(K_1), K_3 = f(K_2), \ldots$. Such a scheme is \emph{leakageresilient} if an adversary that can leak on the first $i$ steps of the evolution process does not get any useful information about any future keys. For such schemes, one must assume some restriction on the \emph{complexity} of the leakage to prevent \emph{precomputation attacks}, where the leakage on a key $K_i$ simply precomputes a future key $K_{i+ t}$ and leaks even a single bit on it. We notice that much of the prior work on this problem, and the restrictions made therein, can be divided into two types. Theoretical work offers rigor and provable security, but at the cost of having to make strong restrictions on the type of leakage and designing complicated schemes to make standard reductionbased proof techniques go through (an example of such an assumption is that only the data actually used in computation can leak to the adversary). On the other hand, practical work focuses on simple and efficient schemes, often at the cost of only achieving an intuitive notion of security without formal wellspecified guarantees. In this paper, we complement the two tracks via a middleoftheroad approach. On one hand, we rely on the randomoracle model, acknowledging the usefulness of this methodology in practice despite its theoretical shortcomings. On the other hand, we show that even in the randomoracle model, designing secure leakageresilient schemes with clear and meaningful guarantees requires great care and is susceptible to pitfalls. For example, just assuming that leakage ``cannot evaluate the random oracle'' can be misleading. Instead, we define a new model in which we assume that the ``leakage'' can be any arbitrary \emph{space bounded} computation that can make random oracle calls itself. We connect the spacecomplexity of a computation in the randomoracle modeling to the \emph{pebbling complexity} on graphs. Using this connection, we derive meaningful guarantees for relatively simple keyevolution constructions. Our security proofs do not rely on the assumption that only data used in the computation can leak. Our scheme is secure also against a large and natural class of active attacks. This is especially important if the key evolution is performed on a PC that can be attacked by a virus. So far, all results that provided solutions against such attacks were secure under the assumption that the virus can download the data from the machine, but he cannot modify any information stored on it (that was called the {\em bounded retrieval model (BRM)}). This paper provides the first scheme were the adversary in the BRM can also modify the data stored on the machine.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 graph pebblingleakageresilient cryptographyboundedretrieval model
 Contact author(s)
 tkazana @ mimuw edu pl
 History
 20111001: received
 Short URL
 https://ia.cr/2011/530
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/530, author = {Stefan Dziembowski and Tomasz Kazana and Daniel Wichs}, title = {KeyEvolution Schemes Resilient to SpaceBounded Leakage}, howpublished = {Cryptology ePrint Archive, Paper 2011/530}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/530}}, url = {https://eprint.iacr.org/2011/530} }