[Colloq] TOMORROW - Thesis Proposal - Foundations of cryptography: Towards bridging theory and implementation - Eric Miles - 4/25, 10:30am, 10 West Village F

[Jessica Biron]

Title: Foundations of cryptography: Towards bridging theory and implementation 
Date/Time: Thu Apr 25, 10:30am 
Location: 10 West Village F 


Abstract: 
It has been widely observed that there is a significant gap between the way that many cryptographic primitives are constructed and analyzed by the theory/foundations community, and the way that they are implemented, used, and attacked in practice. In this work we study from two different perspectives the complexity of constructing cryptographic primitives, with an eye towards bridging this gap. 

We first study the complexity of constructing pseudorandom functions using a certain paradigm known as the substitution-permutation network (SPN). Informally, a pseudorandom function family (PRF) is a small set of functions F such that a function chosen at random from F is indistinguishable from a truly random function by a computationally-bounded adversary. The SPN paradigm is widely used in practical cryptographic constructions, such as the Advanced Encryption Standard [Daemen & Rijmen 2000], but has not previously been used to construct candidate PRFs. We construct several new candidate PRFs inspired by the SPN paradigm, and show that they are computable more efficiently than previous candidates in a variety of computational models. 

We then study the complexity of constructing arbitrary cryptographic primitives in an attack model in which the adversary obtains more information than just the input/output behavior afforded by oracle access. This line of research is motivated by the many so-called side-channel attacks that exploit implementation properties, i.e. properties of the hardware on which an algorithm is run, rather than the algorithm alone. As a general result, we show how to efficiently compile any given circuit C into a so-called "leakage resistant" circuit C' that computes the same function and has the additional property that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing products over the alternating group A_u. In combination with new compression bounds for A_u products which we also obtain, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known.