*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
