Lecture Notes
Cryptographic Protocols
Version 1.8
February 4, 2023
Berry Schoenmakers
Department of Mathematics and Computer Science,
Technical University of Eindhoven,
P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
Cryptographic Protocols (2DMI00)
Spring 2023
,2
,Preface
As a motivating example for the cryptographic protocols covered in these lecture notes con-
sider the Dutch tradition of “Sinterklaaslootjes trekken,” internationally known as “Secret
Santa,” in which a group of people anonymously exchange small gifts—often accompanied by
poems quite a few rhyming couplets long. A lot of websites are available to help people orga-
nize such drawings over the internet; see, for example, lootjestrekken.nl and the “Secret
Santa” service at elfster.com. The interesting question is how to do this securely! That is,
without trusting the website or program providing this service, but with the guarantee (a)
that indeed a random drawing is performed, corresponding to a random permutation without
fixed points, and (b) such that each participant learns nothing except who he or she is a
Secret Santa for.
More serious applications of such privacy-protecting cryptographic protocols are emerging
in lots of places. For instance, over the last two decades many electronic elections using
advanced cryptography have already been conducted. Other applications involve the use of
anonymous cash, anonymous credentials, group signatures, secure auctions, etc., all the way
to (secure) multiparty computation.
To this end we study cryptographic techniques that go beyond what we like to refer to
as Crypto 1.0. Basically, Crypto 1.0 concerns encryption and authentication of data during
communication, storage, and retrieval. Well-known Crypto 1.0 primitives are symmetric (se-
cret key) primitives such as stream ciphers, block ciphers, and message authentication codes;
asymmetric (public key) primitives such as public key encryption, digital signatures, and key
exchange protocols; and, keyless primitives such as cryptographic hash functions. The com-
mon goal is to protect against malicious outsiders, say, attacking storage or communication
media.
On the other hand, Crypto 2.0 additionally aims at protection against malicious insiders,
that is, against attacks by the other parties engaged in the protocol that one is running.
Thus, Crypto 2.0 concerns computing with encrypted data, partial information release of
data, and hiding the identity of data owners or any link with them. Well-known Crypto 2.0
primitives are homomorphic encryption, secret sharing, oblivious transfer, blind signatures,
zero-knowledge proofs, and multiparty computation, which will all be treated to a certain
extent in these lecture notes.
The treatment throughout will be introductory yet precise at various stages. Familiarity
with basic cryptography is assumed. We focus on asymmetric techniques for cryptographic
protocols, also considering proofs of security for various constructions. The topic of zero-
knowledge proofs plays a central role. In particular, Σ-protocols are treated in detail as a
primary example of the so-called simulation paradigm, which forms the basis of much of
modern cryptography.
The first and major version of these lecture notes was written in the period of December
2003 through March 2004. Many thanks to all the students and readers over the years for their
feedback, both directly and indirectly, which helped to finally produce the first full version of
this text. Berry Schoenmakers
3
, Contents
Preface 3
List of Figures 6
1 Introduction 7
1.1 Terminology 7
1.2 Preliminaries 8
Number Theory – Group Theory – Probability Theory – Complexity Theory
1.3 Assumptions 13
Discrete Log and Diffie–Hellman Assumptions – Indistinguishability – Random Self-Reducibility – Random Oracle Model
1.4 Bibliographic Notes 21
2 Key Exchange Protocols 23
2.1 Diffie–Hellman Key Exchange 23
Basic Protocol – Passive Attacks – A Practical Variant – Aside: ElGamal Encryption
2.2 Authenticated Key Exchange 27
Man-in-the-Middle Attacks – A Protocol Using Digital Signatures – A Protocol Using Password-Based Encryption
2.3 Bibliographic Notes 29
3 Commitment Schemes 30
3.1 Definitions 30
3.2 Examples 31
Using a Cryptographic Hash Function – Using a Discrete Log Setting – Impossibility Result
3.3 Homomorphic Commitments 33
3.4 Bibliographic Notes 33
4 Identification Protocols 34
4.1 Definitions 34
4.2 Password-Based Schemes 35
4.3 One-Way Hash Chains 36
4.4 Basic Challenge-Response Protocols 36
Using Symmetric Encryption – Using Symmetric Authentication – Using Asymmetric Encryption – Using Asymmetric Authentication
4.5 Zero-Knowledge Identification Protocols 38
Schnorr Zero-Knowledge Protocol – Schnorr Protocol – Guillou–Quisquater Protocol
4.6 Witness Hiding Identification Protocols 44
Okamoto Protocol
4.7 Bibliographic Notes 46
4
Cryptographic Protocols
Version 1.8
February 4, 2023
Berry Schoenmakers
Department of Mathematics and Computer Science,
Technical University of Eindhoven,
P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
Cryptographic Protocols (2DMI00)
Spring 2023
,2
,Preface
As a motivating example for the cryptographic protocols covered in these lecture notes con-
sider the Dutch tradition of “Sinterklaaslootjes trekken,” internationally known as “Secret
Santa,” in which a group of people anonymously exchange small gifts—often accompanied by
poems quite a few rhyming couplets long. A lot of websites are available to help people orga-
nize such drawings over the internet; see, for example, lootjestrekken.nl and the “Secret
Santa” service at elfster.com. The interesting question is how to do this securely! That is,
without trusting the website or program providing this service, but with the guarantee (a)
that indeed a random drawing is performed, corresponding to a random permutation without
fixed points, and (b) such that each participant learns nothing except who he or she is a
Secret Santa for.
More serious applications of such privacy-protecting cryptographic protocols are emerging
in lots of places. For instance, over the last two decades many electronic elections using
advanced cryptography have already been conducted. Other applications involve the use of
anonymous cash, anonymous credentials, group signatures, secure auctions, etc., all the way
to (secure) multiparty computation.
To this end we study cryptographic techniques that go beyond what we like to refer to
as Crypto 1.0. Basically, Crypto 1.0 concerns encryption and authentication of data during
communication, storage, and retrieval. Well-known Crypto 1.0 primitives are symmetric (se-
cret key) primitives such as stream ciphers, block ciphers, and message authentication codes;
asymmetric (public key) primitives such as public key encryption, digital signatures, and key
exchange protocols; and, keyless primitives such as cryptographic hash functions. The com-
mon goal is to protect against malicious outsiders, say, attacking storage or communication
media.
On the other hand, Crypto 2.0 additionally aims at protection against malicious insiders,
that is, against attacks by the other parties engaged in the protocol that one is running.
Thus, Crypto 2.0 concerns computing with encrypted data, partial information release of
data, and hiding the identity of data owners or any link with them. Well-known Crypto 2.0
primitives are homomorphic encryption, secret sharing, oblivious transfer, blind signatures,
zero-knowledge proofs, and multiparty computation, which will all be treated to a certain
extent in these lecture notes.
The treatment throughout will be introductory yet precise at various stages. Familiarity
with basic cryptography is assumed. We focus on asymmetric techniques for cryptographic
protocols, also considering proofs of security for various constructions. The topic of zero-
knowledge proofs plays a central role. In particular, Σ-protocols are treated in detail as a
primary example of the so-called simulation paradigm, which forms the basis of much of
modern cryptography.
The first and major version of these lecture notes was written in the period of December
2003 through March 2004. Many thanks to all the students and readers over the years for their
feedback, both directly and indirectly, which helped to finally produce the first full version of
this text. Berry Schoenmakers
3
, Contents
Preface 3
List of Figures 6
1 Introduction 7
1.1 Terminology 7
1.2 Preliminaries 8
Number Theory – Group Theory – Probability Theory – Complexity Theory
1.3 Assumptions 13
Discrete Log and Diffie–Hellman Assumptions – Indistinguishability – Random Self-Reducibility – Random Oracle Model
1.4 Bibliographic Notes 21
2 Key Exchange Protocols 23
2.1 Diffie–Hellman Key Exchange 23
Basic Protocol – Passive Attacks – A Practical Variant – Aside: ElGamal Encryption
2.2 Authenticated Key Exchange 27
Man-in-the-Middle Attacks – A Protocol Using Digital Signatures – A Protocol Using Password-Based Encryption
2.3 Bibliographic Notes 29
3 Commitment Schemes 30
3.1 Definitions 30
3.2 Examples 31
Using a Cryptographic Hash Function – Using a Discrete Log Setting – Impossibility Result
3.3 Homomorphic Commitments 33
3.4 Bibliographic Notes 33
4 Identification Protocols 34
4.1 Definitions 34
4.2 Password-Based Schemes 35
4.3 One-Way Hash Chains 36
4.4 Basic Challenge-Response Protocols 36
Using Symmetric Encryption – Using Symmetric Authentication – Using Asymmetric Encryption – Using Asymmetric Authentication
4.5 Zero-Knowledge Identification Protocols 38
Schnorr Zero-Knowledge Protocol – Schnorr Protocol – Guillou–Quisquater Protocol
4.6 Witness Hiding Identification Protocols 44
Okamoto Protocol
4.7 Bibliographic Notes 46
4
