Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de sécurité et de cryptographie LASEC)

Short undeniable signatures : design, analysis, and applications

Monnerat, Jean ; Vaudenay, Serge (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3691.

Ajouter à la liste personnelle
    Summary
    Digital signatures are one of the main achievements of public-key cryptography and constitute a fundamental tool to ensure data authentication. Although their universal verifiability has the advantage to facilitate their verification by the recipient, this property may have undesirable consequences when dealing with sensitive and private information. Motivated by such considerations, undeniable signatures, whose verification requires the cooperation of the signer in an interactive way, were invented. This thesis is mainly devoted to the design and analysis of short undeniable signatures. Exploiting their online property, we can achieve signatures with a fully scalable size depending on the security requirements. To this end, we develop a general framework based on the interpolation of group elements by a group homomorphism, leading to the design of a generic undeniable signature scheme. On the one hand, this paradigm allows to consider some previous undeniable signature schemes in a unified setting. On the other hand, by selecting group homomorphisms with a small group range, we obtain very short signatures. After providing theoretical results related to the interpolation of group homomorphisms, we develop some interactive proofs in which the prover convinces a verifier of the interpolation (resp. non-interpolation) of some given points by a group homomorphism which he keeps secret. Based on these protocols, we devise our new undeniable signature scheme and prove its security in a formal way. We theoretically analyze the special class of group characters on Z*n. After studying algorithmic aspects of the homomorphism evaluation, we compare the efficiency of different homomorphisms and show that the Legendre symbol leads to the fastest signature generation. We investigate potential applications based on the specific properties of our signature scheme. Finally, in a topic closely related to undeniable signatures, we revisit the designated confirmer signature of Chaum and formally prove the security of a generalized version.
    Résumé
    Les signatures numériques sont l'un des principaux accomplissements de la cryptographie à clef publique et constituent un outil indispensable pour assurer l'authenticité des données. Bien que leur vérifiabilité universelle facilite leur vérification par un destinataire, cette propriété peut avoir des conséquences indésirables dans un contexte lié à des informations sensibles ou privées. Motivées par ces considérations, les signatures incontestables, dont la vérification requiert la coopération du signataire de manière interactive, ont vu le jour. Cette thèse se consacre principalement au développement et à l'analyse de signatures incontestables courtes. Grâce à leur propriété interactive, nous parvenons à développer des signatures dont la taille peut être ajustée librement par rapport à la sécurité requise. A cet effet, nous proposons un cadre général, basé sur l'interpolation d'éléments d'un groupe par un homomorphisme, nous permettant de concevoir un schéma de signature incontestable générique. D'une part, ce cadre théorique nous permet de considérer des précédents schémas de signature incontestable de manière unifiée. D'autre part, en choisissant un homomorphisme de groupe adéquat, des signatures courtes sont obtenues de manière naturelle. Après la présentation de résultats théoriques liés à l'interpolation d'homomorphismes de groupe, nous développons des preuves interactives dans lesquelles le prouveur convainc un vérifieur de l'interpolation (ou, respectivement, de la non interpolation) de points donnés, par un homomorphisme secrètement connu de lui-même. A partir de ces protocoles, nous développons un schéma de signature incontestable et prouvons sa sécurité de manière formelle. Nous menons une analyse théorique concernant la classe particulière d'homomorphismes que sont les caractères de groupe sur Z*n. Après une étude des aspects algorithmiques de l'évaluation d'un homomorphisme de groupe, nous comparons l'efficacité de différents homomorphismes et montrons que le symbole de Legendre conduit à la génération de signature la plus efficace. Nous étudions des applications potentielles utilisant les propriétés spécifiques de notre schéma de signature. Finalement, dans un domaine intimement lié aux signatures incontestables, nous décrivons une généralisation du schéma de signature à confirmeur désigné de Chaum et en prouvons la sécurité de manière rigoureuse.