Materials and Timeline of previous talks

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden's revelation of mass-surveillance, PCS was pioneered by the Signal messaging protocol, and is present in OTR. In this paper, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols.

Panorama of Age Verification

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden's revelation of mass-surveillance, PCS was pioneered by the Signal messaging protocol, and is present in OTR. In this paper, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols.

Panorama of Age Verification

Panorama of Age Verification

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden's revelation of mass-surveillance, PCS was pioneered by the Signal messaging protocol, and is present in OTR. In this paper, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols.

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden's revelation of mass-surveillance, PCS was pioneered by the Signal messaging protocol, and is present in OTR. In this paper, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols.

Presentation of the motivation behind Post Quantum Cryptography, and current state of the art

Smooth Hash Proof Systems have been introduced by Cramer and Shoup to build compact efficient CCA2 encryption in the standard model. Since then, they found applications in a broad range of protocols from oblivious transfer to authenticated key exchange, passing by witness examples. In this talk, we will start by a panorama of languages that can be managed by such a primitive and then show how this is enough to instantiate efficiently various primitives. We will provide examples of such constructions first with vanilla cryptography (elliptic curve, paillier) but also show that post-quantum constructions can be achieved with a non-prohibitive efficiency in both lattice and code based cryptography, widening the range of primitive available under those hypotheses.

Smooth Hash Proof Systems have been introduced by Cramer and Shoup to build compact efficient CCA2 encryption in the standard model. Since then, they found applications in a broad range of protocols from oblivious transfer to authenticated key exchange, passing by witness examples. In this talk, we will start by a panorama of languages that can be managed by such a primitive and then show how this is enough to instantiate efficiently various primitives. We will provide examples of such constructions first with vanilla cryptography (elliptic curve, paillier) but also show that post-quantum constructions can be achieved with a non-prohibitive efficiency in both lattice and code based cryptography, widening the range of primitive available under those hypotheses.

Présentation sur le Contact Tracing pour montrer des recherches actives à Limoges

Smooth Hash Proof Systems have been introduced by Cramer and Shoup to build compact efficient CCA2 encryption in the standard model. Since then, they found applications in a broad range of protocols from oblivious transfer to authenticated key exchange, passing by witness examples. In this talk, we will start by a panorama of languages that can be managed by such a primitive and then show how this is enough to instantiate efficiently various primitives. We will provide examples of such constructions first with vanilla cryptography (elliptic curve, paillier) but also show that post-quantum constructions can be achieved with a non-prohibitive efficiency in both lattice and code based cryptography, widening the range of primitive available under those hypotheses.

Showing the limit of a rushed approach to contact tracing

COVID19 has put a new practice in the spotlight: contact tracing. The goal of contact tracing is to slow down the spreading of a pandemic by rapidly identifying people who have been in close contact with infectious people, so to direct them towards precautionary measures: testing, self-quarantining, etc. Contact tracing has been performed by qualified humans in past pandemic events, such as the recent Ebola epidemics, but COVID19 has seen the emergence of a new technique: digital contact tracing. Leveraging the ubiquity of smartphones equipped with GPS or proximity sensors, digital contact tracing seeks to complement, simplify and amplify traditional contact tracing. Digital contact tracing has received its fair share of criticism from security and privacy experts, though: pushing a whole population to willfully carry around a personal tracking technology, in exchange for unverified public health benefits, is not to be taken lightly. This panel will bring together experts from different fields, from epidemiology to security and privacy, to discuss the pro and the cons of digital contact tracing, draw a summary of its (un)success so far, and elaborate on the future of the technology,

Smooth hash proof systems have been introduced by Cramer and shoup to build compact efficient cca2 encryption in the standard model. Since then, they found applications in a broad range of protocols from oblivious transfer to authenticated key exchange, passing by witness examples. In this talk, we will start by a panorama of languages that can be managed by such a primitive and then show how this is enough to instantiate efficiently various primitives. We will provide examples of such constructions first with vanilla cryptography (elliptic curve, paillier) but also show that post-quantum constructions can be achieved with a non-prohibitive efficiency in both lattice and code based cryptography, widening the range of primitive available under those hypotheses.

In Identity-based cryptography, in order to generalize one receiver encryption to multi-receiver encryption, wildcards were introduced: WIBE enables wildcard in receivers' pattern and Wicked-IBE allows one to generate a key for identities with wildcard. However, the use of wildcard makes the construction of WIBE, Wicked-IBE more complicated and significantly less efficient than the underlying IBE. The main reason is that the conventional identity's binary alphabet is extended to a ternary alphabet {0,1,∗} and the wildcard ∗ is always treated in a convoluted way in encryption or in key generation. In this paper, we show that when dealing with multi-receiver setting, wildcard is not necessary. We introduce a new downgradable property for IBE scheme and show that any IBE with this property, called DIBE, can be efficiently transformed into WIBE or Wicked-IBE. While WIBE and Wicked-IBE have been used to construct Broadcast encryption, we go a step further by employing DIBE to construct Attribute-based Encryption of which the access policy is expressed as a boolean formula in the disjunctive normal form.

La cryptographie a pendant longtemps été utilisée pour masquer des informations. En 1988, les preuves « Zero-Knowledge » ont permis d'ouvrir la porte à un champ nouveau d'applications, en proposant de prouver la véracité d'une affirmation sans pour autant en révéler les secrets. Cependant, les exemples récents d'exploitation de metadonnées ont montré que même savoir que quelqu'un peut prouver une affirmation peut être dangereux. Pour contrer ce phénomène la cryptographie implicite a fait son apparition. Elle permet d’obtenir une information sans qu'un serveur soit ni en mesure de savoir laquelle, ni de savoir si on y a réellement eu accès.

With the emergence of the Internet of things and of elec- tronic home health-care, more and more sensitive signals are transiting over easily accessible wireless networks. It has become an important task to manage to spread alerts on a wireless network at the same time as to hide the nature of these signals, in a secure and efficient way. No one (an adversarial observer or even the node transmitting the signal) should be able to learn whether a signal corresponds to an alert or a normal echo. Blind Coupon Mechanism is a primitive proposed at Asiacrypt 2005 that allows to spread such alerts quietly and quickly. In this paper, we pro- pose to strenghten their security model and we give a concrete solution which is both more secure and more efficient than the protocol originally proposed.

Since the seminal work of Diffie and Hellman [19], Non-Interactive Key Exchange (NIKE) has become one of the fundamental problems of modern cryptography, but additional security requirements have led to elaborated ad-hoc constructions, which often lack simplicity in their design. In particular, Identity-Based NIKE is still a major problem with few available constructions, and those ad-hoc con- structions do not give a lot of insight on what is required to be able to achieve such a NIKE scheme only based on the identity (and not relying on the public-key setting). In this work, we focus on the public-key setting and show how to generically build a NIKE scheme using a specific kind of Identity- Based Encryption, while also opening research on a new kind of Identity-Based Key Encapsulation Mechanisms (IBKEM), which we call identity-independent 2-tier IBKEM. As an interesting result, this construction also leads to the first known NIKE construction based on lattices. While most of the instantiations given in this paper lie in the random oracle model, this is not an inherent problem of our generic construction but rather a consequence of the lack of an existing identity-independent 2-tier IBKEM scheme in the standard model. Our proposal thus allows to reduce the problem to the construction of several building blocks, which can be studied independently in order to lead to an instantiation of NIKE in the standard model

La cryptographie a pendant longtemps été utilisée pour masquer des informations. En 1988, les preuves « Zero-Knowledge » ont permis d'ouvrir la porte à un champ nouveau d'applications, en proposant de prouver la véracité d'une affirmation sans pour autant en révéler les secrets. Cependant, les exemples récents d'exploitation de metadonnées ont montré que même savoir que quelqu'un peut prouver une affirmation peut être dangereux. Pour contrer ce phénomène la cryptographie implicite a fait son apparition. Elle permet d’obtenir une information sans qu'un serveur soit ni en mesure de savoir laquelle, ni de savoir si on y a réellement eu accès.

Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt’02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed, by Katz and Vaikuntanathan at Asiacrypt’09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring q many trapdoor inversion attempts, where q is the modulus of the underlying Learning With Error (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt’12).

Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt’02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed, by Katz and Vaikuntanathan at Asiacrypt’09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring q many trapdoor inversion attempts, where q is the modulus of the underlying Learning With Error (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt’12).

La cryptographie devient de plus en plus importante dans notre vie quotidienne, et même si certains politiques aimeraient la criminaliser, nous l’utilisons maintenant plusieurs fois par jour. En théorie, nous pourrions même l’utiliser encore plus et avoir ainsi encore plus de vie privée pour chacun, en pratique très peu de librairie inclue ne serait-ce que la moins exotique des créature de crypto-land. Les chercheurs vivent dans un monde rêvé où de plus en plus de choses sont possibles même si elles manquent parfois d’efficacité ou même d’une implémentation concrète. Vivant de l’autre côté du miroir, la communauté de la sécurité à tendance à réinventer la roue, et utilise de vieilles méthodes pour fournir des fonctionnalités approximatives alors que des solutions sont biens connues par les académiques. Dans cette conférence, nous présenterons une cartographie des principales *solutions* cryptographiques, nous montrerons ce qui existe déjà dans le monde réel des librairies libres et nous ferons la pub pour les créatures cryptographiques les plus fantastiquement utiles qui n’attendent que vous pour rejoindre le monde réel. Non seulement ces implémentations permettraient de mieux protéger la vie privée dans nos logiciels libres mais elles permettraient de faire des retours aux cryptographes et donc améliorerait les échanges entre ces communautés pas si éloignées.

Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt’02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed, by Katz and Vaikuntanathan at Asiacrypt’09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring q many trapdoor inversion attempts, where q is the modulus of the underlying Learning With Error (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt’12).

Smooth projective hashing has proven to be an extremely useful primitive, in particular when used in conjunction with commitments to provide implicit decommitment. This has lead to applications proven secure in the UC framework, even in presence of an adversary which can do adaptive corruptions, like for example Password Authenticated Key Exchange (PAKE), and 1-out-of-m Oblivious Transfer (OT). However such solutions still lack in efficiency. n this work, we introduce and instantiate the concept of Structure-Preserving Smooth Projective Hash Function, and give as applications more efficient instantiations for one-round PAKE and three-round OT, and information retrieval thanks to Anonymous Credentials, all UC-secure against adaptive adversaries.

La monnaie sert de mesure dans les échanges commerciaux. Usuellement, la monnaie est considérée fiable soit parce qu’elle provient d’une autorité de confiance, soit parce qu’elle est composée de biens tangibles. Cependant le XXIème siècle a vu l’émergence de monnaies purement digitales. Comment cette confiance peut-elle se maintenir dans un tel contexte ?

La notion d'Oblivious Transfer a été introduite en 1981 par Rabin, dans le but d'autoriser un receveur à recevoir une (et seulement une) ligne dans une base de k messages, sans que l'émetteur ne sache lequel. Diverses techniques ont été proposées pour réaliser cette fonctionnalité, nous montrerons dans cet exposé de récents développements sur comment instancier génériquement une telle primitive dans le modèle UC avec des corruptions adaptatives. Puis, nous montrerons comment instancier pour la première fois un Oblivious Transfer adaptatif (c'est à dire avec un coup sous linéaire en cas de requêtes supplémentaires de la part de l'utilisateur) et montrerons que dans ce cas, asymptotiquement la complexité est identique à celle des PIR utilisés en pratique.

La notion d'Oblivious Transfer a été introduite en 1981 par Rabin, dans le but d'autoriser un receveur à recevoir une (et seulement une) ligne dans une base de k messages, sans que l'émetteur ne sache lequel. Divers modèles ont été proposés pour réaliser cette fonctionnalité, nous montrerons dans cet exposé de récents développements sur comment instancier génériquement une telle primitive dans le modèle UC avec des corruptions adaptatives. Puis, nous montrerons comment instancier pour la première fois un Oblivious Transfer adaptatif (c'est à dire avec un coup sous linéaire en cas de requêtes supplémentaires de la part de l'utilisateur) et montrerons que dans ce cas, asymptotique

We show how to construct a completely generic UC-secure oblivious transfer scheme from a collision-resistant chameleon hash scheme (CH) and a CCA encryption scheme accepting a smooth projective hash function (SPHF). Our work is based on the work of Abdalla et al. at Asiacrypt 2013, where the authors formalize the notion of SPHF-friendly commitments, i.e. accepting an SPHF on the language of valid commitments (to allow implicit decommitment), and show how to construct from them a UC-secure oblivious transfer in a generic way. But Abdalla et al. only gave a DDH-based construction of SPHF-friendly commitment schemes, furthermore highly relying on pairings. In this work, we show how to generically construct an SPHF-friendly commitment scheme from a collision-resistant CH scheme and an SPHF-friendly CCA encryption scheme. This allows us to propose an instantiation of our schemes based on the DDH, as efficient as that of Abdalla et al., but without requiring any pairing.

Les protocoles d’échanges de clés sont des primitives cryptographiques qui permettent à plusieurs utilisateurs de communiquer sur un canal non sécurisé via une clé de session sûre. Ce qui permet ainsi de créer des canaux virtuels sécurisés sur des réseaux non sécurisés. Un modèle général a été proposé par Bellare et Rogaway , mais dans le cas de l’authentification par mot de passe le problème s’avère plus ardu. (Du fait de leur petite taille, les méthodes d’attaque de type brute force se révèlent efficaces à cause du manque d’entropie). Dans ce talk, nous nous intéresserons aux nouvelles techniques d’authentification par mot de passe, poignées de mains secrêtes, … et ceci au travers d’une méthodologie de preuves implicites. Pour celà, nous reviendrons sur des techniques existantes et montrerons leurs limitations, puis nous verrons des résultats récents permettant d’améliorer ces constructions pour les rendre plus sûres et plus efficaces.

We present a generic method to prove in a non-interactive way that a committed value does not belong to a given language L, along with an efficient realization of our proof system.

Les signatures en blanc ont trouvé de nombreuses applications quand de l'anonymat est nécessaire, on peut penser par exemple à des systèmes de monnaie électronique ou de vote électronique. Elles permettent à un utilisateur de faire signer un message à un signataire sans que celui-ci ne puisse obtenir d'information sur ce qu'il signe. Nous verrons comment l'approche autour des signatures en blanc a évolué, et présenterons comment obtenir un schéma à la fois optimal en terme de nombres d'étapes et efficace en terme de communication. Ensuite, nous montrerons comment un tel schéma peut être utiliser en vue d'application comme le vote, le paiement ou des opérations linéaires sur un réseau de senseurs.

In this talk, we will focus on signatures and how to tightly prove them, in other words, how to show that there security can be reduced to a classical security hypothesis without any loss proportionnal to the number of signing queries. We will show how to generically build such signatures from chameleon hashes, and so relying on RSA, DL, SIS, ... At the end of this talk, we will rapidly come back on an improvement of this construction where we collapse the tree, and obtain 'generically' an efficient tight signature under varitions of Diffie Hellman.

Nous proposons une transformation générique de tout Message Authentication Code (MAC) affine vers un Chiffrement basé sur l'identité (IBE) sur un groupe bilinéaire d'ordre premier. Nous montrons ensuite que si le MAC vérifie des propriétés de résistances aux forges contre des attaques à chiffrés choisis, et que par exemple l'hypothèse k-lin est vraie, alors l'IBE résultant est adaptivement sûr. Notre preuve de sécurité préserve la tightness, c'est à dire si le MAC est tight, l'IBE l'est aussi. Nous parvenons ensuite à étendre cette transformation pour générer des IBE hiérarchiques (HIBE). Nous montrons comment construire (efficacement) de tels MAC sous des hypothèses standards et raisonnables, pour ainsi présenter le premier schéma d'HIBE tight dans le modèle standard.

We provide a generic transformation from any \emph{affine} message authentication code (MAC) to an identity-based encryption (IBE) scheme over pairing groups of prime order. If the MAC satisfies a security notion related to unforgeability against chosen-message attacks and, for example, the k-Linear assumption holds, then the resulting IBE scheme is adaptively secure. Our security reduction is tightness preserving, i.e., if the MAC has a tight security reduction so has the IBE scheme. Furthermore, the transformation also extends to hierarchical identity-based encryption (HIBE). We also show how to construct affine MACs with a tight security reduction to standard assumptions. This, among other things, provides a tightly secure IBE in the standard model.

In this talk, we provide a generic transformation from any affine message authentication code (MAC) to an identity-based encryption (IBE) scheme over pairing groups of prime order. If the MAC satisfies a security notion related to unforgeability against chosen-message attacks and, for example, the k-Linear assumption holds, then the resulting IBE scheme is adaptively secure. Our security reduction is tightness preserving, i.e., if the MAC has a tight security reduction so has the IBE scheme. Furthermore, the transformation also extends to hierarchical identity-based encryption (HIBE). We also show how to construct affine MACs with a tight security reduction to standard assumptions. This, among other things, provides the first tightly secure HIBE in the standard model This is a joint work with Eike Kiltz and Jiaxin Pan, and will appear at Crypto 2014.

Authenticated Key Exchange (AKE) protocols enable two parties to establish a shared, cryptographically strong key over an insecure network using various authentication means, such as cryptographic keys, short (i.e., lowentropy) secret keys or credentials. In this paper, we provide a general framework, that encompasses several previous AKE primitives such as (Verifier-based) Password-Authenticated Key Exchange or Secret Handshakes, we call LAKE for Language-Authenticated Key Exchange. We first model this general primitive in the Universal Composability (UC) setting. Thereafter, we show that the Gennaro-Lindell approach can efficiently address this goal. But we need smooth projective hash functions on new languages, whose efficient implementations are of independent interest. We indeed provide such hash functions for languages defined by combinations of linear pairing product equations. Combined with an efficient commitment scheme, that is derived from the highly-efficient UC-secure Lindell’s commitment, we obtain a very practical realization of Secret Handshakes, but also Credential-Authenticated Key Exchange protocols. All the protocols are UC-secure, in the standard model with a common reference string, under the classical Decisional Linear assumption.

In this thesis, we create new building blocks and use them to present new efficient protocols via a modular design. We first begin by using the Groth-Sahai methodology for non-interactive proofs to design various group signature protocols in the standard model. We also present a new approach allowing to sign ciphertext and then under the knowledge of a secret independent from the signature protocol we show how a user can recover the signature on the plaintext, creating this way some sort of commutative property between signature and encryption where a decryption of a signature on a ciphertext provides a signature on the associated plaintext. This approach allows us to build a Round-Optimal Blind Signature scheme where the user can ultimately exploit a regular signature. We prove the security of this construction under classical hypotheses in the standard model. We then present a new methodology for implicit proofs of knowledge in an interactive environment without random oracle. For that we use Smooth Projective Hash Functions, first to instantiate Oblivious Signature-Based Envelope schemes, and then to create Authenticated Key Exchange scheme. Throughout this process we further refine the notion of language, and greatly widen the set of languages manageable via SPHF. This last result allows us to introduce the concept of LAKE (Language Authenticated Key Exchange), a new AKE design where two users will be able to share a common key if they both possess a secret word in a language expected by the other. We then show how to build standard AKE schemes (like Password Authenticated Key Exchange) using our framework, and show that our design leads to an increment in efficiency from pre existing solutions. We prove the security of our design in the UC framework under regular hypotheses.

This paper presents a one-round partially-blind signature which achieves perfect blindness in the standard model using a Common Reference String, under classical assumptions: CDH and DLin assumptions in symmetric groups, and similar ones in asymmetric groups. This scheme is more efficient than the previous ones: reduced round complexity and communication complexity, but still weaker complexity assumptions. A great advantage is also to end up with a standard Waters signature, which is quite short

In 2008, Groth and Sahai proposed a powerful suite of techniques for constructing non-interactive zero-knowledge proofs in bilinear groups. Their proof systems have found numerous applications, including group signature schemes, anonymous voting, and anonymous credentials. In this paper, we demonstrate that the notion of smooth projective hash functions can be useful to design round-optimal privacy-preserving interactive protocols. We show that this approach is suitable for designing schemes that rely on standard security assumptions in the standard model with a common-reference string and are more efficient than those obtained using the Groth-Sahai methodology. As an illustration of our design principle, we construct an efficient oblivious signature-based envelope scheme and a blind signature scheme, both round-optimal.

Randomizable encryption allows anyone to transform a ciphertext into a fresh ciphertext of the same message. Analogously, a randomizable signature can be transformed into a new signature on the same message. We combine randomizable encryption and signatures to a new primitive as follows: given a signature on a ciphertext, anyone, knowing neither the signing key nor the encrypted message, can randomize the ciphertext and adapt the signature to the fresh encryption, thus maintaining public verifiability. Moreover, given the decryption key and a signature on a ciphertext, one can compute (“extract”) a signature on the encrypted plaintext. As adapting a signature to a randomized encryption contradicts the standard notion of unforgeability, we introduce a weaker notion stating that no adversary can, after querying signatures on ciphertexts of its choice, output a signature on an encryption of a new message. This is reasonable since, due to extractability, a signature on an encrypted message can be interpreted as an encrypted signature on the message.

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zeroknowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) and also for specific popular protocols relying on their methodology (namely Groth’s group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya’s P-signatures)

Un schéma de signature à seuil classique permet aux membres du groupe d'émettre des signatures au nom du groupe, dès qu'un certain nombre d'entre eux participe au processus. Dans ces cas là, l'anonymat est parfait et ainsi personne ne peut savoir qui a aidé à atteindre le seuil. Dans cet exposé, on va s'intéresser à un anonymat révocable dans les signatures à seuil. De cette façon, on pourra, si besoin, trouver qui a signé. On va plus particulièrement s'interesser à des groupes et seuils dynamiques, mais en gardant une taille optimale pour la signature, ie linéaire en la taille du seuil et ce via une signature ne nécessitant aucune interaction entre les signataires. On montrera une construction efficace, non interactive. Dans le modèle de l'oracle aléatoire la sécurité repose sur le SDH pour la non forgeabilité, et le DLIN/DTDH pour l'anonymat.