Practical Provable Security against Side-Channel Attacks

Securing cryptographic systems in the presence of side-channel leakages is still an important problem. Over recent years, the cryptography theory community has shown considerable interest in formally modelling the side-channel leakages and in designing "provably" secure cryptographic primitives in these leakage models. This area is often referred to as leakage-resilient cryptography. Yet, designing a formal model that realistically captures side-channel leakages such as power consumption patterns, and designing primitives efficient enough to be deployed in practice in such a leakage model, remains a challenging research direction.

In this work, we aim to bridge the above gap between the theory of provably secure cryptosystems that resist side-channel attacks and their practical relevance. Keeping this goal in mind, we analyze existing constructions and provide new ones for basic cryptographic primitives such as encryption and authentication in both public-key and symmetric-key cryptography.

This dissertation consists of three parts. In the first part, we analyze existing and design new efficient leakage-resilient constructions for public-key encryption and digital signatures that tolerate continual leakage in the split-state leakage model. Our security reductions are in the generic bilinear group model. The constructions we consider are simple variants of the ElGamal key encapsulation mechanism, and the Boneh-Boyen and the Schnorr signature schemes. We also cryptanalyze a variant of the ElGamal key encapsulation mechanism that was previously conjectured to be leakage-resilient under certain conditions.

The second part of this work is concerned with the protection of block ciphers in the probing adversarial leakage model. This approach, popularly known as masking in the cryptographic engineering community, is an effective countermeasure for block cipher implementations against power-analysis attacks. We improve the efficiency of a generic higher-order masking scheme recently proposed by Carlet et al. Improving the efficiency of this scheme is related to the problem of evaluating polynomials over binary finite fields in a newer cost model that counts only "non-linear" polynomial multiplications. We propose a new method for evaluating polynomials in this cost model, and argue (heuristically) that this method is asymptotically optimal.

The third part deals with the construction of efficient leakage-resilient symmetric-key authentication and encryption schemes. The constructions are shown to be secure in the standard model under a recently introduced simulatable leakage assumption. This assumption offers practitioners a hope to work with a formal leakage model that allows empirical verifiability. We propose a leakage-resilient CBC-like message authentication code, and also propose a leakage-resilient PRG-based chosen-plaintext secure encryption scheme for which we quantify the leakage it tolerates during the challenge phase in terms of security of a single iteration. Our constructions tolerate continual leakage but require leak-free updates.