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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/002}},
      url = {https://eprint.iacr.org/2014/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.