Leakage Resilience and Black-box Impossibility Results in Cryptography

In this thesis, we present constructions of leakage-resilient cryptographic primitives, and we give black-box impossibility results for certain classes of constructions of pseudo-random number generators. The traditional approach for preventing side-channel attacks has been primarily hardware-based. Recently, there has been significant progress in developing algorithmic approaches for preventing such attacks. These algorithmic approaches involve modeling side-channel attacks as {\em leakage} on the internal state of a device; constructions secure against such leakage are {\em leakage-resilient}. We first consider the problem of storing a key and computing on it repeatedly in a leakage-resilient manner. For this purpose, we define a new primitive called a {\em key proxy}. Using a fully-homomorphic public-key encryption scheme, we construct a leakage-resilient key proxy. We work in the ``only computation leaks'' leakage model, tolerating a logarithmic number of bits of polynomial-time computable leakage per computation and an unbounded total amount of leakage. We next consider the problem of verifying that a message sent over a public channel has not been modified, in a setting where the sender and the receiver have previously shared a key, and where the adversary controls the public channel and is simultaneously mounting side-channel attacks on both parties. Using only the assumption that pseudo-random generators exist, we construct a leakage-resilient shared-private-key authenticated session protocol. This construction tolerates a logarithmic number of bits of polynomial-time computable leakage per computation, and an unbounded total amount of leakage. This leakage occurs on the entire state, input, and randomness of the party performing the computation. Finally, we consider the problem of constructing a large-stretch pseudo-random generator given a one-way permutation or given a smaller-stretch pseudo-random generator. The standard approach for doing this involves repeatedly composing the given object with itself. We provide evidence that this approach is necessary. Specifically, we consider three classes of constructions of pseudo-random generators from pseudo-random generators of smaller stretch or from one-way permutations, and for each class, we give a black-box impossibility result that demonstrates a contrast between the stretch that can be achieved by adaptive and non-adaptive black-box constructions.Ph