With the seminal paper by Diffie and Hellman (1976), and the introduction to public-key cryptography, a very broad area of research has emerged. Public-key cryptography includes not only the asymmetric variants of encryption and authentication, i.e. public-key encryption and signature schemes, but also many other innovative and impressively powerful tools.
This book aims at presenting the main cryptographic primitives that have been proposed within the last 40 years, with chapters written by famous cryptographers, who are all specialists in the specific domains, with several publications in the main international venues on cryptography. I am very honored they all accepted my invitation to participate and make this book as complete as possible.
This book starts with a presentation of the main primitives of public key cryptography, namely public-key encryption and signatures, including definitions and security models. This chapter also gives the flavor of the meaning of provable security, explaining what it means when one claims a cryptographic scheme to be secure. In the second chapter we present zero-knowledge proofs. This is a quite magical tool that is thereafter used as a building block in many other protocols. Zero-knowledge proofs allow to convince a verifier of the validity of any true statement, without revealing any additional information. In the same vein, secure multiparty computation allows two or more players with private inputs to compute the output of a well-defined function on these joint inputs, without revealing anything else than this intended output.
After they were initially used for attacking the discrete logarithm problem on elliptic curves, pairings have extensively been applied to construct new primitives, primarily to propose new types of encryption and signature schemes. Consequently, we first make a general introduction to pairing-based cryptography, and then we present advanced cryptographic schemes for confidentiality and authentication, which satisfy additional properties. The first such scheme we present is broadcast encryption, which improves on usual encryption by targeting multiple recipients when sending private information. One could of course give the same decryption key to many users, but if one wants to dynamically change the target set, different personal decryption keys are required. With traitor tracing, it is then possible to trace traitors who reveal their decryption keys to non-legitimate users. Attribute-based encryption is a generalization of broadcast encryption, where the target set can be specified by a policy and attributes. It is then possible to describe the target set in a fine-grained manner, for each new ciphertexts. Advanced signatures add anonymity properties to signature and authentication. Thanks to pairings, it is indeed possible to efficiently authenticate to a service without revealing much about personal data.
Besides encryption and signatures schemes, key exchange is a major tool in real life, as it allows two or more players to agree on a common session key, which can be used to establish a secure communication channel. While it looks like a simple and well-defined task, key exchange protocols are intricate, with many various security notions to consider. There are also several ways to authenticate the users: either by signing the messages or by showing the capability of decryption. The use of a pre-shared symmetric key is also possible. However, the most practical and challenging authentication setting is when the parties hold a short pre-shared symmetric key. The latter common information is called a password, and to address this setting we consider password-authenticated key exchange.
With the massive outsourcing of storage and computation, verifiable computation became a very active domain, where one wants to have strong guarantees on the output of the outsourced computation. Of course, the goal is to be able to verify computation in a much more efficient way than performing the computation itself, hence the development of succinct non-interactive arguments (SNARGs).
The various chapters give a broad overview of some recent advances in public-key cryptography. This is definitely not exhaustive, and each presentation is the author’s point of view of the field. There are some general descriptions, or sometimes more focused examples to illustrate the purpose. They are appropriate for a large audience to discover or learn more about public-key cryptography.