Paper 2007/405

Secure PRNGs from Specialized Polynomial Maps over Any $F_q$

Michael Feng-Hao Liu, Chi-Jen Lu, Bo-Yin Yang, and Jintai Ding


We prove that a random map drawn from any class ${\frak C}$ of polynomial maps from $F_q^n$ to $F_q^{n+r}$ that is (i) totally random in the affine terms, and (ii) has a negligible chance of being not strongly one-way, provides a secure PRNG (hence a secure stream cipher) for any q. Plausible choices for ${\frak C}$ are semi-sparse (i.e., the affine terms are truly random) systems and other systems that are easy to evaluate from a small (compared to a generic map) number of parameters. To our knowledge, there are no other positive results for provable security of specialized polynomial systems, in particular sparse ones (which are natural candidates to investigate for speed). We can build a family of provably secure stream ciphers a rough implementation of which at the same security level can be more than twice faster than an optimized QUAD (and any other provably secure stream ciphers proposed so far), and uses much less storage. This may also help build faster provably secure hashes. We also examine the effects of recent results on specialization on security, e.g., Aumasson-Meier (ICISC 2007), which precludes Merkle-Damgaard compression using polynomials systems {uniformly very sparse in every degree} from being universally collision-free. We conclude that our ideas are consistent with and complements these new results. We think that we can build secure primitives based on specialized (versus generic) polynomial maps which are more efficient.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
multivariate polynomialstream cipherspecial polynomialprovably secure
Contact author(s)
ding @ math uc edu
2007-10-22: received
Short URL
Creative Commons Attribution


      author = {Michael Feng-Hao Liu and Chi-Jen Lu and Bo-Yin Yang and Jintai Ding},
      title = {Secure PRNGs from Specialized Polynomial Maps over Any $F_q$},
      howpublished = {Cryptology ePrint Archive, Paper 2007/405},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.