We extend the well-known Tree-Diffie-Hellman technique used for the design of group key exchange (GKE) protocols with robustness, i.e. with resistance to faults resulting from possible system crashes, network failures, and misbehavior of the protocol participants. We propose a fully robust GKE protocol using the novel tree replication technique: our basic protocol version ensures security against outsider adversaries whereas its extension addresses optional insider security. Both protocols are proven secure assuming stronger adversaries gaining access to the internal states of participants. Our security model for robust GKE protocols can be seen as a step towards unification of some earlier security models in this area.

Shabal is based on a new provably secure mode of operation. Some related-key distinguishers for the underlying keyed permutation have been exhibited recently by Aumasson et al. and Knudsen et al., but with no visible impact on the security of Shabal. This paper then aims at extensively studying such distinguishers for the keyed permutation used in Shabal, and at clarifying the impact that they exert on the security of the full hash function. Most interestingly, a new security proof for Shabalâs mode of operation is provided where the keyed permutation is not assumed to be an ideal cipher anymore, but observes a distinguishing property i.e., an explicit relation verified by all its inputs and outputs. As a consequence of this extended proof, all known distinguishers for the keyed permutation are proven not to weaken the security of Shabal. In our study, we provide the foundation of a generalization of the indifferentiability framework to biased random primitives, this part being of independent interest.

Voting machines are used in France in political elections since 2004. Other examples, notably in the USA, have raised a lot of concerns and some criticisms against their use. The purpose of this paper is to propose new conception rules for voting machines, in order to improve their security to achieve the sincerity of the ballot, to obtain transparency of the voting and counting procedures, so as to raise the confidence of citizens. One way to reach this final goal, is to give to the citizens the ability to participate into control operations, which is easier to do in paper voting than in the case of voting machines.

This paper reports a thorough standard-model investigation on how attacks on hash functions impact the security of hash-and-sign signature schemes. We identify two important properties that appear to be crucial in analyzing the nature of security relations between signature schemes and their inner hash functions. We then investigate the security relations in the general case of hash-and-sign signatures and in the particular case of first-hash-then-sign signatures, showing a gap of security guarantees between the two paradigms. Next, we apply our investigation on three operating modes to construct a hash function family from a hash function based on the well-known Merkle-Damgård construction (such as MD5 and SHA-1). For completeness, we give concrete attack workloads for attacking operating modes used in practical implementations of signature schemes.

In a group key exchange protocol, the resulting group key should be computed by all participants such that none of them can gain any advantage concerning the protocol’s output: misbehaving participants might have personal advantage in influencing the final value of the key. In fact, the absence of trust relationship is the main feature of group key exchange (when compared to group key transport) protocols. This paper enlarges existing notions of security by identifying limitations in some previously proposed security models. To illustrate these notions, two efficient and provably secure generic solutions – compilers – are presented.

In group key exchange (GKE) protocols users usually extract the group key using some auxiliary (ephemeral) secret information generated during the execution. Strong corruptions are attacks by which an adversary can reveal these ephemeral secrets, in addition to the possibly used long-lived keys. Undoubtedly, security impact of strong corruptions is serious, and thus specifying appropriate security requirements and designing secure GKE protocols appears an interesting yet challenging task — the aim of our paper.

We start by investigating the current setting of strong corruptions and derive some refinements such as opening attacks that allow to reveal ephemeral secrets of users without their long-lived keys. This allows to consider even stronger attacks against honest, but “opened” users.

Further, we define strong security goals for GKE protocols in the presence of such powerful adversaries and propose a 3-round GKE protocol, named TDH1, which remains immune to their attacks under standard cryptographic assumptions. Our security definitions allow adversaries to register users and specify their long-lived keys, thus, in particular capture attacks of malicious insiders for the appropriate security goals such as mutual authentication, key confirmation, contributiveness, key control and key-replication resilience.

In 2001, Bellare, Namprempre, Pointcheval and Semanko introduced the notion of “one-more” computational problems. Since their introduction, these problems have found numerous applications in cryptography. For instance, Bellare et al. showed how they lead to a proof of security for Chaum’s RSA-based blind signature scheme in the random oracle model.

In this paper, we provide separation results for the computational hierarchy of a large class of algebraic “one-more” computational problems (e.g. the one-more discrete logarithm problem, the one-more RSA problem and the one-more static Computational Diffie-Hellman problem in a bilinear setting). We also give some cryptographic implications of these results and, in particular, we prove that it is very unlikely, that one will ever be able to prove the unforgeability of Chaum’s RSA-based blind signature scheme under the sole RSA assumption.

When users run a group key exchange (GKE) protocol, they usually extract the key from some auxiliary (ephemeral) secret information generated during the execution. Strong corruptions are attacks by which an adversary can reveal these ephemeral secrets, in addition to the possibly used long-lived keys. Undoubtedly, security impact of strong corruptions is serious, and thus specifying appropriate security requirements and designing secure GKE protocols appears an interesting yet challenging task — the aim of our paper.

We start by investigating the current setting of strong corruptions and derive some further refinements such as opening attacks that allow to reveal ephemeral secrets of users without their long-lived keys. This allows to consider even stronger attacks against honest, but “opened” users.

Further, we define strong security goals for GKE protocols in the presence of such powerful adversaries and propose a Tree Diffie-Hellman protocol immune to their attacks. Our security definitions in particular include the case of malicious insiders, for appropriate security goals such as mutual authentication, key confirmation, contributiveness and key-replication resilience. The proposed protocol proceeds in three rounds and is provably secure in the standard model.

Group key exchange (GKE) protocols can be used to guarantee confidentiality and authentication in group applications. The paradigm of provable security subsumes an abstract formalization (security model) that considers the protocol environment and identifies its security goals. The first security model for GKE protocols was proposed by Bresson, Chevassut, Pointcheval, and Quisquater in 2001, and has been subsequently applied in many security proofs. Their definitions of AKE-security (authenticated key exchange; a.k.a. indistinguishability of the key) and MA-security (mutual authentication) became meanwhile standard.

In this paper we analyze the BCPQ model and some of its variants and identify several risks resulting from its technical core construction – the notion of partnering. Consequently, we propose a revised model extending AKE- and MA-security in order to capture attacks by malicious participants and strong corruptions.

Then, we turn to generic solutions (known as compilers) for AKE- and MA-security in BCPQ-like models. We describe a compiler C-AMA which provides AKE- and MA-security for any GKE protocol, under standard cryptographic assumptions, that eliminates some identified limitations in existing compilers.

In this paper we identify the (P,Q)-DDH assumption, as an extreme, powerful generalization of the Decisional Diffie-Hellman (DDH) assumption: virtually all previously proposed generalizations of DDH are instances of the (P,Q)-DDH problem. We prove that our generalization is no harder than DDH through a concrete reduction that we show to be rather tight in most practical cases. One important consequence of our result is that it yields significantly simpler security proofs for protocols that use extensions of DDH. We exemplify in the case of several group-key exchange protocols (among others we give an elementary, direct proof for the Burmester-Desmedt protocol). Finally, we use our generalization of DDH to extend the celebrated computational soundness result of Abadi and Rogaway [AbaRog00] so that it can also handle exponentiation and Diffie-Hellman-like keys. The extension that we propose crucially relies on our generalization and seems hard to achieve through other means.

Authenticated key exchange protocols allow two participants A and B, communicating over a public network and each holding an authentication means, to exchange a shared secret value. Methods designed to deal with this cryptographic problem ensure A (resp. B) that no other participants aside from B (resp. A) can learn any information about the agreed value, and often also ensure A and B that their respective partner has actually computed this value. A natural extension to this cryptographic method is to consider a pool of participants exchanging a shared secret value and to provide a formal treatment for it. Starting from the famous 2-party Diffie-Hellman (DH) key exchange protocol, and from its authenticated variants, security experts have extended it to the multi-party setting for over a decade and completed a formal analysis in the framework of modern cryptography in the past few years. The present paper synthesizes this body of work on the provably-secure authenticated group DH key exchange.

Group key exchange protocols allow their participants to compute a secret key which can be used to ensure security and privacy for various multi-party applications. The resulting group key should be computed through cooperation of all protocol participants such that none of them is trusted to have any advantage concerning the protocol’s output. This trust relationship states the main difference between group key exchange and group key transport protocols. Obviously, misbehaving participants in group key exchange protocols may try to influence the resulting group key, thereby disrupting this trust relationship, and also causing further security threats. This paper analyzes the currently known security models for group key exchange protocols with respect to this kind of attacks by malicious participants and proposes an extended model to remove the identified limitations. Additionally, it proposes an efficient and provably secure generic solution, a compiler, to guarantee these additional security goals for group keys exchanged in the presence of malicious participants.

Group key exchange protocols allow their participants to compute a secret key which can be used to ensure security and privacy for various multi-party applications. The resulting group key should be computed through cooperation of all protocol participants such that none of them is trusted to have any advantage concerning the protocol’s output. This trust relationship states the main difference between group key exchange and group key transport protocols. Obviously, misbehaving participants in group key exchange protocols may try to influence the resulting group key, thereby disrupting this trust relationship, and also causing further security threats. This paper analyzes the currently known security models for group key exchange protocols with respect to this kind of attacks by malicious participants and proposes an extended model to remove the identified limitations. Additionally, it proposes an efficient and provably secure generic solution, a compiler, to guarantee these additional security goals for group keys exchanged in the presence of malicious participants.

In this talk, we identify the (P,Q)-DDH assumption, as an extreme, powerful generalization of the Decisional Diffie-Hellman (DDH) assumption: virtually all previously proposed generalizations of DDH are instances of the (P,Q)-DDH problem. We prove that our generalization is no harder than DDH through a concrete reduction that we show to be rather tight in most practical cases. One important consequence of our result is that it yields significantly simpler security proofs for protocols that use extensions of DDH. We exemplify in the case of several group-key exchange protocols (among other we give an elementary, direct proof for the Burmester-Desmedt protocol). Finally, we use our generalization of DDH to extend the celebrated computational soundness result of Abadi and Rogaway (2000) so that it can also handle exponentiation and Diffie-Hellman-like keys. The extension that we propose crucially relies on our generalization and seems hard to achieve it through other means.

After years of almost full confidence in the security of common hash functions such as MD5 and SHA-1, the cryptographic community is now facing the unprecedented threat of seeing practical security applications succumb to concrete attacks. A way to cope with this crisis is to fasten the development of new hash functions, but another crucial task is to assess the implications these attacks on hash functions may have on cryptographic systems. This paper reports a thorough investigation on how recent attacks on hash functions impact the security of signature schemes. We suggest the notion of probabilistic hash-and-sign signatures and further classify signature schemes into various related categories which allow us to identify completely the nature of security relations between signature schemes and their inner hash functions. We also determine how using iterated hash functions a la Merkle-Damgård impacts the security of deterministic (resp. probabilistic) hash-and-sign signatures. We confirm that the security gain inherent to using the probabilistic hash-and-sign paradigm may be lost completely if instantiated with a Merkle-Damgård hash function and unwise operating mode.

At PKC 2006 Crutchfield, Molnar, Turner and Wagner proposed a generic on-line/off-line threshold signature scheme, that extends to the threshold setting, the “hash-sign-switch” paradigm introduced by Shamir and Tauman. Such a paradigm strongly relies on chameleon hashing. A chameleon hash function is a keyed hash function which is collision-resistant except for those having knowledge of the private key. This allows the following approach. In the off-line phase, one just hashes and signs a random message s. When given a message m to sign, during the on-line phase, the signer uses its knowledge of the trapdoor to find a second preimage and “switch” m with the random s. Interestingly, Crutchfield et al. noticed that some subtleties arise when trying to adapt this approach to the threshold setting. In particular, they overcome such difficulties by introducing a new computational assumption which turns out to be implied by the so-called one-more discrete logarithm assumption.

In this paper we present an alternative solution to the problem. As in the previous result by Crutchfield et al., our construction is generic and can be based on any threshold signature scheme, combined with a chameleon hash function based on discrete log. However we show that, by appropriately modifying the chameleon function, our scheme can be proven secure based only on the traditional discrete logarithm assumption. While this produces a slight increase in the cost of the off-line phase, the efficiency of the on-line stage (the most important when optimizing signature computation) is unchanged. In other words the efficiency is essentially preserved. Finally, we show how to achieve robustness for our scheme. Compared to the work by Crutchfield et al., we can tolerate at most (arbitrarily) malicious players instead of however we stress that we do not rely on random oracles in our proofs.

At PKC 2006 Crutchfield et al. proposed a generic threshold version of on-line/off-line signature schemes. Their construction strongly relies on chameleon hash functions which are collision-resistant functions, with a secret trapdoor enabling to find arbitrary collisions efficiently. The scheme is as follows. In the off-line phase, the signer hashes and signs a random message s. During the on-line phase, when being given the actual message m, the signer uses the hash trapdoor to find a second preimage and “switches” m with s. As shown by the authors, adapting this paradigm to the threshold setting is not trivial. Their solution makes use of additional assumptions which turn out to be implied by the so-called one-more discrete logarithm assumption.

In this paper we present an alternative solution to the problem. We show that, by appropriately modifying the chameleon function, our scheme can be proven secure based only on the traditional discrete logarithm assumption while (essentially) preserving efficiency. Also, we show how to achieve robustness for our scheme. Compared to the work by Crutchfield et al., our main solution tolerates at most ⌈n∕4⌉ (arbitrarily) malicious players instead of ⌈n∕3⌉ however we stress that we do not rely on random oracles in our proofs. Moreover we present a variant which can achieve robustness in the presence of ⌈n∕3⌉ malicious players.

The Internet has evolved into a very hostile ecosystem where “phishing” attacks are common practice. This paper shows that the three-party group Diffie-Hellman key exchange can help protect against these attacks. We have developed password-based ciphersuites for the Transport Layer Security (TLS) protocol that are not only provably secure but also believed to be free from patent and licensing restrictions based on an analysis of relevant patents in the area.

In this work, we define the notion of private-output multiparty computation: this newly revised notion, which encompasses (as a particular case) the classical definition, allows players to jointly compute the output of a function such that no information about the outputs leaks to an adversary controlling some of the players (apart from what follows from the description of the function itself). We formally verify that no function can be output-privately computed if the adversary gets full access to corrupted players’ memory. However, if the adversary controls only part of the state of corrupted players, any function can be output-privately computed, assuming that enhanced trapdoor permutations exist. We prove security is preserved under sequential composition.

A group key exchange protocol enable a pool of participants, communicating over a public network, to securely establish a common session key, in such a way that nobody outside the pool get information about it. While key exhange is a central primitive in cryptography, the formalization of the underlying security notions, as well as those required in the case of group key exchange, has been achieved only quite recently.

In this talk, we describe the formal security model we have proposed in 2001 (joint work with O. Chevassut and D. Pointcheval) in order to analyze existing protocols, for which only heuristic security arguments had been given. We will discuss in details the extensions and refinements that can be made to this model: formalizing authentication between the players, dealing with concurrent executions, corruption and forward-secrecy, dynamicity of group membership, etc. We will also compare the model with other approaches that have been developped by Bellare, Canetti et al., and we will briefly discuss the possible variants of the model, in particular how to enhance it in order to deal with password-based scenarios.

With the development of grids, distributed applications are spread across multiple computing resources and require efficient security mechanisms among the processes. Although protocols for authenticated group Diffie-Hellman key exchange protocols seem to be the natural mechanisms for supporting these applications, current solutions are either limited by the use of public key infrastructures or by their scalability, requiring a number of rounds linear in the number of group members. To overcome these shortcomings, we propose in this paper the first provably-secure password-based constant-round group key exchange protocol. It is based on the protocol of Burmester and Desmedt and is provably-secure in the random-oracle and ideal-cipher models, under the Decisional Diffie-Hellman assumption. The new protocol is very efficient and fully scalable since it only requires four rounds of communication and a (small) constant number of exponentiations per user. Moreover, the new protocol avoids intricate authentication infrastructures by relying on passwords for authentication.

To support our analysis, we exhibit a dictionary attack on a recently password-based group key exchange protocol. Also, and of independent interest, we carry our security analysis in the simpler, while stronger, Real-or-Random security model and show that our proof is almost optimal in this model.

Dans cet exposé, on examinera les différents modèles de sécurité cryptographiques qui ont été proposés pour l’analyse de protocoles d’échange de clé authentifié par mot de passe. Dans un tel protocole, les participants cherchent à construire un secret commun (la clé) et disposent, pour s’authentifier mutuellement, d’une donnée de faible entropie, appelée mot de passe. La principale caractéristique d’un dictionnaire de mots de passe est d’être énumérable facilement; cette caractéristique empêche un traitement classique du problème car la probabilité de succès d’un adversaire est au moins égale à celle de deviner le mot de passe par choix aléatoire, et donc, ne peut être rendue arbitrairement faible (négligeable). Des adaptations des modèles de sécurité asymptotiques classiques se sont donc avérés nécessaires pour aborder ces protocoles sous l’angle de la sécurité prouvable. Par ailleurs, l’intérêt pratique évident du scénario d’authentification et d’échange de clé par mot de passe, mais aussi la multiplicité des variantes possibles: nombre de participants, exécutions multiples, adversaires passif ou actif, hypothèses calculatoires sous-jacentes, objets théoriques utilisés dans l’analyse, etc. ont donné lieu à une littérature abondante sur le sujet depuis le début des années 1990. On passera en revue les principales familles de protocoles qui s’en sont dégagées, en montrant comment les progrès dans la compréhension du mécanisme de mot de passe ont permis, petit à petit, de parvenir à un traitement plus unifié du problème.

In this paper, we show how to design an efficient and provably secure password-based authenticated key exchange scheme specifically for the TLS (Transport Layer Security) protocol. The goal is to provide a technique that allows users to employ (short) passwords to securely identify themselves to servers. As our main contribution, we describe a new password-based technique for user authentication in TLS, called Simple Open Key Exchange (SOKE). Loosely speaking, SOKE ciphersuites are unauthenticated Diffie-Hellman ciphersuites in which the client’s Diffie-Hellman ephemeral public value is encrypted using a simple mask generation function. The mask is simply a constant value raised to the power of (a hash of) the password.

The SOKE ciphersuites, in advantage over previous password-based authentication ciphersuites in TLS, combines the following three features. First, SOKE has formal security arguments; the proof of security based on the computational Diffie-Hellman assumption is in the random oracle model, and holds for concurrent executions and for arbitrarily large password dictionaries. Second, SOKE is computationally efficient; in particular, it only needs operations in a prime-order subgroup for its Diffie-Hellman computations, and there is no need for safe primes (with large subgroup orders). Third, SOKE provides good protocol flexibility because the user identity and password are only required once a SOKE ciphersuite has actually been negotiated, and after the server has sent a server identity.

In the appendix, we also consider a variant of our main scheme that can be more adequate for distributed computing (when the password is shared among several servers). This variant, however, is proven secure only in limited settings: either in the concurrent setting with password dictionaries of small size, or in the non-concurrent setting with password dictionaries of any size.

The IEEE 802 standards ease the deployment of networking infrastructures and enable employers to access corporate networks while traveling. These standards provide two modes of communication called infrastructure and ad-hoc modes. A security solution for the IEEE 802.11’s infrastructure mode took several years to reach maturity and firmware are still been upgraded, yet a solution for the ad-hoc mode needs to be specified. The present paper is a first attempt in this direction. It leverages the latest developments in the area of password-based authentication and (group) Diffie-Hellman key exchange to develop a provably-secure key-exchange protocol for IEEE 802.11’s ad-hoc mode. The protocol allows users to securely join and leave the wireless group at time, accommodates either a single-shared password or pairwise-shared passwords among the group members, or at least with a central server; achieves security against dictionary attacks in the ideal-hash model (i.e. random-oracles). This is, to the best of our knowledge, the first such protocol to appear in the cryptographic literature.

A group key agreement protocol allows a set of users, communicating over a public network, to agree on a private session key. Most of the schemes proposed so far require a linear number (with respect to the number of participants) of communication rounds to securely achieve this goal. In this work we propose a new methodology to design authenticated group key agreement schemes that require a constant number of communication rounds. We achieve this by generalizing the solution presented at PKC ’04 [BreCat04] to provide a general solution provably secure under the sole assumption that trapdoor permutations exist. As an application of the latter result we propose an efficient implementation based on the so-called RSA-Paillier encryption scheme [CatGenHowNgu01].

Wireless networking has the power to fit the Internet with wings, however, it will not take off until the security technological hurdles have been overcome. In this paper we propose a very efficient and provably secure group key agreement well suited for unbalanced networks consisting of devices with strict power consumption restrictions and wireless gateways with less stringent restrictions. Our method meets practicability, simplicity, and strong notions of security.

L’un des principaux outils utilisé en cryptographie est l’échange de clé, mécanisme qui consiste pour une ou plusieurs entité à se mettre d’accord sur une valeur secrète, dans le but de pouvoir utiliser d’autres outils cryptographiques (comme le chiffrement par exemple). La formalisation de ce type de protocole, pour en étudier la sécurité, a connu beaucoup d’intérêt ces dernières années.

Pour se protéger des intrus (personnes non autorisées à connaître la clé), l’authentification des participants est nécessaire. Cette authentification peut se faire grâce à d’autres clés déjà établies, ou par le biais d’un mot de passe. Nous étudierons dans cet exposé le deuxième scénario, en explicitant les définitions et le modèle de sécurité spécifiques à ce contexte, puis en décrivant les protocoles, à deux joueurs et à n joueurs, qui sont prouvés sûrs dans ce modèle.

Schemes for encrypted key exchange are designed to provide two entities communicating over a public network, and sharing a (short) password only, with a session key to be used to achieve data integrity and/or message confidentiality. An example of a very efficient and “elegant” scheme for encrypted key exchange considered for standardization by the IEEE P1363 Standard working group is AuthA. This scheme was conjectured secure when the symmetric-encryption primitive is instantiated via either a cipher that closely behaves like an “ideal cipher”, or a mask generation function that is the product of the message with a hash of the password. While the security of this scheme in the former case has been recently proven, the latter case was still an open problem. For the first time we prove in this paper that this scheme is secure under the assumptions that the hash function closely behaves like a random oracle and that the computational Diffie-Hellman problem is difficult. Furthermore, since Denial-of-Service (DoS) attacks have become a common threat we enhance AuthA with a mechanism to protect against them.

A group key agreement protocol allows a set of users, communicating over a public network, to agree on a private session key. Most of the schemes proposed so far require a linear number (with respect to the number of participants) of communication rounds to securely achieve this goal. In this paper we propose a new constant-round group key exchange protocol that provides efficiency and privacy under the Decisional Diffie-Hellman assumption. Our construction is practical, conceptually simple and it is obtained by taking advantage of the properties of the El-Gamal encryption scheme combined with standard secret sharing techniques.

At Eurocrypt ’02 Cramer and Shoup [CraSho02] proposed a general paradigm to construct practical public-key cryptosystems secure against adaptive chosen-ciphertext attacks as well as several concrete examples. Among the others they presented a variant of Paillier’s [Pai99] scheme achieving such a strong security requirement and for which two, independent, decryption mechanisms are allowed. In this paper we revisit such scheme and show that by considering a different subgroup, one can obtain a different scheme (whose security can be proved with respect to a different mathematical assumption) that allows for interesting applications. In particular we show how to construct a perfectly hiding commitment schemes that allows for an on-line / off-line efficiency tradeoff. The scheme is computationally binding under the assumption that factoring is hard, thus improving on the previous construction by Catalano et al. [CatGenHowNgu01] whose binding property was based on the assumption that inverting RSA[N,N] (i.e. RSA with the public exponent set to N) is hard.

Password-based key exchange schemes are designed to provide entities communicating over a public network, and sharing a (short) password only, with a session key (e.g, the key is used for data integrity and/or confidentiality). The focus of the present paper is on the analysis of very efficient schemes that have been proposed to the IEEE P1363 Standard working group on password-based authenticated key-exchange methods, but for which actual security was an open problem. We analyze the AuthA key exchange scheme and give a complete proof of its security. Our analysis shows that the AuthA protocol and its multiple modes of operation are provably secure under the computational Diffie-Hellman intractability assumption, in both the random-oracle and the ideal-cipher models.

Wireless networking has the power to fit the Internet with wings, however, it will not take off until the security technological hurdles have been overcome. In this paper we propose a very efficient and provably-secure group key agreement well suited for unbalanced networks consisting of devices with strict power consumption restrictions and wireless gateways with less stringent restrictions. Our method meets practicability, simplicity, and strong notions of security.

Group Diffie-Hellman schemes for password-based key exchange are designed to provide a pool of players communicating over a public network, and sharing just a human-memorable password, with a session key (e.g, the key is used for multicast data integrity and confidentiality). The fundamental security goal to achieve in this scenario is security against dictionary attacks. While solutions have been proposed to solve this problem no formal treatment has ever been suggested. In this paper, we define a security model and then present a protocol with its security proof in both the random oracle model and the ideal-cipher model.

La cryptologie consiste en l’étude des moyens de protection des informations, ainsi qu’en l’analyse de leur sécurité en fournissant des garanties d’intégrité, d’authenticité et de confidentialité. Les nombreux protocoles impliquant plusieurs utilisateurs sont en passe de devenir un enjeu critique pour la cryptographie, étant donné le développement considérable des réseaux de communication grand public tels que l’Internet. De fait, la cryptologie doit proposer des protocoles algorithmiquement efficaces et tenant compte de la diversité des scénarios de groupe possibles. Ces protocoles doivent permettre de protéger les communications mais aussi la vie privée des individus (via les mécanismes d’anonymat), et ce, face à des menaces spécifiques comme la corruption ou la coalition des autres utilisateurs du réseau.

Dans cette thèse, nous abordons dans un premier temps le concept de signature anonyme qui combine élégamment les notions d’authenticité et d’anonymat ; une telle signature permet à un individu de signer des documents de façon anonyme vis-à-vis d’un groupe de personnes. Dans le cas des signatures de groupe, où le groupe de personnes est géré par une autorité, nous développons un mécanisme de preuve autorisant la révocation d’identité, c’est-à-dire la possibilité pour le signataire de prouver sa bonne foi lorsque d’autres joueurs malhonnêtes ont été exclus. Dans le cas des signatures de cercle, où le groupe de personnes est choisi ad-hoc, nous proposons un mécanisme efficace permettant à plusieurs utilisateurs de signer conjointement un document, c’est-à-dire de prouver qu’ils sont plusieurs à signer.

Dans un deuxième temps, nous étudions les protocoles cryptographiques généralisant l’échange de clés Diffie-Hellman à plusieurs utilisateurs. Nous montrons comment, sur un réseau peu sûr, plusieurs utilisateurs peuvent se mettre d’accord sur une clé de session commune, et comment ils peuvent la faire évoluer lorsque le groupe change (ajout ou suppression de membres). Nous étudions notamment pour ces protocoles les problèmes de sécurité de la clé, de corruption et de "forward-secrecy".

Mots-clé: Cryptologie, Crypographie clé publique, Protocoles de groupe, Signatures anonymes, Révocation, Signatures à seuil, Authentification, Échange de clé, Diffie-Hellman de groupe.

Cryptology consists in studying the ways of protecting information, as well as analyzing their security, by providing integrity, authentication and confidentiality services. The numerous multi-user protocols are to become a critical stake for cryptography, due to the considerable development of large public communication networks such as the Internet. Cryptography has to propose algorithmically efficient protocols, taking into account the variety of potential group scenarios. These protocols must allow to protect communications and users’ private life (through anonymity mechanisms), and this, even facing specific threats such as corruption or coalition attacks from other network users.

In this thesis, we first deal with the concept of anonymous signature, that nicely combines anonymity and authenticity notions ; such a signature allows a individual to sign documents in an anonymous way, on behalf of a group of users. In the group signature setting, wherein that group is managed by an authority, we develop a proof mechanism enabling identity revocation, that is, ability for an honest member to be trusted while dishonest members have been excluded. In the ring signature setting, wherein the group is chosen ad-hoc, we propose an efficient mechanism allowing several users to jointly sign a document, that is, to prove they are actually several signers.

Second, we study cryptographic protocols that generalize Diffie-Hellman key agreement to many users. We show how, through an insecure network, many parties can agree on a common session key, and how they can have it evolved when the group membership changes (join or removal of members). For these protocols, we study session key security, corruption and forward-secrecy issues.

Keywords: Cryptology, Public-key cryptography, Group protocols, Anonymous signatures, Revocation, Threshold signatures, Authentication, Key Exchange, Group Diffie-Hellman.

This paper addresses the problem of defining and providing proofs of knowledge for a general class of exponentiation-based formulae. We consider general predicates built from modular exponentiations of secret values, combined by products and connected with the logical operators “AND”,  “OR”,  “NOT”. We first show how to deal with non-linear combination of secret exponents. Next,we extend the work by Brands [Bra97] to a strictly larger class of predicates, allowing a more liberal use of the logical operator “NOT”. We sketch two applications by which we enhance group signatures schemes with revocation of identity and multi-signer features. Such features can be useful to protect privacy or for collabrative use of group signatures, respectively.

In this paper we study generalizations of the Diffie-Hellman problems recently used to construct cryptographic schemes for practical purposes. The Group Computational and the Group Decisional Diffie-Hellman assumptions not only enable one to construct efficient pseudo-random functions but also to naturally extend the Diffie-Hellman protocol to allow more than two parties to agree on a secret key. In this paper we provide results that add to our confidence in the GCDH problem. We reach this aim by showing exact relations among the GCDH, GDDH, CDH and DDH problems.

In this paper, we investigate the recent paradigm for group signatures proposed by Rivest et al.. at Asiacrypt ’01. We first improve on their ring signature paradigm by showing that it holds under a strictly weaker assumption, namely the random oracle model rather than the ideal cipher. Then we provide extensions to make ring signatures suitable in practical situations, such as threshold schemes or ad-hoc groups. Finally we propose an efficient scheme for threshold scenarios based on a combinatorial method and provably secure in the random oracle model.

We recently presented several papers introducing various models and techniques for group key agreement protocols analysis. Such protocols are designed to be executed by a pool of players, possibly dishonest, and the security analysis often raises technical difficulties. Typical example is the group Diffie-Hellman key exchange. The aim of this talk would be to synthesize our results, and discuss the benefits and shortcomings of the applied methods.

Authenticated Diffie-Hellman key exchange allows two principals communicating over a public network, and each holding public/private keys, to agree on a shared secret value. In this paper we study the natural extension of this cryptographic problem to a group of principals. We begin from existing formal security models and refine them to incorporate major missing details (e.g., strong-corruption and concurrent sessions). Within this model we define the execution of a protocol for authenticated dynamic group Diffie-Hellman and show that it is provably secure under the decisional Diffie-Hellman assumption. Our security result holds in the standard model and thus provides better security guarantees than previously published results in the random oracle model.

Les mécanismes cryptographiques impliquant plusieurs acteurs ont reçu beaucoup d’attention ces dernières années. L’un des plus anciens concerne les signatures de groupe, qui combinent astucieusement des propriétés d’authentification et d’anonymat. Dans cet exposé, nous passerons en revue les schémas les plus classiques, notamment celui d’Ateniese et al.. [AteCamJoyTsu00], et etudierons le délicat problème de la révocation d’identité, qui consiste à exclure un membre d’un groupe, sans compromettre l’anonymat de ses signatures antérieures.

Dynamic group Diffie-Hellman protocols for Authenticated Key Exchange (AKE) are designed to work in a scenario in which the group membership is not known in advance but where parties may join and may also leave the multicast group at any given time. While several schemes have been proposed to deal with this scenario no formal treatment for this cryptographic problem has ever been suggested. In this paper, we define a security model for this problem and use it to precisely define Authenticated Key Exchange (AKE) with “implicit” authentication as the fundamental goal, and the entity-authentication goal as well. We then define in this model the execution of a protocol modified from a dynamic group Diffie-Hellman scheme offered in the literature and prove its security.

Group Diffie-Hellman protocols for Authenticated Key Exchange (AKE) are designed to provide a pool of players with a shared secret key which may later be used, for example, to achieve multicast message integrity. Over the years, several schemes have been offered. However, no formal treatment for this cryptographic problem has ever been suggested. In this paper, we present a security model for this problem and use it to precisely define AKE (with “implicit” authentication) as the fundamental goal, and the entity-authentication goal as well. We then define in this model the execution of an authenticated group Diffie-Hellman scheme and prove its security.

We consider the problem of revocation of identity in group signatures. Group signatures are a very useful primitive in cryptography, allowing a member of a group to sign messages anonymously on behalf of the group. Such signatures must be anonymous and unlinkable, but a group authority must be able to open them in case of dispute. Many constructions have been proposed, some of them are quite efficient. However, a recurrent problem remains concerning revocation of group members. When misusing anonymity, a cheating member must be revoked by the authority, making him unable to sign in the future, but without sacrifying the security of past group signatures. No satisfactory solution has been given to completely solve this problem. In this paper, we provide the first solution to achieve such action for the Camenish-Stadler [CamSta97] scheme. Our solution is efficient provided the number of revoked members remains small.