Title : New Constructions of Cryptographic Pseudorandom Functions

Abhishek Banerjee
PhD Candidate in Algorithms, Combinatorics, and Optimization
School of Computer Science
Georgia Institute of Technology

abhishek.banerjee@cc.gatech.edu

http://www.cc.gatech.edu/~abanerje/

Date: Monday, June 29th
Time: 11:00am
Location: Klaus 2100

Committee:

Dr. Chris Peikert, School of Computer Science (Advisor)

Dr. Alexandra Boldyreva, School of Computer Science

Dr. Santanu Dey, School of Industrial and Systems Engineering

Dr. Lance Fortnow, School of Computer Science

Dr. Richard Lipton, School of Computer Science

Dr. Alon Rosen, IDC Herzliya

Abstract:
Pseudorandom functions (PRFs) are the building blocks of symmetric-key cryptography. Almost all central goals of symmetric cryptography (e.g., encryption, authentication, identification) have simple solutions that make efficient use of a PRF. Most existing constructions of these objects are either (a) extremely fast in practice but without provable security guarantees based on hard mathematical problems [AES, Blowfish etc.], or (b) provably secure under assumptions like the hardness of factoring, but extremely inefficient in practice.

Lattice-based constructions enjoy strong security guarantees based on natural mathematical problems, are asymptotically and practically efficient, and have thus far even withstood attacks by quantum algorithms. However, most recent lattice-based constructions are of public-key objects, and it's natural to ask whether these advantages can be brought to the world of symmetric-key constructions.

In this thesis, we construct asymptotically fast and parallel pseudorandom functions basing their security on a well known hard lattice problem called the learning with errors problem. We provide several types of constructions that have their respective efficiency and security advantages. In addition to this, we also provide improved constructions of key-homomorphic PRFs that achieve almost optimal quasi-linear magnitudes of public parameters, key sizes and incremental run times. We also propose a new cryptographic primitive, constrained key-homomorphic PRFs, provide secure candidate constructions and applications. Lastly, we detail an implementation in software of a candidate PRF and analyze its efficiency and security.