. Ring-sis and . Ring-lwe, est de trouver une petite base d'un réseau correspondantàcorrespondantà un idéal d'un anneau de polynômes Z[x]/f (x) [44], où a un idéal de l'anneau d'entiers d'un corps de nombres, Certaines constructions cryptographiquesàcryptographiquesà partir de SIS et LWE se transposent facilementàfacilementà Ring-SIS et Ring-LWE

. Remerciements, Ce travail a ´ eté financé en partie par le Conseil Européen de la Recherche (ERC Starting Grant ERC-2013-StG-335086-LATTAC) Nous remercions Guilhem Castagnos pour sa lecture attentive de ce chapitre

R. , .. M. Abdalla, M. Bellare, D. Catalano, E. Kiltz et al., Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions, J. Cryptology, vol.21, issue.3, pp.350-391, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00918362

S. Agrawal, D. Boneh, and X. Boyen, Efficient Lattice (H)IBE in the Standard Model, Proc. of Eurocrypt 2010, pp.553-572, 2010.
DOI : 10.1007/978-3-642-13190-5_28

S. Agrawal, D. Boneh, and X. Boyen, Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE, Proc. of Crypto 2010, pp.98-115, 2010.
DOI : 10.1007/978-3-642-14623-7_6

S. Agrawal, X. Boyen, V. Vaikuntanathan, P. Voulgaris, and H. Wee, Functional Encryption for Threshold Functions (or Fuzzy IBE) from Lattices, Proc. of PKC, pp.280-297, 2012.
DOI : 10.1007/978-3-642-30057-8_17

S. Agrawal, D. M. Freeman, and V. Vaikuntanathan, Functional Encryption for Inner Product Predicates from Learning with Errors, Proc. of Asiacrypt 2011, pp.21-40, 2011.
DOI : 10.1007/978-3-642-25385-0_2

M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , STOC '96, pp.99-108, 1996.
DOI : 10.1145/237814.237838

M. Ajtai, Generating Hard Instances of the Short Basis Problem, Proc. of ICALP, pp.1-9, 1999.
DOI : 10.1007/3-540-48523-6_1

J. Alwen and C. Peikert, Generating Shorter Bases for Hard Random Lattices, Theory of Computing Systems, vol.26, issue.5, pp.535-553, 2011.
DOI : 10.1007/s00224-010-9278-3
URL : https://hal.archives-ouvertes.fr/inria-00359718

N. Attrapadung and B. Libert, Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation, Proc. of PKC, pp.384-402, 2010.

W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen, vol.68, issue.1, pp.625-635, 1993.
DOI : 10.1007/BF01445125

M. Bellare, A. Boldyreva, A. Desai, and D. Pointcheval, Key-Privacy in Public-Key Encryption, Proc. of Asiacrypt, pp.566-582, 2001.
DOI : 10.1007/3-540-45682-1_33

B. Boneh, R. Canetti, S. Halevi, and J. Katz, Chosen???Ciphertext Security from Identity???Based Encryption, SIAM Journal on Computing, vol.36, issue.5, pp.915-942, 2006.
DOI : 10.1137/S009753970544713X

D. Boneh and X. Boyen, Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles, Proc. of Eurocrypt, pp.223-238, 2004.
DOI : 10.1007/978-3-540-24676-3_14

D. Boneh, G. Di-crescenzo, R. Ostrovsky, and G. Persiano, Public Key Encryption with Keyword Search, Proc. of Eurocrypt, pp.506-522, 2004.
DOI : 10.1007/978-3-540-24676-3_30

D. Boneh and M. Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, vol.32, issue.3, pp.586-615, 2003.
DOI : 10.1137/S0097539701398521

D. Boneh, V. Nikolaenko, and G. Segev, Attribute-based encryption for arithmetic circuits, 2013.

D. Boneh, A. Sahai, and B. Waters, Functional Encryption: Definitions and Challenges, Proc. of TCC, pp.253-273, 2011.
DOI : 10.1007/978-3-642-19571-6_16

X. Boyen, Attribute-Based Functional Encryption on Lattices, Proc. of TCC, pp.122-142, 2013.
DOI : 10.1007/978-3-642-36594-2_8

Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehlé, Classical hardness of learning with errors, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.575-584, 2013.
DOI : 10.1145/2488608.2488680
URL : https://hal.archives-ouvertes.fr/hal-00922194

R. Canetti, S. Halevi, and J. Katz, A forward-secure public-key encryption scheme, Proc. of Eurocrypt 2003, pp.255-271, 2003.

R. Canetti, S. Halevi, and J. Katz, Chosen-Ciphertext Security from Identity-Based Encryption, Proc. of Eurocrypt, pp.207-222, 2004.
DOI : 10.1007/978-3-540-24676-3_13

D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert, Bonsai trees, or how to delegate a lattice basis, Proc. of Eurocrypt, pp.523-552, 2010.

B. Chor and R. L. Rivest, A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Transactions on Information Theory, vol.34, issue.5, pp.901-909, 1988.
DOI : 10.1109/18.21214

C. Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of IMA Cryptography and Coding, pp.360-363, 2001.
DOI : 10.1007/3-540-45325-3_32

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, 2004.
DOI : 10.1137/S0097539702403773

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol.22, issue.6, pp.644-654, 1976.
DOI : 10.1109/TIT.1976.1055638

D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing , STOC '91, 1991.
DOI : 10.1145/103418.103474

S. Garg, C. Gentry, S. Halevi, A. Sahai, and B. Waters, Attribute-Based Encryption for Circuits from Multilinear Maps, Proc. of Crypto 2013, pp.479-499, 2013.
DOI : 10.1007/978-3-642-40084-1_27

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

C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.197-206, 2008.
DOI : 10.1145/1374376.1374407

O. Goldreich, Foundations of Cryptography, volume I ? Basic Tools, 2001.

S. Gorbunov, V. Vaikuntanathan, and H. Wee, Attribute-based encryption for circuits, Proc. of STOC, pp.545-554, 2013.

V. Goyal, O. Pandey, A. Sahai, and B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, Proceedings of the 13th ACM conference on Computer and communications security , CCS '06, pp.89-98, 2006.
DOI : 10.1145/1180405.1180418

I. Haviv and O. Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , STOC '07, pp.513-531, 2012.
DOI : 10.1145/1250790.1250859
URL : https://hal.archives-ouvertes.fr/hal-01111558

J. Herranz, F. Laguillaumie, and C. , Relations between semantic security and anonymity in identity-based encryption, Information Processing Letters, vol.111, issue.10, pp.453-460, 2011.
DOI : 10.1016/j.ipl.2011.02.002
URL : https://hal.archives-ouvertes.fr/hal-01084549

J. Horwitz and B. Lynn, Toward Hierarchical Identity-Based Encryption, Proc. of Eurocrypt, pp.466-481, 2002.
DOI : 10.1007/3-540-46035-7_31

R. Impagliazzo, L. A. Levin, and M. Luby, Pseudo-random generation from one-way functions (extended abstract), Proc. of STOC, pp.12-24, 1989.

J. Katz and Y. Lindell, Introduction to Modern Cryptography, 2007.

J. Katz, S. Sahai, and B. Waters, Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, Journal of Cryptology, vol.55, issue.2, pp.191-224, 2013.
DOI : 10.1007/s00145-012-9119-4

P. N. Klein, Finding the closest lattice vector when it's unusually close, Proc. of SODA, pp.937-941, 2000.

A. K. Lenstra, H. W. Lenstra, J. , and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, vol.32, issue.4, pp.515-534, 1982.
DOI : 10.1007/BF01457454

A. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters, Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption, Proc. of Eurocrypt, pp.62-91, 2010.
DOI : 10.1007/978-3-642-13190-5_4

V. Lyubashevsky, Lattice Signatures without Trapdoors, Proc. of Eurocrypt 2012, pp.738-755, 2012.
DOI : 10.1007/978-3-642-29011-4_43
URL : https://hal.archives-ouvertes.fr/hal-00864308

V. Lyubashevsky and D. Micciancio, Generalized Compact Knapsacks Are Collision Resistant, Proc. of ICALP, pp.144-155, 2006.
DOI : 10.1007/11787006_13

V. Lyubashevsky and D. Micciancio, Asymptotically Efficient Lattice-Based Digital Signatures, Proc. of TCC, pp.37-54, 2008.
DOI : 10.1007/978-3-540-78524-8_3

V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings, Proc. of Eurocrypt, pp.1-23, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00921792

R. Mceliece, A public-key cryptosystem based on algebraic number theory, 1978.

R. Merkle and M. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, vol.24, issue.5, pp.525-530, 1978.
DOI : 10.1109/TIT.1978.1055927

D. Micciancio, On the hardness of the shortest vector problem, 1998.

D. Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, computational complexity, vol.16, issue.4, pp.365-411, 2007.
DOI : 10.1007/s00037-007-0234-9

D. Micciancio and S. Goldwasser, Complexity of lattice problems: a cryptographic perspective, 2002.
DOI : 10.1007/978-1-4615-0897-7

D. Micciancio and C. Peikert, Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Proc. of Eurocrypt 2012, pp.700-718, 2012.
DOI : 10.1007/978-3-642-29011-4_41

D. Micciancio and O. Regev, Worst???Case to Average???Case Reductions Based on Gaussian Measures, SIAM Journal on Computing, vol.37, issue.1, pp.267-302, 2007.
DOI : 10.1137/S0097539705447360

D. Micciancio and P. Voulgaris, A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations, SIAM Journal on Computing, vol.42, issue.3, pp.1364-1391, 2013.
DOI : 10.1137/100811970

P. Q. Nguyen and J. Stern, The two faces of lattices in cryptology, Proceedings of the 2001 Cryptography and Lattices Conference, pp.146-180, 2001.

A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, volume 42 of Proc. of Symposia in Applied Mathematics, pp.75-88, 1990.
DOI : 10.1090/psapm/042/1095552

T. Okamoto and T. K. , Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption, Proc. of Crypto 2010, pp.191-208, 2010.
DOI : 10.1007/978-3-642-14623-7_11

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.333-342, 2009.
DOI : 10.1145/1536414.1536461

C. Peikert and A. Rosen, Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices, Proc. of TCC, pp.145-166, 2006.
DOI : 10.1007/11681878_8

O. Regev, Lecture notes of lattices in computer science

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Proc. of STOC, pp.84-93, 2005.

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, vol.56, issue.6, 2009.

R. L. Rivest, A. Shamir, and L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, vol.21, issue.2, pp.120-126, 1978.
DOI : 10.1145/359340.359342

A. Sahai and B. Waters, Fuzzy Identity-Based Encryption, Proc. of Eurocrypt, pp.457-473, 2005.
DOI : 10.1007/11426639_27

C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, vol.53, issue.2-3, pp.201-224, 1987.
DOI : 10.1016/0304-3975(87)90064-8

A. Shamir, Identity-Based Cryptosystems and Signature Schemes, Proc. of CRYPTO, pp.47-53, 1984.
DOI : 10.1007/3-540-39568-7_5

D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa, Efficient Public Key Encryption Based on Ideal Lattices, Proc. of Asiacrypt, pp.617-635, 2009.
DOI : 10.1007/978-3-642-10366-7_36

S. Vaudenay, Cryptanalysis of the Chor???Rivest Cryptosystem, Journal of Cryptology, vol.14, issue.2, pp.87-100, 2001.
DOI : 10.1007/s001450010005

B. Waters, Functional Encryption for Regular Languages, Proc. of Crypto 2012, pp.218-235, 2012.
DOI : 10.1007/978-3-642-32009-5_14

A. Yao, Theory and application of trapdoor functions, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.80-91, 1982.
DOI : 10.1109/SFCS.1982.45