Cryptology ePrint Archive: Report 2014/002

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 ]