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 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.

1

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.