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

The well-studied task of learning a linear function with errors is a seemingly hard problem and the basis for several cryptographic schemes. Here the authors demonstrate additional applications that enjoy strong security properties and a high level of efficiency. Namely, they construct: Public-key and symmetric-key cryptosystems that provide security for key-dependent messages and enjoy circular security. The schemes are highly efficient: in both cases the ciphertext is only a constant factor larger than the plaintext, and the cost of encryption and decryption is only npolylog(n) bit operations per message symbol in the public-key case, and polylog(n) bit operations in the symmetric case.