Provable Security at Implementation-level

Sebastian Faust

Abstract

Traditionally, cryptography views cryptographic schemes as black-boxes. An adversary may have access to its inputs and outputs, but the internal computation within the box stays secret. Unfortunately, this model neglects many powerful real-world adversaries that exploit information leakage from the scheme’s physical implementation, and may provide the adversary with a partial view on the internal computation. Attacks that exploit such physical leakage are called side-channel attacks, and are a serious threat for a cryptographic implementation. The goal of this thesis is to develop theoretical models that incorporate these attacks, and devise cryptographic schemes that can be proven secure therein. In this thesis, we design a general compiler that transforms any cryptographic scheme, e.g., a block-cipher, into a functionally equivalent scheme which is resilient to a broad class of leakage. We allow the protected scheme to continuously leak information that may depend on all intermediate values of the computation, as long as the leakage can be described by a computationally weak or noisy function. An example are leakage functions that can be computed by circuits of small depth. Our construction requires a small, stateless and computation-independent leak-proof component, which reduces the problem of shielding arbitrarily complex computation to the problem of shielding a simple component. As a second contribution, we propose the first construction of a digital signature scheme that is resilient to arbitrary leakage (i.e., it must not be computationally weak or noisy), as long as the amount of information leaked in each invocation is bounded and “only computation leaks information”. Such leakage incorporates many real-world side-channel attacks, e.g., the Hamming weight function which is something frequently measured in practice. In contrast to our compiler, which is mainly of theoretical interest, our digital signature scheme is efficient and may be implemented on real-world devices.

Details

Publication typePhdThesis
URLhttp://cs.au.dk/~sfaust/HomepageFiles/thesis.pdf
InstitutionKatholieke Universiteit Leuven
> Publications > Provable Security at Implementation-level