AFRICACRYPT '11 4th International Conference on Cryptology in Africa Dakar, Senegal, July 5-7, 2011, Proceedings. Lecture Notes in Computer Science 6737 Springer 2011 ISBN: 978-3-642-21968-9.

On-line version

Public Key Cryptography 13th International Conference on Practice and Theory in Public Key Cryptography, PKC 2010 Paris, France, May 26-28, 2010, Proceedings. Lecture Notes in Computer Science 6056 Springer 2010 ISBN: 978-3-642-13012-0.

On-line version

Applied Cryptography and Network Security 7th International Conference, ACNS 2009 Paris-Rocquencourt, France, June 2-5, 2009, Proceedings. Lecture Notes in Computer Science 5536 Springer 2009 ISBN: 978-3-642-01956-2.

On-line version

Topics in Cryptology - CT-RSA 2006 The Cryptographers' Track at the RSA Conference 2006 San Jose, CA, USA, February 13-17, 2006, Proceedings. Lecture Notes in Computer Science 3860 Springer 2006 ISBN 3-540-31033-9.

On-line version

Cryptology and Network Security 5th International Conference, CANS 2006 Suzhou, China, December 8-10, 2006, Proceedings. Lecture Notes in Computer Science 4301 Springer 2006 ISBN 3-540-49462-6.

On-line version

Advanced Courses CRM Barcelona, Spain -- February 2004. Advanced Course on Contemporary Cryptology, pages 133-189, June 2005. ISBN: 3-7643-7294-X. Birkhäuser Publishers, Basel, 2005.

Since the appearance of public-key cryptography in the Diffie-Hellman seminal paper, many schemes have been proposed, but many have been broken. Indeed, for a long time, the simple fact that a cryptographic algorithm had withstood cryptanalytic attacks for several years was considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken.
A much more convincing line of research has tried to provide ``provable'' security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can efficiently solve the underlying problem. Unfortunately, this initially was a purely theoretical work: very few practical schemes could be proven in this so-called ``standard model'' because such a security level rarely meets with efficiency. Ten years ago, Bellare and Rogaway proposed a trade-off to achieve some kind of validation of efficient schemes, by identifying some concrete cryptographic objects with ideal random ones. The most famous identification appeared in the so-called ``random-oracle model''. More recently, another direction has been taken to prove the security of efficient schemes in the standard model (without any ideal assumption) by using stronger computational assumptions.
In these lectures, we focus on practical asymmetric protocols together with their ``reductionist'' security proofs, mainly in the random-oracle model. We cover the two main goals that public-key cryptography is devoted to solve: authentication with digital signatures, and confidentiality with public-key encryption schemes.

Quisquater Festschrif
D. Naccache Ed. Pages 108-131, LNCS 6805, © Springer-Verlag, 2011.

Traceable signatures schemes were introduced by Kiayias, Tsiounis and Yung in order to solve traceability issues in group signature schemes. They wanted to enable authorities to delegate some of their detection capabilities to tracing sub-authorities. Instead of opening every single signatures and then threatening privacy, tracing sub-authorities are able to know if a signature was emitted by specific users only.
In 2008, Libert and Yung proposed the first traceable signature schemes proven secure in the standard model. We design another scheme in the standard model, with two instantiations based either on the SXDH or the DLIN assumptions. Our construction is far more efficient, both in term of group elements for the signature, and pairing computation for the verification. Besides the ``step-in'' (confirmation) feature that allows a user to prove he was indeed the signer, our construction provides the ``step-out'' (disavowal) procedure that allows a user to prove he was not the signer.
Since list signature schemes are closely related to this primitive, we consider them, and answer an open problem: list signature schemes are possible without random oracles.

Towards Trustworthy Elections
D. Chaum, R. Rivest, M. Jakobsson, B. Schoenmakers, P. Ryan, and J. Benaloh Eds.
Pages 191-199, LNCS 6000, © IAVOSS/Springer-Verlag, 2010.

In this paper, we study the problem of simultaneously achieving several security properties, for voting schemes, without non-standard assumptions. More specifically, we focus on the universal verifiability of the computation of the tally, on the unconditional privacy/anonymity of the votes, and on the receipt-freeness properties, for the most classical election processes. Under usual assumptions and efficiency requirements, we show that a voting system that wants to publish the final list of the voters who actually voted, and to compute the number of times each candidate has been chosen, we cannot achieve:

• universal verifiability of the tally (UV) and unconditional privacy of the votes (UP) simultaneously, unless all the registered voters actually vote;
• universal verifiability of the tally (UV) and receipt- freeness (RF), unless private channels are available between the voters and/or the voting authorities.

Formal to Practical Security
V. Cortier, C. Kirchner, M. Okada, and H. Sakurada Eds.
Pages 95-115, LNCS 5458, © Springer-Verlag, 2009.

We define a general model for consecutive delegations of signing rights with the following properties: The delegatee actually signing and all intermediate delegators remain anonymous. As for group signatures, in case of misuse, a special authority can open signatures to reveal all delegators' and the signer's identity. The scheme satisfies a strong notion of non-frameability generalizing the one for dynamic group signatures. We give formal definitions of security and show them to be satisfiable by constructing an instantiation proven secure under general assumptions in the standard model. Our primitive is a proper generalization of both group signatures and proxy signatures and can be regarded as non-frameable dynamic hierarchical group signatures.

Formal to Practical Security
V. Cortier, C. Kirchner, M. Okada, and H. Sakurada Eds.
Pages 138-157, LNCS 5458, © Springer-Verlag, 2009.

Identity-based encryption is a very convenient tool to avoid key management. Recipient-privacy is also a major concern nowadays. To combine both, anonymous identity-based encryption has been proposed. This paper extends this notion to stronger adversaries (the authority itself). We discuss this new notion, together with a new kind of non- malleability with respect to the identity, for several existing schemes. Interestingly enough, such a new anonymity property has an independent application to password-authenticated key exchange. We thus come up with a new generic framework for password-authenticated key exchange, and a concrete construction based on pairings.

ACM Transactions on Information and System Security, Volume 10 - Number 3. © ACM, 2007.

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.

International Journal of Security and Networks, Volume 2 - Numbers 3/4.
Pages 284-296, © Inderscience, 2007.

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.

International Journal of Wireless and Mobile Computing.
Special Issue on Security of Computer Network and Mobile Systems.
Volume 2, Number 1, pages 4-13. © IJWMC, Inderscience, 2007.

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.

Journal of Cryptology, Volume 20 - Number 1.
Pages 115-149, Springer-Verlag, 2007.
© IACR 2007.

In the security chain the weakest link is definitely the human one: human beings cannot remember long secrets and often resort to rather insecure solutions to keep track of their passwords or pass-phrases. For this reason it is very desirable to have protocols that do not require long passwords to guarantee security, even in the case on which exhaustive search is feasible. This is actually the goal of password-based key exchange protocols, secure against off-line dictionary attacks: two people share a password (possibly a very small one, say a 4-digit number), and after the protocol execution, they end-up sharing a large secret session key (known to both of them, but nobody else.) Then an adversary attacking the system should try several connections (on average 5,000 for the above short password) in order to be able to get the correct password. Such a large number of erroneous connections can be prevented by various means.
Our results can be highlighted as follows. First we define a new primitive that we call trapdoor hard-to-invert group isomorphisms, and give some candidates. Then we present a generic password-based key exchange construction, that admits a security proof assuming that these objects exist. Finally, we instantiate our general scheme with some concrete examples, such as the Diffie-Hellman function and the RSA function, but more interestingly the modular square root function, which leads to the first scheme with security related to the integer factorization problem. Furthermore, the latter variant is very efficient for one party (the server.) Our results hold in the random-oracle model.

IEE Proceedings -- Information Security.
Volume 153, Issue 1, pages 27-39. © IET, 2006.

Password-based authenticated key exchange (PAKE) are protocols which are designed to be secure even when the secret key used for authentication is a human-memorable password. In this paper, we consider PAKE protocols in the three-party scenario, in which the users trying to establish a common secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for PAKE protocols and introduce new ones that are more suitable to the case of generic constructions of three-party protocols. We then present a natural generic construction of a three-party PAKE protocol from any two-party PAKE protocol and prove its security. To the best of our knowledge, the new protocol is the first provably-secure PAKE protocol in the three-party setting.

Journal of Computer Communications.
Special Issue on Security and Performance in Wireless and Mobile Networks.
Volume 27 - Numer 17 - Pages 1730-1737, © Elsevier, 2004.

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.

Journal of Cryptology, Volume 17 - Number 2.
Pages 81-104, Springer-Verlag, 2004.
© IACR 2004.

Recently Victor Shoup noted that there is a gap in the widely-believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) one-wayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight.

Designs, Codes and Cryptography. Volume 28, Number 1, pages 5-32.
Kluwer Academic Publishers, Boston. January 2003.

The appearance of the theory of zero-knowledge, presented by Goldwasser, Micali and Rackoff in 1985, opened a way to secure identification schemes. The first application was the famous Fiat-Shamir scheme based on the problem of modular square roots extraction. In the following years, many other schemes have been proposed, some Fiat-Shamir extensions but also new discrete logarithm based schemes. Therefore, all of them were based on problems from number theory. The main drawback thus was common: a high computational load because of arithmetical operations modulo large integers. Implementation on low-cost smart cards was made difficult and inefficient.
With the Permuted Kernels Problem (PKP), Shamir proposed the first efficient scheme allowing for an implementation on such low-cost smart cards, but very few others have afterwards been suggested.
In this paper, we present an efficient identification scheme based on a combinatorial NP-complete problem: the Permuted Perceptrons Problem (PPP). This problem seems hard enough to be unsolvable even with very small parameters, and some recent cryptanalysis studies confirm that position. Furthermore, it admits efficient zero-knowledge proofs of knowledge and so it is well-suited for cryptographic purposes. An actual implementation completes the optimistic opinion about efficiency and practicability on low-cost smart cards, and namely with less than 2KB of EEPROM and just 100 Bytes of RAM and 5KB of communication.

Journal of Cryptology, Volume 16 - Number 3.
Pages 185-215, Springer-Verlag, 2003.
© IACR 2003.

We introduce a new class of computational problems which we call the ``one-more-RSA-inversion'' problems. Our main result is that two problems in this class, which we call the chosen-target and known-target inversion problems respectively, have polynomially-equivalent computational complexity. We show how this leads to a proof of security for Chaum's RSA-based blind signature scheme in the random oracle model based on the assumed hardness of either of these problems. We define and prove analogous results for ``one-more-discrete-logarithm'' problems. Since the appearence of the preliminary version of this paper, the new problems we have introduced have found other uses as well.

Journal of Telecommunications and Information Technology. Volume 4/2002. Pages 41-56.
Copyright by National Institute of Telecommunications, Warsaw 2002.

Since the appearance of public-key cryptography in Diffie-Hellman seminal paper, many schemes have been proposed, but many have been broken. Indeed, for many people, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken.
A much more convincing line of research has tried to provide ``provable'' security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can efficiently solve the underlying problem.
Unfortunately, very few practical schemes can be proven in this so-called ``standard model'' because such a security level rarely meets with efficiency. A convenient but recent way to achieve some kind of validation of efficient schemes has been to identify some concrete cryptographic objects with ideal random ones: hash functions are considered as behaving like random functions, in the so-called ``random oracle model'', block ciphers are assumed to provide perfectly independent and random permutations for each key in the ``ideal cipher model'', and groups are used as black-box groups in the ``generic model''.
In this paper, we focus on practical asymmetric protocols together with their ``reductionist'' security proofs. We cover the two main goals that public-key cryptography is devoted to solve: authentication with digital signatures, and confidentiality with public-key encryption schemes.

RSA Laboratories' CryptoBytes. Volume 5, No. 1 -- Winter/Spring 2002, pages 9-19.
© RSA Security Inc. 2002.

In 1993, Bellare and Rogaway formalized the concept of a random oracle, imported from complexity theory for cryptographic purposes. This new tool allowed them to present several asymmetric encryption and signature schemes that are both efficient and provably secure (in the random oracle model). The Optimal Asymmetric Encryption Padding (OAEP) is the most significant application of the random oracle model to date. It gives an efficient RSA encryption scheme with a strong security guarantee (semantic security against chosen-ciphertext attacks). After Bleichenbacher's devastating attack on RSA--PKCS #1 v1.5 in 1998, RSA-OAEP became the natural successor (RSA-PKCS #1 v2.0) and thus a de facto international standard. Surprisingly, Shoup recently showed that the original proof of security for OAEP is incorrect. Without a proof, RSA-OAEP cannot be trusted to provide an adequate level of security. Luckily, shortly after Shoup's discovery a formal and complete proof was found in joint work by the author and others that reaffirmed the strong level of security provided by RSA-OAEP. However, this new security proof still does not guarantee security for key sizes used in practice due to the inefficiency of the security reduction (the reduction to inverting RSA takes quadratic time). Recent alternatives to OAEP, such as OAEP+, SAEP+, and REACT, admit more efficient proofs and thus provide adequate security for key sizes used in practice.

Journal of Cryptology, Volume 13 - Number 3.
Pages 361-396, Springer-Verlag, 2000.
© IACR 2000.

Since the appearance of public-key cryptography in the seminal Diffie-Hellman paper, many new schemes have been proposed and many have been broken. Thus, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is often considered as a kind of validation procedure. A much more convincing line of research has tried to provide ``provable'' security for cryptographic protocols. Unfortunately, in many cases, provable security is at the cost of a considerable loss in terms of efficiency. Another way to achieve some kind of provable security is to identify concrete cryptographic objects such as hash functions with ideal random objects and to use arguments from relativized complexity theory. The model underlying this approach is often called the ``random oracle model''. We will use the word ``arguments'' for security results proved in this model. As usual, these arguments are relative to well-established hard algorithmic problems such as factorization or the discrete logarithm.
In this paper, we offer security arguments for a large class of known signature schemes. Moreover, we give for the first time an argument for a very slight variation of the well-known El Gamal signature scheme. In spite of the existential forgery of the original scheme, we prove that our variant resists existential forgeries even against an adaptively chosen-message attack. This is provided that the discrete logarithm problem is hard to solve.
Next, we study the security of blind signatures which are the most important ingredient for anonymity in off-line electronic cash systems. We first define an appropriate notion of security related to the setting of electronic cash. We then propose new schemes for which one can provide security arguments.

Proceedings of the 9th Theory of Cryptography Conference (TCC 2012)
(March 18-21, 2012, Taormina, Italy)
R. Cramer Ed., Pages ???-???, LNCS 7194, Springer-Verlag, 2012.
© IACR 2012.

TBA

In Proceedings of the Conference on Applied Cryptography and Network Security (ACNS '11)
(7 -- 10 june 2011, Nerja, Spain)
J. Lopez and G. Tsudik Eds., Pages 377-394, LNCS 6715, © Springer-Verlag, 20011.

This paper clarifies the relationships between security notions for broadcast encryption. In the past, each new scheme came with its own definition of security, which makes them hard to compare. We thus define a set of notions, as done for signature and encryption, for which we prove implications and separations, and relate the existing notions to the ones in our framework. We find some interesting relationships between the various notions, especially in the way they define the receiver set of the challenge message. In addition, we define a security notion that is stronger than all previous ones, and give an example of a scheme that fulfills this notion.

Proceedings of the 2011 International Conference on Practice and Theory in Public Key Cryptography (PKC 2011)
(March 6-9, 2011, Taormina, Italy)
D. Catalano, N. Fazio, R. Gennaro, and A. Nicolosi Eds., Pages 403-422, LNCS 6571, Springer-Verlag, 2011.
© IACR 2011.

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. Using Groth-Sahai proofs and Waters signatures, we give several instantiations of our primitive and prove them secure under classical assumptions in the standard model and the CRS setting. As an application, we show how to construct an efficient non-interactive receipt-free universally verifiable e-voting scheme. In such a scheme a voter cannot prove what his vote was, which precludes vote selling. Besides, our primitive also yields an efficient round-optimal blind signature scheme based on standard assumptions, and namely for the classical Waters signature.

Proceedings of the Cryptographers' Track at RSA Conference '11 (CT-RSA '11)
(february 14-18, 2011, San Francisco, California, USA)
A. Kiayias Ed., Pages 142-160, LNCS 6558, © Springer-Verlag, 2011.

Password-based authenticated group key exchange allows any group of users in possession of a low-entropy secret key to establish a common session key even in the presence of adversaries. In this paper, we propose a new generic construction of password-authenticated group key exchange protocol from any two-party password-authenticated key exchange with explicit authentication. Our new construction has several advantages when compared to existing solutions. First, our construction only assumes a common reference string and does not rely on any idealized models. Second, our scheme enjoys a simple and intuitive security proof in the universally composable framework and is optimal in the sense that it allows at most one password test per user instance. Third, our scheme also achieves a strong notion of security against insiders in that the adversary cannot bias the distribution of the session key as long as one of the players involved in the protocol is honest. Finally, we show how to easily extend our protocol to the dynamic case in a way that the costs of establishing a common key between two existing groups is significantly smaller than computing a common key from scratch.

First International Conference on Cryptology and Information Security (LatinCrypt 2010)
(august 8-11, 2010, Puebla, Mexico)
M. Abdalla and P. Barreto Eds., Pages 40-60, LNCS 6212, © Springer-Verlag, 2010.

The notion of key privacy for asymmetric encryption schemes was formally defined by Bellare, Boldyreva, Desai and Pointcheval in 2001: it states that an eavesdropper in possession of a ciphertext is not able to tell which specific key, out of a set of known public keys, is the one under which the ciphertext was created. Since anonymity can be misused by dishonest users, some situations could require a tracing authority capable of revoking key privacy when illegal behavior is detected. Prior works on traceable anonymous encryption miss a critical point: an encryption scheme may produce a covert channel which malicious users can use to communicate illegally using ciphertexts that trace back to nobody or, even worse, to some honest user. In this paper, we examine subliminal channels in the context of traceable anonymous encryption and we introduce a new primitive termed mediated traceable anonymous encryption that provides confidentiality and anonymity while preventing malicious users to embed subliminal messages in ciphertexts. In our model, all ciphertexts pass through a mediator (or possibly several successive mediators) and our goal is to design protocols where the absence of covert channels is guaranteed as long as the mediator is honest, while semantic security and key privacy hold even if the mediator is dishonest. We give security definitions for this new primitive and constructions meeting the formalized requirements. Our generic construction is fairly efficient, with ciphertexts that have logarithmic size in the number of group members, while preventing collusions. The security analysis requires classical complexity assumptions in the standard model.

Third African International Conference on Cryptology (AfricaCrypt '10)
(may 3-6, 2010, Stellenbosch, South Africa)
D. Bernstein and T. Lange Eds., Pages 297-315, LNCS 6055, © Springer-Verlag, 2010.

Distributed-password public-key cryptography (DPWPKC) allows the members of a group of people, each one holding a small secret password only, to help a leader to perform the private operation, associated to a public-key cryptosystem. Abdalla et al. recently defined this tool, with a practical construction. Unfortunately, the latter applied to the ElGamal decryption only, and relied on the DDH assumption, excluding any recent pairing-based cryptosystems. In this paper, we extend their techniques to support, and exploit, pairing-based properties: we take advantage of pairing-friendly groups to obtain efficient (simulation-sound) zero-knowledge proofs, whose security relies on the Decisional Linear assumption. As a consequence, we provide efficient protocols, secure in the standard model, for ElGamal decryption, but also for Linear decryption, as well as extraction of several identity-based cryptosystems. Furthermore, we strenghten their security model by suppressing the useless TestPwd queries in the functionality.

Third African International Conference on Cryptology (AfricaCrypt '10)
(may 3-6, 2010, Stellenbosch, South Africa)
D. Bernstein and T. Lange Eds., Pages 351-368, LNCS 6055, © Springer-Verlag, 2010.

Modern multi-user communication systems, including popular instant messaging tools, social network platforms, and cooperative-work applications, offer flexible forms of communication and exchange of data. At any time point concurrent communication sessions involving different subsets of users can be invoked. The traditional tool for achieving security in a multi-party communication environment are group key exchange (GKE) protocols that provide participants with a secure group key for their subsequent communication. Yet, in communication scenarios where various user subsets may be involved in different sessions the deployment of classical GKE protocols has clear performance and scalability limitations as each new session should be preceded by a separate execution of the protocol. The motivation of this work is to study the possibility of designing more flexible GKE protocols allowing not only the computation of a group key for some initial set of users but also efficient derivation of independent secret keys for all potential subsets. In particular we improve and generalize the recently introduced GKE protocols enabling on-demand derivation of peer-to-peer keys (so called GKE+P protocols). We show how a group of users can agree on a secret group key while obtaining some additional information that they can use on-demand to efficiently compute independent secret keys for any possible subgroup. Our security analysis relies on the Gap Diffie-Hellman assumption and uses random oracles.

Proceedings of CANS '09
(december 12 - 14, 2009, Kanazawa, Ishikawa, Japan)
J. A. Garay, A. Miyaji, and A. Otsuka Eds. Pages 226-247, LNCS 5888, Springer-Verlag, 2009.

We propose a new blind certification protocol that provides interesting properties while remaining efficient. It falls in the Groth-Sahai framework for witness-indistinguishable proofs, thus extended to a certified signature it immediately yields non-frameable group signatures. We then use it to build an efficient (offline) e-cash system that guarantees user anonymity and transferability of coins without increasing their size. As required for fair e-cash, in case of fraud, anonymity can be revoked by an authority, which is also crucial to deter from double spending.

In Advances in Cryptology - Proceedings of CRYPTO '09
(august 16 - 20, 2009, Santa Barbara, California, USA)
Sh. Halevi Ed. Pages 671-689, LNCS 5677, Springer-Verlag, 2009.
© IACR 2009.

The notion of smooth projective hash functions was proposed by Cramer and Shoup and can be seen as special type of zero-knowledge proof system for a language. Though originally used as a means to build efficient chosen-ciphertext secure public-key encryption schemes, some variations of the Cramer-Shoup smooth projective hash functions also found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer. In this paper, we first address the problem of building smooth projective hash functions for more complex languages. More precisely, we show how to build such functions for languages that can be described in terms of disjunctions and conjunctions of simpler languages for which smooth projective hash functions are known to exist. Next, we illustrate how the use of smooth projective hash functions with more complex languages can be efficiently associated to extractable commitment schemes and avoid the need for zero-knowledge proofs. Finally, we explain how to apply these results to provide more efficient solutions to two well-known cryptographic problems: a public-key certification which guarantees the knowledge of the private key by the user without random oracles nor zero-knowledge proofs and adaptive security for password-based authenticated key exchange protocols in the universal composability framework.

Third International Conference on Pairing-based Cryptography (Pairing 2009)
(August 12 - 14, 2009, Palo Alto, California, USA)
H. Shacham and B. Waters Eds.
Pages 132-149, LNCS 5671, © Springer-Verlag, 2009.

We give a generic methodology to unlinkably anonymize cryptographic schemes in bilinear groups using the Boneh-Goh-Nissim cryptosystem and NIZK proofs in the line of Groth, Ostrovsky and Sahai. We illustrate our techniques by presenting the first instantiation of anonymous proxy signatures (in the standard model), a recent primitive unifying the functionalities and strong security notions of group and proxy signatures. To construct our scheme, we introduce various efficient NIZK and witness-indistinguishable proofs, and a relaxed version of simulation soundness.

Second African International Conference on Cryptology (AfricaCrypt '09)
(june 21-25, 2009, Gammarth, Tunisia)
B. Preneel Ed., Pages 254-271, LNCS 5580, © Springer-Verlag, 2009.

Adaptively-secure key exchange allows the establishment of secure channels even in the presence of an adversary that can corrupt parties adaptively and obtain their internal states. In this paper, we give a formal definition of contributory protocols and define an ideal functionality for password-based group key exchange with explicit authentication and contributiveness in the UC framework. As with previous definitions in the same framework, our definitions do not assume any particular distribution on passwords or independence between passwords of different parties. We also provide the first steps toward realizing this functionality in the above strong adaptive setting by analyzing an efficient existing protocol and showing that it realizes the ideal functionality in the random-oracle and ideal-cipher models based on the CDH assumption.

In Advances in Cryptology - Proceedings of EUROCRYPT '09
(april 26 - 30, 2009, Kohln, Germany)
A. Joux Ed. Pages 572--589, LNCS 5479, Springer-Verlag, 2009.
© IACR 2009.

In this paper, we study a quite simple deterministic randomness extractor from random Diffie-Hellman elements defined over a prime order multiplicative subgroup G of a finite field Z_p (the truncation), and over a group of points of an elliptic curve (the truncation of the abscissa). Informally speaking, we show that the least significant bits of a random element in G, a subset of Z*_p, or of the abscissa of a random point in E(F_p) are indistinguishable from a uniform bit-string. Such an operation is quite efficient, and is a good randomness extractor, since we show that it can extract nearly the same number of bits as the Leftover Hash Lemma can do for most Elliptic Curve parameters and for large subgroups of finite fields. To this aim, we develop a new technique to bound exponential sums that allows us to double the number of extracted bits compared with previous known results proposed at ICALP'06 by Fouque et al. It can also be used to improve previous bounds proposed by Canetti et al.
One of the main application of this extractor is to mathematically prove an assumption proposed at Crypto '07 and used in the security proof of the Elliptic Curve Pseudo Random Generator proposed by the NIST. The second most obvious application is to perform efficient key derivation given Diffie-Hellman elements.

Proceedings of the 2009 International Conference on Practice and Theory in Public Key Cryptography (PKC 2009)
(march 18-20, 2009, Irvine, California, USA)
S. Jarecki and G. Tsudik Eds., Pages 139-159, LNCS 5443, Springer-Verlag, 2009.
© IACR 2009.

We introduce the notion of distributed password-based public-key cryptography, where a virtual high-entropy private key is implicitly defined as a concatenation of low-entropy passwords held in separate locations. The users can jointly perform private-key operations by exchanging messages over an arbitrary channel, based on their respective passwords, without ever sharing their passwords or reconstituting the key. Focusing on the case of ElGamal encryption as an example, we start by formally defining ideal functionalities for distributed public-key generation and virtual private-key computation in the UC model. We then construct efficient protocols that securely realize them in either the RO model (for efficiency) or the CRS model (for elegance). We conclude by showing that our distributed protocols generalize to a broad class of ``discrete-log''-based public-key cryptosystems, which notably includes identity-based encryption. This opens the door to a powerful extension of IBE with a virtual PKG made of a group of people, each one memorizing a small portion of the master key.

Proceedings of CANS '08
(december 2 - 4, 2008, Hong-Kong, China)
M. Franklin, L. Hui, and D. Wong Eds. Pages 133--148, LNCS 5339, Springer-Verlag, 2008.

In Asiacrypt 2005, Abdalla et al. put forward the notion of gateway-based password-authenticated key exchange GPAKE protocol, which allows clients and gateways to establish a common session key with the help of an authentication server. In addition to the semantic security of the session key, their solution also provided additional security properties such as password protection with respect to malicious gateways and key privacy with respect to curious authentication servers. In this paper, we further pursue this line of research and present a new and stronger security model for GPAKE schemes, combining all above-mentioned security properties. In addition to allowing a security proof for all these security properties, the new security model has also other advantages over the previous one such as taking into account user corruptions. After describing the new security model, we then present a new variant of the GPAKE scheme of Abdalla et al. with similar efficiency. Like the original scheme, the new scheme is also transparent in that it does not differ significantly from a classical PAKE scheme from the point of view of a client. Finally, we also show how to add client anonymity with respect to the server to the basic GPAKE scheme by using private information retrieval protocols.

Proceedings of the 3rd International Workshop on Security (IWSEC '08)
(november 25-27, 2008, Kagawa, Japan)
Kanta Matsuura and Eiichiro Fujisaki Eds., Pages 219-230, LNCS 5312, © Springer-Verlag, 2008.

We introduce a new way for generating strong keys from biometric data. Contrary to popular belief, this leads us to biometric keys which are easy to obtain and renew. Our solution is based on two-factor authentication: a low-cost card and a biometric trait are involved. Following the Boneh and Shacham group signature construction, we introduce a new biometric-based remote authentication scheme. Surprisingly, for ordinary uses no interactions with a biometric database are needed in this scheme. As a side effect of our proposal, privacy of users is easily obtained while it can possibly be removed, for instance under legal warrant.

Sixth Conference on Security in Communication Networks '08
(September 10 - 12, 2008, Amalfi, Italy)
R. Ostrovsky Ed.
Pages 201-217, LNCS 5229, © Springer-Verlag, 2008.

Sixth Conference on Security in Communication Networks '08
(September 10 - 12, 2008, Amalfi, Italy)
R. Ostrovsky Ed.
Pages 375-391, LNCS 5229, © Springer-Verlag, 2008.

Identity-based encryption is a very convenient tool to avoid key management. Recipient-privacy is also a major concern nowadays. To combine both, anonymous identity-based encryption has been proposed. This paper extends this notion to stronger adversaries (the authority itself). We discuss this new notion, together with a new kind of non-malleability with respect to the identity, for several existing schemes. Interestingly enough, such a new anonymity property has an independent application to password-authenticated key exchange. We thus come up with a new generic framework for password-authenticated key exchange, and a concrete construction based on pairings.

In Advances in Cryptology - Proceedings of CRYPTO '08
(august 17 - 21, 2008, Santa Barbara, California, USA)
D. Wagner Ed. Pages 317--334, LNCS 5157, Springer-Verlag, 2008.
© IACR 2008.

This paper deals with threshold public-key encryption which allows a pool of players to decrypt a ciphertext if a given threshold of authorized players cooperate. We generalize this primitive to the dynamic setting, where any user can dynamically join the system, as a possible recipient; the sender can dynamically choose the authorized set of recipients, for each ciphertext; and the sender can dynamically set the threshold t for decryption capability among the authorized set. We first give a formal security model, which includes strong robustness notions, and then we propose a candidate achieving all the above dynamic properties, that is semantically secure in the standard model, under a new non-interactive assumption, that fits into the general Diffie-Hellman exponent framework on groups with a bilinear map. It furthermore compares favorably with previous proposals, a.k.a. threshold broadcast encryption, since this is the first threshold public-key encryption, with dynamic authorized set of recipients and dynamic threshold that provides constant-size ciphertexts.

In Proceedings of the Conference on Applied Cryptography and Network Security (ACNS '08)
(3 -- 6 june 2008, New York, USA)
S. Bellovin and R. Gennaro Eds., Pages 277-295, LNCS 5037, © Springer-Verlag, 2008.

In order to increase the security for authenticated key exchange protocols, various authentication means can be used together. In this paper, we introduce a security model for multi-factor authenticated key exchange, which combines a password, a secure device, and biometric authentications. We thereafter present a scheme, that can be proven secure, in the random-oracle model.

Proceedings of the 4th Information Security Practice and Experience Conference (ISPEC '08)
(april 21-23, 2008, Sydney, Australia)
Liqun Chen and Yi Mu Eds., Pages 56-70, LNCS 4991, © Springer-Verlag, 2008.

With their increasing popularity in cryptosystems, biometrics have attracted more and more attention from the information security community. However, how to handle the relevant privacy concerns remains to be troublesome. In this paper, we propose a novel security model to formalize the privacy concerns in biometric-based remote authentication schemes. Our security model covers a number of practical privacy concerns such as identity privacy and transaction anonymity, which have not been formally considered in the literature. In addition, we propose a general biometric-based remote authentication scheme and prove its security in our security model.

Proceedings of the Cryptographers' Track at RSA Conference '08 (CT-RSA '08)
(april 8-11, 2008, San Francisco, California, USA)
T. Malkin Ed., Pages 335-351, LNCS 4964, © Springer-Verlag, 2008.

Most of the existing password-based authenticated key exchange protocols have proofs either in the indistinguishability-based security model of Bellare, Pointcheval, and Rogaway (BPR) or in the simulation-based of Boyko, MacKenzie, and Patel (BMP). Though these models provide a security level that is sufficient for most applications, they fail to consider some realistic scenarios such as participants running the protocol with different but possibly related passwords. To overcome these deficiencies, Canetti et al proposed a new security model in the universal composability (UC) framework which makes no assumption on the distribution on passwords used by the protocol participants. They also proposed a new protocol, but, unfortunately, the latter is not as efficient as some of the existing protocols in BPR and BMP models. In this paper, we investigate whether some of the existing protocols that were proven secure in BPR and BMP models can also be proven secure in the new UC model and we answer this question in the affirmative. More precisely, we show that the protocol by Bresson, Chevassut, and Pointcheval (BCP) in CCS 2003 is also secure in the new UC model. The proof of security relies in the random-oracle and ideal-cipher models and works even in the presence of adaptive adversaries, capable of corrupting players at any time and learning their internal states.

Proceedings of the 3rd ACM Symposium on InformAtion, Computer and Communications Security (ASIACCS '08)
(march 18 - 20, 2008, Tokyo, Japan)
M. Abe and V. Gligor Eds, Pages 21-32, © ACM Press, 2008.

In this paper, we study the security of a practical randomness extractor and its application on the TLS standard. Randomness extraction is the first stage of key derivation function since the secret shared between the entities does not always come from a uniformly distributed source. More precisely, we wonder if the HMAC function, used in many standards, can be considered as a randomness extractor? We show that when the shared secret is put in the key space of the HMAC function, there are two cases to consider depending on whether the key is larger than the block-length of the hash function or not. In both cases, we provide a formal proof that the output is pseudo-random, but under different assumptions. Nevertheless, all the assumptions are related to the fact that the compression function of the underlying hash function behaves like a pseudo-random function. This analysis allows us to prove the TLS randomness extractor for Diffie-Hellman and RSA key exchange. Of independent interest, we study a computational analog to the leftover hash lemma for computational almost universal hash function families: any pseudo-random function family matches the latter definition.

Proceedings of CANS '07
(december 8 - 10, 2007, Singapore)
T. Okamoto Ed. Pages 175-193, LNCS 4856, Springer-Verlag, 2007.

In this paper we generalize the concept of Private Information Retrieval (PIR) by formalizing a new cryptographic primitive, named Extended Private Information Retrieval (EPIR). Instead of enabling a user to retrieve a bit (or a block) from a database as in the case of PIR, an EPIR protocol enables a user to evaluate a function f which takes a string chosen by the user and a block from the database as input. Like PIR, EPIR can also be considered as a special case of the secure two-party computation problem (and more specifically the oblivious function evaluation problem). We propose two EPIR protocols, one for comparing equality and the other for computing Hamming distance. As an important application, we show how to construct strong privacy-preserving biometric-based authentication schemes by employing these EPIR protocols.

First International Conference on Pairing-based Cryptography (Pairing 2007)
(July 2 - 3, 2007, Tokyo, Japan)
T. Takagi, T. Okamoto, E. Okamoto and T. Okamoto Eds.
Pages 39-59, LNCS 4575, © Springer-Verlag, 2007.

This paper puts forward new efficient constructions for public-key broadcast encryption that simultaneously enjoy the following properties: receivers are stateless; encryption is collusion-secure for arbitrarily large collusions of users and security is tight in the standard model; new users can join dynamically i.e. without modification of user decryption keys nor ciphertext size and little or no alteration of the encryption key. We also show how to permanently revoke any subgroup of users. Most importantly, our constructions achieve the optimal bound of O(1)-size either for ciphertexts or decryption keys, where the hidden constant relates to a couple of elements of a pairing-friendly group. Our broadcast-KEM trapdoor technique, which has independent interest, also provides a dynamic broadcast encryption system improving all previous efficiency measures (for both execution time and sizes) in the private-key setting.

Proceedings of ACISP '07
(july 2 - 4, 2007, Townsville, Queensland, Australia)
J. Pieprzyk, H. Ghodosi and E. Dawson Eds. Pages 96-106, LNCS 4586, Springer-Verlag, 2007.

This work deals with the security challenges in authentication protocols employing volatile biometric features, where the authentication is indeed a comparison between a fresh biometric template and that enrolled during the enrollment phase. We propose a security model for biometric-based authentication protocols by assuming that the biometric features to be public. Extra attention is paid to the privacy issues related to the sensitive relationship between a biometric feature and the relevant identity. Relying on the Goldwasser-Micali encryption scheme, we introduce a protocol for biometric-based authentication and prove its security in our security model.

In Advances in Cryptology - Proceedings of ASIACRYPT '06
(december 2 - 6, 2006, Shanghai, China)
X. Lai and K. Chen Eds. Pages 332-347, LNCS 4284, Springer-Verlag, 2006.
© IACR 2006.

This paper presents a secure constant-round password-based group key exchange protocol in the common reference string model. Our protocol is based on the group key exchange protocol by Burmester and Desmedt and on the 2-party password-based authenticated protocols by Gennaro and Lindell, and by Katz, Ostrovsky, and Yung. The proof of security is in the standard model and based on the notion of smooth projective hash functions. As a result, it can be instantiated under various computational assumptions, such as decisional Diffie-Hellman, quadratic residuosity, and N-residuosity.

International Conference on Cryptology in Vietnam 2006
(September 25 - 28, 2006, Hanoi, Vietnam)
P. Q. Nguyen Ed.
Pages 193-210, LNCS 4341, © Springer-Verlag, 2006.

Group signatures allow members to sign on behalf of a group. Recently, several schemes have been proposed, in order to provide more efficient and shorter group signatures. However, this should be performed achieving a strong security level. To this aim, a formal security model has been proposed by Bellare, Shi and Zang, including both dynamic groups and concurrent join. Unfortunately, very few schemes satisfy all the requirements, and namely the shortest ones needed to weaken the anonymity notion.
We present an extremely short dynamic group signature scheme, with concurrent join, provably secure in this model. It achieves stronger security notions than BBS, and namely the full anonymity, while still shorter. The proofs hold under the q-SDH and the XDH assumptions, in the random oracle model.

Fifth Conference on Security in Communication Networks '06
(September 6 - 8, 2006, Maiori, Italy)
M. Yung Ed.
Pages 186--200, LNCS 4116, © Springer-Verlag, 2006.

Designing authenticated key exchange algorithms is a problem well understood in cryptography: there are established security models, and proposals proved secure in these models. However, models currently used assume that a honest entity involved in a key exchange is trusted as a whole. In many practical contexts, the entity is divided in an \emph{authentication device} storing a private key and having low computing power, and a \emph{computing device}, that performs part of the computations required by protocol runs. The computing device might be a PC connected to the Internet, and the authenticating device a smart card. In that case as well in many others, a compromise of the computing device is to be expected. We therefore propose a variant of the MQV and HMQV key exchange protocols secure in that context, unlike the original protocols. The security claim is supported by a proof in a model derived from the Canetti-Krawczyk one, which takes into account more general rogue behaviours of the computing device.

Fifth Conference on Security in Communication Networks '06
(September 6 - 8, 2006, Maiori, Italy)
M. Yung Ed.
Pages 156--172, LNCS 4116, © Springer-Verlag, 2006.

The main application of cryptography is the establishment of secure channels. The most classical way to achieve this goal is definitely the use of variants of the signed Diffie-Hellman protocol. It applies a signature algorithm on the flows of the basic Diffie-Hellman key exchange, in order to achieve authentication. However, signature-less authenticated key exchange have numerous advantages, and namely from the efficiency point of view. They are thus well-suited for some constrained environments. On the other hand, this efficiency comes at the cost of some uncertainty about the actual security.

This paper focuses on the two most famous signature-less authenticated key exchange protocols, MTI/C0 and MQV. While the formal security of MTI/C0 has never been studied, results for the plain MQV protocol are still debated. We point out algorithmic assumptions on which some security proofs can be built in the random oracle model. The stress is put on implementation aspects that must be properly dealt with in order to obtain the expected security.

Some formalizations about authenticated key exchange, and the generic model, are of independent interest.

In Advances in Cryptology - Proceedings of CRYPTO '06
(august 20 - 24, 2006, Santa Barbara, California, USA)
C. Dwork Ed. Pages 537-554, LNCS 4117, Springer-Verlag, 2006.
© IACR 2006.

This paper presents the first automatic technique for proving not only protocols but also primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP '06)
(july 9-16, 2006, Venice, Italy)
B. Preneel Ed., Pages 240--251, LNCS 4052, © Springer-Verlag, 2006.

In this paper we introduce very simple deterministic randomness extractors for Diffie-Hellman distributions. More specifically we show that the k most significant bits or the k least significant bits of a random element in a subgroup of Zp* are indistinguishable from a random bit-string of the same length. This allows us to show that under the Decisional Diffie-Hellman assumption we can deterministically derive a uniformly random bit-string from a Diffie-Hellman exchange in the standard model. Then, we show that it can be used in key exchange or encryption scheme to avoid the leftover hash lemma and universal hash functions.

Proceedings of the 2006 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2006)
(april 23-26, 2006, New York, USA)
M. Yung Ed., Pages 427-442, LNCS 3958, Springer-Verlag, 2006.
© IACR 2006.

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 four multi-exponentiations per user. Moreover, the new protocol avoids intricate authentication infrastructures by relying on passwords for authentication.

Proceedings of the 2006 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2006)
(april 23-26, 2006, New York, USA)
M. Yung Ed., Pages 410-426, LNCS 3958, Springer-Verlag, 2006.
© IACR 2006.

Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, formal proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to deriving other keys. Whereas this is a quite simple tool, it is not easy to use in practice -or it is easy to misuse it-. In addition, in many standards, the acronym PRF (Pseudo-Random Functions) is used for several tasks, and namely the randomness extraction. While randomness extractors and pseudo-random functions are a priori distinct tools, we first study whether such an application is correct or not. We thereafter study the case of Zp* where p is a safe-prime and the case of elliptic curve since in IPSec for example, only these two groups are considered. We present very efficient and provable randomness extraction techniques for these groups under the DDH assumption. In the special case of elliptic curves, we present a new technique -the so-called 'Twist-AUgmented' technique- which exploits specific properties of some elliptic curves, and avoids the need of any randomness extractor. We finally compare the efficiency of this method with other solutions.

Proceedings of the 2006 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2006)
(april 23-26, 2006, New York, USA)
M. Yung Ed., Pages 91-104, LNCS 3958, Springer-Verlag, 2006.
© IACR 2006.

ElGamal encryption is the most extensively used alternative to RSA. Easily adaptable to many kinds of cryptographic groups, ElGamal encryption enjoys homomorphic properties while remaining semantically secure providing that the DDH assumption holds on the chosen group. Its practical use, unfortunately, is intricate: plaintexts have to be encoded into group elements before encryption, thereby requiring awkward and ad hoc conversions which strongly limit the number of plaintext bits or may partially destroy homomorphicity. Getting rid of the group encoding (e.g. with a hash function) is known to ruin the standard model security of the system. This paper introduces a new alternative to group encodings and hash functions which remains fully compatible with standard model security properties. Partially homomorphic in customizable ways, our encryptions are comparable to plain ElGamal in efficiency, and boost the encryption ratio from about $13$ for classical parameters to the optimal value of 2.

Proceedings of the 1st ACM Symposium on InformAtion, Computer and Communications Security (ASIACCS '06)
(march 21 - 24, 2006, Taipei, Taiwan)
S. Shieh and S. Jajodia Eds, Pages 35--45, © ACM Press, 2006.

In this paper, we show how to design an efficient, provably secure password-based authenticated key exchange mechanism 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, the 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, combine 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 Advances in Cryptology - Proceedings of ASIACRYPT '05
(december 4 - 8, 2005, Chennai, India)
B. Roy Ed. Pages 566-588, LNCS 3788, Springer-Verlag, 2005.
© IACR 2005.

This paper brings the password-based authenticated key exchange (PAKE) problem closer to practice. It takes into account the presence of firewalls when clients communicate with authentication servers. An authentication server can indeed be seen as two distinct entities, namely a gateway (which is the direct interlocutor of the client) and a back-end server (which is the only one able to check the identity of the client). The goal in this setting is to achieve both transparency and security for the client. And to achieve these goals, the most appropriate choices seem to be to keep the client's password private --even from the back-end server-- and to use threshold-based cryptography. In this paper, we present the Threshold Password-based Authenticated Key Exchange (GTPAKE) system: GTPAKE uses a pair of public/private keys and, unlike traditional threshold-based constructions, shares only the private key among the servers. The system does no require any certification --except during the registration and update of clients' passwords-- since clients do not use the public-key to authenticate to the gateway. Clients only need to have their password in hand. In addition to client security, this paper also presents highly-desirable security properties such as \emph{server password protection} against dishonest gateways and \emph{key privacy} against curious authentication servers.

In Proceedings of the Conference on Applied Cryptography and Network Security (ACNS '05)
(6 -- 10 june 2005, New York, USA)
J. Ioannidis, A. J. Keromytis and M. Yung Eds., Pages 254-268, LNCS 3531, © Springer-Verlag, 2005.

Strong security notions often introduce strong constraints on the construction of cryptographic schemes: semantic security implies probabilistic encryption, while the resistance to existential forgeries requires redundancy in signature schemes. Some paddings have thus been designed in order to provide these minimal requirements to each of them, in order to achieve secure primitives.
A few years ago, Coron et al. suggested the design of a common construction (a universal padding) which one could apply for both encryption and signature. As a consequence, such a padding has to introduce both randomness and redundancy, which does not lead to an optimal encryption nor an optimal signature.
In this paper, we refine this notion of universal padding, in which a part can be either a random string in order to introduce randomness or a zero-constant string in order to introduce some redundancy. This helps us to build, with a unique padding, optimal encryption and optimal signature: first, in the random-permutation model, and then in the random-oracle model. In both cases, we study the concrete sizes of the parameters, for a specific security level: The former achieves an optimal bandwidth.

In Advances in Cryptology - Proceedings of EUROCRYPT '05
(may 22 - 26, 2005, Aarhus, Denmark)
R. Cramer Ed. Pages 542-558, LNCS 3494, Springer-Verlag, 2005.
© IACR 2005.

Traitor tracing schemes are of major importance for secure distribution of digital content. They indeed aim at protecting content providers from colluding users to build pirate decoders. If such a collusion happens, at least one member of the latter collusion will be detected. Several solutions have already been proposed in the literature, but the most important problem to solve remains having a very good ciphertext/plaintext rate. At Eurocrypt '02, Kiayias and Yung proposed the first scheme with such a constant rate, but still not optimal. In this paper, granted bilinear maps, we manage to improve it, and get an 'almost' optimal scheme, since this rate is asymptotically 1. Furthermore, we introduce a new feature, the 'public traceability', which means that the center can delegate the tracing capability to any 'untrusted' person.
This is not the first use of bilinear maps for traitor tracing applications, but among the previous proposals, only one has remained unbroken: we present an attack by producing an anonymous pirate decoder. We furthermore explain the flaw in their security analysis. For our scheme, we provide a complete proof, based on new computational assumptions, related to the bilinear Diffie-Hellman ones, in the standard model.

Proceedings of Financial Cryptography and Data Security 2005
(february 28 - march 3, 2005, Roseau, The Commonwealth Of Dominica)
A. Patrick and M. Yung Eds., Pages 341-356, LNCS 3570, Springer-Verlag, 2005.
© IFCA 2005.

The area of password-based authenticated key exchange protocols has been the subject of a vast amount of work in the last few years due to its practical aspects. In these protocols, the goal is to enable users communicating over an unreliable channel to establish a secure session key even when the secret key that they share is drawn from a small set of values. Despite the attention given to it, it was only recently that this problem has been formally addressed in the three-party setting. In this setting, the users trying to establish a secret session key are only required to share a password with a trusted server and not directly among themselves. In this paper, we introduce a new three-party password-based authenticated key exchange protocol based on the two-party encrypted key exchange of Bellovin and Merritt. Our protocol is reasonably efficient and has a per-user computational cost that is comparable to that of the underlying two-party encrypted key exchange. The proof of security is in the random oracle model and is based on new and apparently stronger variants of the decisional Diffie-Hellman problem which are of independent interest.

Proceedings of the Cryptographers' Track at RSA Conference '05 (CT-RSA '05)
(february 14-18, 2005, San Francisco, California, USA)
A. J. Menezes Ed., Pages 191-208, LNCS 3376, © Springer-Verlag, 2005.

Password-based encrypted key exchange are protocols that are designed to provide pair of users communicating over an unreliable channel with a secure session key even when the secret key or password shared between two users is drawn from a small set of values. In this paper, we present two simple password-based encrypted key exchange protocols based on that of Bellovin and Merritt. While one protocol is more suitable to scenarios in which the password is shared across several servers, the other enjoys better security properties. Both protocols are as efficient, if not better, as any of the existing encrypted key exchange protocols in the literature, and yet they only require a single random oracle instance. The proof of security for both protocols is in the random oracle model and based on hardness of the computational Diffie-Hellman problem. However, some of the techniques that we use are quite different from the usual ones and make use of new variants of the Diffie-Hellman problem, which are of independent interest. We also provide concrete relations between the new variants and the standard Diffie-Hellman problem.

Proceedings of the 2005 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2005)
(january 23-26, 2005, Les Diablerets, Switzerland)
S. Vaudenay Ed., Pages 47-64, LNCS 3386, Springer-Verlag, 2005.
© IACR 2005.

``Grid'' technology enables complex interactions among computational and data resources; however, to be deployed in production computing environments ``Grid'' needs to implement additional security mechanisms. Recent compromises of user and server machines at Grid sites have resulted in a need for secure password-authentication key-exchange technologies. AuthA is an example of such a technology considered for standardization by the IEEE P1363.2 working group. Unfortunately in its current form AuthA does not achieve the notion of forward-secrecy in a provably-secure way nor does it allow a Grid user to log into his account using an un-trusted computer. This paper addresses this void by first proving that AuthA indeed achieves this goal, and then by modifying it in such a way that it is secure against attacks using captured user passwords or server data.

Proceedings of the 2005 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2005)
(january 23-26, 2005, Les Diablerets, Switzerland)
S. Vaudenay Ed., Pages 65-84, LNCS 3386, Springer-Verlag, 2005.
© IACR 2005.

Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only. In this paper, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. To the best of our knowledge, the new protocol is the first provably-secure password-based protocol in the three-party setting.

In Advances in Cryptology - Proceedings of ASIACRYPT '04
(december 5 - 9, 2004, Jeju Island, South Korea)
P. J. Lee Ed. Pages 63-78, LNCS 3329, Springer-Verlag, 2004.
© IACR 2004.

The OAEP construction is already 10 years old and well-established in many practical applications. But after some doubts about its actual security level, four years ago, the first efficient and provably IND-CCA1 secure encryption padding was formally and fully proven to achieve the expected IND-CCA2 security level, when used with any trapdoor permutation. Even if it requires the partial-domain one-wayness of the permutation, for the main application (with the RSA permutation family) this intractability assumption is equivalent to the classical (full-domain) one-wayness, but at the cost of an extra quadratic-time reduction. The security proof which was already not very tight to the RSA problem is thus much worse.
However, the practical optimality of the OAEP construction is two-fold, hence its attractivity: from the efficiency point of view because of two extra hashings only, and from the length point of view since the ciphertext has a minimal bit-length (the encoding of an image by the permutation.) But the bandwidth (or the ratio ciphertext/plaintext) is not optimal because of the randomness (required by the semantic security) and the redundancy (required by the plaintext-awareness, the sole way known to provide efficient CCA2 schemes.)
At last Asiacrypt '03, the latter intuition had been broken by exhibiting the first IND-CCA2 secure encryption schemes without redundancy, and namely without achieving plaintext-awareness, while in the random-oracle model: the OAEP 3-round construction. But this result achieved only similar practical properties as the original OAEP construction: the security relies on the partial-domain one-wayness, and needs a trapdoor permutation, which limits the application to RSA, with still a quite bad reduction.
This paper improves this result: first we show the OAEP 3-round actually relies on the (full-domain) one-wayness of the permutation (which improves the reduction), then we extend the application to a larger class of encryption primitives (including ElGamal, Paillier, etc.) The extended security result is still in the random-oracle model, and in a relaxed CCA2 model (which lies between the original one and the replayable CCA scenario.)

Fourth Conference on Security in Communication Networks '04
(September 8 - 10, 2004, Amalfi, Italy)
C. Blundo and S. Cimato Eds.
Pages 33-47, LNCS 3352, © Springer-Verlag, 2004.

In this paper, we revisit the security notions for public-key encryption, and namely indistinguishability. We indeed achieve the surprising result that no decryption query before receiving the challenge ciphertext can be replaced by queries (whatever the number is) after having received the challenge, and vice-versa. This remark leads to a stricter and more complex hierarchy for security notions in the public-key setting: the (i,j)-IND level, in which an adversary can ask at most i (j resp.) queries before (after resp.) receiving the challenge. Excepted the trivial implications, all the other relations are strict gaps, with no polynomial reduction (under the assumption that IND-CCA secure encryption schemes exist.) Similarly, we define different levels for non-malleability (denoted (i,j)-NM.)

In Advances in Cryptology - Proceedings of CRYPTO '04
(august 15 - 19, 2004, Santa Barbara, California, USA)
M. Franklin Ed. Pages 477-493, LNCS 3152, Springer-Verlag, 2004.
© IACR 2004.

In this paper we revisit one of the most popular password-based key exchange protocols, namely the OKE (for Open Key Exchange) scheme, proposed by Luck in 1997. Our results can be highlighted as follows. First we define a new primitive that we call trapdoor hard-to-invert isomorphisms, and give some candidates. Then we present a generic password-based key exchange construction, that admits a security proof assuming that these objects exist. Finally, we instantiate our general scheme with some concrete examples, such as the Diffie-Hellman function and the RSA function, but more interestingly the modular square root function, which leads to the first scheme with security related to the integer factorization problem. Furthermore, the latter variant is very efficient for one party (the server). Our results hold in the random-oracle model.

Selected Areas in Cryptography '04
(August 9 - 10, 2004, Waterloo, Ontario, Canada)
H. Handschuh and A. Hasan Eds.
Pages 185-200, LNCS 3357, © Springer-Verlag, 2005.

Probabilistic symmetric encryption have already been widely studied, from a theoretical point of view. Nevertheless, many applications require length-preserving encryption, to be patched at a minimal cost to include privacy without modifying the format (e.g. encrypted filesystems). In this paper, we thus consider the security notions for length-preserving, deterministic and symmetric encryption schemes, also termed ciphers: semantic security under lunchtime and challenge-adaptive adversaries. We furthermore provide some relations for this notion between different models of adversaries, and the more classical security notions for ciphers: pseudo-random permutations (PRP) and super pseudo-random permutations (SPRP).

Cryptographic Hardware and Embedded Systems (CHES 2004)
(august 11 - 13, 2004, Boston, Massachusetts, USA)
M. Joye and J.-J. Quisquater Eds. Pages 441-454, LNCS 3156, Springer-Verlag, 2004.

This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all. While exporting all the device's executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity. After describing the machine's instruction-set we introduce a public-key oriented architecture design which relies on a new RSA screening scheme and features a relatively low communication overhead. We propose two protocols that execute and dynamically authenticate arbitrary programs, provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.

Proceedings of the 2004 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2004)
(march 1-4, 2004, Singapore)
F. Bao Ed., Pages 145-158, LNCS 2947, Springer-Verlag, 2004.
© IACR 2004.

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.

In Advances in Cryptology - Proceedings of ASIACRYPT '03
(november 30 - december 4, 2003, Taiwan)
C. L. Laih Ed. Pages 37-54, LNCS 2894, Springer-Verlag, 2003.
© IACR 2003.

At Eurocrypt '02 Cramer and Shoup 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 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. 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.

In Advances in Cryptology - Proceedings of ASIACRYPT '03
(november 30 - december 4, 2003, Taiwan)
C. L. Laih Ed. Pages 1-18, LNCS 2894, Springer-Verlag, 2003.
© IACR 2003.

We propose asymmetric encryption schemes for which all ciphertexts are valid (which means here ``reachable'': the encryption function is not only a probabilistic injection, but also a surjection). We first introduce the Full-Domain Permutation encryption scheme which uses a random permutation. This is the first IND-CCA cryptosystem based on any trapdoor one-way permutation without redundancy, and more interestingly, the bandwidth is optimal: the ciphertext is over k more bits only than the plaintext, where 2^-k is the expected security level. Thereafter, we apply it into the random oracle model by instantiating the random permutation with a Feistel network construction, and thus using OAEP. Unfortunately, the usual 2-round OAEP does not seem to be provably secure, but a 3-round can be proved IND-CCA even without the usual redundancy m||0^k₁, under the partial-domain one-wayness of any trapdoor permutation. Although the bandwidth is not as good as in the random permutation model, absence of redundancy is quite new and interesting: many implementation risks are ruled out.

Proceedings of the 10th ACM Conference on Computer and Communications Security
(october 27 - 31, 2003, Washington DC, USA)
Pages 241-250, © ACM Press, 2003.

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 which actual security was an open problem. We analyze the AuthA key exchange scheme and give the first complete proof of its security. Our analysis shows that the AuthA protocol and its multiple modes of operations are provably secure under the computational Diffie-Hellman intractability assumption, in both the random oracle and ideal-cipher models.

Proceedings of the 5th IFIP-TC6 International Conference on Mobile and Wireless Communications Networks
(october 27 - 29, 2003, Singapore)
K. Al Agha and C. G Omidyar Ed. Pages 59-62. © World Scientific Publishing, 2003.

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.

In Advances in Cryptology - Proceedings of CRYPTO '03
(august 17 - 21, 2003, Santa Barbara, California, USA)
D. Boneh Ed. Pages 226-246, LNCS 2729, Springer-Verlag, 2003.
© IACR 2003.

NTRUEncrypt is unusual among public-key cryptosystems in that, with standard parameters, validly generated ciphertexts can fail to decrypt. This affects the provable security properties of a cryptosystem, as it limits the ability to build a simulator in the random oracle model without knowledge of the private key. We demonstrate attacks which use decryption failures to recover the private key. Such attacks work for all standard parameter sets, and one of them applies to any padding. The appropriate countermeasure is to change the parameter sets and possibly the decryption process so that decryption failures are vanishingly unlikely, and to adopt a padding scheme that prevents an attacker from directly controlling any part of the input to the encryption primitive. We outline one such candidate padding scheme.

Proceedings of ACISP '03
(july 9 - 11, 2003, Wollongong, Australia)
R. Safavi-Naini Ed. Pages 383-401, LNCS 2727, Springer-Verlag, 2003.

A parallel authentication and public-key encryption is introduced and exemplified on joint encryption and signing which compares favorably with sequential Encrypt-then-Sign (EtS) or Sign-then-Encrypt (StE) schemes as far as both efficiency and security are concerned. A security model for signcryption, and thus joint encryption and signing, has been recently defined which considers possible attacks and security goals. Such a scheme is considered secure if the encryption part guarantees indistinguishability and the signature part prevents existential forgeries, for outsider but also insider adversaries. We propose two schemes of parallel signcryption, which are efficient alternative to Commit-then-Sign-and-Encrypt (CtEaS). They are both provably secure in the random oracle model. The first one, called generic parallel encrypt and sign, is secure if the encryption scheme is semantically secure against chosen-ciphertext attacks and the signature scheme prevents existential forgeries against random-message attacks. The second scheme, called optimal parallel encrypt and sign, applies random oracles similar to the OAEP technique in order to achieve security using encryption and signature components with very weak security requirements -- encryption is expected to be one-way under chosen-plaintext attacks while signature needs to be secure against universal forgeries under random-plaintext attack, that is actually the case for both the plain-RSA encryption and signature under the usual RSA assumption. Both proposals are generic in the sense that any suitable encryption and signature schemes (i.e. which simply achieve required security) can be used. Furthermore they allow both parallel encryption and signing, as well as parallel decryption and verification. Properties of parallel encrypt and sign schemes are considered and a new security standard for parallel signcryption is proposed.

Actes de la Première Conférence Internationale RIVF'03
Rencontres en Informatique Vietnam-France (feburary 10-13, Hanoi, Vietnam)
Editions Suger, Paris, pages 105-110.

In this paper, we compare two methods for security proofs - a formal method, and the method by reduction from the complexity theory. A modification of the Otway-Rees protocol is proposed to show out a difference between the two methods: the exchanged key is provably secure in the sense of the BAN logic but it is not when we analyze it by reduction. The difference is due to a limitation of BAN logic, which has not been noticed before, that it does not consider the relation between different ciphertexts. Note that in the original Otway-Rees protocol, under the hypothesis of semantic security of the symmetric encryption scheme, we prove the semantic security of the exchanged key which is a similar result to the one obtained with BAN logic.

Dans cet article, nous comparons deux méthodes de preuve de sécurité : une méthode formelle et la méthode par réduction au sens de la théorie de la complexité. Une modification du protocole Otway-Rees est proposée pour montrer une différence entre ces deux méthodes : la clé échangée est montrée sûre avec la logique BAN, alors qu'elle ne l'ai pas lorsque nous analysons le schéma selon la méthode par réduction. Cette différence montre une limitation de la logique BAN qui n'était pas connue, à savoir qu'elle ne considère pas les relations possibles entre différents chiffrés. Remarquons que dans le protocole original Otway-Rees, sous l'hypothèse de la sécurité sémantique du schéma de chiffrement symétrique, nous prouvons la sécurité sémantique de la clé échangée, qui est un résultat similaire à celui obtenu suite à une analyse par la logique BAN.

In Advances in Cryptology - Proceedings of ASIACRYPT '02
(december 1 - 5, 2002, Queenstown, New-Zealand)
Y. Zheng Ed. Pages 497-514, LNCS 2501, Springer-Verlag, 2002.
© IACR 2002.

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 the ideal-cipher model.

In Advances in Cryptology - Proceedings of CRYPTO '02
(august 18 - 22, 2002, Santa Barbara, California, USA)
M. Yung Ed. Pages 93-110, LNCS 2442, Springer-Verlag, 2002.
© IACR 2002.

Methods from provable security, developed over the last twenty years, have been recently extensively used to support emerging standards. However, the fact that proofs also need time to be validated through public discussion was somehow overlooked. This became clear when Shoup found that there was a gap in the widely believed security proof of OAEP against adaptive chosen-ciphertext attacks. We give more examples, showing that provable security is more subtle than it at first appears. Our examples are in the area of signature schemes: one is related to the security proof of ESIGN and the other two to the security proof of ECDSA. We found that the ESIGN proof does not hold in the usual model of security, but in a more restricted one. Concerning ECDSA, both examples are based on the concept of duplication: one shows how to manufacture ECDSA keys that allow for two distinct messages with identical signatures, a duplicate signature; the other shows that from any message-signature pair, one can derive a second signature of the same message, the malleability. The security proof provided by Brown does not account for our first example while it surprisingly rules out malleability, thus offering a proof of a property, non-malleability, that the actual scheme does not possess.

In Advances in Cryptology - Proceedings of CRYPTO '02
(august 18 - 22, 2002, Santa Barbara, California, USA)
M. Yung Ed. Pages 210-225, LNCS 2442, Springer-Verlag, 2002.
© IACR 2002.

NTRU is an efficient patented public-key cryptosystem proposed in 1996 by Hoffstein, Pipher and Silverman. Although no devastating weakness of NTRU has been found, Jaulmes and Joux presented at Crypto '00 a simple chosen-ciphertext attack against NTRU as originally described. This led Hoffstein and Silverman to propose three encryption padding schemes more or less based on previous work by Fujisaki and Okamoto on strengthening encryption schemes. It was claimed that these three padding schemes made NTRU secure against adaptive chosen-ciphertext attacks (IND-CCA) in the random oracle model. In this paper, we analyze and compare the three NTRU schemes obtained. It turns out that the first one is not even semantically secure (IND-CPA). The second and third ones can be proven IND-CCA-secure in the random oracle model, under however rather unusual assumptions. They indeed require a partial-domain one-wayness of the NTRU one-way function which is likely to be a stronger assumption than the one-wayness of the NTRU one-way function. We propose several modifications to achieve IND-CCA-security in the random oracle model under the original NTRU inversion assumption.

Selected Areas in Cryptography '02
(August 15 - 16, 2002, St John's, Newfoundland, Canada)
H. Heys and K. Nyberg Eds.
Pages 325-338, LNCS 2595, © Springer-Verlag, 2002.

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 Advances in Cryptology - Proceedings of EUROCRYPT '02
(april 28 - may 2, 2002, Amsterdam, Netherlands)
L. Knudsen Ed. Pages 321-336, LNCS 2332, Springer-Verlag, 2002.
© IACR 2002.

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.

Proceedings of the Cryptographers' Track at RSA Conference '02 (CT-RSA '02)
(february 18-22, 2002, San Jose, California, USA)
B. Preneel Ed., Pages 263-276, LNCS 2271, © Springer-Verlag, 2002.

This paper proposes an efficient and provably secure transform to encrypt a message with any asymmetric one-way cryptosystem. The resulting scheme achieves adaptive chosen-ciphertext security in the random oracle model.
Compared to previous known generic constructions (Bellare, Rogaway, Fujisaki, Okamoto, and Pointcheval), our embedding reduces the encryption size and/or speeds up the decryption process. It applies to numerous cryptosystems, including (to name a few) ElGamal, RSA, Okamoto-Uchiyama and Paillier systems.

Proceedings of the 2002 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2002)
(12-14 february 2002, Paris, France)
D. Naccache and P. Paillier Eds., Pages 17-33, LNCS 2274, © Springer-Verlag, 2002.

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, Gem-1 and Gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (CCA) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

In Advances in Cryptology - Proceedings of ASIACRYPT '01
(december 9 - 13, 2001, Gold Coast, Australia)
C. Boyd Ed. Pages 566-582, LNCS 2248, Springer-Verlag, 2001.
© IACR 2001.

We consider a novel security requirement of encryption schemes that we call ``key-privacy'' or ``anonymity''. It asks that an eavesdropper in possession of a ciphertext not be able to tell which specific key, out of a set of known public keys, is the one under which the ciphertext was created, meaning the receiver is anonymous from the point of view of the adversary. We investigate the anonymity of known encryption schemes. We prove that the El Gamal scheme provides anonymity under chosen-plaintext attack assuming the Decision Diffie-Hellman problem is hard and that the Cramer-Shoup scheme provides anonymity under chosen-ciphertext attack under the same assumption. We also consider anonymity for trapdoor permutations. Known attacks indicate that the RSA trapdoor permutation is not anonymous and neither are the standard encryption schemes based on it. We provide a variant of RSA-OAEP that provides anonymity in the random oracle model assuming RSA is one-way. We also give constructions of anonymous trapdoor permutations, assuming RSA is one-way, which yield anonymous encryption schemes in the standard model.

In Advances in Cryptology - Proceedings of ASIACRYPT '01
(december 9 - 13, 2001, Gold Coast, Australia)
C. Boyd Ed. Pages 290-309, LNCS 2248, Springer-Verlag, 2001.
© IACR 2001.

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 litterature and prove its security.

In Advances in Cryptology - Proceedings of ASIACRYPT '01
(december 9 - 13, 2001, Gold Coast, Australia)
C. Boyd Ed. Pages 351-368, LNCS 2248, Springer-Verlag, 2001.
© IACR 2001.

Semantic security against chosen-ciphertext attacks (IND-CCA) is widely believed as the correct security level for public-key encryption scheme. On the other hand, it is often dangerous to give to only one people the power of decryption. Therefore, threshold cryptosystems aimed at distributing the decryption ability. However, only two efficient such schemes have been proposed so far for achieving IND-CCA. Both are El Gamal-like schemes and thus are based on the same intractability assumption, namely the Decisional Diffie-Hellman problem.
In this article we rehabilitate the twin-encryption paradigm proposed by Naor and Yung to present generic conversions from a large family of (threshold) IND-CPA scheme into a (threshold) IND-CCA one in the random oracle model. An efficient instantiation is also proposed, which is based on the Paillier cryptosystem. This new construction provides the first example of threshold cryptosystem secure against chosen-ciphertext attacks based on the factorization problem. Moreover, this construction provides a scheme where the ``homomorphic properties'' of the original scheme still hold. This is rather cumbersome because homomorphic cryptosystems are known to be malleable and therefore not to be CCA secure. However, we do not build a ``homomorphic cryptosystem'', but just keep the homomorphic properties.

Proceedings of the 4th International Conference on Information Security and Cryptology (ICISC '01)
(december 6 - 7, 2001, Seoul, South Korea)
K. Kim Ed., Pages 1-17, LNCS 2288, © Springer-Verlag, 2002.

Since the appearance of public-key cryptography in Diffie-Hellman seminal paper, many schemes have been proposed, but many have been broken. Indeed, for many people, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken.
A much more convincing line of research has tried to provide ``provable'' security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can ``efficiently'' solve the underlying problem. Unfortunately, very few practical schemes can be proven in this so-called ``standard model'' because such a security level rarely meets with efficiency. Moreover, for a long time the security proofs have only been performed in an asymptotic framework, which provides some confidence in the scheme but for very huge parameters only, and thus for unpractical schemes.
A recent trend consists in providing very efficient reductions, with a practical meaning: with usual parameters (such as 1024-bit RSA moduli) the computational cost of any attack is actually 2<sup>72</sup>, given the state of the art about classical problems (e.g. integer factoring).
In this paper, we focus on practical schemes together with their ``reductionist'' security proofs. We cover the two main goals that public-key cryptography is devoted to solve: authentication with digital signatures and confidentiality with public-key encryption schemes.

Proceedings of the 8th ACM Conference on Computer and Communications Security
(november 5 - 8, 2001, Philadelphia, Pennsylvania, USA)
Pages 20-27, © ACM Press, 2001.

This paper introduces a simple alternative to the hash-and-sign paradigm, from the security point of view but for signing short messages, called twinning. A twin signature is obtained by signing twice a short message by a signature scheme. Analysis of the concept in different settings yields the following results:

• We prove that no generic algorithm can efficiently forge a twin DSA signature. Although generic algorithms offer a less stringent form of security than computational reductions in the standard model, such successful proofs still produce positive evidence in favor of the correctness of the new paradigm.
• We prove in standard model an equivalence between the hardness of producing existential forgeries (even under adaptively chosen message attacks) of a twin version of a signature scheme proposed by Gennaro, Halevi and Rabin and the Flexible RSA Problem.

We consequently regard twinning as an interesting alternative to hash functions for eradicating existential forgery in signature schemes.

Proceedings of the 8th ACM Conference on Computer and Communications Security
(november 5 - 8, 2001, Philadelphia, Pennsylvania, USA)
Pages 255-264, © ACM Press, 2001.

Group Diffie-Hellman protocols for Authenticated Key Exchange (AKE) are designed to provide a pool of players with a shared secret key which may latter 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.

In Advances in Cryptology - Proceedings of CRYPTO '01
(august 19 - 23, 2001, Santa Barbara, California, USA)
J. Kilian Ed., Pages 260-274, LNCS 2139, Springer-Verlag, 2001.
© IACR 2001.

Very recently Victor Shoup noted that there is a gap in the widely believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation.
This paper establishes another result on the security of OAEP, proving that OAEP achieves semantical security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to the (full-domain) one-wayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, even if the reduction is not tight.

Proceedings of the 20th ACM Symposium on Principles of Distributed Computing
(august 26 - 29, 2001, Newport, Rhode Island)
N. Shavit Ed., Pages 274-283, © ACM Press, 2001.

The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.

Proceedings of Financial Cryptography 2001
(february 19 - 22, 2001, Grand Cayman Island, British West Indies)
P. Syverson Ed., Pages 319-338, LNCS 2339, Springer-Verlag, 2001.
© IFCA 2002.

Blind signatures are the central cryptographic component of digital cash schemes. In this paper, we investigate the security of the first such scheme proposed, namely Chaum's RSA-based blind signature scheme, in the random-oracle model. This leads us to formulate and investigate a new class of RSA related computational problems which we call the ``one-more-RSA-inversion'' problems. Our main result is that two problems in this class which we call the chosen-target and known-target inversion problems, have polynomially-equivalent computational complexity. This leads to a proof of security for Chaum's scheme in the random oracle model based on the assumed hardness of either of these problems.

Proceedings of Financial Cryptography 2001
(february 19 - 22, 2001, Grand Cayman Island, British West Indies)
P. Syverson Ed., Pages 178-195, LNCS 2339, Springer-Verlag, 2001.
© IFCA 2002.

We propose methods for mutual authentication and key exchange. Our methods are well suited for applications with strict power consumption restrictions, such as wireless medical implants and contactless smart cards. We prove the security of our schemes based on the discrete log gap problem.

Proceedings of Financial Cryptography 2001
(february 19 - 22, 2001, Grand Cayman Island, British West Indies)
P. Syverson Ed., Pages 305-318, LNCS 2339, Springer-Verlag, 2001.
© IFCA 2002.

In many real-life situations, massive quantities of signatures have to be issued on cheap passive supports (e.g. paper-based) such as bank-notes, badges, ID cards, driving licenses or passports (hereafter IDs); while large-scale ID replacements are costly and prohibitive, one may reasonably assume that the updating of verification equipment (e.g. off-line border checkpoints or mobile patrol units) is exceptionally acceptable.
In such a context, an attacker using coercive means (e.g. kidnapping) can force the system authorities to reveal the infrastructure's secret signature keys and start issuing signatures that are indistinguishable from those issued by the authority.
The solution presented in this paper withstands such attacks up to a certain point: after the theft, the authority restricts the verification criteria (by an exceptional verification equipment update) in such a way that the genuine signatures issued before the attack become easily distinguishable from the fresher signatures issued by the attacker. Needless to say, we assume that at any point in time the verification algorithm is entirely known to the attacker.

In Proceedings of the Cryptographers' Track at RSA Conference '01 (CT-RSA '01)
(april 8-12, 2001, San Francisco, California, USA)
D. Naccache Ed., Pages 159-175, LNCS 2020, © Springer-Verlag, 2001.

Seven years after the optimal asymmetric encryption padding (OAEP) which makes chosen-ciphertext secure encryption scheme from any trapdoor one-way permutation (but whose unique application is RSA), this paper presents REACT, a new conversion which applies to any weakly secure cryptosystem, in the random oracle model: it is optimal from both the computational and the security points of view. Indeed, the overload is negligible, since it just consists of two more hashings for both encryption and decryption, and the reduction is very tight. Furthermore, advantages of REACT beyond OAEP are numerous:

• it is more general since it applies to any partially trapdoor one-way function (a.k.a. weakly secure public-key encryption scheme) and therefore provides security relative to RSA but also to the Diffie-Hellman problem or the factorization;
• it is possible to integrate symmetric encryption (block and stream ciphers) to reach very high speed rates;
• it provides a key distribution with session key encryption, whose overall scheme achieves chosen-ciphertext security even with weakly secure symmetric scheme.

Therefore, REACT could become a new alternative to OAEP, and even reach security relative to factorization, while allowing symmetric integration.

In Proceedings of the Cryptographers' Track at RSA Conference '01 (CT-RSA '01)
(april 8-12, 2001, San Francisco, California, USA)
D. Naccache Ed., Pages 110-125, LNCS 2020, © Springer-Verlag, 2001.

We study lightweight and secure gambling methods, and propose a general framework that is secure against various ``disconnection'' and ``payment refusal'' attacks. Our method can be employed for single- and multi-player games in which players are independent, such as slot machines, roulette and blackjack. We focus on ``open card'' games, i.e., games where the casino's best game strategy is not affected by knowledge of the randomness used by the players (once both or all parties have committed to their random strings.) Our method allows players as well as casinos to ascertain that the game is played exactly according to the rules agreed on, including that the various random events in fact are random. Given the low computational costs involved, we can implement the games on cellular phones, without concerns of excessive computation or power consumption.

Proceedings of the 2001 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2001)
(13-15 february 2001, Cheju Island, South Korea)
K. Kim Ed., Pages 104-118, LNCS 1992, © Springer-Verlag, 2001.

This paper introduces a novel class of computational problems, the gap problems, which can be considered as a dual to the class of the decision problems. We show the relationship among inverting problems, decision problems and gap problems. These problems find a nice and rich practical instantiation with the Diffie-Hellman problems.
Then, we see how the gap problems find natural applications in cryptography, namely for proving the security of very efficient schemes, but also for solving a more than 10-year old open security problem: the Chaum's undeniable signature.

Fourth Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography
(21-24 november 2000, Tokyo, Japan).

Since the appearance of public-key cryptography in the seminal Diffie-Hellman paper, many schemes have been proposed, but many have been broken. Indeed, for many people, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken.
A much more convincing line of research has tried to provide ``provable'' security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can efficiently solve the underlying problem.
Unfortunately, very few practical schemes can be proven in this so-called ``standard model'' because such a security level rarely meets with efficiency. A convenient way to achieve some kind of validation of efficient schemes has been to identify some concrete cryptographic objects with ideal random ones: hash functions are considered as behaving like random functions, in the so-called ``random oracle model'', and groups are used as black-box groups, in which one has to ask for additions to get new elements, in the so-called ``generic model''.
In this paper we present some generic designs for asymmetric encryption with provable security in the random oracle model.

Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP '00)
(july 9-15, 2000, Geneva, Switzerland)
U. Montanari, J. D. P. Rolim and E. Welzl Eds., Pages 499-511, LNCS 1853, © Springer-Verlag, 2000.

In this paper we introduce two notions of security: multi-user indistinguishability and multi-user non-malleability. We believe that they encompass the correct requirements for public key encryption schemes in the context of multicast communications. A precise and non-trivial analysis prove that they are equivalent to the former single-user notions, provided the number of participants is polynomial. We also introduce a new definition for non-malleability which is simpler than those currently in use. We believe that our results are of practical significance: especially they support the use of PKCS#1 v.2 based on OAEP in the multicast setting.

In Advances in Cryptology - Proceedings of EUROCRYPT '00
(may 14-18, 2000, Brugge, Belgium)
B. Preneel Ed., Pages 139-155, LNCS 1807, Springer-Verlag, 2000.
© IACR 2000.

Password-based protocols for authenticated key exchange (AKE) are designed to work despite the use of passwords drawn from a space so small that an adversary might well enumerate, off line, all possible passwords.
While several such protocols have been suggested, the underlying theory has been lagging. We begin by defining a model for this problem, one rich enough to deal with password guessing, forward secrecy, server compromise, and loss of session keys. The one model can be used to define various goals.
We take AKE (with implicit authentication) as the basic goal, and we give definitions for it, and for entity-authentication goals as well. Then we prove correctness for the idea at the center of the Encrypted Key-Exchange (EKE) protocol of Bellovin and Merritt: we prove security, in an ideal-cipher model, of the two-flow protocol at the core of EKE.

Proceedings of Financial Cryptography 2000
(february 21 - 24, 2000, Anguilla, British West Indies)
Y. Frankel Ed., Pages 259-275, LNCS 1962, © Springer-Verlag, 2001.

For the two last decades, people have tried to provide practical electronic cash schemes, with more or less success. Indeed, the most secure ones generally suffer from inefficiency, largely due to the use of restrictive blind signatures, on the other hand efficient schemes often suffer from serious security drawbacks. In this paper, we propose both a new tool providing scalable anonymity at a low cost, and a new Internet business: ``Anonymity Providers''.
Those ``Anonymity Providers'' certify re-encrypted data after having been convinced of the validity of the content, but without knowing anything about this latter. It is a very useful third party in many applications (e.g. for revocable anonymous electronic cash, where a coin would be a certified encryption of the user's identity, such that a Revocation Center, and only it, can recover this identity, if needed).
With this new tool, each user can get the required anonymity level, depending on the available time, computation and/or money amounts. Furthermore, the ``Anonymity Provider'' may be a new type of business over the Internet, profitable for everybody:

• from the provider's point of view as he can charge the service;
• from the user's point of view as he can obtain a high level of anonymity at low computational cost. And a user who does not require anonymity has no extra computation to perform.

This technique is quite efficient because of its ``optimistic'' orientation: in case of honest use, everything is very efficient. Some slightly more heavy processes have to be performed in case of fraud detection, but with overwhelming tracing success.

Proceedings of the 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000)
(18-20 january 2000, Melbourne, Australia)
H. Imai and Y. Zheng Eds.
Pages 113-128, LNCS 1751, © Springer-Verlag, 2000.

For the two last decades, electronic authentication has been an important topic. The first applications were digital signatures to mimic handwritten signatures for digital documents. Then, Chaum wanted to create an electronic version of money, with similar properties, namely bank certification and users' anonymity. Therefore, he proposed the concept of blind signatures.
For all those problems, and furthermore for online authentication, zero-knowledge proofs of knowledge became a very powerful tool. Nevertheless, high computational load is often the drawback of a high security level. More recently, witness-indistinguishability has been found to be a better property that can conjugate security together with efficiency.
This paper studies the discrete logarithm problem with a composite modulus and namely its witness-indistinguishability. Then we offer new authentications more secure than factorization and furthermore very efficient from the prover point of view. Moreover, we significantly improve the reduction cost in the security proofs of Girault's variants of the Schnorr schemes which validates practical sizes for security parameters.
Finally, thanks to the witness-indistinguishability of the basic protocol, we can derive a blind signature scheme with security related to factorization.

Proceedings of the 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000)
(18-20 january 2000, Melbourne, Australia)
H. Imai and Y. Zheng Eds.
Pages 276-292, LNCS 1751, © Springer-Verlag, 2000.

A number of signature schemes and standards have been recently designed, based on the Discrete Logarithm problem. In this paper we conduct design validation of such schemes while trying to minimize the use of ideal hash functions. We consider several Discrete Logarithm (DSA-like) signatures abstracted as generic schemes.
We show that the following holds: ``if the schemes can be broken by an existential forgery using an adaptively chosen-message attack then either the discrete logarithm problem can be solved, or some hash function can be distinguished from an ideal one, or multi-collisions can be found.'' Thus, for these signature schemes, either they are equivalent to the discrete logarithm problem or there is an attack that takes advantage of properties which are not desired (or expected) in strong practical hash functions (SHA-1 or whichever high quality cryptographic hash function is used). What is interesting is that the schemes we discuss include KCDSA and slight variations of DSA.
Further, since our schemes coincide with (or are extremely close to) their standard counterparts they benefit from their desired properties: efficiency of computation/space, employment of certain mathematical operations and wide applicability to various algebraic structures. We feel that adding variants with strong validation of security is important to this family of signature schemes since, as we have experienced in the recent past, lack of such validation has led to attacks on standard schemes, years after their introduction. In addition, schemes with formal validation which is made public, may ease global standardization since they neutralize much of the suspicions regarding potential knowledge gaps and unfair advantages gained by the scheme designer's country (e.g. the NSA being the designers of DSA).

Proceedings of the 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000)
(18-20 january 2000, Melbourne, Australia)
H. Imai and Y. Zheng Eds.
Pages 129-146, LNCS 1751, © Springer-Verlag, 2000.

For two years, public key encryption has become an essential topic in cryptography, namely with security against chosen-ciphertext attacks. This paper presents a generic technique to make a highly secure cryptosystem from any partially trapdoor one-way function, in the random oracle model. More concretely, any suitable problem providing a one-way cryptosystem can be efficiently derived into a chosen-ciphertext secure encryption scheme. Indeed, the overhead only consists of two hashing and a XOR. As application, we provide the most efficient El Gamal encryption variant, therefore secure relative to the computational Diffie-Hellman problem. Furthermore, we present the first scheme whose security is relative to the factorization of large integers, with a perfect reduction (factorization is performed within the same time and with identical probability of success as the security break).

In Advances in Cryptology - Proceedings of ASIACRYPT '99
(november 14 - 18, 1999, Singapore)
K. Y. Lam, E. Okamoto and C. Xing Eds.
Pages 165-179, LNCS 1716, © Springer-Verlag, 1999.

This paper proposes two new public-key cryptosystems semantically secure against adaptive chosen-ciphertext attacks. Inspired from a recently discovered trapdoor technique based on composite-degree residues, our converted encryption schemes are proven, in the random oracle model, secure against active adversaries (IND-CCA2) under the assumptions that the Decision Composite Residuosity and Decision Partial Discrete Logarithms problems are intractable. We make use of specific techniques that differ from Bellare-Rogaway or Fujisaki-Okamoto conversion methods. Our second scheme is specifically designed to be efficient for decryption and could provide an elegant alternative to OAEP.

In Advances in Cryptology - Proceedings of EUROCRYPT '99
(may 2 - 6, 1999, Prague, Czech Republic)
J. Stern Ed.
Pages 239-254, LNCS 1592, Springer-Verlag, 1999.
© IACR 1999.

Since the Diffie-Hellman paper, asymmetric encryption has been a very important topic, and furthermore ever well studied. However, between the efficiency of RSA and the security of some less efficient schemes, no trade-off has ever been provided.
In this paper, we propose better than a trade-off: indeed, we first present a new problem, derived from the RSA assumption, the ``Dependent-RSA Problem''. A careful study of its difficulty is performed and some variants are proposed, namely the ``Dependent-RSA Problem''.
They are next used to provide new encryption schemes which are both secure and efficient. More precisely, the main scheme is proven semantically secure in the standard model. Then, two variants are derived with improved security properties, namely against adaptive chosen-ciphertext attacks, in the random oracle model. Furthermore, all those schemes are more or less as efficient as the original RSA encryption scheme and reach semantic security.

In Advances in Cryptology - Proceedings of CRYPTO '98
(august 23 - 27, 1998, Santa Barbara, California, USA)
H. Krawczyk Ed., Pages 26-45, LNCS 1462, © Springer-Verlag, 1998.

We compare the relative strengths of popular notions of security for public-key encryption schemes. We consider the goals of privacy and non-malleability, each under chosen-plaintext attack and two kinds of chosen-ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at all). We similarly treat plaintext awareness, a notion of security in the random-oracle model. An additional contribution of this paper is a new definition of non-malleability which we believe is simpler than the previous one.

Selected Areas in Cryptography '98
(August 17 - 18, 1998, Kingston, Ontario, Canada)
S. Tavares and H. Meijer Eds.
Pages 72-80, LNCS 1556, © Springer-Verlag, 1999.

In this paper, we present a simple method for generating random-based signatures when random number generators are either unavailable or of suspected quality (malicious or accidental).
By opposition to all past state-machine models, we assume that the signer is a memoryless automaton that starts from some internal state, receives a message, outputs its signature and returns precisely to the same initial state; therefore, the new technique formally converts randomised signatures into deterministic ones.
Finally, we show how to translate the random oracle concept required in security proofs into a realistic set of tamper-resistance assumptions.

In Advances in Cryptology - Proceedings of EUROCRYPT '98
(june 1 - 4, 1998, Espoo, Finland)
K. Nyberg Ed.
Pages 391-405, LNCS 1403, © Springer-Verlag, 1998.

Provable security is a very nice property for cryptographic protocols. Unfortunately, in many cases, this is at the cost of a considerable loss in terms of efficiency. More recently, a new approach to achieve some kind of provable security was explored using the so-called ``random oracle model''.
Last year, Pointcheval and Stern studied the security of blind signatures in this model. They first defined appropriate notions of security for electronic cash purpose, then, they proposed the first efficient and provably secure schemes. Unfortunately, even if their proof prevents a user from spending more coins than he had withdrawn, this is only if the number of withdrawn coins is poly-logarithmically bounded.
In this paper, we propose a generic transformation of their schemes which extends the security even after polynomially many withdrawals. Moreover, this transformation keeps the scheme efficient and so can be used in a secure and efficient anonymous off-line electronic cash system.

Proceedings of Financial Cryptography 98
(february 23 - 25, 1998, Anguilla, British West Indies)
R. Hirschfeld Ed., Pages 28-41, LNCS 1465, © Springer-Verlag, 1998.

Regarding von Solms and Naccache's observations, the construction of a practical and secure e-money system supposes controlling its privacy level. Furthermore, when the system benefits from a widely connected communication network, tuning precisely this control for achieving efficiency without endangering security is a hard task. In order to solve this specific problem, we propose an e-cash scheme based on the usage of provably secure primitives, where trustee quorum are in charge of privacy control. Moreover, Trustees remain off-line during e-coin life to reduce the communication flow and improve the resulting scheme performance.

Proceedings of the 4th ACM Conference on Computer and Communications Security
(april 2 - 4, 1997, Zurich, Switzerland)
Pages 92-99, © ACM Press, 1997.

In this paper, we present new blind signature schemes based on the factorization problem. They are the first blind signature schemes proved secure relatively to factorization. By security, we mean that no ``one-more forgery'' is possible even under a parallel attack.
In other terms, a user that receives k electronic coins cannot manufacture k+1. Those security definitions have been introduced by Pointcheval and Stern for use in electronic cash. In fact, blind signatures were defined with this aim and it is still their most important application, together with anonymous voting. In the following, we will present an efficient reduction of an attack to a factorization algorithm in the random oracle model.

Advances in Cryptology - Proceedings of ASIACRYPT '96
(november 3 - 7, 1996, KyongJu, S. Korea)
K. Kim and T. Matsumoto Eds.
Pages 252-265, LNCS 1163, © Springer-Verlag, 1996

In this paper, we give a provably secure design for blind signatures, the most important ingredient for anonymity in off-line electronic cash systems. Previous examples of blind signature schemes were constructed from traditional signature schemes with only the additional proof of blindness.
The design of some of the underlying signature schemes can be validated by a proof in the so-called random oracle model, but the security of the original signature scheme does not, by itself, imply the security of the blind version.
In this paper, we first propose a definition of security for blind signatures, with application to electronic cash. Next, we focus on a specific example which can be successfully transformed in a provably secure blind signature scheme.

Advances in Cryptology - Proceedings of EUROCRYPT '96
(may 12 - 16, 1996, Zaragoza, Spain)
U. Maurer, Ed.
Pages 387-398, LNCS 1070, © Springer-Verlag, 1996.

In this paper, we address the question of providing security proofs for signature schemes in the so-called random oracle model. In particular, we establish the generality of this technique against adaptively chosen message attacks.
Our main application achieves such a security proof for a slight variant of the El Gamal signature scheme where committed values are hashed together with the message.
This is a rather surprising result since the original El Gamal is, as RSA, subject to existential forgery.

Advances in Cryptology - Proceedings of EUROCRYPT '95
(may 21 - 25, 1995, Saint-Malo, France)
L.C. Guillou and J.-J. Quisquater, Eds.
Pages 319-328, LNCS 921, © Springer-Verlag, 1995.

Identification is a useful cryptographic tool. Since the zero-knowledge theory appeared, several interactive identification schemes have been proposed (in particular Fiat-Shamir and its variants, Schnorr). These identifications are based on number theoretical problems. More recently, new schemes appeared with the particularity that they are more efficient from the computational point of view and their security is based on NP-complete problems: PKP (Permuted Kernels Problem), SD (Syndrome Decoding) and CLE (Constrained Linear Equations).
We present a new NP-complete linear problem which comes from learning machines: the Perceptrons Problem.
Next, we provide some zero-knowledge interactive identification protocols based on this problem, with an evaluation of their security. Eventually, those protocols are well suited for smart card applications.

IAVoSS Workshop On Trustworthy Elections (WOTE 2006)
(29-30 june 2006, Robinson College, Cambridge, United Kingdom).

In this paper, we study the problem of simultaneously achieving several security properties, for voting schemes, without non-standard assumptions. This paper is a work in progress. More specifically, we focus on the universal verifiability of the computation of the tally, on the unconditional privacy/anonymity of the votes, and on the receipt-freeness properties. More precisely, under usual assumptions and efficiency requirements, we show that we cannot achieve:

• universal verifiability of the tally (UV) and unconditional privacy of the votes (UP) simultaneously, unless all the registered voters actually vote;
• universal verifiability of the tally (UV) and receipt-freeness (RF), unless the voting process involves interactions between several voters (and possibly the voting authority).

Second NESSIE Workshop
(12-13 september 2001, Egham, UK).

The last few months, several new results appeared about the OAEP construction, and namely the RSA-OAEP cryptosystem. Whereas OAEP was believed to provide the highest security level (IND-CCA), with an efficient exact security level, the effective security result had been showed to be incomplete. Nevertheless, the particular instantiation with RSA (which is anyway almost the sole application) had been eventually proven secure, but the security reduction appears to be quite inefficient. Therefore, with respect to the provable security result, RSA-OAEP with a 1024-bit modulus just provides a 2⁴⁰ security level.
Several alternatives have been recently proposed, but most of them face the same problem with a quadratic time security reduction. Excepted the recent generic conversion, called REACT, which admits a linear time reduction. Consequently, RSA-REACT appears to be the best alternative to RSA-OAEP, granted the high security level, even with real world parameters. RSA--REACT with a 1024-bit modulus indeed guarantees a 2⁸⁰ security level (IND-CCA under the RSA assumption).
Furthermore, the full construction is already proven secure when integrating symmetric encryption, which guarantees the security of the overall communication.

Combinatorial and Computational Mathematics: Present and Future
(february 15 - 17, 2000, Pohang, South Korea)
S. P. Hong, J. H. Kwak, K. H. Kim and F. W. Roush Eds.
© World Scientific Publishing, 2001.

For a long time, cryptology had been a mystic art more than a science, solving the confidentiality concerns with secret and private techniques. Automatic machines, electronic and namely computers modified the environment and the basic requirements. The main difference was the need of public mechanisms to allow large-scale communications with just a small secret shared between the interlocutors, but that furthermore resist against adversaries with more powerful computers. Unfortunately, the security remained heuristic: with a permanent fight between designers (the cryptographers) and breakers (the cryptanalysts).
In 1976, Diffie and Hellman claimed the possibility of achieving confidentiality between two people without any common secret information. However, they needed quite new objects: (trapdoor) one-way functions. Hopefully, mathematics, with algorithmic number theory, have been realized to provide such objects. A new direction in cryptography was under investigations: asymmetric cryptography and provable security.
In this paper we review the main problems that cryptography tries to solve, and how it achieves these goals thanks to the algorithmic number theory. After a brief history of the ancient and conventional cryptography, we review the Diffie-Hellman's suggestion with the apparent paradox. Then, we survey the solutions based on the integer factorization or the discrete logarithm, two problems that nobody knows how to efficiently solve.

Second AES Candidate Conference
(march 22-23, 1999, Rome, Italy).

This document reports the activities of the AES working group organized at the École Normale Supérieure. Several candidates are evaluated. In particular we outline some weaknesses in the designs of some candidates. We mainly discuss selection criteria between the candidates, and make case-by-case comments. We finally recommend the selection of Mars, RC6, Serpent, ... and DFC. As the report is being finalized, we also added some new preliminary cryptanalysis on RC6 and Crypton in the Appendix which are not considered in the main body of the report.

Second AES Candidate Conference
(march 22-23, 1999, Rome, Italy).

This document reports an update of DFC. We answer to a question about the rationale for the CP Confusion Permutation. We give new implementation results for DFC. In particular we present an impressively fast implementation which takes 323 cycles on Compaq's 21164 Alpha microprocessor. On the new 21264 we expect to reach software encryption rates over 500 Mbps. We also discuss making DFC scalable to allow the block size or the number of rounds, in the encryption or key schedule, to be varied. Finally, we describe how DFC may be subject to slight change in its key schedule in order to fix a minor drawback noticed by Coppersmith.

Livre des résumés - EUROCODE '94
(october 1994, La Bussière sur Ouche, France)
P. Charpin, Ed.
Pages 183-193, © INRIA, 1994.

Study of the Perceptrons Problem, a new linear NP-complete problem which comes from neural networks and learning machines. Application of the Permuted Perceptrons Problem to cryptography.

Cryptology ePrint Archive: Report 2006/069
February 23rd 2006, revised June 11th 2006. eprint.iacr.org.

This paper presents the first automatic technique for proving not only protocols but also primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Cryptology ePrint Archive: Report 2005/061
March 19th 2005. eprint.iacr.org.

Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to derive other keys.

This paper first deals with the protocol Sigma_0, in which the key derivation phase is (deliberately) omitted, and security inaccuracies in the analysis and design of the Internet Key Exchange (IKE version 1) protocol, corrected in IKEv2. They do not endanger the practical use of IKEv1, since the security could be proved, at least, in the random oracle model. However, in the standard model, there is not yet any formal global security proof, but just separated analyses which do not fit together well. The first simplification is common in the theoretical security analysis of several key exchange protocols, whereas the key derivation phase is a crucial step for theoretical reasons, but also practical purpose, and requires careful analysis. The second problem is a gap between the recent theoretical analysis of HMAC as a good randomness extractor (functions keyed with public but random elements) and its practical use in IKEv1 (the key may not be totally random, because of the lack of clear authentication of the nonces). Since the latter problem comes from the probabilistic property of this extractor, we thereafter review some deterministic randomness extractors.

As a second contribution, we suggest the 'Twist-AUgmented' technique, a new extraction method quite well-suited for Diffie-Hellman-like scenarios. It exploits specific properties of some elliptic curves. We then discuss the practicality of this new method.

Cryptology ePrint Archive: Report 2002/192
December 19th 2002. eprint.iacr.org.

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 schemes that have been adopted by the IEEE P1363 Standard working group on password-based authenticated key-exchange methods. We analyze the AuthA key exchange scheme and give the first complete proof of its security. Our analysis shows that the AuthA protocol and its multiple modes of operations are provably secure under the computational Diffie-Hellman intractability assumption. Our result also suggests a new mode allowing AuthA to run on low-power computing devices such as smart-cards or pocket PCs.

Thèse d'habilitation à diriger des recherches, université Paris VII, 2002.

Confidentiality is certainly the oldest security concern when communicating on a public channel. The concept of asymmetric cryptography introduced by Diffie and Hellman in 1976 provided a new direction for encryption, with new features and new kinds of security analyses. For instance, with the public key of the recipient, anybody can secretly send a message, without either having to ever met in person before, or even prior knowledge of any common secret information. This allows confidentiality in many more domains, but also increases the threats since the public key provides some information to the adversary, which rules out perfect and unconditional secrecy. We are thus led to consider computational security, under some specific algorithmic assumptions.
A cryptographic scheme based on an algorithmic assumption such as integer factoring provides no guarantee that one actually has to factor in order to break the scheme. Several famous incorrect constructions illustrate this fact. In this thesis, we lay out foundations for provable security, and more precisely for asymmetric encryption. This helps us to design concrete cryptosystems meaningful in practice whose security relies on a specific algorithmic assumption only, and no other heuristic. To reach this aim, one precisely defines the security notions to be guaranteed, considering both the goals an adversary would like to achieve and the means it could provide. Then, one compares the difficulty to defeat security relative to the algorithmic assumption. Complexity theory may help through the notion of reduction: a program, that uses an algorithm against the former problem as a sub-program in order to solve the latter. People have quickly realized how much such reductions could help for ruling out flawed designs for cryptographic schemes. They recently highlighted the importance of their efficiency. Indeed, the more efficient is the reduction, the tighter is the relation between both the attack and the algorithm problem. The size of the parameters to be used in practice then depends on this more or less tight link for achieving a specific security level. Several papers are appended to this thesis which illustrate all the above steps for provable security and its practical impacts.

La confidentialité des messages est certainement le plus ancien des besoins en sécurité de l'information. Le concept de cryptographie asymétrique, proposé en 1976 par Diffie et Hellman, a provoqué un important bouleversement, aussi bien au niveau des fonctionnalités que de l'analyse de sécurité. Par exemple, avec la clé publique de son interlocuteur, il est possible de lui envoyer un message confidentiel, sans jamais avoir précédemment été en contact avec lui ; et donc sans partager de convention secrète avec ce dernier. Les applications potentielles sont alors plus vastes, mais les risques aussi plus importants. En effet, la clé publique fournit de l'information à l'attaquant, ce qui exclut notamment la confidentialité parfaite, ou inconditionnelle. On s'est alors intéressé à la confidentialité calculatoire, sous des hypothèses algorithmiques précises.
Décrire un schéma cryptographique basé sur une hypothèse algorithmique, telle que la difficulté de la factorisation, ne garantit néanmoins pas qu'il soit nécessaire de contredire cette dernière pour ``casser'' le système. Les contre-exemples sont d'ailleurs très nombreux, à cause de mauvaises constructions. Le but de ce mémoire est d'établir les fondements de la sécurité prouvée, notamment en chiffrement asymétrique, afin de décrire des schémas cryptographiques concrets dont la sécurité repose exclusivement sur l'hypothèse algorithmique prédéterminée, et non sur une construction heuristique. Pour cela, on définit les notions de sécurité à garantir, avec les buts et les moyens de l'adversaire. Ensuite, on étudie le lien qu'il existe entre la difficulté à mettre en défaut l'une de ces notions et la difficulté à contredire l'hypothèse algorithmique. La théorie de la complexité permet d'évaluer cette difficulté relative, avec les réductions, soit des programmes qui utilisent un algorithme contre le premier problème comme sous-programme pour résoudre le second. On a vite pris conscience de l'intérêt de telles réductions pour garantir l'absence de failles structurelles dans le schéma cryptographique. Mais on n'a que récemment mesuré l'importance de leur efficacité. Plus une réduction est efficace, plus le niveau de sécurité et l'hypothèse algorithmique sont liés. De ce lien dépendra la taille des paramètres à utiliser, et donc l'efficacité du protocole cryptographique pratique pour un niveau de sécurité fixé. De nombreux articles en annexe illustrent toutes ces étapes de la sécurité prouvée, et leurs implications pratiques.

Technical Report, Ecole Normale Supérieure, LIENS 96-17, Dec. 1996.

In this paper we consider provable security for ElGamal-like digital signature schemes. We point out that the good the security criterion on the underlying hash function is pseudorandomness. We extend Pointcheval-Stern's results about the use of the random oracle model to prove the security of two variants of the US Digital Signature Algorithm against adaptive attacks which issue an existential forgery. We prove that a very practical use of the random oracle model is possible whith tamper-resistant modules.

Ph. D. Thesis, Université de Caen, Dec 1996.
Technical Report, Ecole Normale Supérieure, LIENS 96-26, Dec. 1996.

The aim of cryptography is to protect communications, using encryption and authentication protocols. But what is the real security of proposed schemes against clever attackers? In this dissertation, we present provably secure cryptographic schemes in the random oracle model. This model, formalized in 1993 by Bellare and Rogaway, opens a way towards formal security proofs for schemes using one-way or hash functions, which satisfy only computational properties.
First, we present a new identification scheme, provably robust against active attacks, based on a combinatorial NP-complete problem, the Permuted Perceptrons Problem.
Then, we focus on digital signatures and blind signatures. Here, we derive a generic lemma, the ``forking lemma''. It allows us to prove that any signature scheme derivated from a fair verifier zero-knowledge identification protocol is existentially unforgeable against adaptively chosen messages attacks.
An improvement of this ``forking lemma'' allows its application for the more complex concept of blind signatures. It then provides the proof that a large number of blind signature schemes derivated from witness indistinguishable identification protocols cannot admit the so-called ``one-more forgery'', even under parallel attacks.
Finally, we apply the results about blind signatures to electronic cash. We present an ``off-line'' electronic payment system protecting privacy and we give formal proofs of its security for the bank and the users.

La cryptographie a pour but de garantir des communications sûres, par l'intermédiaire notamment de protocoles de chiffrement et d'authentification. Mais encore faut-il que les schémas proposés satisfassent les propriétés de sécurité énoncées face à n'importe quel attaquant. Cette thèse se propose donc de présenter des schémas cryptographiques prouvés sûrs dans le modèle de l'oracle aléatoire. Ce modèle, formalisé par Bellare et Rogaway en 1993, a ouvert la voie à des preuves formelles de sécurité de schémas utilisant des fonctions à sens-unique ou de hachage, qui ne satisfont que des propriétés calculatoires.
Tout d'abord, nous proposons un nouveau schéma d'identification résistant aux attaques actives basé sur un problème combinatoire NP-complet, le Problème des Perceptrons Permutés.
Puis, nous nous intéressons aux schémas de signature électronique et de signature en blanc. Pour cela, nous formulons un lemme générique, le ``lemme de bifurcation''. Ce lemme permet, dans un premier temps, de prouver que tout schéma de signature dérivé d'un protocole d'identification à divulgation nulle de connaissance face à un vérifieur honnête est existentiellement infalsifiable face aux attaques à messages choisis adaptatives. Une nouvelle version de ce ``lemme de bifurcation'' s'applique ensuite au concept plus complexe des signatures en blanc. Nous prouvons alors, pour un grand nombre de schémas de signature en blanc dérivés de protocoles d'identification à témoin indistinguable, l'impossibilité d'une falsification supplémentaire, même selon des attaques parallèles.
Enfin, nous appliquons ces derniers résultats sur les signatures en blanc à la monnaie électronique. Nous présentons alors un schéma de monnaie électronique ``off-line'' respectant l'anonymat avec des preuves formelles de sécurité aussi bien pour l'utilisateur que pour la Banque.

Technical Report, Ecole Normale Supérieure, LIENS 95-2, Feb. 1995.

L'identification est un outil cryptographique très important. Avec la théorie du zero-knowledge, de nombreux schémas interactifs d'identification ont été proposés (en particulier, Fiat-Shamir et ses variantes, Schnorr, etc ). Ces schémas sont basés sur des problèmes de théorie des nombres. Plus récemment, de nouveaux schémas sont apparus avec la particularité qu'ils mettent en jeu des petits entiers, et dont la sécurité dépend de problèmes NP-complets : PKP (Permuted Kernels Problem), SD (Syndrome Decoding) ou CLE (Constrained Linear Equations).
Nous allons présenter un nouveau problème NP-complet qui provient des réseaux de neurones : le Problème des Perceptrons.
Nous présenterons ensuite des protocoles interactifs d'identification zero-knowledge basés sur ce problème, avec une analyse de la sécurité. Finalement, ces protocoles semblent tout à fait adaptés pour un usage sur un système à faibles ressources, telles les cartes à puces.

Mémoire de DEA - Université de Caen. Juillet 1993