**Pseudorandom Generator Based on Hard Lattice Problem**

*Kuan Cheng*

**Abstract: **This paper studies how to construct a pseudorandom generator using hard lattice problems.

We use a variation of the classical hard problem \emph{Inhomogeneous Small Integer Solution} ISIS of lattice, say \emph{Inhomogeneous Subset Sum Solution} ISSS. ISSS itself is a hash function. Proving the preimage sizes ISSS hash function images are almost the same, we construct a pseudorandom generator using the method in \cite{GKL93}. Also, we construct a pseudoentropy generator using the method in \cite{HILL99}. Most theoretical PRG constructions are not feasible in fact as they require rather long random bits as seeds. Our PRG construction only requires seed length to be $O(n^{2}\log_{2} n)$ which is feasible practically.

**Category / Keywords: **foundations /

**Date: **received 1 Jan 2014

**Contact author: **chengk11 at mails tsinghua edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20140102:095717 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]