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

Abstract

The well-studied task of learning a linear function with errors is a seemingly hard problem and the basis for several cryptographic schemes. Here we demonstrate additional applications that enjoy strong security properties and a high level of efficiency. Namely, we construct:

1. Public-key and symmetric-key cryptosystems that provide security for key-dependent messages and enjoy circular security. Our 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 n·polylog(n) bit operations per message symbol in the public-key case, and polylog(n) bit operations in the symmetric-case.
2. Two efficient pseudorandom objects: a “weak randomized pseudorandom function” — a relaxation of standard PRF — that can be computed obliviously via a simple protocol, and a length-doubling pseudorandom generator that can be computed by a circuit of n ·polylog(n) size. The complexity of our pseudorandom generator almost matches the complexity of the fastest known construction (Applebaum et al., RANDOM 2006), which runs in linear time at the expense of relying on a nonstandard intractability assumption.

Our constructions and security proofs are simple and natural, and involve new techniques that may be of independent interest. In addition, by combining our constructions with prior ones, we get fast implementations of several other primitives and protocols.

Keywords: Encryption, Key-dependent message security, Learning problems, Lattice-based cryptography