Fast Cryptographic Primitives Based on the Hardness of Decoding Random Linear Code

Abstract:

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.