Lossy trapdoor primitives, zero-knowledge proofs and applications

In this thesis, we study two different primitives: lossy trapdoor functions and zero-knwoledge proof systems. The lossy trapdoor functions (LTFs) are function families in which injective functions and lossy ones are computationally indistinguishable. Since their introduction, they have been found useful in constructing various cryptographic primitives. We give in this thesis efficient constructions of a variant of LTF : Lossy Algebraic Filter. Using this variant, we can improve the efficiency of the KDM-CCA (Key-Depended-Message Chosen-Ciphertext-Attack) encryption schemes and fuzzy extractors. In the second part of this thesis, we investigate on constructions of zero-knowledge proof systems. We give the first logarithmic-size ring-signature with tight security using a variant of Groth-Kolhweiz Σ-protocol in the random oracle model. We also propose one new construction of lattice-based Designated-Verifier Non-Interactive Zero-Knowledge arguments (DVNIZK). Using this new construction, we build a lattice-based voting scheme in the standard model.; Dans cette thèse, nous étudions deux primitives différentes : les lossy trapdoor functions (LTF) et les systèmes de preuve à divulgation nulle de connaissance. Les LTFs sont des familles de fonctions dans lesquelles les fonctions injectives et les fonctions lossy sont calculatoirement indistinguables. Depuis leur introduction, elles se sont avérées utiles pour la construction de diverses primitives cryptographiques. Nous donnons dans cette thèse des constructions efficaces d’une variante de la LTF : le filtre algébrique lossy. Avec cette variante, nous pouvons améliorer l’efficacité du schéma de chiffrement KDM-CCA et extracteur flous. Dans la deuxième partie de cette thèse, nous étudions les constructions de systèmes de preuve à divulgation nullle de connaissance. Nous donnons la première signature d’anneau de taille logarithmique avec la sécurité étroite en utilisant une variante de Groth-Kolhweiz Σ-protocole dans le modèle de l’oracle aléatoire. Nous proposons également une nouvelle construction d’arguments à divulgation nulle de connaissance non-intéractive et à vérifieur désigné (DVNIZK) sous l’hypothèse de réseaux Euclidiens. En utilisant cette nouvelle construction, nous construisons un système de vote basé sur les réseaux Euclidiens dans le modèle standard.