Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems

Benny Applebaum, David Cash, Chris Peikert, Amit Sahai - This project deals with the problem of circular security, an issue that arises in several contexts, including distributed systems with complicated key management schemes. The essential problem is that when applications encrypt keys as messages and potentially create so-called encrypted key cycles, our standard notions of security are insufficient to guarantee safety. Previously, one construction of circular-secure encryption which was known (Boneh et al., CRYPTO 2008), but this construction paid a large cost in terms of efficiency over standard constructions. In this work we show that circular security is very naturally supported by encryption schemes that are based on problems from learning theory. We give constructions of circular-secure encryption that are as efficient as standard-secure schemes from the same problem. That is, we pay no efficiency cost for circular-security. Our results include a public-key scheme from the Learning with Errors problem, and a very efficient symmetric-key scheme from the Learning Parity with Noise problem.