Secure PRNGs from Specialized Polynomial Maps over Any

Feng-Hao Liu, Chi-Jen Lu, Bo-Yin Yang

TL;DR

This paper introduces a new class of secure pseudorandom number generators (PRNGs) based on specialized, sparse multivariate polynomial maps over any finite field $F_q$. The authors prove that these systems, when designed with random affine terms and a negligible chance of being invertible, can form the basis of provably secure stream ciphers that are significantly faster and more storage-efficient than previous constructions.

What Problem Does This Paper Address?

The field of cryptography has long sought efficient and provably secure primitives. Multivariate quadratic (MQ) systems have been a candidate for public-key cryptosystems and stream ciphers, but proving their security often relies on strong, worst-case hardness assumptions that are difficult to satisfy in practice. While some progress has been made with specific constructions like QUAD, they often suffer from performance issues or require impractically high parameters for provable security. The core problem this paper addresses is how to achieve provable security for stream ciphers using polynomial maps that are specialized (e.g., sparse) to improve efficiency, without sacrificing security. The authors aim to bridge the gap between the theoretical hardness of generic polynomial systems and the practical need for fast, secure cryptographic primitives.

Methods

The paper's core contribution lies in defining and analyzing a new class of functions called "POWFRAT" (probabilistically one-way functions, random affine terms). These are multivariate polynomial maps over $F_q$ that are random in their affine terms and have a negligible chance of being invertible. The authors leverage a generalization of the Goldreich-Levin theorem, which states that linear functions are "hardcore bits" of one-way functions. By showing that if a POWFRAT map is not a PRNG, then a linear function of its input can be predicted with high probability, they can then use this to construct a secure PRNG.

Key techniques include:

  • Defining POWFRAT classes: This class of functions is designed to be easier to evaluate than generic MQ systems while maintaining a strong hardness assumption.
  • Generalizing Goldreich-Levin: The paper extends the Goldreich-Levin theorem from $F_2$ to any finite field $F_q$, which is crucial for their generalized construction.
  • Constructing PRNGs from POWFRAT: They show how to build a PRNG by combining a POWFRAT map with an update function and an output filter, similar to existing stream cipher constructions.
  • Analyzing Sparse Polynomial Systems: The paper investigates specific types of sparse polynomial systems, namely "Sparse Multivariate Polynomials" (SMP) and "Sparse-Rotated Quadratics" (SRQ), as candidates for POWFRAT classes.
  • Computational Distinguishability: The security proofs rely on the concept of computational distinguishability between the output of the PRNG and a truly random sequence.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs, with experimental results presented in the form of timing measurements for solving polynomial systems.

Key Insights and Ideas

  • Sparsity for Security and Speed: The paper demonstrates that specialized, sparse polynomial maps can be used to build provably secure PRNGs that are significantly faster and more efficient in terms of storage than generic constructions. This challenges the notion that only generic, dense systems offer strong security guarantees.
  • Random Affine Terms are Crucial: The "random affine terms" property of POWFRAT classes is highlighted as essential for the security proofs, ensuring that the system doesn't collapse into trivial solutions or become easily invertible.
  • Generalization to $F_q$: Extending the security proofs and constructions from $F_2$ to any finite field $F_q$ is a significant theoretical advancement, broadening the applicability of these techniques.
  • Bridging Theory and Practice: The work provides a concrete path towards building practical cryptographic primitives with provable security guarantees, addressing a long-standing challenge in the field.
  • Complementary to Existing Attacks: The authors show that their findings are consistent with and complement recent research on attacking sparse polynomial systems, indicating that their proposed constructions are robust against known specialized attacks.

Key Results

  • Provable Security for Sparse Polynomial PRNGs: The paper proves that a random map from a POWFRAT class provides a secure PRNG (and thus a secure stream cipher) over any finite field $F_q$.
  • Efficiency Gains: Preliminary implementations of their proposed SPONGE stream cipher (based on sparse polynomials) achieve significantly higher performance (cycles/byte) and lower storage requirements compared to existing provably secure stream ciphers like QUAD, while maintaining comparable or better security levels. For example, one SPONGE instance achieved 11744 cycles/byte with a proven security level of $2^{82}$, outperforming QUAD.
  • Parameter Choices: The paper provides concrete parameter examples for SPONGE constructions over $F_2$, $F_{16}$, and $F_{256}$, demonstrating the practical feasibility of their approach.
  • Theoretical Bounds: The paper derives bounds on the complexity of solving sparse polynomial systems and the security levels achievable by their constructions.

Limitations and Future Work

  • "Looseness Factor": The authors acknowledge that their theorem has a "looseness factor" and suggest tightening this bound for even stronger security guarantees.
  • Parameter Optimization: While preliminary implementations show promise, further work is needed to optimize programming and parameter choices for maximum efficiency.
  • Specialized Attacks: The paper mentions that specialized attacks on sparse systems are an active area of research, and further investigation is needed to understand how small parameter choices might be vulnerable.
  • Hash Functions: The authors suggest that their work could also help build faster provably secure hashes, indicating a potential future direction.
  • Tightness of Bounds: Quantifying exactly how small certain parameters (like the advantage $\epsilon$) can be before specialized attacks become a serious problem is an open question.

Summary updated

Abstract

Berbain, Gilbert, and Patarin presented QUAD, a pseudo random number generator (PRNG) at Eurocrypt 2006. QUAD (as PRNG and stream cipher) may be proved secure based on an interesting hardness assumption about the one-wayness of multivariate quadratic polynomial systems over \(\mathbb{F}_{2}\).
BibTeX
@article{liu2007secure,
  author = {Feng-Hao Liu and Chi-Jen Lu and Bo-Yin Yang},
  title = {{Secure PRNGs from Specialized Polynomial Maps over Any}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2007},
}

Loading related content...

Figure