Pseudorandom Generator Based on Hard Lattice Problem

Kuan Cheng

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

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Contact author(s): chengk11 @ mails tsinghua edu cn
History: 2014-01-02: received
Short URL: https://ia.cr/2014/002
License: CC BY

BibTeX

@misc{cryptoeprint:2014/002,
      author = {Kuan Cheng},
      title = {Pseudorandom Generator Based on Hard Lattice Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/002},
      year = {2014},
      url = {https://eprint.iacr.org/2014/002}
}