Applications of Structure-Preserving Cryptography and Pairing-Based NIZK Proofs

This habilitation thesis deals with cryptographic primitives that preserve the algebraic structure of underlying objects (messages, keys, etc) and their applications to the design of non-interactive zero-knowledge proofs and privacy-enhancing cryptographic primitives.In 2008, Groth and Sahai showed how to make these proof systems relatively efficient in abelian groups endowed with a bilinear map. These techniques, however, require to work with lower-level primitives where handled objects all live in a cyclic abelian group. Among other things, we need to sign messages without destroying their algebraic structure (in particular, without hashing them first) so as to be able to efficiently prove properties about hidden signed messages. The first part of this thesis describes a structure-preserving signature scheme which was the first efficient realization under previously studied algorithmic assumptions. These tools are also utilized in the design of a novel revocation mechanism for group signatures, which allow users to anonymously sign messages on behalf of a population they belong to. The second part of this thesis considers structure-preserving signatures endowed with homomorphic properties. We show how to use them in the design of non-malleable cryptographic primitives. Using linearly homomorphic structurepreserving signatures, we notably obtain non-malleable commitments to group elements and non-interactive zero-knowledge proofs, as well as public-key encryption schemes that resist chosen-ciphertext attacks.Ce mémoire s’intéresse aux primitives cryptographiques qui préservent la structure algébrique, ainsi qu’à leur utilisation dans la conception de preuves non-interactives sans divulgation de connaissance (de l’anglais “zero-knowledge”) et de primitives protégeant la vie privée. En 2008, Groth et Sahai ont montré comment rendre ces systèmes de preuve efficaces dans des groupes abéliens munis de formes bilinéaires. Toutefois, l’utilisation de ces techniques nécessite de manipuler des objets qui vivent dans des groupes abéliens cycliques. On a donc besoin de signer des messages sans affecter leur structure algébrique (en particulier, sans les hacher) de façon à pouvoir prouver efficacement des propriétés à propos de messages signés secrets. La première partie du mémoire décrit un schéma de signature préservant la structure qui a été la première réalisation efficace de la primitive sous des hypothèses algorithmiques ayant fait l’objet d’études préalables. Les mêmes outils sont ensuite utilisés dans la conception d’un nouveau mécanisme de révocation pour les signatures de groupe, qui permettent à des membres d’une population de signer des messages au nom de celle-ci tout en cachant leur identité. La seconde partie étudie les applications des signatures préservant la structure dotées de propriétés homomorphes. Nous montrons comment les utiliser dans la construction de cryptosystèmes non-malléables. Au moyen de signatures homomorphes qui gardent la structure, nous construisons ainsi des systèmes de mise sous scellé et des preuves “zero-knowledge” non-malléables, ainsi que des systèmes de chiffrement résistant aux attaques à chiffrés choisis