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 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}
}