## Cryptology ePrint Archive: Report 2007/405

**Secure PRNGs from Specialized Polynomial Maps over Any $F_q$ **

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

**Abstract: **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.

**Category / Keywords: **secret-key cryptography / multivariate polynomial, stream cipher, special polynomial, provably secure

**Date: **received 22 Oct 2007

**Contact author: **ding at math uc edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20071022:192841 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]