Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Current cryptographic constructions typically involve a large

multiplicative computational overhead that grows with the

desired level of security. Recently, at STOC 2008, Ishai,

Kushilevitz, Ostrovsky, and Sahai (IKOS) suggested the

possibility of implementing cryptographic primitives, while

incurring only a constant computational overhead compared to

insecure implementations of the same tasks. Surprisingly, Ishai

et al. showed that such highly efficient cryptographic

constructions can be realized, under plausible, yet

nonstandard, intractability assumptions.In this paper, we show that if one is willing to accept

polylogarithmic computational overhead, many constructions can be

achieved under \emph{standard} assumptions. Specifically,

assuming the hardness of \emph{decoding random linear code} (or

equivalently, hardness of \emph{learning parity with noise}),

we get the following results.\begin{enumerate}

\item A pseudorandom generator $G:\bit^n \ra \bit^{2n}$ which doubles its input length

and can be computed in quasilinear time

$\Ot(n)=n\cdot \polylog(n)$.

\item A construction of weak randomized pseudorandom

function -- a relaxation of standard PRF -- which can

be obliviously computed in quasilinear time. This is

far more efficient than previously known

constructions, such as the oblivious evaluation of

the Naor-Reingold PRF (FOCS 1997).\item A symmetric encryption scheme whose encryption and

decryption algorithms are computable by circuits of

quasilinear size (in the message length). Our scheme

provides security against key-dependent messages and

achieves circular security. This provides a highly

efficient alternative in the private-key setting to

the circular-secure \emph{public-key} encryption

scheme of Boneh, Halevi, Hamburg, and Ostrovsky

(CRYPTO 2008).

\end{enumerate}By combining our results with previous ones, we get fast implementations of various other primitives and protocols.