M. R. Albrecht, P. Farshim, J. Faugère, and L. Perret, Polly Cracker, Revisited, Advances in Cryptology ? ASIACRYPT 2011, pp.179-196, 2011.
DOI : 10.1007/978-3-642-25385-0_10
URL : https://hal.archives-ouvertes.fr/hal-01112976

M. R. Albrecht, J. Faugère, D. Lin, and L. Perret, Polynomials With Errors (PWE). in preparation, 2012.

B. Applebaum, D. Cash, C. Peikert, and A. Sahai, Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems, Advances in Cryptography -CRYPTO 2009, pp.595-618, 2009.
DOI : 10.1007/978-3-642-03356-8_35

S. Arora and R. Ge, New Algorithms for Learning in Presence of Errors, Lecture Notes in Computer Science, vol.6755, issue.1, pp.403-415, 2011.
DOI : 10.1007/978-3-540-85174-5_31

G. Ars, Applications des bases de GröbnerGröbner`Gröbnerà la cryptographie, 2005.

G. V. Bard, N. T. Courtois, and C. Jefferson, Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers. Cryptology ePrint Archive, Report, vol.024, p.24, 2007.

M. Bardet, ´ Etude des systèmes algébriques surdéterminés Applications aux codes correcteurs etàet`età la cryptographie, 2004.

M. Bardet, J. Faugère, and B. Salvy, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, International Conference on Polynomial System Solving - ICPSS, pp.71-75, 2004.

M. Bardet, J. Faugère, B. Salvy, and B. Yang, Asymptotic expansion of the degree of regularity for semi-regular systems of equations, Algebraic Geometry Conference, pp.1-14, 2005.

B. Barkee, D. Cac-can, J. Ecks, T. Moriarty, and R. F. Ree, Why You Cannot Even Hope to use Gr??bner Bases in Public Key Cryptography: An Open Letter to a Scientist Who Failed and a Challenge to Those Who Have Not Yet Failed, Journal of Symbolic Computation, vol.18, issue.6, pp.497-501, 1994.
DOI : 10.1006/jsco.1994.1061

D. Bayer and M. Stillman, On the complexity of computing syzygies, Journal of Symbolic Computation, vol.6, issue.2-3, pp.1-13, 1988.
DOI : 10.1016/S0747-7171(88)80039-7

T. Becker and V. Weispfenning, Gröbner Bases -A Computational Approach to Commutative Algebra, 1991.

M. Bellare, T. Ristenpart, and S. Tessaro, Multi-instance security and its application to passwordbased cryptography, pp.312-329
DOI : 10.1007/978-3-642-32009-5_19
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.231.129

M. Bellare and P. Rogaway, The Security of Triple Encryption and a Framework??for??Code-Based??Game-Playing??Proofs, Advances in Cryptology ? EUROCRYPT, pp.409-426, 2004.
DOI : 10.1007/11761679_25

C. Berbain, H. Gilbert, and J. Patarin, QUAD: A multivariate stream cipher with provable security, Journal of Symbolic Computation, vol.44, issue.12, pp.1703-1723, 2009.
DOI : 10.1016/j.jsc.2008.10.004

Z. Brakerski, When homomorphism becomes a liability Cryptology ePrint Archive, 2012.

Z. Brakerski, C. Gentry, and V. Vaikuntanathan, (leveled) fully homomorphic encryption without bootstrapping, ITCS, pp.309-325, 2012.
DOI : 10.1145/2090236.2090262
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.456.1531

Z. Brakerski and V. Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.97-106, 2011.
DOI : 10.1109/FOCS.2011.12
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.400.6463

B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, 1965.

B. Buchberger, Gröbner bases: an algorithmic method in polynomial ideal theory, Multidimensional Systems Theory. D, 1985.

B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, Journal of Symbolic Computation, vol.41, pp.3-4475, 2006.

S. Bulygin, Chosen-ciphertext attack on noncommutative Polly Cracker. CoRR, abs, p.508015, 2005.

M. Caboara, F. Caruso, and C. Traverso, Lattice Polly Cracker cryptosystems, Journal of Symbolic Computation, vol.46, issue.5, pp.534-549, 2011.
DOI : 10.1016/j.jsc.2010.10.004
URL : http://doi.org/10.1016/j.jsc.2010.10.004

Y. Chen and P. Q. Nguyen, Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers, Pointcheval and Johansson [58], pp.502-519
DOI : 10.1007/978-3-642-29011-4_30
URL : https://hal.archives-ouvertes.fr/hal-00864374

H. Cohn and N. Heninger, Approximate common divisors via lattices. Cryptology ePrint Archive, Report, vol.437, 2011.
DOI : 10.2140/obs.2013.1.271
URL : http://arxiv.org/abs/1108.2714

A. Jean-sébastien-coron, D. Mandal, M. Naccache, and . Tibouchi, Fully Homomorphic Encryption over the Integers with Shorter Public Keys, Lecture Notes in Computer Science, vol.6841, pp.487-504, 2011.
DOI : 10.1007/978-3-642-22792-9_28

D. Jean-sebastien-coron, M. Naccache, and . Tibouchi, Public key compression and modulus switching for fully homomorphic encryption over the integers, Cryptology ePrint Archive Report, vol.440, 2011.

T. Nicolas, J. Courtois, and . Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations, Advances in Cryptology ? ASIACRYPT 2002, pp.267-287, 2002.

D. Cox, J. Little, and D. O. Shea, Ideals, Varieties, and Algorithms, 2005.

R. Cramer and V. Shoup, Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, SIAM Journal on Computing, vol.33, issue.1, pp.167-226, 2003.
DOI : 10.1137/S0097539702403773

A. Dickenstein, N. Fitchas, M. Giusti, and C. Sessa, The membership problem for unmixed polynomial ideals is solvable in single exponential time, Discrete Applied Mathematics, vol.33, issue.1-3, pp.73-94, 1991.
DOI : 10.1016/0166-218X(91)90109-A

F. Levy, M. G. Vehel, L. Marinari, C. Perret, and . Traverso, A survey on Polly Cracker systems, Massimiliano Sala Gröbner Bases. Coding and Cryptography, pp.285-305, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00974896

J. Faugère, A new efficient algorithm for computing Gr??bner bases (F4), Journal of Pure and Applied Algebra, vol.139, issue.1-3, pp.61-88, 1999.
DOI : 10.1016/S0022-4049(99)00005-5

J. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp.75-83, 2002.

J. Faugère, P. M. Gianni, D. Lazard, and T. Mora, Efficient Computation of Zero- Dimensional Gröbner Bases by Change of Ordering, Journal of Symbolic Computation 16, pp.329-344, 1993.

J. Faugère and A. Joux, Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases, Advances in Cryptology ? CRYPTO 2003, 2003.

J. Faugère and S. Rahmany, Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, ISSAC '09, pp.151-158, 2009.

M. Fellows, N. Koblitz, !. In, G. L. Mullen, and P. J. Shiue, Combinatorial cryptosystems galore!, Finite Fields: Theory, Applications, and Algorithms, pp.51-61, 1994.
DOI : 10.1090/conm/168/01688

C. Gentry, A fully homomorphic encryption scheme, 2009.

C. Gentry, Fully homomorphic encryption using ideal lattices, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.169-178, 2009.
DOI : 10.1145/1536414.1536440
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.362.7592

C. Gentry and S. Halevi, Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.107-109, 2011.
DOI : 10.1109/FOCS.2011.94

C. Gentry and S. Halevi, Implementing Gentry???s Fully-Homomorphic Encryption Scheme, Advances in Cryptology ? EUROCRYPT 2010, pp.129-148, 2011.
DOI : 10.1007/978-3-642-20465-4_9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.400.6183

C. Gentry, S. Halevi, and N. P. Smart, Better Bootstrapping in Fully Homomorphic Encryption, Public Key Cryptography ? PKC 2012, 2012.
DOI : 10.1007/978-3-642-30057-8_1

C. Gentry, S. Halevi, and N. P. Smart, Homomorphic Evaluation of the AES Circuit, pp.850-867
DOI : 10.1007/978-3-642-32009-5_49

J. Håstad, S. Phillips, and S. Safra, A well-characterized approximation problem, [1993] The 2nd Israel Symposium on Theory and Computing Systems, pp.301-305, 1993.
DOI : 10.1109/ISTCS.1993.253463

G. Herold, Polly Cracker, Revisited, Revisited, Public Key Cryptography ? PKC 2012, pp.17-33
DOI : 10.1007/978-3-642-30057-8_2
URL : https://hal.archives-ouvertes.fr/hal-01112976

N. Koblitz, A. J. Menezes, Y. Wu, and R. J. Zuccherato, Algebraic aspects of cryptography, 1998.
DOI : 10.1007/978-3-662-03642-6

D. Lazard, Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, 1983.

R. Lindner and C. Peikert, Better Key Sizes (and Attacks) for LWE-Based Encryption, Lecture Notes in Computer Science, vol.66, issue.6, pp.319-339, 2011.
DOI : 10.1007/3-540-45708-9_19

V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings, Advances in Cryptology ? EUROCRYPT 2010, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00921792

C. Aguilar-melchor, P. Gaborit, and J. Herranz, Additively Homomorphic Encryption with d-Operand Multiplications, Advances in Cryptology ? CRYPTO 2010, pp.138-154, 2010.
DOI : 10.1007/978-3-642-14623-7_8

D. Micciancio and O. Regev, Lattice-based cryptography, Post-Quantum Cryptography, pp.147-191, 2009.

F. Mora, De Nugis Groebnerialium 2: Applying Macaulay's Trick in Order to Easily Write a Gr??bner Basis, Applicable Algebra in Engineering, Communication and Computing, vol.13, issue.6, pp.437-446, 2003.
DOI : 10.1007/s00200-002-0112-2

M. Naehrig, K. Lauter, and V. Vaikuntanathan, Can homomorphic encryption be practical?, Proceedings of the 3rd ACM workshop on Cloud computing security workshop, CCSW '11, pp.113-124, 2011.
DOI : 10.1145/2046660.2046682

C. Peikert, V. Vaikuntanathan, and B. Waters, A Framework for Efficient and Composable Oblivious Transfer, Advances in Cryptology ? CRYPTO 2008, pp.554-571, 2008.
DOI : 10.1007/978-3-540-85174-5_31

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, vol.5634, pp.1-3440, 2009.

O. Regev, The learning with errors problem, IEEE Conference on Computational Complexity 2010, pp.191-204, 2010.

R. Rothblum, Homomorphic Encryption: From Private-Key to Public-Key, Lecture Notes in Computer Science, vol.6597, pp.219-234, 2011.
DOI : 10.1007/978-3-642-19571-6_14

M. Rückert and M. Schneider, Estimating the security of lattice-based cryptosystems. Cryptology ePrint Archive, Report, vol.137137, 2010.

P. Nigel, F. Smart, and . Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes, Public Key Cryptography, pp.420-443, 2010.

W. Stein, The Sage Development Team, 2011.

A. J. Stothers, On the Complexity of Matrix Multiplication, 2010.

M. Van-dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, Fully Homomorphic Encryption over the Integers, Gilbert [46], pp.24-43
DOI : 10.1007/978-3-642-13190-5_2

J. Von, Z. Gathen, and J. Gerhard, Modern computer algebra, 2003.

V. Vassilevska and W. , Multiplying matrices faster than Coppersmith-Winograd, STOC, pp.887-898, 2012.

W. Shang, X. Zhao, and . Gao, Minimal achievable approximation ratio for MAX-MQ in finite fields, Theor. Comput. Sci, vol.410, pp.21-232285, 2009.