SALSA   LIP6 Calcul Scientifique UMPC

Main Publications - Jean-Charles Faugère

Journal Papers

KEY J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity. Journal of Symbolic Computation, pages 1-39, 2010. Available online 4 November 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and Y. Liang. Artificial discontinuities of single-parametric Gröbner bases. Journal of Symbolic Computation, In Press, Accepted Manuscript:1-17, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY L. Bettale, J.-C. Faugère, and L. Perret. Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology, 3(3):177197, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY G. Bourgeois and J.-C. Faugère. Algebraic Attack on NTRU using Witt Vectors and Gröbner bases. Journal of Mathematical Cryptology, 3(3):205-214, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY D. Augot, M. Bardet, and J.-C. Faugère. On the decoding of binary cyclic codes with the Newton identities. Journal of Symbolic Computation, 44(12):1608-1625, 2009. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and L. Perret. An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography. Journal of Symbolic Computation, 44(12):1676-1689, 2009. [ bib | Digital Object Identifier | Download PDF ]
KEY F. Cazals, J.-C. Faugère, M. Pouget, and F. Rouillier. Ridges and Umbilics of Polynomial Parametric Surfaces. Geometric Modeling and Algebraic Geometry, pages 141-159, 2008. [ bib | Digital Object Identifier | Download PDF ]
KEY R.J. Cameron, J.-C. Faugère, F. Rouillier, and F. Seyfert. Exhaustive approach to the coupling matrix synthesis problem and application to the design of high degree asymmetric filters. Int J RF and Microwave Comp Aid Eng, 17(1):4-12, January 2007. [ bib | Digital Object Identifier | Download PDF ]
KEY F. Cazals, J.-C. Faugère, M. Pouget, and F. Rouillier. The implicit structure of ridges of a smooth parametric surface. Comput. Aided Geom. Des., 23(7):582-598, October 2006. [ bib | Digital Object Identifier | Download PDF ]
KEY A. Basiri, A. Enge, J.-C. Faugère, and N. Gürel. The arithmetic of jacobian groups of superelliptic cubics. Mathematics of Computation, 74(249):389-410, 2005. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, M. Hering, and J. Phan. The membrane inclusions curvature equations. Advances in Applied Mathematics, 31(4):643-658, June 2003. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1-3):61-88, June 1999. [ bib | Digital Object Identifier | Download PDF ]
KEY J.C. Faugère, F. Moreau de Saint-Martin, and F. Rouillier. Design of regular nonseparable bidimensional wavelets using Grobner basis techniques. Signal Processing, IEEE Transactions on, 46(4):845 -856, April 1998. Special Issue on Theory and Applications of Filter Banks and Wavelets. [ bib | Digital Object Identifier | Download PDF ]
KEY J.C. Faugère and D. Lazard. Combinatorial classes of parallel manipulators. Mechanism and Machine Theory, 30(6):765-776, 1995. [ bib | Digital Object Identifier | Download PDF ]
KEY J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering. Journal of Symbolic Computation, 16(4):329-344, 1993. [ bib | Digital Object Identifier | Download PDF ]

Fully Refereed International Conferences Papers: : Rank A+ or A

KEY J.-C. Faugère, J. von zur Gathen, and L. Perret. Decomposition of Generic Multivariate Polynomials. In ISSAC '10: Proceedings of the 2010 international symposium on Symbolic and algebraic computation, ISSAC '10, pages 131-137, New York, NY, USA, 2010. ACM. isbn: 0747-7171 (updated version). [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. Computing Loci of Rank Defects of Linear Matrices using Grobner Bases and Applications to Cryptology. In ISSAC '10: Proceedings of the 2010 international symposium on Symbolic and algebraic computation, ISSAC '10, pages 257-264, New York, NY, USA, 2010. ACM. Best Student Paper Award. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, A. Otmani, L. Perret, and J.-P. Tillich. Algebraic Cryptanalysis of McEliece variants with compact keys. In Proceedings of Eurocrypt 2010, volume 6110 of Lecture Notes in Computer Science, pages 279-298. Springer Verlag, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and P.-J. Spaenlehauer. Algebraic Cryptanalysis of the PKC'09 Algebraic Surface Cryptosystem. In P.Q. Nguyen and D. Poincheval, editors, Public Key Cryptography PKC 2010, volume 6056 of Lecture Notes in Computer Science, pages 35-52. Springer-Verlag, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, R. Marinier, and G. Renault. Implicit Factoring with Shared Most Significant and Middle Bits. In P.Q. Nguyen and D. Poincheval, editors, in 13th International Conference on Practice and Theory in Public Key Cryptography - PKC 2010, volume 6056 of Lecture Notes in Computer Science, pages 70-87. Springer-Verlag, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and L. Perret. High order derivatives and decomposition of multivariate polynomials. In ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC '09, pages 207-214, New York, NY, USA, 2009. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and S. Rahmany. Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases. In ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC '09, pages 151-158, New York, NY, USA, 2009. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, F. Levy-dit Vehel, and L. Perret. Cryptanalysis of minrank. In David Wagner, editor, Advances in Cryptology CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 280-296, Berlin, Heidelberg, August 2008. Springer-Verlag. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, G. Moroz, F. Rouillier, and M. Safey El Din. Classification of the Perspective-Three-Point problem, discriminant variety and real solving polynomial systems of inequalities. In D. Jeffrey, editor, ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, pages 79-86, New York, NY, USA, 2008. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and L. Perret. Cryptanalysis of 2R- Schemes. In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, volume 4117 of Lecture Notes in Computer Science, pages 357-372. Springer Berlin / Heidelberg, August 2006. 10.1007/11818175_21. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and L. Perret. Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 30-47. Springer Berlin / Heidelberg, 2006. 10.1007/11761679_3. [ bib | Digital Object Identifier | Download PDF ]
KEY A. Basiri, A. Enge, J.-C. Faugère, and N. Gürel. Implementing the Arithmetic of C_3,4 Curves. In Duncan Buell, editor, Algorithmic Number Theory, volume 3076 of Lecture Notes in Computer Science, pages 87-101. Springer Berlin / Heidelberg, June 2004. 10.1007/978-3-540-24847-7_6. [ bib | Digital Object Identifier | Download PDF ]
KEY G. Ars, J.-C. Faugère, H. Imai, M. Kawazoe, and M. Sugita. Comparison Between XL and Gröbner Basis Algorithms. In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, volume 3329 of Lecture Notes in Computer Science, pages 157-167. Springer Berlin / Heidelberg, 2004. 10.1007/978-3-540-30539-2_24. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and A. Joux. Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In Boneh Dan, editor, Advances in Cryptology - CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 44-60. Springer Berlin / Heidelberg, 2003. 10.1007/978-3-540-45146-4_3. [ bib | Digital Object Identifier | Download PDF ]
KEY A. Basiri and J.-C. Faugère. Changing the ordering of Gröbner bases with LLL: case of two variables. In Proceedings of the 2003 international symposium on Symbolic and algebraic computation, ISSAC '03, pages 23-29, New York, NY, USA, 2003. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC '02, pages 75-83, New York, NY, USA, 2002. ACM. [ bib | Digital Object Identifier | Download PDF ]

Fully Refereed International Conferences Papers: : Rank B or C

KEY J.-C. Faugère, R. Odegard, L. Perret, and D. Gligoroski. Analysis of the MQQ Public Key Cryptosystem. In Swee-Huay Heng, Rebecca N. Wright, and Bok-Min Goi, editors, Ninth International Conference on Cryptology And Network Security (CANS 2010), volume 6467 of Subseries: Security and Cryptology, pages 1-14. Springer-Verlag, December 2010. [ bib | Download PDF ]
KEY M. Albrecht, C. Cid, T. Dulien, J.-C. Faugère, and L. Perret. Algebraic Precomputations in Differential Cryptanalysis. In M. Yung and X. Lai, editors, Information Security and Cryptology: 6th International Conference, Inscrypt 2010, Revised Selected Papers, volume To appear, pages 1-18. Springer-Verlag, October 2010. [ bib | Download PDF ]
KEY J.-C. Faugère. FGb: A Library for Computing Gröbner Bases. In Komei Fukuda, Joris Hoeven, Michael Joswig, and Nobuki Takayama, editors, Mathematical Software ICMS 2010, volume 6327 of Lecture Notes in Computer Science, pages 84-87, Berlin, Heidelberg, September 2010. Springer Berlin / Heidelberg. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and S. Lachartre. Parallel Gaussian Elimination for Gröbner bases computations in finite fields. In M. Moreno-Maza and J.L. Roch, editors, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, PASCO '10, pages 89-97, New York, NY, USA, July 2010. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, A Otmani, L. Perret, and J.-P. Tillich. Algebraic Cryptanalysis of McEliece variants with compact keys - toward a complexity analysis. In SCC '10: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pages 45-55, RHUL, June 2010. [ bib | Download PDF ]
KEY J.-C. Faugère, R. Odegard, L. Perret, and D. Gligoroski. Analysis of the MQQ Public Key Cryptosystem. In SCC'10: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pages 101-116, RHUL, June 2010. [ bib | Download PDF ]
KEY L. Bettale, J.-C. Faugère, and L. Perret. Hybrid Approach : a Tool for Multivariate Cryptography. In Tools'10: Proceedings of the Workshop on Tools for Cryptanalysis 2010, pages 1-2, RHUL, June 2010. Ecrypt II. [ bib | Download PDF ]
KEY M. Albrecht, C. Cid, T. Dulien, J.-C. Faugère, and L. Perret. Algebraic Precomputations in Differential Cryptanalysis. In Tools'10: Proceedings of the Workshop on Tools for Cryptanalysis 2010, pages 1-14, RHUL, June 2010. Ecrypt II. [ bib | Download PDF ]
KEY J.-C. Faugère and L. Perret. Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages. In M. Yung and F. Bao, editors, Information Security and Cryptology: 5th International Conference, Inscrypt 2009, Beijing, China, December, 2009, Revised Selected Papers, volume 6151, pages 266-277, Berlin, Heidelberg, 2010. Springer-Verlag. [ bib | Download PDF ]
KEY J.-C. Faugère, A. Joux, L. Perret, and J. Treger. Cryptanalysis of the Hidden Matrix Cryptosystem. In Michel Abdalla and Paulo Barreto, editors, Progress in Cryptology LATINCRYPT 2010, volume 6212 of Lecture Notes in Computer Science, pages 241-254. Springer Berlin / Heidelberg, 2010. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, R. Marinier, and G. Renault. Implicit Factoring with Shared Most Significant and Middle Bits. In SCC '10: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pages 197-201, RHUL, 2010. [ bib | Download PDF ]
KEY J.-C. Faugère, A Otmani, L. Perret, and J.-P. Tillich. A Distinguisher for High Rate McEliece Cryptosystem - Extended Abstract. In P. Véron, editor, Yet Another Conference on Cryptography, YACC 2010, pages 1-4, Toulon, 2010. [ bib | Download PDF ]
KEY J.-C. Faugère, A Otmani, L. Perret, and J.-P. Tillich. Algebraic Cryptanalysis of McEliece variants with compact keys - toward a complexity analysis. In P. Véron, editor, Yet Another Conference on Cryptography, YACC 2010, pages 1-4, Toulon, 2010. [ bib | Download PDF ]
KEY J.-C. Faugère. Structured Polynomial Systems and Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In DSO National Labs, pages 1-1, January 2010. [ bib ]
KEY L. Bettale, J.-C. Faugère, and L. Perret. Security Analysis of Multivariate Polynomials for Hashing. In Moti Yung, Dongdai Lin, and Peng Liu, editors, Information Security and Cryptology: 4th International Conference, Inscrypt 2008, Revised Selected Papers, volume 5487, pages 115-124, Berlin, Heidelberg, December 2009. Springer-Verlag. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère, L. Perret, and P.-J. Spaenlehauer. Algebraic-Differential Cryptanalysis of DES. In Western European Workshop on Research in Cryptology - WEWoRC 2009, pages 1-5, July 2009. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère. Efficient algorithms to compute Groebner Bases and applications in Cryptology. In Polynomial Computer Algebra'09, pages 1-1, April 2009. [ bib ]
KEY J.-C. Faugère. Interactions between computer algebra (Gröbner bases) and cryptology. In ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC '09, pages 383-384, New York, NY, USA, 2009. ACM. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère. Solving Structured Polynomial Systems and Applications to Cryptology. In Vladimir Gerdt, Ernst Mayr, and Evgenii Vorozhtsov, editors, Computer Algebra in Scientific Computing - CASC'09, volume 5743 of Lecture Notes in Computer Science, pages 79-80. Springer Berlin / Heidelberg, 2009. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C Faugère. On the complexity of the Minrank problem. In Second Workshop on Mathematical Cryptology, pages 2-3, Santander, Spain, October 2008. [ bib ]
KEY J.-C. Faugère and L. Perret. High order derivatives and decomposition of multivariate polynomials. In Second Workshop on Mathematical Cryptology, pages 15-19, Santander (Spain), October 2008. [ bib ]
KEY J.-C. Faugère and L. Perret. On the Security of UOV. In First International Conference on Symbolic Computation and Cryptography, SCC 08, LMIB, pages 103-109, Beijing, China, April 2008. [ bib | Download PDF ]
KEY I. Simonetti, J.-C. Faugère, and L. Perret. Algebraic Attack Against Trivium. In First International Conference on Symbolic Computation and Cryptography, SCC 08, LMIB, pages 95-102, Beijing, China, April 2008. [ bib | Download PDF ]
KEY L. Bettale, J.-C. Faugère, and L Perret. Cryptanalysis of the TRMS Cryptosystem of PKC'05. In Serge Vaudenay, editor, AfricaCrypt 2008, volume 5023 of Lecture Notes in Computer Science, pages 143-155, Casablanca, Morocco, 2008. Springer. [ bib | Digital Object Identifier | Download PDF ]

Book Chapter

KEY J.-C. Faugère and M. Safey El Din. Mathématiques Appliquées (L3), chapter De l'algèbre linéaire à la résolution des systèmes polynomiaux, pages 331-388. Pearson, 2009. isbn: 978-2-7440-7352-6. [ bib ]
KEY F. Cazals, J.-C. Faugère, M. Pouget, and F. Rouillier. Ridges and Umbilics of Polynomial Parametric Surfaces, volume 8, chapter 8, pages 141-160. Springer, 2008. isbn: 978-3-540-72184-0. [ bib | Download PDF ]

Books or Special Issues

KEY J.-C. Faugère and L. Perret. Symbolic Computation and Cryptography, volume 3. Birkhäuser and Springer, Mathematics in Computer Science, 2010. isbn: 1661-8270. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and C. Cid, editors. Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography (SCC 2010), Royal Holloway, University of London, Egham, June, 2010. Royal Holloway, University of London, 2010. isbn: 0000-0000. [ bib | Download PDF ]
KEY J.-C. Faugère and F. Rouillier. Polynomial system solving, volume 44. Academic Press, Inc., Journal of Symbolic Computation, 2009. isbn: 0747-7171. [ bib | Digital Object Identifier | Download PDF ]
KEY D. Augot, J.-C. Faugère, and L. Perret. Gröbner Bases Techniques in Coding Theory and Cryptography, volume 44. Academic Press, Inc., Journal of Symbolic Computation, 2009. isbn: 0747-7171. [ bib | Digital Object Identifier | Download PDF ]
KEY J.-C. Faugère and D. Wang, editors. Proceedings of the First International Conference on Symbolic Computation and Cryptography (SCC 2008), Beijing, China, April 28-30, 2008. Beihang University, China, 2008. isbn: 0000-0000. [ bib ]

Ph.D. Thesis - Habilitation

KEY J.-C. Faugère. Calcul efficace des bases de Gröbner et Applications. PhD thesis, HDR, Université Paris 6, 2007. [ bib ]
KEY J.-C. Faugère. Résolution des systèmes d'équations algébriques. PhD thesis, PhD thesis, Université Paris 6, 1994. [ bib | Download PDF ]