Deterministic Encryption: Theory and Applications

The focus of the talk is deterministic public-key encryption schemes. Besides being interesting from theoretical and historical perspectives, the deterministic encryption primitive has applications to fast and secure search on remote data. We study several new notions of security for deterministic encryption and relations among them. We present several very efficient deterministic encryption schemes that provably satisfy the strongest-possible security definition (in the random oracle model). We finally provide the constructions that achieve security for many practical settings, without relying on the idealized random oracle model. The talk is based on joint papers with Mihir Bellare, Serge Fehr and Adam O'Neill.