PhD Defense by Abhishek Banerjee

Primary tabs

Title : New Constructions of Cryptographic Pseudorandom Functions

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



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


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

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.



  • Workflow Status:Published
  • Created By:Tatianna Richardson
  • Created:06/26/2015
  • Modified By:Fletcher Moore
  • Modified:10/07/2016


Target Audience