Post-quantum cryptography

Multivariate-quadratic-equations public-key cryptography

Early constructions

1985. H. Ong, Claus-Peter Schnorr, Adi Shamir. "Efficient signature schemes based on polynomial equations." Pages 37–46 in: G. R. Blakley, David Chaum (editors). Advances in cryptology, proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19–22, 1984, proceedings. Lecture Notes in Computer Science 196. Springer. ISBN 3-540-15658-5.

1985. Harriet J. Fell, Whitfield Diffie. "Analysis of a public key approach based on polynomial substitution." Pages 340–349 in: Hugh C. Williams (editor). Advances in cryptology—CRYPTO '85, Santa Barbara, California, USA, August 18–22, 1985, proceedings.

1987. John M. Pollard, Claus-Peter Schnorr. "An efficient solution of the congruence x^2 + ky^2 = m (mod n)." IEEE Transactions on Information Theory 33, 702–709.

Large fields and medium fields

1996. Jacques Patarin. "Asymmetric cryptography with a hidden monomial and a candidate algorithm for =~ 64 bits asymmetric signatures." MR 99b:94040. Pages 45–60 in: Neal Koblitz (editor). Advances in cryptology—CRYPTO '96, proceedings of the 16th annual international cryptology conference held at the University of California, Santa Barbara, CA, August 18–22, 1996. Lecture Notes in Computer Science 1109. Springer. ISBN 3-540-61512-1. MR 98f:94001.

1996. Jacques Patarin. "Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms." Pages 33–48 in: Ueli Maurer (editor). Advances in Cryptology—EUROCRYPT '96. International conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12–16, 1996, proceedings. Lecture Notes in Computer Science 1070. Springer. ISBN 978-3-540-61186-8.

1998. Jacques Patarin, Louis Goubin, Nicolas T. Courtois. "C*-+ and HM: variations around two schemes of T. Matsumoto and H. Imai." Pages 35–49 in: Kazuo Ohta, Dingyi Pei (editors). Advances in cryptology—ASIACRYPT'98. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security held in Beijing, October 18–22, 1998. Lecture Notes in Computer Science 1514. Springer. ISBN 3-540-65109-8.

1999. Aviad Kipnis, Adi Shamir. "Cryptanalysis of the HFE public key cryptosystem by linearization." Pages 19–30 in: Michael J. Wiener (editor). Advances in cryptology—CRYPTO '99, 19th annual international cryptology conference, Santa Barbara, California, USA, August 15–19, proceedings. Lecture Notes in Computer Science 1666. Springer. ISBN 3-540-66347-9.

2000. Jacques Patarin. "Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88." Designs, Codes and Cryptography 20, 175–209. Earlier version: 1995. MR 98d:94022. Pages 248–261 in: Don Coppersmith (editor). Advances in Cryptology—CRYPTO 1995, proceedings of the 15th annual international cryptology conference held at the University of California, Santa Barbara, CA, August 27–31, 1995. Lecture Notes in Computer Science 963. Springer. ISBN 3-540-60221-6. MR 97k:94002.

2001. Nicolas T. Courtois. "The security of hidden field equations (HFE)." MR 1907103. Pages 266–281 in: David Naccache (editor). Topics in cryptology—CT-RSA 2001, proceedings of the cryptographers' track at the RSA conference held in San Francisco, CA, April 8–12, 2001. Lecture Notes in Computer Science 2020. Springer. ISBN 3-540-41898-9. MR 2003a:94039.

2001. Jacques Patarin, Nicolas T. Courtois, Louis Goubin. "QUARTZ, 128-bit long digital signatures." MR 1907104. Pages 282–297 in: David Naccache (editor). Topics in cryptology—CT-RSA 2001, proceedings of the cryptographers' track at the RSA conference held in San Francisco, CA, April 8–12, 2001. Lecture Notes in Computer Science 2020. Springer. ISBN 3-540-41898-9. MR 2003a:94039.

2001. Jacques Patarin, Nicolas T. Courtois, Louis Goubin. "FLASH, a fast multivariate signature algorithm." MR 1907105. Pages 298–307 in: David Naccache (editor). Topics in cryptology—CT-RSA 2001, proceedings of the cryptographers' track at the RSA conference held in San Francisco, CA, April 8–12, 2001. Lecture Notes in Computer Science 2020. Springer. ISBN 3-540-41898-9. MR 2003a:94039.

2002. Nicolas T. Courtois, Magnus Daum, Patrick Felke. "On the security of HFE, HFEv- and Quartz." MR 2007g:94044. Pages 337–350 in: Yvo G. Desmedt (editor). Public key cryptography—PKC 2003, proceedings of the 6th international workshop on practice and theory in public key cryptography held in Miami, FL, January 6–8, 2003. Lecture Notes in Computer Science 2567. Springer. ISBN 3-540-00324-X. MR 2006d:94071.

2002. Nicolas T. Courtois. "Generic attacks and the security of Quartz." MR 2006i:94045. Pages 351–364 in: Yvo G. Desmedt (editor). Public key cryptography—PKC 2003, proceedings of the 6th international workshop on practice and theory in public key cryptography held in Miami, FL, January 6–8, 2003. Lecture Notes in Computer Science 2567. Springer. ISBN 3-540-00324-X. MR 2006d:94071.

2003. Jean-Charles Faugère., Antoine Joux. "Algebraic cryptanalysis of Hidden Field Equations (HFE) using Gröbner bases." MR 2005e:94140. Pages 44–60 in: Dan Boneh (editor). Advances in cryptology—CRYPTO 2003, proceedings of the 23rd annual international cryptology conference held in Santa Barbara, CA, August 17–21, 2003. Lecture Notes in Computer Science 2729. Springer. ISBN 3-540-40674-3. MR 2005d:94151.

2004. Jintai Ding, Dieter Schmidt. "Cryptanalysis of SFlash v3." http://eprint.iacr.org/2004/103.

2004. Nicolas T. Courtois. "Algebraic attacks over GF(2^k), application to HFE Challenge 2 and Sflash-v2." MR 2005e:94132. Pages 201–217 in: Feng Bao, Robert Deng, Jianying Zhou (editors). Public key cryptography—PKC 2004, proceedings of the 7th international workshop on theory and practice in public key cryptography held in Singapore, March 1–4, 2004. Lecture Notes in Computer Science 2947. Springer. ISBN 3-540-21018-0. MR 2005d:94155.

2004. Jintai Ding. "A new variant of the Matsumoto-Imai cryptosystem through perturbation." Pages 305–318 in: Feng Bao, Robert Deng, Jianying Zhou (editors). Public key cryptography—PKC 2004, proceedings of the 7th international workshop on theory and practice in public key cryptography held in Singapore, March 1–4, 2004. Lecture Notes in Computer Science 2947. Springer. ISBN 3-540-21018-0. MR 2005d:94155.

2005. Jintai Ding, Jason E. Gower, Dieter Schmidt, Christopher Wolf, Zhijun Yin. "Complexity estimates for the F_4 attack on the perturbed Matsumoto-Imai cryptosystem." MR 2007f:94036. Pages 262–277 in: Nigel P. Smart (editor). Cryptography and coding, 10th IMA international conference, Cirencester, UK, December 19–21, 2005, proceedings. Lecture Notes in Computer Science 3796. Springer. ISBN 3-540-30276-X. MR 2006m:94081.

2005. Jintai Ding, Dieter Schmidt. "Cryptanalysis of HFEv and internal perturbation of HFE." MR 2006j:94061. Pages 288–301 in: Serge Vaudenay (editor). Public key cryptography—PKC 2005: proceedings of the 8th international workshop on theory and practice in public key cryptography held in Les Diablerets, January 23–26, 2005. Lecture Notes in Computer Science 3386. Springer. ISBN 3-540-24454-9. MR 2006d:94072.

2005. Pierre-Alain Fouque, Louis Granboulan, Jacques Stern. "Differential cryptanalysis for multivariate schemes." Pages 341–353 in: Ronald Cramer (editor). Advances in cryptology—EUROCRYPT 2005. Proceedings of the 24th annual international conference on the theory and applications of cryptographic techniques held in Aarhus, May 22–26, 2005. Lecture Notes in Computer Science 3494. Springer. ISBN 3-540-25910-4. MR 2008e:94035.

2006. Vivien Dubois, Louis Granboulan, Jacques Stern. "An efficient provable distinguisher for HFE." MR 2008b:94065. Pages 156–167 in: Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener (editors). Automata, languages and programming. Part II. Proceedings of the 33rd International Colloquium (ICALP 2006) held in Venice, July 10–14, 2006. Lecture Notes in Computer Science 4052. Springer. ISBN 978-3-540-35907-4.

2006. Louis Granboulan, Antoine Joux, Jacques Stern. "Inverting HFE is quasipolynomial." Pages 345–356 in: Cynthia Dwork (editor). Advances in cryptology—CRYPTO 2006. Proceedings of the 26th annual international cryptology conference held in Santa Barbara, CA, August 20–24, 2006. Lecture Notes in Computer Science 4117. Springer. ISBN 978-3-540-37432-9. MR 2422188.

2006. Aline Gouget, Jacques Patarin. "Probabilistic multivariate cryptography." Pages 1–18 in: Phong Q. Nguyen (editor). Progress in cryptology—VIETCRYPT 2006, first international conference on cryptology in Vietnam, Hanoi, Vietnam, September 25–28, 2006, revised selected papers. Lecture Notes in Computer Science 4341. Springer. ISBN 3-540-68799-8.

2006. Jintai Ding, Jason E. Gower. "Inoculating multivariate schemes against differential attacks." MR 2423196. Pages 290–301 in: Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin (editors). Public key cryptography—PKC 2006. Proceedings of the 9th International Conference on Theory and Practice of Public-Key Cryptography held in New York, April 24–26, 2006. Lecture Notes in Computer Science 3958. Springer. MR 2009a:94034.

2006. Adama Diene, Jintai Ding, Jason E. Gower, Timothy J. Hodges, Zhijun Yin. "Dimension of the linearization equations of the Matsumoto-Imai cryptosystems." MR 2423694. Pages 242–251 in: Oyvind Ytrehus, Coding and cryptography, revised selected papers from the international workshop (WCC 2005) held in Bergen, March 14–18, 2005. Lecture Notes in Computer Science 3969. Springer. ISBN 3-540-35481-6. MR 2428233.

2006. Lih-Chung Wang, Fei-Hwang Chang. "Revision of tractable rational map cryptosystem." Version 20061227:165851. http://eprint.iacr.org/2004/046.

2006. Lih-Chung Wang, Bo-Yin Yang, Yuh-Hua Hu, Feipei Lai. "A 'medium-field' multivariate public-key encryption scheme." Pages 132–149 in: David Pointcheval (editor). Topics in cryptology—CT-RSA 2006, proceedings of the cryptographers' track at the RSA conference held in San Jose, CA, February 13–17, 2006. Lecture Notes in Computer Science 3860. Springer. ISBN 3-540-31033-9. MR 2007b:94003.

2007. Jintai Ding, Christopher Wolf, Bo-Yin Yang. "l-invertible cycles for Multivariate Quadratic (MQ) public key cryptography." MR 2404125. Pages 266–281 in: Tatsuaki Okamoto, Xiaoyun Wang (editors). Public key cryptography—PKC 2007, proceedings of the 10th international conference on practice and theory in public-key cryptography held at Tsinghua University, Beijing, April 16–20, 2007. Lecture Notes in Computer Science 4450. Springer. ISBN 3-540-71676-9. MR 2404107.

2007. Jintai Ding, Bo-Yin Yang, Chen-Mou Cheng, Owen Chen, Vivien Dubois. "Breaking the symmetry: a way to resist the new differential attack." http://eprint.iacr.org/2007/366.

2007. Vivien Dubois, Louis Granboulan, Jacques Stern. "Cryptanalysis of HFE with internal perturbation." MR 2404124. Pages 249–265 in: Tatsuaki Okamoto, Xiaoyun Wang (editors). Public key cryptography—PKC 2007, proceedings of the 10th international conference on practice and theory in public-key cryptography held at Tsinghua University, Beijing, April 16–20, 2007. Lecture Notes in Computer Science 4450. Springer. ISBN 3-540-71676-9. MR 2404107.

2007. Vivien Dubois, Pierre-Alain Fouque, Jacques Stern. "Cryptanalysis of SFLASH with slightly modified parameters." Pages 264–275 in: Moni Naor (editor). Advances in Cryptology—EUROCRYPT 2007. 26th annual international conference on the theory and applications of cryptographic techniques, Barcelona, Spain, May 20–24, 2007, proceedings. Lecture Notes in Computer Science 4515. Springer. ISBN 978-3-540-72539-8.

2007. Vivien Dubois, Pierre-Alain Fouque, Adi Shamir, Jacques Stern. "Practical cryptanalysis of SFLASH." MR 2419591. Pages 1–12 in: Alfred Menezes (editor). Advances in cryptology—CRYPTO 2007, proceedings of the 27th annual international cryptology conference held in Santa Barbara, CA, August 19–23, 2007. Lecture Notes in Computer Science 4622. Springer. ISBN 978-3-540-74142-8.

2008. Xin Jiang, Jintai Ding, Lei Hu. "Kipnis-Shamir attack on HFE revisited." Pages 399–411 in: Dingyi Pei, Moti Yung, Dongdai Lin, Chuankun Wu (editors). Information security and cryptology, third SKLOIS conference, Inscrypt 2007, Xining, China, August 31–September 5, 2007, revised selected papers. Lecture Notes in Computer Science 4990. Springer. ISBN 978-3-540-79498-1.

2008. Jintai Ding, Dieter Schmidt, Fabian Werner. "Algebraic attack on HFE revisited." Pages 215–227 in: Tzong-Chen Wu, Chin-Laung Lei, Vincent Rijmen, Der-Tsai Lee (editors). Information security: 11th international conference, ISC 2008, Taipei, Taiwan, September 15–18, 2008, proceedings. Lecture Notes in Computer Science 5222. Springer. ISBN 978-3-540-85884-3.

2008. Pierre-Alain Fouque, Gilles Macario-Rat, Ludovic Perret, Jacques Stern. "Total break of the l-IC signature scheme." Pages 1–17 in: Ronald Cramer (editor). Public key cryptography—PKC 2008, 11th international workshop on practice and theory in public-key cryptography, Barcelona, Spain, March 9–12, 2008, proceedings. Lecture Notes in Computer Science 4939. Springer. ISBN 978-3-540-78439-5.

Small fields (by themselves or as vinegar)

1993. Adi Shamir. "Efficient signature schemes based on birational permutations." Pages 1–12 in: Douglas R. Stinson (editor). Advances in Cryptology—CRYPTO '93, 13th annual international cryptology conference, Santa Barbara, California, USA, August 22–26, 1993, proceedings. Lecture Notes in Computer Science 773. Springer. ISBN 3-540-57766-1.

1997. Don Coppersmith, Jacques Stern, Serge Vaudenay. "The security of the birational permutation signature schemes." Journal of Cryptology 10, 207–221. MR 99e:94033.

1998. Aviad Kipnis, Adi Shamir. "Cryptanalysis of the oil and vinegar signature scheme." Pages 257–266 in: Hugo Krawczyk (editor). Advances in cryptology—CRYPTO '98, 18th annual international cryptology conference, Santa Barbara, California, USA, August 23–27, 1998, proceedings. Lecture Notes in Computer Science 1462. Springer. ISBN 3-540-64892-5.

1999. Aviad Kipnis, Jacques Patarin, Louis Goubin. "Unbalanced oil and vinegar signature schemes." MR 1717470. Pages 206–222 in: Jacques Stern (editor). Advances in cryptology—EUROCRYPT '99, proceedings of the 17th international conference on the theory and application of cryptographic techniques held in Prague, May 2–6, 1999. Lecture Notes in Computer Science 1592. Springer. ISBN 3-540-65889-0. MR 2000i:94001.

1999. T. Moh. "A public key system with signature and master key functions." Communications in Algebra 27, 2207–2222.

2000. Louis Goubin, Nicolas T. Courtois. "Cryptanalysis of the TTM cryptosystem." MR 2002j:94037. Pages 44–57 in: Tatsuaki Okamoto (editor). Advances in cryptology—ASIACRYPT 2000, proceedings of the 6th annual international conference on the theory and application of cryptology and information security held in Kyoto, December 3–7, 2000. Lecture Notes in Computer Science 1976. Springer. ISBN 3-540-41404-5. MR 2002d:94046.

2001. T. Moh, Jiun-Ming Chen. "On the Goubin-Courtois attack on TTM." http://eprint.iacr.org/2001/072.

2004. Jiun-Ming Chen, Bo-Yin Yang. "A more secure and efficacious TTS signature scheme." Pages 320–338 in: Lecture Notes in Computer Science 2971. Springer. ISBN 3-540-21376-7. MR 2005d:94153.

2004. Jintai Ding, Dieter Schmidt. "The new implementation schemes of the TTM cryptosystem are not secure." MR 2005d:94100. Pages 113–127 in: Keqin Feng, Harald Niederreiter, Chaoping Xing (editors). Coding, cryptography and combinatorics. Progress in Computer Science and Applied Logic 23. Birkhauser. ISBN 3-7643-2429-5.

2004. Jintai Ding, Timothy Hodges. "Cryptanalysis of an implementation scheme of the tamed transformation method cryptosystem." Journal of Algebra and its Applications 3, 273–282. MR 2005f:94093.

2004. Masao Kasahara, Ryuichi Sakai. "A construction of public key cryptosystem for realizing ciphertext of size 100 bit and digital signature scheme." IEICE Transactions on Fundamentals 87-A, 102–109. http://search.ieice.org/bin/summary.php?id=e87-a_1_102&category=D&year=2004&lang=E&abst=.

2004. Bo-Yin Yang, Jiun-Ming Chen, Yen-Hung Chen. "TTS: high-speed signatures on a low-cost smart card." Pages 371–385 in: Marc Joye, Jean-Jacques Quisquater (editors). Cryptographic hardware and embedded systems—CHES 2004, 6th international workshop, Cambridge, MA, USA, August 11–13, 2004, proceedings. Lecture Notes in Computer Science 3156. Springer. ISBN 3-540-22666-4.

2004. Lih-Chung Wang, Fei-Hwang Chang. "Tractable rational map cryptosystem." Version 20040221:212731. http://eprint.iacr.org/2004/046.

2004. Bo-Yin Yang, Jiun-Ming Chen. "TTS: rank attacks in tame-like multivariate PKCs." http://eprint.iacr.org/2004/061.

2005. Masao Kasahara, Ryuichi Sakai. "A construction of public-key cryptosystem based on singular simultaneous equations." IEICE Transactions on Fundamentals 88-A, 74–80. http://search.ieice.org/bin/summary.php?id=e88-a_1_74&category=D&year=2005&lang=E&abst=.

2005. Christopher Wolf, Bart Preneel. "Large superfluous keys in multivariate quadratic asymmetric systems." Pages 275–287 in: Serge Vaudenay (editor). Public key cryptography—PKC 2005: proceedings of the 8th international workshop on theory and practice in public key cryptography held in Les Diablerets, January 23–26, 2005. Lecture Notes in Computer Science 3386. Springer. ISBN 3-540-24454-9. MR 2006d:94072.

2005. An Braeken, Christopher Wolf, Bart Preneel. "A study of the security of unbalanced oil and vinegar signature schemes." MR 2006h:94169. Pages 29–43 in: Alfred Menezes (editor). Topics in cryptology—CT-RSA 2005. Proceedings of the cryptographers' track at the RSA conference held in San Francisco, CA, February 14–18, 2005. Lecture Notes in Computer Science 3376. Springer. MR 2006d:94073. ISBN 3-540-24399-2.

2005. Lih-Chung Wang, Yuh-Hua Hu, Feipei Lai, Chun-yen Chou, Bo-Yin Yang. "Tractable rational map signature." Pages 244–257 in: Serge Vaudenay (editor). Public key cryptography—PKC 2005: proceedings of the 8th international workshop on theory and practice in public key cryptography held in Les Diablerets, January 23–26, 2005. Lecture Notes in Computer Science 3386. Springer. ISBN 3-540-24454-9. MR 2006d:94072.

2005. Bo-Yin Yang, Jiun-Ming Chen. "Building secure tame-like multivariate public-key cryptosystems: the new TTS." Pages 518–531 in: Colin Boyd, Juan Manuel González Nieto (editors). Information security and privacy, 10th Australasian conference, ACISP 2005, Brisbane, Australia, July 4–6, 2005, proceedings. Lecture Notes in Computer Science 3574. Springer. ISBn 3-540-26547-3.

2005. Jintai Ding, Dieter Schmidt. "Rainbow, a new multivariable polynomial signature scheme." Pages 164–175 in: John Ioannidis, Angelos D. Keromytis, Moti Yung (editors). Applied cryptography and network security, third international conference, ACNS 2005, New York, NY, USA, June 7-10, 2005, proceedings. Lecture Notes in Computer Science 3531. Springer. ISBN 3-540-26223-7.

2006. Olivier Billet, Henri Gilbert. "Cryptanalysis of Rainbow." Pages 336–347 in: Roberto De Prisco, Moti Yung (editors). Security and cryptography for networks, 5th international conference, SCN 2006, Maiori, Italy, September 6–8, 2006, proceedings.. Lecture Notes in Computer Science 4116. Springer. ISBN 3-540-38080-9.

2006. Xuyun Nie, Lei Hu, Jianyu Li, Crystal Updegrove, Jintai Ding. "Breaking a new instance of TTM cryptosystems." Pages 210–225 in: Jianying Zhou, Moti Yung, Feng Bao (editors). Applied cryptography and network security, 4th international conference, ACNS 2006, Singapore, June 6-9, 2006, proceedings. Lecture Notes in Computer Science 3989. Springer. ISBN 3-540-34703-8.

2006. Christopher Wolf, An Braeken, Bart Preneel. "On the security of stepwise triangular systems." Designs, Codes and Cryptography 40, 285–302. Older version: 2004. "Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC." Pages 294–309 in: SCN 2004. Lecture Notes in Computer Science 3352. Springer.

2006. Jintai Ding, Dieter Schmidt, Zhijun Yin. "Cryptanalysis of the new TTS scheme in CHES 2004." International Journal of Information Security 5, 231–240.

2006. T. Moh. "The recent attack of Nie et al on TTM is faulty." http://eprint.iacr.org/2006/417

2007. Jintai Ding, Lei Hu, Xuyun Nie, Jianyu Li, John Wanger. "High order linearization equation (HOLE) attack on multivariate public key cryptosystems." MR 2404123. Pages 230–247 in: Tatsuaki Okamoto, Xiaoyun Wang (editors). Public key cryptography—PKC 2007, proceedings of the 10th international conference on practice and theory in public-key cryptography held at Tsinghua University, Beijing, April 16–20, 2007. Lecture Notes in Computer Science 4450. Springer. ISBN 3-540-71676-9. MR 2404107.

2007. Xuyun Nie, Lei Hu, Jintai Ding, Jianyu Li, John Wagner. "Cryptanalysis of the TRMC-4 public key cryptosystem." Pages 104–115 in: Jonathan Katz, Moti Yung (editors). Applied Cryptography and Network Security, 5th international conference, ACNS 2007, Zhuhai, China, June 5–8, 2007, proceedings. Lecture Notes in Computer Science 4521. Springer. ISBN 978-3-540-72737-8.

2007. T. Moh. "Two new examples of TTM." http://eprint.iacr.org/2007/144.

2008. Jintai Ding, Vivien Dubois, Bo-Yin Yang, Chia-Hsin Owen Chen, Chen-Mou Cheng. "Could SFLASH be repaired?" Pages 691–701 in: Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz (editors). Automata, languages and programming, 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, proceedings, part II, track B: logic, semantics, and theory of programming; track C: security and cryptography foundations. Lecture Notes in Computer Science 5126. Springer. ISBN 978-3-540-70582-6.

2008. Jintai Ding, Bo-Yin Yang, Chia-Hsin Owen Chen, Ming-Shing Chen, Chen-Mou Cheng. "New differential-algebraic attacks and reparametrization of Rainbow." Pages 242–257 in: Steven M. Bellovin, Rosario Gennaro, Angelos D. Keromytis, Moti Yung (editors). Applied cryptography and network security, 6th international conference, ACNS 2008, New York, NY, USA, June 3-6, 2008, proceedings. Lecture Notes in Computer Science 5037. Springer. ISBN 978-3-540-68913-3.

2008. Jean-Charles Faugère, Françoise Levy-dit-Vehel, Ludovic Perret. "Cryptanalysis of MinRank." Pages 280–296 in: David Wagner (editor). Advances in cryptology—CRYPTO 2008, 28th annual international cryptology conference, Santa Barbara, CA, USA, August 17–21, 2008, proceedings. Lecture Notes in Computer Science 5157. Springer. ISBN 978-3-540-85173-8.

2008. Luk Bettale, Jean-Charles Faugère, Ludovic Perret: "Cryptanalysis of the TRMS signature scheme of PKC'05." Pages 143–155 in: Serge Vaudenay (editor). Progress in cryptology—AFRICACRYPT 2008, first international conference on cryptology in Africa, Casablanca, Morocco, June 11–14, 2008, proceedings. Lecture Notes in Computer Science 5023. Springer. ISBN 978-3-540-68159-5.

2008. Jintai Ding, John Wagner. "Cryptanalysis of rational multivariate public key cryptosystems." Pages 124–136 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

2008. John Baena, Crystal Clough, Jintai Ding. "Square-vinegar signature scheme." Pages 17–30 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Speedups

2003. Christopher Wolf. "Efficient public key generation for multivariate cryptosystems." http://eprint.iacr.org/2003/089.

2006. Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen, Jiun-Ming Chen. "Implementing minimized multivariate PKC on low-resource embedded systems." Pages 73–88 in: John A. Clark, Richard F. Paige, Fiona Polack, Phillip J. Brooke (editors). Security in pervasive computing, third international conference, SPC 2006, York, UK, April 18-21, 2006, proceedings. Lecture Notes in Computer Science 3934. Springer. ISBN 3-540-33376-2.

2007. Côme Berbain, Olivier Billet, Henri Gilbert. "Efficient implementations of multivariate quadratic systems." Pages 174–187 in: Eli Biham, Amr M. Youssef (editors). Selected areas in cryptography, 13th international workshop, SAC 2006, Montreal, Canada, August 17–18, 2006, revised selected papers. Lecture Notes in Computer Science 4356. Springer. ISBN 978-3-540-74461-0.

2008. Sundar Balasubramanian, Andrey Bogdanov, Andy Rupp, Jintai Ding, Harold W. Carter. "Fast multivariate signature generation in hardware: the case of Rainbow." ASAP 2008. IEEE.

Gröbner bases, XL, F4, F5, etc.

1983. Daniel Lazard. "Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations." MR 86m:13002. Pages 146–156 in: J. A. van Hulzen (editor). Computer algebra: proceedings of the European computer algebra conference (EUROCAL) held in London, March 28–30, 1983. Lecture Notes in Computer Science 162. Springer. ISBN 3-540-12868-9. MR 86f:68004.

1993. Jean-Charles Faugère, Patrizia M. Gianni, Daniel Lazard, Teo Mora. "Efficient computation of zero-dimensional Gröbner bases by change of ordering." Journal of Symbolic Computation 16, 329–344.

1999. Jean-Charles Faugère. "A new efficient algorithm for computing Gröbner bases (F4)." Journal of Pure and Applied Algebra 139, 61–88.

2000. Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, Adi Shamir. "Efficient algorithms for solving overdefined systems of multivariate polynomial equations." MR 1772028. Pages 392–407 in: Bart Preneel (editor). Advances in cryptology—EUROCRYPT 2000, proceedings of the 19th international annual conference on the theory and application of cryptographic techniques held in Bruges, May 14–18, 2000. Lecture Notes in Computer Science 1807. Springer. ISBN 3-540-67517-5. MR 2001b:94028.

2002. Jean-Charles Faugère. "A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)." Pages 75–83 in: Marc Giusti (chair). Proceedings of the 2002 international symposium on symbolic and algebraic computation. ISBN 1-58113-484-3. ACM Press.

2002. Nicolas T. Courtois, Louis Goubin, Willi Meier, Jean-Daniel Tacier. "Solving underdefined systems of multivariate quadratic equations." Pages 211–227 in: David Naccache, Pascal Paillier (editors). Public key cryptography, proceedings of the 5th international workshop on practice and theory in public key cryptosystems (PKC 2002) held in Paris, February 12–14, 2002. Lecture Notes in Computer Science 2274. Springer. ISBN 3-540-43168-3. MR 2005b:94044.

2003. Nicolas T. Courtois, Jacques Patarin. "About the XL algorithm over GF(2)." MR 2080135. Pages 141–157 in: Marc Joye (editor). Topics in cryptology—CT-RSA 2003, the cryptographers' track at the RSA conference 2003, San Francisco, CA, USA, April 13–17, 2003, proceedings. Lecture Notes in Computer Science 2612. Springer. ISBN 3-540-00847-0. MR 2005b:94045.

2004. Bo-Yin Yang, Jiun-Ming Chen. "Theoretical analysis of XL over small fields." Pages 277–288 in: Huaxiong Wang, Josef Pieprzyk, Vijay Varadharajan (editors). Information security and privacy, 9th Australasian conference, ACISP 2004, Sydney, Australia, July 13–15, 2004, proceedings. Lecture Notes in Computer Science 3108. Springer. ISBN 978-3-540-22379-5.

2004. Bo-Yin Yang, Jiun-Ming Chen, Nicolas T. Courtois. "On asymptotic security estimates in XL and Gröbner bases-related algebraic cryptanalysis." Pages 401–413 in: Javier López, Sihan Qing, Eiji Okamoto (editors). Information and communications security, 6th international conference, ICICS 2004, Malaga, Spain, October 27–29, 2004, proceedings. Lecture Notes in Computer Science 3269. Springer. ISBN 978-3-540-23563-7.

2004. Claus Diem. "The XL-algorithm and a conjecture from commutative algebra." MR 2006m:12011. Pages 323–337 in: Pil Joong Lee (editor). Advances in cryptology—ASIACRYPT 2004, proceedings of the 10th international conference on the theory and application of cryptology and information security held on Jeju Island, December 5–9, 2004. Lecture Notes in Computer Science 3329. Springer. ISBN 3-540-23975-8. MR 2006b:94042.

2004. Gwénolé Ars, Jean-Charles Faugère, Hideki Imai, Mitsuru Kawazoe, Makoto Sugita. "Comparison between XL and Gröbner Basis algorithms." Pages 338–353 in: Pil Joong Lee (editor). Advances in cryptology—ASIACRYPT 2004, proceedings of the 10th international conference on the theory and application of cryptology and information security held on Jeju Island, December 5–9, 2004. Lecture Notes in Computer Science 3329. Springer. ISBN 3-540-23975-8. MR 2006b:94042.

2004. Magali Bardet, Jean-Charles Faugère, Bruno Salvy. "On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations." http://www-calfor.lip6.fr/ICPSS/papers/43BF/43bf.htm. Pages 71–74 in: Jean-Charles Faugère, Fabrice Rouillier (editors). Proceedings of the international conference on polynomial system solving.

2004. Bo-Yin Yang, Jiun-Ming Chen. "All in the XL family: theory and practice." MR 2006k:13060. Pages 67–86 in: Choonsik Park, Seongtaek Chee (editors). Information security and cryptology—ICISC 2004, revised selected papers from the 7th International Conference held in Seoul, December 2–3, 2004. Lecture Notes in Computer Science 3506. Springer. ISBN 3-540-26226-1. MR 2006j:94101.

2005. Magali Bardet, Jean-Charles Faugère, Bruno Salvy, Bo-Yin Yang. "Asymptotic expansion of the index of regularity of quadratic semi-regular polynomial systems." http://www-spiral.lip6.fr/~bardet/Publis/bardet_et_all_MEGA05.pdf

2006. Bo-Yin Yang, Chia-Hsin Owen Chen, Jiun-Ming Chen. "The limit of XL implemented with sparse matrices." Pages 215–225 in: http://postquantum.cr.yp.to/pqcrypto2006record.pdf

2008. Jintai Ding, Johannes Buchmann, Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Ralf-Philipp Weinmann. "MutantXL." http://www.cdc.informatik.tu-darmstadt.de/reports/reports/MutantXL_Algorithm.pdf.

2008. Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding, Johannes Buchmann. "Solving polynomial equations over GF(2) using an improved mutant strategy." Pages 203–215 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Detecting equivalent polynomials

2002. Willi Geiselmann, Willi Meier, Rainer Steinwandt. "An attack on the Isomorphisms of Polynomials problem with one secret." http://eprint.iacr.org/2002/143.

2003. Françoise Levy-dit-Vehel, Ludovic Perret. "Polynomial equivalence problems and applications to multivariate cryptosystems." MR 2005e:94175. Pages 235–251 in: Thomas Johansson, Subhamoy Maitra (editors). Proceedings in cryptology—INDOCRYPT 2003. Proceedings of the 4th international conference on cryptology in India held in New Delhi, December 8–10, 2003. Lecture Notes in Computer Science 2904. Springer. ISBN 3-540-20609-4. MR 2005d:94154.

2005. Ludovic Perret. "A fast cryptanalysis of the isomorphism of polynomials with one secret problem." Pages 354–370 in: Ronald Cramer (editor). Advances in cryptology—EUROCRYPT 2005. Proceedings of the 24th annual international conference on the theory and applications of cryptographic techniques held in Aarhus, May 22–26, 2005. Lecture Notes in Computer Science 3494. Springer. ISBN 3-540-25910-4. MR 2008e:94035.

2006. Jean-Charles Faugère, Ludovic Perret. "Polynomial equivalence problems: algorithmic and theoretical aspects." Pages 30–47 in: Serge Vaudenay (editor). 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. Lecture Notes in Computer Science 4004. Springer. ISBN 3-540-34546-9.

2006. Jean-Charles Faugère, Ludovic Perret. "Cryptanalysis of 2R^- schemes." MR 2422172. Pages 357–372 in: Cynthia Dwork (editor). Advances in cryptology—CRYPTO 2006. Proceedings of the 26th annual international cryptology conference held in Santa Barbara, CA, August 20–24, 2006. Lecture Notes in Computer Science 4117. Springer. ISBN 978-3-540-37432-9. MR 2422188.

Hashing, block ciphers, etc.

2003. Nicolas T. Courtois. "Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt." MR 2005d:94098. Pages 182–199 in: Pil Joong Lee, Chae Hoon Lim (editors). Information security and cryptology—ICISC 2002, papers from the 5th international conference held in Seoul, November 28–29, 2002. Lecture Notes in Computer Science 2587. Springer. ISBN 3-540-00716-4. MR 2005b:94052.

2003. Nicolas T. Courtois, Willi Meier. "Algebraic attacks on stream ciphers with linear feedback." MR 2005e:94098. Pages 345–359 in: Eli Biham (editor). Advances in cryptology—EUROCRYPT 2003, proceedings of the 22nd international conference on the theory and applications of cryptographic techniques held in Warsaw, May 4–8, 2003. Lecture Notes in Computer Science 2656. Springer. ISBN 3-540-14039-5. MR 2005c:94003.

2003. Nicolas T. Courtois. "Fast algebraic attacks on stream ciphers with linear feedback." MR 2005e:94131. Pages 176–194 in: Dan Boneh (editor). Advances in cryptology—CRYPTO 2003, proceedings of the 23rd annual international cryptology conference held in Santa Barbara, CA, August 17–21, 2003. Lecture Notes in Computer Science 2729. Springer. ISBN 3-540-40674-3. MR 2005d:94151.

2003. Frederik Armknecht, Matthias Krause. "Algebraic attacks on combiners with memory." Pages 162–176 in: Dan Boneh (editor). Advances in cryptology—CRYPTO 2003, proceedings of the 23rd annual international cryptology conference held in Santa Barbara, CA, August 17–21, 2003. Lecture Notes in Computer Science 2729. Springer. ISBN 3-540-40674-3. MR 2005d:94151.

2007. Olivier Billet, Matthew J. B. Robshaw, Thomas Peyrin. "On building hash functions from multivariate quadratic equations." Pages 82–95 in: Josef Pieprzyk, Hossein Ghodosi, Ed Dawson (editors). Information security and privacy, 12th Australasian conference, ACISP 2007, Townsville, Australia, July 2-4, 2007, proceedings. Lecture Notes in Computer Science 4586. Springer. ISBN 978-3-540-73457-4.

2007. Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai. "Algebraic cryptanalysis of 58-round SHA-1." Pages 349–365 in: Alex Biryukov (editor). Fast software encryption, 14th international workshop, FSE 2007, Luxembourg, Luxembourg, March 26–28, 2007, revised selected papers. Lecture Notes in Computer Science 4593. Springer. ISBN 978-3-540-74617-1.

2007. Jean-Philippe Aumasson, Willi Meier. "Analysis of multivariate hash functions." Pages 309–323 in: Kil-Hyun Nam and Gwangsoo Rhee (editors). Information security and cryptology—ICISC 2007, 10th international conference, Seoul, Korea, November 29–30, 2007, proceedings. Lecture Notes in Computer Science 4817. Springer. ISBN 978-3-540-76787-9.

2008. Jintai Ding, Bo-Yin Yang. "Multivariates polynomials for hashing." Pages 358–371 in: Dingyi Pei, Moti Yung, Dongdai Lin, Chuankun Wu (editors). Information security and cryptology, third SKLOIS conference, Inscrypt 2007, Xining, China, August 31–September 5, 2007, revised selected papers. Lecture Notes in Computer Science 4990. Springer. ISBN 978-3-540-79498-1.

Surveys

2005. Christopher Wolf. "Multivariate quadratic polynomials in public key cryptography." http://eprint.iacr.org/2005/393.

2006. Jintai Ding, Dieter Schmidt. "Multivariable public-key cryptosystems." MR 2008a:94115. Pages 79–94 in: Dinh V. Huynh, S. K. Jain, S. R. Lopez-Permouth (editors). Algebra and its applications: papers from the international conference held at Ohio University, Athens, OH, March 22–26, 2005. Contemporary Mathematics 419. AMS. ISBN 0-8218-3842-3. MR 2007h:16002.

2006. Jintai Ding, Jason E. Gower, Dieter S. Schmidt. Multivariable public key cryptosystems. Advances in Information Security 25. Springer. ISBN 0-387-32229-9. MR 2007i:94049.

2009. Jintai Ding, Bo-Yin Yang. "Multivariate public key cryptography." Pages 193–242 in: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.

Version