QUAD: A multivariate stream cipher with provable security. We present the stream cipher QUAD and the provable security arguments supporting its conjectured strength for suitable parameter values. QUAD was first proposed at Eurocrypt 2006 by {it C. Berbain} et al. [in: Advances in cryptology -- EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 -- June 1, 2006. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 4004, 109--128 (2006; Zbl 1140.94322)]. It relies on the iteration of a set of multivariate quadratic polynomials over a finite field, typically GF(2) or a small extension. We show that in the binary case, the security of the keystream generation can be related, in the concrete security model, to the conjectured intractability of the MQ problem of solving a random system of m equations in n unknowns. We show furthermore that this security reduction can be extended to incorporate the key and IV setup and provide a security argument related to the whole stream cipher. We also briefly address software and hardware performance issues and show that if one is willing to pseudo-randomly generate the sets of quadratic polynomials underlying the cipher, this leads to surprisingly inexpensive hardware implementations of QUAD.

References in zbMATH (referenced in 15 articles )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Li, Weijian; Huang, Xian; Zhao, Huimin; Xie, Guoliang; Lu, Fuxiang: Fuzzy matching template attacks on multivariate cryptography: a case study (2020)
  2. Cayrel, Pierre-Louis; Meziani, Mohammed; Ndiaye, Ousmane; Lindner, Richard; Silva, Rosemberg: A pseudorandom number generator based on worst-case lattice problems (2017)
  3. Paul, Goutam; Sanyal, Abhiroop: Revisiting the security proof of QUAD stream cipher: some corrections and tighter bounds (2017)
  4. Albrecht, Martin R.; Faugère, Jean-Charles; Farshim, Pooya; Herold, Gottfried; Perret, Ludovic: Polly cracker, revisited (2016)
  5. Tang, Shaohua; Lv, Bo; Shen, Wuqiang: Hybrid MQ signature for embedded device (2016)
  6. Tanaka, Satoshi; Cheng, Chen-Mou; Sakurai, Kouichi: Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU (2015)
  7. Carlet, Claude: A survey on nonlinear Boolean functions with optimal algebraic immunity suitable for stream ciphers (2013)
  8. Hashimoto, Yasufumi; Takagi, Tsuyoshi; Sakurai, Kouichi: General fault attacks on multivariate public key cryptosystems (2011)
  9. Shi, Hongsong; Jiang, Shaoquan; Qin, Zhiguang: More efficient DDH pseudorandom generators (2010)
  10. Berbain, Côme; Gilbert, Henri; Patarin, Jacques: QUAD: A multivariate stream cipher with provable security (2009)
  11. Hell, Martin; Johansson, Thomas; Brynielsson, Lennart: An overview of distinguishing attacks on stream ciphers (2009)
  12. Patarin, Jacques; Seurin, Yannick: Building secure block ciphers on generic attacks assumptions (2009)
  13. Finiasz, Matthieu: Syndrome based collision resistant hashing (2008)
  14. Liu, Feng-Hao; Lu, Chi-Jen; Yang, Bo-Yin: Secure PRNGs from specialized polynomial maps over any (\mathbbF_q) (2008)
  15. Berbain, Côme; Gilbert, Henri; Patarin, Jacques: QUAD: A practical stream cipher with provable security (2006)