Key-Evolution Schemes Resilient to Space-Bounded Leakage.
Stefan Dziembowski, Tomasz Kazana, Daniel Wichs · 2011
Much recent work in cryptography attempts to build secure schemes in the presence of side-channel 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 key-evolution schemes that allow a user to evolve a secret-key K1 via a deterministic function f, to get updated keys K2 = f(K1), K3 = f(K2),.... Such a scheme is leakage-resilient 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 complexity of the leakage to prevent pre-computation attacks, where the leakage on a key Ki simply pre-computes a future key Ki+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 reduction-based 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