Avec l'arrivée des systèmes auto-organisés tels que les réseaux ad hoc ou l'informatique diffuse, les protocoles de sécurité doivent répondre à de nouveaux besoins. Dans ce travail nous étudions comment une relation de confiance peut être établie entre des entités qui ne se connaissent pas a priori. Nous proposons des protocoles de sécurité permettant à une entité de garder un historique de ses interactions: après chaque interaction, une preuve est délivrée par exemple sous la forme d'une recommandation ou d'une preuve d'interaction. Chaque preuve concernant une entité est stockée par celle-ci dans son historique. Les preuves peuvent être sélectivement démontrées, lorsqu'il est nécessaire de dévoiler une partie de son historique pour établir une relation de confiance. Prouver son historique à différentes entités révèle en général trop d'information et des mécanismes pour protéger la vie privée des utilisateurs sont nécessaires. Dans ce but, nous proposons un mécanisme de certificat non traçable qui empêche de faire le lien entre plusieurs preuves et qui protège l'anonymat des utilisateurs. Ce schéma est une extension des signatures de groupe où le signataire n'est plus un membre anonyme d'un groupe mais le détenteur d'un historique. Un autre besoin récurrent de l'informatique diffuse est la création d'un lien entre les entités virtuelles et le monde physique qui les entoure. Dans ce but, nous proposons les preuves de proximité qui combinent une mesure de distance et de la cryptographie dans le but de vérifier la proximité d'une entité connaissant un secret, par exemple une clé privée. Ce mécanisme peut être utilisé durant une interaction pour obtenir une preuve de cette interaction ou une preuve de localisation. Finalement, nous combinons ces deux mécanismes pour définir une architecture dédiée à l'établissement de confiance basé sur un historique. Ce schéma nous permet de confirmer la thèse qu'il est possible d'établir une relation de confiance en protégeant sa vie privée. Les résultats d'une première implémentation sont également discutés.

Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l’apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l’amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu’elles représentent un des piliers des protocols de confidentialité, n’ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité. Cette thèse s’attelle dans un premier temps à améliorer l’état de l’art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d’appartenance à un sous ensemble dont la taille est indépendante de l’ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent. Notre second propos est d’utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu’un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle. / Lattice based cryptography has developed greatly in the last two decades, both with new and stimulating results such as fully-homomorphic encryption, and with great progress in the efficiency of existing cryptographic primitives like encryption and signatures which are becoming competitive with their number theoretic counterparts. On the other hand, even though they are a crucial part of many privacy-based protocols, zero-knowledge proofs of knowledge are still lagging behind in expressiveness and efficiency. The first goal of this thesis is to improve the quality of lattice-based proofs of knowledge. We construct new zero-knowledge proofs of knowledge such as a subset membership proof with size independent of the subset. We also work towards making zero-knowledge proofs more practical, by introducing a new amortized proof of knowledge that subsumes all previous results. Our second objective will be to use the proofs of knowledge we designed to construct novel and efficient cryptographic primitives. We build a group signature whose size does not depend on the size of the group, as well as a practical and highly scalable lattice-based e-voting scheme.