Public-Key Cryptography
Theory and Practice
Vom Fachbereich Informatik
der Technischen Universität Darmstadt
genehmigte

Dissertation
zur Erreichung des akademischen Grades
Doctor rerum naturalium (Dr. rer. nat.)vonDipl.-Inform. Bodo Möller
aus Hamburg

Referenten:

Prof. Dr. Johannes Buchmann (TU Darmstadt)
Prof. Dr. Christof Paar (Ruhr-Universität Bochum)Tag der Einreichung:Tag der mündlichen Prüfung:

1. Juli 2003
16. September 2003

Darmstadt, 2003
Hochschulkennziffer: D 17

Viele haben auf die eine oder andere Weise dazu beigetragen, dass diese Dissertation so entstehen
konnte, wie sie nun vorliegt. Der Versuch einer vollständigen Aufzählung müsste scheitern; hier seien
zunächst die erwähnt, die nicht mit Namen genannt werden können, weil sie als anonyme Gutachterfür Konferenzen tätig waren und dabei Anregungen zur Darstellung einiger der hier präsentierten
Ergebnisse beigetragen haben. Außerdem zu nennen ist David Hopwood, der in einer früheren Fassung
der Ausführungen zur beweisbaren Sicherheit des Mix-Verfahrens (hier in Abschnitt 4.2) eine Lückeaufgespürt hat. Prof. Johannes Buchmann hat es auf bemerkenswerte Weise verstanden, die Arbeitsbedingungen zu schaffen, in denen diese Dissertation gedeihen konnte, und hat wertvolle Anregungengeliefert. Auch alle anderen am Fachgebiet Theoretische Informatik hatten teil daran, eine angenehme
und fruchtbare Arbeitsatmosphäre zu schaffen. Danke!
Darmstadt, im September 2003

B. M.

3

Abstract
Part I: Theory
Provable security is an important goal in the design of public-key cryptosystems. For mostsecurity properties, it is computational security that has to be considered: an attack scenario
describes how adversaries interact with the cryptosystem, trying to attack it; the system canbe called secure if adversaries with reasonably bounded computational means have negligible
prospects of success. The lack of computational problems that are guaranteed to be hard in an
appropriate sense means that there is little hope for absolute proofs of computational security.
Instead, reduction-based security proofs have to be used: the computational security of acomplex cryptographic scheme is related to the security of simpler underlying cryptographic
primitives (under appropriate notions of security). The idea is to show that if the complex
scheme is not secure, then this is because one of the primitives is not secure. Security can be
described quantitatively as “concrete security”, measured depending on the power given toadversaries.
The DHAES construction (due to Abdalla, Bellare, and Rogaway) allows building a publickey encryption scheme from a key encapsulation mechanism (KEM), a one-time message
authentication code (one-time MAC), and a pseudo-random bit string generator. A reductionbased security proof shows that DHAES achieves security against (adaptive) chosen-ciphertext
attacks if these underlying primitives are secure. (Such chosen-ciphertext attacks are the mostgeneral attack scenario for public-key encryption.)
A specific application for public-key cryptography is considered, namely Chaum’s mix
chain concept for untraceable electronic mail via cryptographic remailers: to obtain anonymity
without requiring trust in a single authority, messages are recursively public-key encrypted
to multiple intermediates (mixes), each of which forwards the message after removing one
layer of encryption. To conceal as much information as possible when using variable (source
routed) chains, all messages passed to mixes should be of the same length; thus, message
length should not decrease when a mix transforms an input message into the corresponding
output message directed at the next mix in the chain. Chaum described an implementation forsuch length-preserving mixes, but it is not secure against active attacks. This thesis presents
a new construction for practical length-preserving mixes, which uses the cryptographic primitives described for DHAES. The conventional definition of security against chosen ciphertext
attacks for public-key encryption schemes is not applicable to length-preserving mixes, so appropriate security definitions are introduced; it is shown that the mix construction achieves
provable security.

Part II: Practice
Most instantiations of public-key cryptography involve computing powers (exponentiation)or computing power products (“multi-exponentiation”) in some commutative semigroup withneutral element. This thesis describes the sliding window technique for arbitrary commutative semigroups with neutral element and its signed-digit variant (“window NAF”) for groups
where inversion is fast (e.g. point groups of elliptic curves and class groups of imaginary
quadratic number fields), and then presents new techniques. Fractional windows, a generalization of the previously known window methods, can be useful for devices with limited
storage. Interleaved exponentiation is a simple strategy for multi-exponentiation; the comparison with previous simultaneous exponentiation methods shows that it often provides better4efficiency. Window NAF splitting is a method for fast exponentiation with precomputation
for a fixed base in groups where inversion is fast.
For the case of elliptic curves, side-channel attacks are discussed, i.e. attacks where adversaries use power consumption measurements or similar observations to derive information on
secret values. Two methods are shown that are designed to limit potential information leakage available to adversaries: a 2w -ary left-to-right method employing special representationsof scalars, and a 2w -ary right-to-left method with a special randomized initialization stage.

5

Zusammenfassung
Teil I: Theorie
Beweisbare Sicherheit ist ein wichtiges Ziel beim Entwurf von Public-Key-Kryptosystemen.
Für die meisten Sicherheitseigenschaften muss hierbei praktische Sicherheit gegen Angreifer
mit beschränkten Mitteln betrachtet werden: Ein Angriffsszenario beschreibt, wie Gegner
mit dem Kryptosystem interagieren dürfen, um es anzugreifen; das System kann dann als
sicher bezeichnet werden, wenn Gegner mit einem praktikablen Rechenaufwand nur vernachlässigbare Erfolgsaussichten erzielen können. Da es keine Berechnungsprobleme gibt, diebewiesenermaßen in einem geeigneten Sinne schwer sind, gibt es nur wenig Hoffnung für
absolute Sicherheitsbeweise im Sinne solcher praktischer Sicherheit. Statt dessen muss auf
reduktionsbasierte Sicherheitsbeweise zurückgegriffen werden: Die praktische Sicherheit eines
komplexen kryptographischen Systems wird zu der Sicherheit einfacherer zugrundeliegender
kryptographischer Primitive (mit jeweils passenden Sicherheitsbegriffen) in Beziehung gestellt.
Der Grundgedanke ist, zu zeigen, dass das komplexe System nur dann unsicher sein kann,wenn eine der Primitiven unsicher ist. Die Sicherheit kann als ,,konkrete Sicherheit“ quantitativ beschrieben werden in Abhängigkeit von den Mitteln, die Gegnern zur Verfügung stehen.
Mit dem DHAES-Schema von Abdalla, Bellare und Rogaway kann man aus einem
Schlüsselaustauschverfahren (key encapsulation mechanism, KEM), einem Einmal-MAC(message authentication code) und einem Pseudozufallsbitstringgenerator ein Public-KeyVerschlüsselungsverfahren konstruieren. Ein reduktionsbasierter Sicherheitsbeweis zeigt, dass
DHAES Sicherheit gegen (adaptive) ,,Chosen-ciphertext“-Angriffe erzielt, falls die zugrundeliegenden Primitive sicher sind. (Solche Chosen-ciphertext-Angriffe sind das allgemeinste
Angriffsszenario für Public-Key-Verschlüsselung.)
Eine spezifische Anwendung für Public-Key-Kryptographie wird betrachtet, Chaums MixKetten-Konzept für nicht verfolgbare E-Mail über kryptographische Remailer: Damit Absender Anonymität erreichen können, ohne einer einzelnen Stelle vertrauen zu müssen, werden
Nachrichten rekursiv für mehrere Zwischenstellen verschlüsselt (die ,,Mixe“), die jeweils die
Nachricht weitersenden, nachdem sie eine Ebene der Verschlüsselung entfernt haben. Um bei
der Benutzung von variablen Mix-Ketten sowenig Information wie möglich zu verraten, sollten
alle an Mixe gesandte Nachrichten die gleiche Länge haben; also sollte die Nachrichtenlänge
sich nicht verringern, wenn ein Mix eine ankommende Nachricht umwandelt in die Nachricht,
die er an den nächsten Mix in der Kette weiterzuleiten hat. Die von Chaum beschriebene
Konstruktion für solche längenerhaltene Mixe ist nicht sicher gegen aktive Angreifer. Diese
Dissertation stellt eine neue Konstruktion für praktische längenerhaltene Mixe vor, welche auf
den für DHAES angegebenen kryptographischen Primitiven aufbaut. Die übliche Definitionfür Sicherheit gegen ,,Chosen-ciphertext“-Angriffe bei Public-Key-Verschlüsselung kann für
längenerhaltende Mixe nicht angewendet werden; deshalb werden angemessene Sicherheitsdefinitionen vorgestellt. Es wird gezeigt, dass die Mix-Konstruktion beweisbare Sicherheit
bietet.

Teil II: Praxis
Bei der Durchführung von Public-Key-Kryptographie sind üblicherweise Potenzen zu berechnen (Exponentiation) oder Produkte von Potenzen (,,Multi-Exponentiation“). Diese Dissertation beschreibt die ,,Sliding-window“-Technik für beliebige kommutative Halbgruppen mit
neutralem Element und ihre Variante mit vorzeichenbehafteter Codierung (,,window NAF“),6

die für Gruppen mit schneller Invertierung verwendet werden kann (z. B. Punktegruppen
elliptischer Kurven oder Klassengruppen imaginärquadratischer Zahlkörper). Anschließend
werden neue Techniken präsentiert: Die Verallgemeinerung der bekannten Fenstermethodenzu ,,fractional windows“ kann für Rechner mit beschränktem Speicherplatz von Vorteil sein.
,,Interleaved exponentiation“ ist eine einfache Strategie für Multi-Exponentiation; der Vergleich mit den bekannten Multi-Exponentiations-Methoden (,,simultaneous exponentiation“)
zeigt, dass der neue Ansatz oft bessere Effizienz liefert. ,,Window NAF splitting“ ist eine Methode zur schnellen Exponentiation mit Vorberechnung für eine feststehende Basis in Gruppen
mit schneller Invertierung.
Für den Fall von elliptischen Kurven werden schließlich Seitenkanalangriffe diskutiert,
d. h. Angriffe, bei denen Angreifer Messungen des Stromverbrauchs oder ähnliche Beobachtungen benutzen, um Information über geheime Werte zu erhalten. Zwei Verfahren werden vorgestellt, die gezielt dem Bekanntwerden von geheimer Information über Seitenkanäleentgegenwirken: eine 2w -äre Links-nach-rechts-Methode, die auf einer speziellen Darstellung
der Skalare beruht, und eine 2w -äre Rechts-nach-links-Methode mit einem besonderen randomisierten Initialisierungsschritt.

7

Erklärung1
Hiermit erkläre ich, dass ich die vorliegende Arbeit – abgesehen von den in ihr ausdrücklichgenannten Hilfen – selbständig verfasst habe.

Wissenschaftlicher Werdegang des Verfassers in Kurzfassung2
Okt. 1993 – Okt. 1999
20. 10. 1999
Nov. 1999 – Sept. 2003

1
2

Studium der Informatik mit Ergänzungsfach Mathematik
an der Universität Hamburg
Diplomprüfung (Dipl.-Inform.)wissenschaftlicher Mitarbeiter am Fachgebiet Theoretische
Informatik (Prof. J. Buchmann), Fachbereich Informatik,
Technische Universität Darmstadt

gemäß § 9 Abs. 1 der Promotionsordnung der TU Darmstadt
gemäß § 20 Abs. 3 der Promotionsordnung der TU Darmstadt

8

Contents
1 Introduction

13

I

15

Theory2 Public-Key Cryptography and Provable Security
2.1 Information-Theoretic Security . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Computational Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Example: IND-CPA Security . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Reduction-Based Security Proofs . . . . . . . . . . . . . . . . . . . . .
2.3.3 Asymptotic Security Proofs . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 The Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . .
2.3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
18
20
21
22
23
24
25

3 Hybrid Public-Key Encryption: The DHAES Construction
3.1 Adaptive Chosen-Ciphertext Attacks . . . . . . . . . . . . . . . . . . . . . . .
3.2 Primitives for the DHAES Construction . . . . . . . . . . . . . . . . . . . . .
3.3 The DHAES Public-Key Encryption Scheme . . . . . . . . . . . . . . . . . .
3.4 The Security of the DHAES Construction . . . . . . . . . . . . . . . . . . . .
3.4.1 Security of the Key Encapsulation Mechanism . . . . . . . . . . . . .
3.4.2 Security of the One-Time Message Authentication Code . . . . . . . .
3.4.3 Security of the Pseudo-Random Bit String Generator . . . . . . . . .
3.4.4 Security Result for the DHAES Construction . . . . . . . . . . . . . .

27
28
30
32
33
33
34
35
35

4 A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes
4.1 The Mix Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Provable Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Unlinkability of the Mix Encryption Scheme . . . . . . . . . . . . . . .
4.2.2 CCA Security of the Mix Encryption Scheme . . . . . . . . . . . . . .
4.2.3 Security Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39
41
42
43
45
46
47
49

9

10

II

Contents

Practice

53

5 Exponentiation and Multi-Exponentiation in Public-Key Cryptography

55

6 Efficient Exponentiation
6.1 A Framework for Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Left-to-Right Methods . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.2 Right-to-Left Methods . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Sliding Window Exponentiation and Window NAF Exponentiation . . . . . .
6.2.1 Modified Window NAFs . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Fractional Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Signed Fractional Windows . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2 Unsigned Fractional Windows . . . . . . . . . . . . . . . . . . . . . . .
6.4 Compact Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59
59
60
61
62
63
64
64
67
69

7 Efficient Multi-Exponentiation
71
7.1 Simultaneous Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
7.1.1 Simultaneous 2w -Ary Exponentiation Method . . . . . . . . . . . . . .
73
7.1.2 Simultaneous Sliding Window Exponentiation Method . . . . . . . . .
74
7.2 Interleaved Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
7.2.1 Basic Interleaved Exponentiation Method . . . . . . . . . . . . . . . .
76
7.2.2 Window-NAF Based Interleaved Exponentiation Method . . . . . . .
77
7.3 Comparison of Simultaneous and Interleaved Exponentiation Methods . . . .
78
7.3.1 Comparison between the Simultaneous 2w -Ary Method and the Basic
Interleaved Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
7.3.2 Comparison between the Simultaneous Sliding Window Method andthe Window-NAF Based Interleaved Method . . . . . . . . . . . . . .
79
7.3.3 Comparison between the Dimitrov-Jullien-Miller Multi-Exponentiation
Method and Interleaved Exponentiation . . . . . . . . . . . . . . . . .
80
7.3.4 Multi-Exponentiation with Fractional Windows . . . . . . . . . . . . .
81
7.3.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
7.3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
7.4 Exponentiation and Multi-Exponentiation with Precomputation for Fixed Bases 82
7.4.1 Exponent Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.4.2 Lim-Lee Precomputation . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.4.3 Window NAF Splitting . . . . . . . . . . . . . . . . . . . . . . . . . .
85
8 Elliptic Curve Point Multiplication with Resistance against Side-Channel
Attacks87
8.1 Previous Side-Channel Attack Countermeasures . . . . . . . . . . . . . . . . .
88
8.2 Security against Side-Channel Attacks . . . . . . . . . . . . . . . . . . . . . .
90
8.2.1 Elliptic Curve Point Operations . . . . . . . . . . . . . . . . . . . . . .
90
8.2.2 Field Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
8.3 2w -Ary Left-to-Right Method . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
8.3.1 Recoding Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
8.3.2 Point Multiplication Algorithm . . . . . . . . . . . . . . . . . . . . . .
94
8.3.3 Uniformity of the Point Multiplication Algorithm . . . . . . . . . . . .
95

Contents

8.4

8.5
8.6

2w -Ary Right-to-Left Method . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.1 Initialization Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.2 Right-to-Left Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.3 Result Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.4 Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Efficiency Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Scalar Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

97
98
99
100
100
102
104

Bibliography

107

Index

115

12

Contents

Chapter 1

Introduction
This dissertation examines multiple aspects of public-key cryptography.
Part I looks at the theory of provably secure public-key cryptography, focusing on encryption. First, chapter 2 gives an introduction to this topic area and discusses the limitationsof provable security. Then, chapter 3 describes the DHAES construction for public-key encryption and gives a reduction-based security proof for it. Chapter 4 concludes the part bypresenting a construction for a specific variant of encryption, namely public-key encryption
with length-expanding decryption for use with Chaum’s mix concept for untraceable electronic
mail. Again, security is proved in a reduction-based way.
Part II concerns itself with an important topic for the practice of public-key cryptography,
namely the implementation of exponentiation and multi-exponentiation. Chapter 5 showssome typical application scenarios. Chapter 6 presents techniques for efficient exponentiation.
Chapter 7 presents techniques for efficient multi-exponentiation and for efficient exponentiation with precomputation for fixed bases. Finally, chapter 8 includes the issue of side-channel
attacks into the consideration and describes techniques for elliptic curve point multiplication(a specific case of exponentiation) that are designed to resist such attacks.
Of course, no attempt is made to give a complete survey on the theory or the practice of
public-key cryptography. This would amount to compiling a vast collection of material, andsuch a collection would be outdated quickly as much research is done in both areas. Instead,the goal here is to provide an introduction to provable security (chapters 2 and 3) and to
give sufficient context for the areas of my own research results concerning provably securepublic-key cryptography (chapter 4; cf. my conference publication [63]), efficient implementation of exponentiation and multi-exponentiation (chapters 6 and 7; cf. [58, 62]), and point
multiplication with resistance against side-channel attacks (chapter 8; cf. [59, 60, 61]).

13

14

IntroductionPart I

Theory15

16Chapter 2

Public-Key Cryptography andProvable Security
The term cryptography originally refers to hidden writing. Today it has a much broader
meaning and covers various related concepts besides encryption, such as authentication. In
the following chapters on the theory of provably secure public-key cryptography, we will
look at certain constructions specifically for encryption. The present chapter provides somebackground for this, focusing on the aspect of provability; much of its content applies to othertypes of public-key cryptography as well.
Notational Conventions
x ∈R S means that x is uniformly randomly chosen from set S (where the distribution is understood to be independent of any other given probability distributions that do not explicitly
depend on x).
For a bit string s (an element of {0, 1}∗ ), |s| denotes its length. The concatenation ofstrings s and t is denoted s || t. For |s| ≥ w, prefixw (s) is the string consisting of the leftmost
w bits of s. Thus, prefix|s| (s || t) = s ∈ {0, 1}|s| .
Algorithms are usually probabilistic (randomized).

2.1

Information-Theoretic Security

Here we look at symmetric cryptography before proceeding to public-key cryptography, whichis also known as asymmetric cryptography, in the next section. Assume a simple scenario
where just two parties are involved, A and B. Then, in symmetric cryptography, A and B
must both have knowledge of a piece of data that should be kept secret from others, the key.
A simple symmetric cryptosystem is the following ([88], [79]).
Protocol 2.1. Let G be a finite group. Vernam encryption in group G works as follows.
Parties A and B agree on a key K ∈R G (a uniformly random element of G). To encrypt
some message represented by an element m ∈ G (the plaintext), A computes the group elementc = m + K (the ciphertext). B, when having received c, can recover the plaintext m as c − K.
The Vernam encryption scheme is also known as the one-time pad (OTP) because eachkey should be used only for encrypting a single message. Often the group is G = {0, 1}k forsome k ∈ N with XOR as group operation, but the scheme works in any finite group.
17

18

Public-Key Cryptography and Provable Security

The only assumption we make on the distribution of m is that it be stochastically indee ce ∈ G, we havependent of the distribution of K. Then for any elements m,
e | c = ce] = Pr[m = m
e | K = ce − m] = Pr[m = m]ePr[m = mbecause K has independent uniform distribution. This means that, if K is kept secret, anadversary who observes some ciphertext c cannot learn any information whatsoever on mfrom it: the Vernam encryption scheme is information-theoretically secure.
A caveat is that this result only holds if keys K are perfectly random. In implementations,
there will usually be some bias. However miniscule it may be, this means that ciphertexts
will reveal at least a tiny amount of information on the corresponding plaintexts. Typicallythe bias will be small enough so that it does not really matter at all, and no-one will know
the details about the bias that would be necessary to exploit it; we should just keep in mind
that perfect information-theoretic security remains a mathematical utopia an epsilon away.

2.2

Public-Key Cryptography

In asymmetric or public-key cryptography ([32], [33]), there is no longer a single key shared by
the parties that are involved. Instead, the key generation algorithm produces multiple keys
that are associated with another: usually, there is a secret key that should be known only toa single entity, and a public key that may be made known to everyone.
One form of public-key cryptography is public-key encryption, where someone’s publickey can be used to encrypt plaintexts such that the resulting ciphertexts can be decryptedusing the corresponding secret key. Another important form of public-key cryptography
are digital signature schemes: the entity holding the secret key can use it to “sign” digital
documents by computing a value, a “signature”, such that anyone who knows the public key
can verify whether the signature is valid for a given message. Also various other scenarios forcryptographic protocols are known that belong into the area of public-key cryptography. We
will focus on public-key encryption and specific closely related notions and not go into thedetails of digital signatures or other protocols.
A concept related to public-key encryption is the notion of a key encapsulation mechanism (KEM; see [80]). As in public-key encryption, someone’s public key is used to create aciphertext from which a plaintext can be recovered using the associated secret key. Unlike forpublic-key encryption, the sender does not get to specify an arbitrary plaintext when creating
the ciphertext; instead, the randomized “encryption” algorithm outputs both the plaintext
and a corresponding ciphertext. This approach is appropriate for use in cryptographic protocols where the plaintext is intended as a key for symmetric cryptography – hence the term
key encapsulation.
Note that both symmetric and public-key encryption schemes can be randomized: encrypting a given plaintext for a constant key does not necessarily yield a unique result. However,encryption followed by decryption has a deterministic result, namely the original plaintext;
this is in contrast with KEMs. (The variant of public-key encryption that we will consider inchapter 4 is an unusual exception where decryption yields the original plaintext padded withsome additional data, which is determined while encrypting. In that public-key cryptosystemwith length-expanding decryption, the result of encryption followed by decryption is partiallydeterministic and partially pseudo-random.)2.2 Public-Key Cryptography

19

A formalization of the notion of a public-key encryption scheme will appear in section 3.1,
where we will also look at different attack scenarios and see how the security of public-key
encryption in a strong sense (i.e. when exposed to an adversary in a far-going attack scenario)
can be expressed quantitatively. A formalization of the notion of a KEM will appear insection 3.2 (see section 3.4.1 for security notions for a KEM). In the present chapter, we will
preview some of these subjects, but without going all the way yet (we treat these concepts
somewhat informally, and we confine to rather limited attack scenarios for ease of exposition).
As basic examples, we look at three variants of the Diffie-Hellman (DH) key encapsulation
mechanism ([33], [1], [2], [80]).
Protocol 2.2. Let G be a finite group (whose order #(G) is known) and g ∈ G. A key pairconsisting of a secret key SK and a public key PK is generated as follows: pickSK ∈R 0, 1, . . ., #(G) − 1
and let
PK = g SK .
A sender who knows the public key PK generates a ciphertext K ∈ G and the corresponding
plaintext K ∈ G as follows: pickx ∈R 0, 1, . . ., #(G) − 1
and letK = gxand
K = PKx .
Now if the sender transmits K to the owner of the secret key, the latter can recover theplaintext K by computing
KSK .
(Observe that KSK = g x·SK = PKx = K).
Protocol 2.3. Again, let G be a finite group (of known order) and g ∈ G.
Let k be a positive integer, and let h : G → {0, 1}k be some hash function. (By this, wemean that h should intuitively behave like a randomly chosen map from the first set to thesecond: we want to be able assume that for any y ∈ G, the k-bit string h(y) is random.
However, note that this is just a way to think about what happens and is certainly not how hcan be defined in practice.)
Now the Diffie-Hellman key encapsulation mechanism can be performed similar to protocol 2.2 with the help of the hash function. Key generation is as above:SK ∈R 0, 1, . . ., #(G) − 1 ,PK = g SK .

The sender now proceeds as follows to generate a ciphertext K ∈ G and a corresponding
plaintext K ∈ {0, 1}k : pickx ∈R 0, 1, . . ., #(G) − 1 ,then let
K = PKx

20

Public-Key Cryptography and Provable Security

andK = h(g x ).
The owner of the secret key can recover K from K by computingh(KSK ).
Protocol 2.4. A further variant of the Diffie-Hellman scheme works mostly as the previous
one, but applies a hash function differently. We describe just the differences to protocol 2.3.
This time, we have a hash function h : G×G → {0, 1}k . The sender computes K ∈ {0, 1}kas
K = h(K, g x ),and the owner of the secret key computes it as
K = h(K, KSK ).
In these three protocols, we have assumed that in addition to the specific public keys,
senders also have certain additional information: they know which group G to computein, they know which element g ∈ G to use, and they know the order #(G) of the group.
Such information is collectively referred to as domain parameters. It is possible to consider
generating domain parameters part of key generation, but it is also possible to use fixed
domain parameters for many key pairs.
Observe that key encapsulation mechanisms can easily be combined with symmetric encryption schemes to create public-key encryption schemes. For example, any of the DiffieHellman variants described above can be followed by Vernam encryption (protocol 2.1) in an
appropriate group using the DH result K as a key. In the case of the DH variant without ahash function (protocol 2.2), this combination is called ElGamal encryption [35].
Note that it is impossible to achieve full information-theoretic security in a meaningful
sense for public-key cryptography: the public key necessarily must contain at least partial
information on the secret key, or the two keys (secret and public) would not be associatedwith each other. For example, in the Diffie-Hellman schemes that we presented above, key
PK determines SK modulo the order of g in G (secret keys that are congruent modulo ord(g)are equivalent if the protocol is followed by both parties). Instead of information-theoretic
security, in section 2.3 we will consider computational security, i.e. security against adversaries
with bounded computational means.
(Some public-key protocols exist that are designed to achieve at least a certain notion of
security in more than a computational sense. Fail-stop signature schemes [72] are signatureschemes where a security failure of the system can be detected with very high probability:
many different possible secret keys match each given public key, and if an adversary breaks
the system computationally and produces a seemingly valid signature, then this signature
will likely be based on a secret key differing from the legitimate one, and differ from thesignature on the same message that would have been produced by the legitimate signer withhis original secret key. In such cases, the key owner can demonstrate that there has been asecurity failure and that thus the fake signature should not be considered valid.)

2.3

Computational Security

As information-theoretic security is out of the question for public-key cryptography, we haveto examine computational security. Adversaries are modelled as probabilistic algorithms that2.3 Computational Security

21

somehow interact with the cryptographic scheme that they are attacking (details of thisinteraction depend on the specific notion of security). Then we can try to analyze the probabilities with which an adversary can achieve certain attack goals under given complexity
bounds. These bounds might be explicit (e.g. a maximum number of algorithm steps) or
implicit. Based on such probabilities, we will define the advantage of the adversary in therespective attack scenario as a real number in the interval [0, 1] where value 0 (no advantage)means that the cryptographic scheme is secure under the notion of security under consideration against the respective adversary, and where value 1 means that the cryptographic scheme
is totally insecure under the notion of security considered against the respective adversary(with its complexity bounds).
(Beware that other definitions for the advantage can be found in the literature: sometimes,
the advantage ranges from −1/2 to 1/2, where value 0 means no advantage as above and where
both −1/2 and 1/2 indicate total insecurity. Such a measure Adv0 can be transformed into ameasure Adv following our convention by taking Adv = 2 · |Adv0 |.)What we are really interested in is the inherent security of the cryptographic scheme undera certain notion of security, not just the security against some specific adversary. Somethingthat will usually have to be specified is an upper time bound for the adversaries that are to beconsidered. We can also include additional parameters besides the time bound: for example,
attack models often provide the adversary with “encryption oracles” and “decryption oracles”
or the like, which will process requests sent by the adversary; in such models, we can haveparameters for the maximum number of queries to specific oracles, and the maximum size ofall queries to them. Then the advantage of arbitrary adversaries can be defined as a functionof all such parameters: it is the infimum of advantages of all adversaries that observe all
the specified bounds. This is known as the concrete security approach ([7], [8]): security is
described quantitatively, measured depending on the power given to adversaries.

2.3.1

Example: IND-CPA Security

As a first example, we show a basic notion of security for public-key encryption, namely
indistinguishability under chosen-plaintext attack (IND-CPA), which goes back to [37]. (Forstronger security notions, see the next chapter.) Assume that some public-key encryption
scheme PKE is given. In the IND-CPA scenario, adversaries engage in the following attackgame:
1. The adversary queries a key generation oracle, which computes a key pair (PK, SK) using
the key generation algorithm specified for PKE. The public key PK is made available tothe adversary, and SK is kept secret.
2. Now the adversary chooses two binary strings m0 and m1 of the same length andsends them to a so-called encryption oracle, which secretly picks b ∈R {0, 1}, applies theencryption algorithm of PKE to mb using the key PK, and responds with the resulting
string, which we call the challenge ciphertext.
3. The adversary outputs a bit eb ∈ {0, 1}, which is supposed to be a guess for the value ofbit b.
Now for a specific adversary A (an interactive probabilistic algorithm with bounded runningtime), we define its CPA advantage against the public-key encryption scheme as
AdvCPAPKE,A = Pr[eb = 1 | b = 1] − Pr[eb = 1 | b = 0] .

22Public-Key Cryptography and Provable Security

Note that because
Pr[eb = 1 | b = 1] − Pr[eb = 1 | b = 0] = Pr[eb = 1 | b = 1] + Pr[eb = 0 | b = 0] − 1= 2 Pr[eb = b] − 1,

we can also write this as
AdvCPAPKE,A = 2 · Pr[eb = b] −1.
2

(Observe that if there is an adversary that tends to guess wrong, this is just as bad as if
it tends to guess right: by always inverting the adversary’s output bit eb, one case can betransformed into the other.)
The term “chosen-plaintext attack” refers to the fact that the adversary can encrypt
arbitrary plaintexts of its own choice because it knows the public key PK. Observe that apublic-key encryption scheme cannot be secure under this definition unless it is randomized(presuming that it is sound in the sense that decrypting the encryption of a given plaintext
will actually recover the original plaintext): for a deterministic scheme, the adversary could
simply encrypt m0 or m1 ; one of the ciphertexts will equal the challenge ciphertext, and if
m0 6= m1 , this immediately reveals b.

2.3.2

Reduction-Based Security Proofs

Proving the computational security of a cryptographic scheme would amount to showing thatsomething that is easy to do with knowledge of all cryptographic keys involved is a hard computational problem for an adversary who does not know the relevant secret keys. However,except in the very narrow range where we actually have information-theoretic security, thistouches the limits of complexity theory, and there is little hope for actually provable computational security. Instead, one can resort to reduction-based security proofs, in which it isshown that a cryptographic scheme complies to the security notion in question provided thata certain underlying computational problem is hard, or that a complex cryptographic scheme
is secure under an appropriate security definition provided that the simpler cryptographic
schemes (or primitives) from which it is built are secure under their respective security notions. The point of such proofs by reduction is that expressions of security for cryptographic
schemes can be related to computational problems that are simple to describe and more directly accessible for complexity analyses, and the intractability of which may be supported
by experience, i.e. by the failure to find efficient algorithms after intensive research.
Observe that saying that a computational problem “is hard” is quite ambiguous: it might
merely mean that the problem has some difficult instances (cf. the expression “NP-hard” incomplexity theory); or it might mean that easy instances are indeed rare. In the context ofcryptography, we need problems that are hard in the stricter sense. To avoid the ambiguity,
we will usually speak of “secure cryptographic primitives” rather than “hard computational
problems” (any “hard problem” in the appropriate sense can be considered a cryptographic
primitive).
Saying that some cryptographic scheme “is secure” is clearly simplicistic. The concrete
security approach can be used to make quantitative statements about security. Reductionbased security proofs work as follows: if the advantage that an adversary may be able toobtain against a cryptographic scheme can be bounded by a function of the advantages of2.3 Computational Security

23

related adversaries against the underlying primitives (where these adversaries are derived
from the adversary against the full scheme), then one can obtain security statements thatessentially state that the full scheme must be secure unless one of the underlying primitives
is vulnerable. (Some care must be taken as this intuitive interpretation may sometimes be
too simplicistic, e.g. if a derived adversary incurs a significant slowdown compared with theoriginal adversary that it is based on.)Security assumptions made for primitives often have basically the following form: “Noadversary running in at most n steps can achieve an advantage better than .” Observethat while such statements may appear to describe an inherent property of the primitive inquestion, in fact they implicitly make assumptions on the adversaries as well. The reason
is that the machine model that adversaries are supposed to run in is left unspecified. (Forexample, one “step of computation” in some machine formalization might require a large
number of steps in another one.) The formal assumption describes restrictions on what
adversaries can achieve, but nothing specific about the primitive taken for itself.
In principle we could fill this void and define a precise machine model for adversaries.
Then, with respect to this particular model, the security assumption would be either true or
false. For some possible models, it will be true, for others it will be false. (We could consider
a machine model in which the problem at hand can be solved immediately because there
is some specific built-in operation that achieves this.) Of course we usually hope that themodels in which the security assumption is false are contrived, and that for realistic ones it
is true.

2.3.3

Asymptotic Security Proofs

Often cryptographic schemes are thought to be parameterized by a security parameter, anon-negative integer k, which is possibly bounded from below, i.e. k ≥ k0 for some k0 . Key
generation, encryption and any other legitimate use of the cryptographic scheme is expected
to be possible in time polynomial in k (assuming appropriate length bounds for inputs suchas plaintexts). In such parameterized settings, we will usually be concerned with sets of keys
and of messages that have unbounded cardinality. It is understood that to make it possible
to describe cryptographic schemes through algorithms, elements of such sets will have to be
represented as words over some finite alphabet.
For example, for Diffie-Hellman (protocols 2.2, 2.3 and 2.4) using the multiplicative groupof some prime field, i.e. G = (Z/pZ)∗ , k could be the length of prime p in bits (here we haveto insist that k ≥ 2). Elements of G can be represented as bit strings of length k that containthe minimum positive integer in the respective residue class modulo p, expressed in binary.
The use of security parameters provides an approach to provable computational securityfor cryptographic schemes. A function f : N → R is called negligible if f (n) = O 1/P (n) for
any polynomial P , i.e. if for any m ∈ N there is an nm such that f (n) < 1/nm for n ≥ nm .
We want to call a cryptographic scheme secure according to some specified security notion if
breaking it is hard in the sense that any adversary with run-time bounded polynomially insecurity parameter k has advantage negligible in k. Observe that security statements of thisform are asymptotic.
As has already been noted in section 2.3.2, we cannot really hope for actual provable
computational security for public-key cryptography: remember that the famous question
whether the class of languages accepted by deterministic polynomial-time machines coincides
with the class of languages accepted by non-deterministic polynomial-time machines (P =

24

Public-Key Cryptography and Provable SecurityNP) remains unsettled, and observe that because NP algorithms can internally guess secretkeys, efficient adversaries could be constructed if P = NP. So we still have to confine to
reduction-based security proofs that rely on assumptions about the security of underlying
primitives (which, in turn, are captured in the presumed negligibility of the advantage of any
polynomially bounded adversary targeting the respective primitive).
One superficial advantage of asymptotic security results showing a negligible advantage
compared with security results describing concrete security as discussed in the previous section is that here we can appeal to well-known equivalences between different machine models:
asymptotic security statements do not depend on specific machine models. However, a canonical class of equivalent models exists only in asymptotics, and this in itself is a basic drawback.
Security statements that are asymptotic in the security parameter imply that, given any adversary, its advantage can be kept arbitrarily close to zero if only the security parameter ischosen sufficiently large (provided that the underlying primitives are indeed secure). However,when a cryptographic scheme is actually employed, one has to fix some specific value of the
security parameter, so this parameter clearly cannot change depending on which adversary
one considers. With the security parameter fixed, the problem degenerates to one with a finite
number of cases (since generating an instance of the problem is assumed to have polynomial
complexity). This means that the problem can now be solved in constant time. An adversary
against a public-key cryptosystem could even use a fixed table that maps each public key toa corresponding secret key to solve each instance of the problem instantly.
While thus an asymptotic statement obtained through a reduction-based security proof
does not really say anything about practical instantiations of the cryptographic scheme, it
can still be considered a valuable heuristic result: essentially, one can hope that the concrete
choice of the security parameter will be large enough such that the asymptotic result has aclose correspondence to reality.

2.3.4

The Random Oracle Model

One approach to heuristic security is the random oracle model [9]. Remember the remark (forprotocol 2.3 above) that it is convenient to assume that hash functions behave like randomly
chosen functions. The random oracle model formalizes this idealization by replacing concretehash functions by randomly chosen functions. The adversary’s advantage in the attack gameis measured under this random distribution. The adversary does not obtain a complete
description of the hash function. Instead, values of the hash function can only be obtained
individually by way of oracle queries: a random oracle is substituted for the hash function.
The intuition behind the random oracle model is that security proofs in this idealization
indicate that a cryptographic scheme is secure against generic attacks that do not exploit
specific properties of some particular hash function. However, clearly no specific choice of ahash function can behave like a random oracle – the random oracle model does not correspondto any explicit assumption on security properties of hash functions.
It is easy to see that it is already problematic to consider a hash function as a single fixed
function. A collision of a hash function
h : dom(h) → {0, 1}kwhere dom(h) ⊆ {0, 1}∗ is a pair (m0 , m1 ) of strings such that m0 6= m1 but
h(m0 ) = h(m1 ).

2.3 Computational Security

25

Unless # dom(h) ≤ 2k , it is clear that h will have a collision. If h behaves somehow “randomly”, one might expect that finding a collision would be difficult (if k is chosen sufficiently
large). However, if h is fixed, there are conceivably simple algorithms for “finding” a collision:
such algorithms do not have to do any actual work, they can simply output a collision of hthat is built into the algorithm. Hence, hash functions used in practice should be modeled
as keyed function families (hK )K∈K where a specific hash function hK , K ∈R K, is determined at system set-up time. Then the advantage of adversaries can be considered under
this random distribution. This approach makes it possible to formalize the security of hashfunctions including the intractability of finding collisions, but does not provide justification
for the random oracle model.
Particular doubt has been cast on the methodology of employing the random oracle model
for security proofs by showing that an essential discrepancy remaining between the keyed
function family model for practical hash functions and the random oracle model allows constructing cryptographic schemes that can be proven secure in the random oracle model, but
are insecure for any instantiation of the hash function [20, 21]. Descriptions of actual hashfunctions will be “small” (of polynomial size, considered asymptotically), while the complete
specification of a randomly chosen function as in the random oracle model would be “large”(require exponential size). The example constructions from [20, 21] use a diagonalization
technique to exploit this discrepancy.
These negative results have been presented in asymptotic form in [20, 21]. As we haveseen in section 2.3.3, asymptotic security statements cannot say anything on practical instantiations of cryptographic schemes anyway, so the published result is not directly meaningful.
However, the asymptotic form is not essential, and similar results could be obtained for particular machine models in non-asymptotic settings [19].


2.3.5

Conclusions

In sections 2.3.3 and 2.3.4, we have considered asymptotic security and the random oracle
model. No specific choice of a security parameter can be “asymptotic”, and no specificchoice of a hash function can be a “random oracle”; so security results should avoid theseconcepts if we want them to have a direct practical interpretation. In the following chapters,
provable security will be handled according to a reduction-based concrete-security approach:cryptographic schemes are built from simpler cryptographic primitives; the security of thecompound scheme can be related quantitatively to the security of the underlying primitives,
where security is expressed through the advantage that can be achieved by an adversary.
The security proofs will not refer explicitly to security parameters or to asymptotic security,and they will avoid random oracles. However, it is understood that the use of such concepts
might be appropriate to examine in more detail the security assumptions that we make on
cryptographic primitives. We will simply assume that appropriate primitives are available,
so this issue will remain out of sight. Since we do not have justification for the security
assumptions on primitives, in any case we end up relying on heuristical considerations, andwe cannot get far if we are not willing to do so.

26

Public-Key Cryptography and Provable Security

Chapter 3

Hybrid Public-Key Encryption:
The DHAES Construction
To improve over the security of the ElGamal public-key encryption scheme, which as we
will see does not resist extended notions of an attack, the scheme DHAES [1] was devised.
This scheme combines multiple cryptographic primitives: a key encapsulation mechanism(KEM), a one-time message authentication code (one-time MAC), and a symmetric cipher.
Constructions for public-key encryption that involve symmetric encryption are often called
hybrid.
DHAES stands for Diffie-Hellman Authenticated Encryption Scheme or Diffie-Hellman
Augmented Encryption Scheme. The scheme as originally published uses the Diffie-Hellman
key exchange mechanism as in protocol 2.4. A later variant of the scheme published as DHIES,
which stands for Diffie-Hellman Integrated Encryption Scheme [2], uses protocol 2.3 instead(there is some indication that this change of the KEM was ill-advised from a security pointof view [80]). Other KEMs can be used without changing the essence of the DHAES/DHIES
scheme. The generalization for arbitrary key encapsulation mechanisms was first laid out
in [30]. In the following, the term “the DHAES construction” refers to the general scheme
using any KEM.
In this chapter, we will look at the DHAES construction for arbitrary key encapsulation mechanisms, but only for specific symmetric ciphers, namely XOR-based stream ciphers(where the ciphertext is generated from the plaintext and vice versa by XORing a pseudorandom bit string) – a case that was accidentily not covered by the original security result in[1] and [2]. The security result for the DHAES construction that we will arrive at leans on[30].
Section 3.1 describes chosen-ciphertext attacks against public-key encryption schemes andshows that the ElGamal public-key encryption scheme is not secure under this strong notion.
Then section 3.2 describes the cryptographic primitives needed by the DHAES construction,and section 3.3 describes how they are used to encrypt and decrypt with DHAES. Finally,
section 3.4 shows how the security of DHAES follows from the security of the underlying
primitives.
27

28

3.1

Hybrid Public-Key Encryption: The DHAES Construction

Adaptive Chosen-Ciphertext Attacks

In section 2.3.1, we have looked at a basic security notion for public-key encryption, indistinguishability under chosen-plaintext attack (IND-CPA). In practice, adversaries are often
in a better position to launch an attack than provided in that attack model: they may beable to make up ciphertexts and submit these chosen ciphertexts for decryption. Dependingon the specific attack scenario, the decryption results may or may not be made completely
available to the adversary. We are interested in a very strong characterization of security for
public-key encryption, so we assume the worst and use attack models where the adversary
has access to a decryption oracle.
Remember that in the attack scenario for IND-CPA, the adversary chooses two messages
m0 and m1 , obtains the encryption of a random one mb of these, and then has to guess
whether b = 0 or b = 1. The adversary can be considered as running its attack in two stages:
first the find stage, which ends when the adversary outputs m0 and m1 , and then the guessstage, which starts when the adversary is given the challenge ciphertext. If we extend this
attack scenario to allow a chosen-ciphertext attack, we always provide the adversary with adecryption oracle for the find stage. The strongest notion of a chosen-ciphertext attack is anadaptive chosen-ciphertext attack [74], where the adversary also has access to a decryption
oracle in the guess stage; for the guess-stage oracle, we have to impose the restriction thatthe adversary may not use the literal challenge ciphertext as a query (otherwise, the oracle’s
answer would make it trivial to determine b for any sound public-key encryption scheme if
m0 6= m1 ).
Sometimes both non-adaptive chosen-ciphertext attacks (CCA1) and adaptive chosenciphertext attacks (CCA2) are considered in the literature, but usually only the strongest
notion of attack is relevant. In the following, the term chosen-ciphertext attack (CCA) without
further qualification is understood to refer to the adaptive kind.
Before we proceed to formalize CCA security for public-key encryption, first we define thenotion of a public-key encryption scheme more completely. Here we assume that all messages
are encoded as bit strings (if we start with a scheme defined for group elements, such as the
ElGamal encryption scheme as sketched in section 2.2, we have to add appropriate encoding
and decoding functionality to the system’s specification). For this definition, remember thatalgorithms are usually probabilistic (refer to the notational conventions at the beginning of
the present chapter). Note that our formalization uses no explicit security parameter; thiscorresponds to having some fixed security parameter built into the key generation algorithm.
Definition 3.1. A public-key encryption scheme
PKE
specifies a key generation algorithm
PKE.KeyGenthat produces key pairs (PK, SK) consisting of a public key PK and a secret key SK, analgorithm
PKE.Encryptusing the public key, and an algorithm
PKE.Decrypt3.1 Adaptive Chosen-Ciphertext Attacks

29

using the secret key. For a plaintext m (an arbitrary bit string, possibly subject to length
limitations for the specific public-key encryption scheme),
PKE.Encrypt(PK, m)
returns a bit string c, a ciphertext. On arbitrary input c0 ,PKE.Decrypt(SK, c0 )may either return some string m0 or fail and return the special value invalid. If the key pair
(PK, SK) has been produced by PKE.KeyGen and c has been produced by PKE.Encrypt(PK, m),then evaluation of PKE.Decrypt(SK, c) will return string m.
Security in the sense of indistinguishability under chosen-ciphertext attack (IND-CCA) is
described through the following attack game:
1. The adversary queries a key generation oracle, which uses PKE.KeyGen to determine akey pair(PK, SK)and responds with PK (while secretly storing SK).
2. [Find stage.] The adversary makes a sequence of queries to a decryption oracle. Eachquery is an arbitrary string s, and the oracle responds with PKE.Decrypt(SK, s).
3. The adversary chooses messages m0 and m1 subject only to the condition that |m0 | =|m1 | and sends them to an encryption oracle. The encryption oracle chooses a uniformly
random bit b ∈ {0, 1} and determinesc = PKE.Encrypt(PK, mb ),which is returned to the adversary as the challenge ciphertext.
4. [Guess stage.] The adversary again makes a sequence of queries to a decryption oracle
as in the find stage, where this time the decryption oracle refuses being asked for thechallenge ciphertext c (it returns invalid for this case).
5. The adversary outputs a bit eb ∈ {0, 1}.
The bit eb output by the adversary is supposed to be its guess for the value of b.
Now let A be any adversary in the above attack game, i.e. an interactive probabilistic
algorithm with bounded running time. Its CCA advantage against the public key encryption
scheme isAdvCCAPKE,A = Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0 .
Similarly to what we have seen in section 2.3.1, this can also be written as
2 · Pr[eb = b] −1.
2

Let us consider the security of the ElGamal public-key encryption scheme (see section 2.2).
If messages are encoded as group elements, then IND-CPA security (section 2.3.1) can be30

Hybrid Public-Key Encryption: The DHAES Construction

proven provided that the scheme is used in groups for which the so-called Decision DiffieHellman (DDH) assumption holds; see [85] for details on the reduction. (The DDH assumption
states essentially thatadversaries trying to tell apart the random distributions (g a , g b , g ab ) and(g a , g b , y) with a, b∈R 0, . . ., #(G)−1 , y∈R G cannot do significantly better than guess.) Now
let us consider ElGamal encryption under the stronger IND-CCA security notion. ElGamal
ciphertexts for plaintext m have the general structure (K, m + K), and for any group elementx, computing (K, x + m + K) yields a ciphertext corresponding to plaintext x + m. Thus,
given the challenge ciphertext, the adversary can easily derive a related ciphertext that may
be used as a query to the decryption oracle so that the plaintext can be recovered from theoracle’s reply simply by subtracting a group element. This makes it easy to successfully attack
the encryption scheme in the IND-CCA scenario; clearly, ElGamal encryption is not securein this sense.
Thus, if the IND-CCA notion of cryptographic security must be met, the ElGamal publickey encryption scheme is not sufficient. In this chapter, we will examine the DHAES construction, which achieves this goal.

3.2

Primitives for the DHAES Construction

The DHAES construction as presented in the following requires three underlying cryptographic primitives: a key encapsulation mechanism (KEM), a one-time message authentication code (one-time MAC), and a pseudo-random bit string generator for use in an XOR-based
stream cipher. (Note that DHAES/DHIES as described in [1] and [2] can use other symmetricciphers as well.)Definition 3.2. A key encapsulation mechanism
KEM
specifies a key generation algorithm
KEM.KeyGenthat produces key pairs (PK, SK) consisting of a public key PK and a secret key SK, analgorithm
KEM.Encryptusing the public key, and an algorithm
KEM.Decryptusing the secret key. In contrast with public-key encryption, the Encrypt algorithm of a key
encapsulation mechanism takes no input apart from the public key:
KEM.Encrypt(PK)generates a ciphertext K of a fixed length
KEM.CipherLen3.2 Primitives for the DHAES Construction

31

corresponding to a (pseudo-)random string K of a fixed length
KEM.OutLen
and outputs the pair (K, K). Evaluation of
KEM.Decrypt(SK, K)
will return said string K if the key pair (PK, SK) has been produced by KEM.KeyGen. On
arbitrary input K0 , the computation KEM.Decrypt(SK, K0 ) may either return some string K 0
or fail (return the special value invalid).
The random message K will be known both to the party running KEM.Encrypt(PK) and to
the secret key owner who runs KEM.Decrypt(SK, K). In this sense, ciphertext K encapsulates
the random message K. It can be used as a key for symmetric-key cryptography; hence theterm “key encapsulation”.
One choice for a key encapsulation mechanism is the Diffie-Hellman variant from protocol 2.4. KEM.CipherLen can be kept particularly small by using the group of rational points
on an appropriate elliptic curve [12] and using (except in internal computations) just x coordinates of points (see [55]). Specifications for various key encapsulation mechanisms can befound in [80].
Definition 3.3. A one-time message authentication code (one-time MAC)
MAC
specifies a key length
MAC.KeyLen,
an output length
MAC.OutLen,
and a deterministic algorithm that takes as input a key K of length MAC.KeyLen and a bit
string s (of theoretically arbitrary length, although practical realizations will typically havesome large fixed limit) and returns a string
MAC(K, s)of length MAC.OutLen.
Candidate one-time message authentication codes are UHASH [50] and HMAC [5]. (TheUHASH scheme is the combination of a key derivation function with an almost strongly
universal hash function [89] and is the core of UMAC as specified in [50]. Note that there isan earlier version of UMAC described in [11], for which security arguments are provided thatare based on a different approach.)Definition 3.4. A pseudo-random bit string generator
STREAM
specifies a key length
STREAM.KeyLen,

32

Hybrid Public-Key Encryption: The DHAES Construction

an output length
STREAM.OutLen,
and a deterministic algorithm taking as input a key K of length STREAM.KeyLen and generating an output string
STREAM(K)of length STREAM.OutLen. Alternatively,
STREAM.OutLen
may be infinite; in this case, for any integer n,
STREAM(K, n)
generates an output stream of length n.
A convenient example implementation is the so-called counter mode of a symmetric blockcipher (the output sequence is the prefix of appropriate length of EK (0) || EK (1) || EK (2) || . . .
where EK denotes block cipher encryption using key K; see [6] and [52]).

3.3

The DHAES Public-Key Encryption Scheme

We specify DHAES as a public-key encryption scheme PKE following definition 3.1, assumingthat primitives KEM, MAC, and STREAM as described in section 3.2 are available. We require
that
KEM.OutLen = MAC.KeyLen + STREAM.KeyLen
and that
STREAM.OutLen = ∞.
DHAES permits encrypting messages of arbitrary length.
The key generation algorithm PKE.KeyGen for DHAES is simply KEM.KeyGen.
The encryption algorithm determines PKE.Encrypt(PK, m) as follows:
1. Use KEM.Encrypt(PK) to generate a pair (K, K).
2. Split K in the form
K = KMAC || KSTREAM
such that |KMAC | = MAC.KeyLen (and thus |KSTREAM | = STREAM.KeyLen).
3. Compute C = m ⊕ STREAM(KSTREAM , |m|).
4. Compute M = MAC(KMAC , C).
5. Return the ciphertext K || M || C.
The decryption algorithm computes PKE.Decrypt(PK, K || M || C) as follows (note thatthe ciphertext can be uniquely split into its three components because KEM.CipherLen and
MAC.OutLen are fixed):

3.4 The Security of the DHAES Construction

33

1. Compute
K = KEM.Decrypt(SK, K).
If this computation fails, abort with an error (return invalid).
2. Split K in the form
K = KMAC || KSTREAM
such that |KMAC | = MAC.KeyLen.
3. Computeand test whether

f = MAC(KM
MAC , C)f = M.
M

If this is not the case, abort with an error (return invalid).
4. Return the string
C ⊕ STREAM(KSTREAM , |C|)
as decryption result.

3.4

The Security of the DHAES Construction

In section 3.1, we have seen how the security of a public-key encryption scheme against
adaptive chosen-ciphertext attacks can be captured quantitatively. The DHAES construction
is designed to be secure against such attacks provided that the underlying primitives fulfill
certain security notions.
The present section first defines according quantitative expressions of security for theprimitives used in the DHAES construction (sections 3.4.1, 3.4.2, and 3.4.3) and then gives asecurity result that relates the IND-CCA security of DHAES to the security of these primitives(section 3.4.4).

3.4.1

Security of the Key Encapsulation Mechanism

Security against adaptive chosen-ciphertext attacks for the key encapsulation mechanism KEM
is expressed through the following attack game (cf. [30, section 7.1.2]):
1. The adversary queries a key generation oracle, which uses KEM.KeyGen to compute a
key pair(PK, SK)and responds with PK (and secretly stores SK).
2. The adversary makes a sequence of queries to a decryption oracle. Each query is anarbitrary string s of length KEM.CipherLen; the oracle responds with
KEM.Decrypt(SK, s).
Thus each oracle response is either a string of length KEM.OutLen or the special
value invalid.

34

Hybrid Public-Key Encryption: The DHAES Construction

3. The adversary queries a key encapsulation oracle, which works as follows: it uses
KEM.Encrypt(PK)to obtain a pair (K0 , Koracle ), it generates a uniformly randomly string K1 such that
|K0 | = |K1 |, chooses a uniformly random bit bKEM ∈ {0, 1}, and responds with
(KbKEM , Koracle )as challenge.
4. The adversary again makes a sequence of queries to a decryption oracle as in stage 2,
where this time the oracle refuses the specific query Koracle (and responds invalid for thiscase).
5. The adversary outputs a bit ebKEM ∈ {0, 1}.
The CCA advantage of an adversary A (an interactive probabilistic algorithm with boundedrunning time) against KEM in this attack game is








AdvCCAKEM,A = Pr ebKEM = 1 | bKEM = 1 − Pr ebKEM = 1 | bKEM = 0 .
This can also be written as
2 · Pr[ebKEM = bKEM ] −

3.4.2

1
.
2

Security of the One-Time Message Authentication CodeTo express the security of MAC, we use the following attack game (cf. [30, section 7.2.2]:
1. The adversary submits a string s to a MAC oracle. This oracle generates a uniformly
random string K of length MAC.KeyLen and responds with MAC(K, s).
2. The adversary outputs a list (s1 , t1 ), (s2 , t2 ), . . ., (sm , tm ) of pairs of strings.
An adversary A again is an interactive probabilistic algorithm with bounded running time;note that the running time bound implies a bound on the length m of the list. We say thatadversary A has produced a forgery if
MAC(K, sk ) = tk
and sk 6= s for some k (1 ≤ k ≤ m). The adversary’s advantage against MAC, denoted
AdvForgeMAC,A ,is the probability that it produces a forgery in the above game.

3.4 The Security of the DHAES Construction

3.4.3

35

Security of the Pseudo-Random Bit String Generator

To express the security of STREAM, we use the following attack game:
1. The adversary queries a bit string oracle. This oracle generates a uniformly random
string K of length STREAM.KeyLen, computes stream 0 = STREAM(K), generates a
uniformly random string stream 1 with |stream 0 | = |stream 1 |, chooses a uniformly random bit bSTREAM ∈ {0, 1}, and responds withstream b
as challenge.
2. The adversary outputs a bit ebSTREAM ∈ {0, 1}.
The advantage of an adversary A (again an interactive probabilistic algorithm with boundedrunning time) against STREAM is
AdvSTREAMA =









Pr ebSTREAM = 1 | bSTREAM = 1 − Pr ebSTREAM = 1 | bSTREAM = 0 ,which can also be written as
2 · Pr[ebSTREAM = bSTREAM ] −

3.4.4

1
.
2

Security Result for the DHAES Construction

Let A be an adversary launching an adaptive chosen-ciphertext attack (see the attack gamein section 3.1) against DHAES with some key encapsulation mechanism KEM, some one-time
message authentication code MAC, and some pseudo-random bit string generator STREAM.
It can be shown that there are adversaries A1 , A2 , A3 against KEM, MAC, STREAM all having
essentially the same running time as A such that

AdvCCAPKE,A ≤ 2 · AdvCCAKEM,A1 + AdvForgeMAC,A2 + AdvSTREAM,A3 .
This quantitative security result can be interpreted as saying essentially that if DHAES isnot secure, then this is because one of the underlying cryptographic primitives is not secure.
In the remainder of this section, we will prove this result. Let G0 denote the attack gamedescribed in section 3.1. We will modify it in multiple steps, essentially disabling the underlying cryptographic schemes (key encapsulation mechanism, one-time message authentication
code, and pseudo-random bit string generator) one after another.
For DHAES, stage 3 (invocation of the encryption oracle) in the attack game from section 3.1 can be expressed as follows. First the adversary submits messages m0 and m1
such that |m0 | = |m1 |. The encryption oracle uses KEM.Encrypt(PK) to generate a pair
(Koracle , Koracle ) and splits Koracle in the form
Koracle = KMAC || KSTREAM
such that |KMAC | = MAC.KeyLen. Then it chooses a uniformly random bit b ∈ {0, 1}, computes
C = mb ⊕ STREAM(KSTREAM , |mb |)36Hybrid Public-Key Encryption: The DHAES Construction

and
M = MAC(KMAC , C),
and returns
Koracle || M || C
as challenge ciphertext. In the following, when we talk about the encryption oracle stage, it
is understood that we refer to this procedure.
G1 is like G0 except that a uniformly random string is used for Koracle , whereas Koracle isstill generated by KEM.Encrypt(PK). In the decryption oracle, Koracle is substituted wheneverKEM.Decrypt(SK, Koracle ) would have to be computed. This applies to both the find and theguess stage, i.e. stages 2 and 4 in the attack game from section 3.1. Thus, the invocationof KEM.Encrypt(PK) to generate Koracle must be advanced from stage 3 to an earlier stage.
In G0 , this is only a descriptive change and does not affect the behavior observed by theadversary.
G2 is like G1 except that the decryption oracle always responds with invalid when facedwith any query prefixed with string Koracle .
G3 is like G2 except that the encryption oracle uses a uniformly random string stream of
the appropriate length instead of computing STREAM(KSTREAM , |mb |).
Now we consider an adversary A as in section 3.1, exposed to these different
attack gamese
Gx , 0 ≤ x ≤ 3, and look at the respective success probabilities Pr Gx b = b . Based on A,
adversaries A1 , A2 , A3 against KEM, MAC, STREAM will be built all having essentially thesame running time as A.
A1 attacks KEM as follows (cf. section 3.4.1). At first, it generates b ∈ {0, 1} uniformly at random and queries its key encapsulation oracle to obtain a pair (Koracle , Koracle ).
Then, it runs the adversary A, playing the roles of the decryption oracle and encryption oracle: when A queries its decryption oracle, A1 uses its own decryption oracle tocompute KEM.Decrypt(SK, K) when performing the decryption algorithm from section 3.3,
substituting Koracle when KEM.Decrypt(SK, Koracle ) would have to be computed; when A
queries its encryption oracle, A1 performs the encryption oracle stage using the pregenerated pair (Koracle , Koracle ) and the pregenerated bit b. Finally, when A outputs its bit eb, A1
outputs 1 if eb = b and 0 otherwise. Observe that








Pr G1 eb = b − Pr G0 eb = b = AdvCCAKEM,A1(G0 corresponds to bKEM = 0, G1 corresponds to bKEM = 1 in section 3.4.1).
A2 attacks MAC as follows (cf. section 3.4.2). At first, it generates b ∈ {0, 1} and astring KSTREAM of length STREAM.KeyLen uniformly at random and uses KEM.Encrypt(PK)to generate Koracle . Then, it runs the adversary A, playing the roles of the key generation
oracle (so that A2 knows SK), decryption oracle, and encryption oracle. Whenever A submits
any query K||M||C to the decryption oracle, A2 adds the pair (C, M) to its own output; queries
prefixed with Koracle are refused, all other questions are answered using SK. In the encryption
oracle stage, A2 substitutes the pregenerated string KSTREAM and the pregenerated bit b, andit invokes its MAC oracle on C instead of using MAC directly to obtain M for the challenge
ciphertext. A’s final output bit eb is ignored. Observe that








Pr G2 eb = b − Pr G1 eb = b ≤ AdvForgeMAC,A2

3.4 The Security of the DHAES Construction

37(A2 runs A as in game G2 , and A would observe different behavior in game G1 only in thecases where a forgery is produced).
A3 attacks STREAM as follows (cf. section 3.4.3). First, it generates b ∈ {0, 1} and a string
Koracle of length KEM.OutLen uniformly at random. Then, it runs the adversary A, playing
the roles of the key generation oracle, encryption oracle, and decryption oracle, substituting
the pregenerated string Koracle and the pregenerated bit b in the encryption oracle stage, andrefusing any decryption oracle query prefixed with Koracle (both in the find stage and in theguess stage). When A outputs its bit eb, A3 outputs 1 if eb = b and 0 otherwise. Observe that








Pr G3 eb = b − Pr G2 eb = b = AdvSTREAM,A3(G2 corresponds to bSTREAM = 0, G3 corresponds to bSTREAM = 1 in section 3.4.3).
Finally observe that Pr G3 eb = b = 21 .
From this we obtain the inequality
AdvCCAPKE,A = 2 ·
=2·



1
− Pr G0 eb = b
2
X 

1≤x≤3







Pr Gx eb = b − Pr Gx−1 eb = b≤ 2 · AdvCCAKEM,A1 + AdvForgeMAC,A2 + AdvSTREAM,A3 ,which concludes the proof.

38

Hybrid Public-Key Encryption: The DHAES Construction

Chapter 4

A Public-Key Cryptosystem for
Length-Preserving Chaumian Mixes
Chaum’s mix concept [24] is intended to allow users to send untraceable electronic mailwithout having to trust a single authority. The idea is to use a number of intermediates suchthat it suffices for just one of these to be trustworthy in order to achieve untraceability. The
sender does not have to decide which particular intermediate he is willing to trust, he just must
be convinced that at least one in a given list will behave as expected. These intermediates,
the mixes, are remailers accepting public-key encrypted input. Messages must be of a fixed
size (shorter messages can be padded, longer messages can be split into multiple parts). To
send a message, it is routed through a chain of mixes M1 , . . ., Mn : the sender obtains the
public key of each mix; then he recursively encrypts the message(including the address ofthe final recipient) yielding EM1 EM2 (. . . EMn (payload ) . . .) where EMi denotes encryption
with Mi ’s public key, and sends the resulting ciphertext to mix M1 . Each mix removes thecorresponding layer of encryption and forwards the decrypted message to the next mix; thus
mix Mn will finally recover payload .
Each mix is expected to collect a large batch of messages before forwarding the decryption
results. The messages in the batch must be reordered (mixed) to prevent message tracing.
It is important to prevent replay attacks: a mix must not process the same message twice,or active adversaries would be able to trace messages by duplicating them at submission tocause multiple delivery. (Timestamps can be used to limit the timespan for which mixes haveto remember which messages they have already processed; see [24] and [29].)
Usually it is desireable to allow source routing, i.e. let senders choose mix chains on a
per-message basis. This increases the flexibility of the whole scheme: senders can make use of
new mixes that go into operation, and they can avoid mixes that appear not to work properly;
in particular, they can avoid mixes that suppress messages (be it intentionally or because oftechnical problems), which might be noticed when sending probe messages to oneself over mix
chains. For source routing, in the recursively encrypted message, each layer must contain theaddress of the next mix in the chain so that each mix knows where to forward the message.
A problem with the straightforward implementation of source routing is that messages will
shrink as they proceed through the chain, not only because of the forwarding address for eachlayer that must be included, but also because public-key encryption increases message size.
For optimal untraceability, we need length-preserving mixes: the messages that mixes receive
should essentially look like the resulting messages that they forward to other mixes.
39

40

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

A construction for length-preserving mixes is given in [24] (a variant of this is used in thefielded system Mixmaster [56]): mix messages consist of a fixed number of slots of a fixed
size. The first slot is public-key encrypted so that it can be read by the first mix in the
chain. Besides control information directed at that mix (such as the address of the next mix
in the chain or, in case of the last mix, the address of the final recipient), decryption yields
a symmetric key that the mix uses to decrypt all the other slots. Then slots are shifted by
one position: the decryption of the second slot becomes the new first slot, and so on. A new
final slot is added consisting of random (garbage) data to obtain a mix message of the desired
fixed length, which can then be forwarded to the next mix. On the way through the chain,each mix message consists of a number of slots with valid data followed by enough slots withgarbage to fill all available slots; mixes are oblivious of how many slots contain valid dataand how many are random. Each mix in the chain, when decrypting and shifting the slots,
will “decrypt” the garbage slots already present and add a new final slot, thus increasing thenumber of garbage slots by one. We note that while the transformation of an incoming mix
message to the corresponding outgoing mix message is length-preserving, the decryption step
itself is actually length-expanding because some of the data obtained by decryption is control
data intended for the current mix.
The problem with this slot-based approach for obtaining a hybrid public-key cryptosystemwith length-expanding decryption is that it is not secure against active attacks: assume thatan adversary controls at least one mix, and that all senders submit well-formed messages.
Now when the victim submits a message, the adversary can mark it by modifying one of theslots. This mark will persist as the message is forwarded through the mix chain: due to thedecryption and slot shifting performed by each mix, the corresponding slot will always besomehow different from what it should look like (whereas unmarked messages will not showsuch defects). If the final mix is controlled by the adversary, the adversary may be able tonotice the modification, e.g. detect a region of garbage bits in an otherwise comprehensible
message, and thus break untraceability.
To rule out such attacks, the public-key cryptosystem should provide security against
adaptive chosen ciphertext attacks (CCA security). The usual notion of CCA security for
public-key encryption schemes as presented in section 3.1 is not applicable to public-key
cryptosystems with length-expanding decryption because the encryption operation must be
defined differently here: encryption cannot be treated as an atomic black-box operation that,given a fixed public key, takes a plaintext and returns a ciphertext (within this approach,length-expanding decryption could not recover the original plaintext). Rather, the encryption process that we will use first is input part of the desired ciphertext and determines acorresponding part of what will be the decryption result (it is this step that provides length
expansion); then it is input the payload plaintext and finally outputs the complete ciphertext,
which includes the portion requested in the first input.
Section 4.1 describes a secure and practical hybrid construction for length-preserving
mixes, which is also more flexible than the slot-based approach. The structure of each layerof encryption resembles that of the public-key encryption scheme DHAES (see chapter 3).
Section 4.2 discusses appropriate security notions and gives provable security results for theconstruction.
This chapter shows essentially how Mixmaster ([56], [64]) should have been specified tobe cryptographically secure against active attacks. (Note that an entirely different model ofoperation for mix networks is assumed by Ohkubo and Abe [68] and Jakobsson and Juels [44]:these constructions assume the existence of a shared authenticated bulletin board, whereas

4.1 The Mix Encryption Scheme

41

here we are interested in an open system that can be used with point-to-point communicationby e-mail or similar means.) Various ideas and techniques that are familiar from the previous
chapter on the DHAES construction are transferred to fit the new notions of security neededin the context of length-preserving mixes.

4.1

The Mix Encryption Scheme

The construction presented in the following allows much flexibility in the choice of cryptographic schemes, even in a single chain. The single parameter that must be fixed for all mixes
is the desired mix message length `. Also it may be desireable to define a maximum length forthe actual message payload, i.e. the part of the plaintext as recovered by the final mix thatcan be chosen by the sender: as a message proceeds through the mix chain, more and more of
the data will be pseudo-random gibberish; the length of the useful part of the final plaintext
reveals that chains leaving less than this amount cannot have been used. The length n of themix chain (i.e. the number of consecutive mixes) need not be fixed.
For purposes of exposition, we number the mixes M1 , . . ., Mn according to their positionin the chain chosen by the sender. (Note that in practice the same mix might appear multiple
times in one chain.) For each mix Mi , the following must be defined and, with the exceptionof the secret key SKMi , known to senders who want to use the mix:
• A key encapsulation mechanism
KEMMi(see definition 3.2) and a key pair
(PKMi , SKMi )for this key encapsulation mechanism as generated by
KEMMi .KeyGen.
• A one-time message authentication code
MACMi
(see definition 3.3). In our construction, MACMi will only be used for strings s of fixed
length ` − KEMMi .CipherLen − MACMi .OutLen.
• A pseudo-random bit string generator
STREAMMi(see definition 3.4) with a fixed output size
STREAMMi .OutLen.
This will be used for an XOR-based stream cipher.

42

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes• An integer
PlainLenMi
specifying the length of the prefix of each decrypted message that is considered control
data directed to mix MMi and will not be forwarded. (This is the amount of message
expansion: the decrypted message minus the prefix must be of size ` because that iswhat will be sent to the next mix.)
The parameters must fulfill the following conditions:

4.1.1

KEMMi .CipherLen + MACMi .OutLen + PlainLenMi < `(4.1)

KEMMi .OutLen = STREAMMi .KeyLen + MACMi .KeyLen(4.2)

STREAMMi .OutLen = PlainLenMi + `(4.3)

Encryption

We now describe encryption for sending a message through a chain M1 , . . ., Mn . Let payload
be the message of length|payload | = ` −X(KEMMi .CipherLen + MACMi .OutLen + PlainLenMi )

(4.4)

1≤i≤n

(messages shorter than this maximum should be randomly padded on the right). For each i,let plain i be the control message of length PlainLenMi directed to the respective mix. The
encryption algorithm for these arguments is denoted
chain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload )orchain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload ; λ)where λ is the empty string. The algorithm is defined recursively. Let 1 ≤ i ≤ n, and let Ci
be a string of length|Ci | =

X

(KEMMk .CipherLen + MACMk .OutLen + PlainLenMk )

(4.5)

1≤k<i

(thus specifically |C1 | = 0, i.e. C1 is the empty string). Then algorithm
chain encrypt Mi ,...,Mn (plain i , . . ., plain n ; payload ; Ci )works as follows:
1. Use KEMMi .Encrypt(PKMi ) to generate a pair (Ki , Ki ).
2. Split Ki in the form
Ki = Ki,MAC || Ki,STREAM
such that |Ki,MAC | = MACMi .KeyLen (and, by (4.2), |Ki,STREAM | = STREAMMi .KeyLen).

4.1 The Mix Encryption Scheme

43

3. Compute STREAMMi (Ki,STREAM ) and split this string in the form
stream i,L || stream i,Rsuch that the left part stream i,L is of length` − |Ci | − KEMMi .CipherLen − MACMi .OutLen.
4. For i = n (last mix), by (4.4) and (4.5) it follows that |stream n,L | = PlainLenn +|payload |.
In this case, setCn = stream n,L ⊕ (plain n || payload ) || Cn .
Otherwise, let
Ci+1 = stream i,R ⊕ (Ci || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi ),by recursion computexi = chain encrypt Mi+1 ,...,Mn (plain i+1 , . . ., plain n ; payload ; Ci+1 ),and letCi = stream i,L ⊕ (plain i || prefix|stream i,L |−PlainLenM (xi )) || Ci .
i

5. Compute Mi = MACi (Ki,MAC , Ci ).
6. Return the ciphertext
Ki || Mi || Ci ,which is of length `.
The following illustration depicts a ciphertext generated by the encryption algorithm for achain of length three, namely
chain encrypt M1 ,M2 ,M3 (plain 1 , plain 2 , plain 3 ; payload ).
In the illustration, we have concatenation horizontally and XOR vertically (i.e. boxes in thesame row represent bit strings that are concatenated, and the ciphertext is the XOR of themultiple rows shown).
plain 2 K3plain 1 K2
K1

4.1.2

M1

M2

plain 3 payload
stream 3,L
M3
stream 2,Lstream 1,L

Decryption

The decryption algorithm for mix Mi (1 ≤ i ≤ n) works as follows, given a length-` ciphertext
K || M || C (split into its three components according to parameters KEMMi .CipherLen = |K|
and MACMi .OutLen = |M|). We denote it
mix decrypt Mi (K || M || C).
Remember that Mi in general is not aware of the mix chain used by the sender or even of its
own position i in the chain.

44

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

1. Compute
K = KEMMi .Decrypt(SKMi , K).
If this computation fails, abort with an error (return invalid).
2. Split K in the form
K = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen.
3. Computef = MAC (KM
Mi
MAC , C)and test whether

f = M.
M

If this is not the case, abort with an error (return invalid).
4. Compute the string
stream = STREAMMi (KSTREAM )of length STREAMMi .OutLen.
5. Computestream ⊕ (C || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi )and split the resulting string in the form
plain i || P
where plain i is of length PlainLenMi (and thus, by (4.3), P is of length `).
6. Return the pair (plain i , P ).
If this algorithm finishes without an error, plain i is a control message directed to the current
mix, and P is the message to be forwarded to another mix or to the final recipient (as requestedby the control message).
It is straightforward to verify that for ciphertexts computed as
chain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload ),iterative decryption by mixes M1 , . . ., Mn will indeed work without an error and recover therespective strings plain i and finally also the message payload concatenated with some (useless)extra data.
Continuing the example at the end of section 4.1.2, we look at illustrations for decryption.
The result obtained by mix M1 when applying the decryption algorithm given above to theciphertext generated as
chain encrypt M1 ,M2 ,M3 (plain 1 , plain 2 , plain 3 ; payload )is composed as follows:
plain 2 K3plain 1

K2

M2

plain 3 payload
stream 3,L
M3
stream 2,Lstream 1,R

4.2 Provable Security

45

The string plain 1 is directed to M1 . The remainder of the decryption result is a ciphertext thatshould be forwarded to the next mix in the chain, M2 , which will then obtain the following
result:plain 2

K3

M3

plain 3 payload
stream 3,Lstream 2,R
stream 1,R

Similarly, mix M3 will obtain the following final decryption result:plain 3

payloadstream 3,R
stream 2,R
stream 1,R

4.2

Provable Security

The mix concept is intended to provide security when at least one mix can be trusted andbehaves correctly. (However note that denial-of-service attacks by incorrectly operating mixes
cannot be ruled out; the only option is to avoid mixes that appear to malfunction.) Thus
we assume that some single mix Mi works as expected while all other mixes are controlled
by the adversary and may not follow the protocol (also the cryptographic schemes KEMMj ,MACMj , and STREAMMj associated with mixes Mj , j 6= i, might be not secure, and KEMMj
might even not be a valid key encapsulation mechanism according to the description given in
section 4.1).
This leaves only Mi to be attacked: outer layers of encryption for mixes that appear before
Mi in a mix chain are easily removed by the adversary and thus are not relevant for security;and inner layers of encryption for mixes that appear after Mi in a mix chain are involved in
the encryption process
chain encrypt Mi ,...,Mn (plain i , . . ., plain n ; payload ; Ci )described in section 4.1.1, but cannot provide protection against the adversary.
An important security property for mixes is unlinkability: an adversary who observes abatch of encrypted messages as these are sent to a mix and who sees the resulting decrypted
messages when these are forwarded elsewhere should not be able to tell better than by chance
which decrypted messages correspond to which encrypted messages.
Beyond this basic security notion, we also want to achieve security against active attacks.
As noted in the introduction the the current chapter, it is crucial to detect message replay
and ignore replayed message. However, this does not rule out active attacks based on message
modifications. To show that our construction for length-preserving mixes is secure against
this kind of attacks, we will model an active adversary who is able to launch an adaptive
chosen ciphertext attack (CCA).
We point out that in the model of operation that we assume, unlinkability cannot be fully
guaranteed in the presence of active attacks: an active adversary who suppresses all but asingle one of the legitimate encrypted messages in a batch and substitutes new messages for46

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

them can easily trace the remaining legitimate message. This can be avoided only heuristically(each sender of mix messages should occasionally route a message to himself to see if it gets
through). To avoid related flooding attacks (where an adversary injects lots of messages tocause a mix to process all messages currently in the pool), mixes should not start a new batch
whenever a certain fixed number of messages has arrived; instead, each batch should be kept
open for additional messages during some time frame.
Sections 4.2.1 and 4.2.2 show how the security of the mix construction can be captured
formally by describing unlinkability and CCA security, respectively. We have already seen
security definitions for the underlying key encapsulation mechanism (section 3.4.1), one-time
message authentication code (section 3.4.2), and pseudo-random bit string generator (section 3.4.3). Section 4.2.3 presents security results that relate the security of the mix encryption scheme to the security of these primitives: we will see that if the mix encryption scheme
is not secure, then this is because one of the underlying cryptographic schemes is not secure.

4.2.1

Unlinkability of the Mix Encryption Scheme

An intuitive approach to defining unlinkability is as follows: the adversary sees a batch of
m ciphertexts and a random permutation of the resulting m decryption results; for eachdecryption result, the adversary makes a guess on the index of the corresponding ciphertext.
With random guessing, the expected number of correct guesses is one. An adversary who can
do better than this breaks unlinkability.
More specifically, we let the adversary select the plaintexts as far as possible (rememberthat as we have length-expanding decryption, it is not possible to choose all of the decryption
result arbitrarily when generating a ciphertext). In the formal definition, we confine to asetting with two plaintexts where only one ciphertext is shown to the adversary (an adversary
in the unrestricted setting can be used to build an adversary in this setting). This is captured
in the following attack game:
1. The adversary queries a key generation oracle, which uses KEMMi .KeyGen to computea key pair
(PK, SK)and responds with PK (and secretly stores SK).
2. The adversary uses an encryption oracle as follows (cf. the encryption algorithm
from section 4.1.1 in the case of a length-1 mix chain, i.e. with no recursion and |Ci | = 0):• The adversary submits a pair of string pairs(plain i,0 , m0 ), (plain i,1 , m1 )where|plain i,b | = PlainLenMi
and|mb | = ` − KEMMi .CipherLen − MACMi .OutLen − PlainLenMi
for b = 0, 1.

4.2 Provable Security

47• The encryption oracle chooses a bit b ∈ {0, 1} uniformly at random. Then it uses
KEMMi .Encrypt(PK) to generate a pair (Koracle , Koracle ) and splits Koracle in theform
Koracle = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen; it computes STREAMMi (KSTREAM ) and splits
the resulting string stream in the form
stream = stream L || stream R
such that |stream L | = ` − KEMMi .CipherLen − MACMi .OutLen; and it computes
C = stream L ⊕ (plain i,b || mb )andM = MACMi (KMAC , C).
Then it outputs the pair
(Koracle || M || C, stream R ).
3. The adversary outputs a bit eb ∈ {0, 1}.
The bit eb output by the adversary is supposed to be its guess for the value of b. Note thatthe decryption result corresponding to the ciphertext Koracle || M || C is(plain i,b , mb || stream R )(see section 4.1.2), and all of this except for the choice of the bit b is known to the adversary
in the above game.
Let A be any adversary (interactive probabilistic algorithm with bounded running time)in this attack game. Its advantage against unlinkability for Mi ’s instantiation of the mix
encryption scheme is








AdvLinkMi ,A = Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0= 2 · Pr[eb = b] −

4.2.2

1
.
2

CCA Security of the Mix Encryption SchemeDue to the recursive nature of our encryption algorithm for mix chains, we cannot directly
apply the usual definitions of security under adaptive chosen ciphertext attack (CCA) for ordinary public-key encryption as presented in section 3.1. We adapt the attack game described
there as follows to take into account the special properties of our construction:
1. The adversary queries a key generation oracle, which uses KEMMi .KeyGen to computea key pair
(PK, SK)and responds with PK (and secretly stores SK).

48

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

2. [Find stage.] The adversary makes a sequence of queries to a decryption oracle. Eachquery is an arbitrary string s of length `, and the oracle responds with
mix decrypt Mi (s),using the secret key SK from stage 1. That is, each oracle response is either a pair(plain, P ) where |plain| = PlainLenMi and |P | = `, or the special value invalid.
3. The adversary uses an interactive encryption oracle as follows (compare with the encryption algorithm in section 4.1.1):• First the adversary submits some string Ci subject only to the condition that0 ≤ |Ci | < ` − KEMMi .CipherLen − MACMi .OutLen.
• The interactive encryption oracle uses KEMMi .Encrypt(PK) to generate a pair
(Koracle , Koracle ) and splits Koracle in the form
Koracle = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen; it computes STREAMMi (KSTREAM ) and splits
the resulting string stream in the form
stream = stream L || stream R
such that |stream L | = `−|Ci |−KEMMi .CipherLen−MACMi .OutLen; and it computes
Ci+1 = stream R ⊕ (Ci || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi )and sends Ci+1 to the adversary.
• The adversary submits a pair of string pairs(plain i,0 , m0 ), (plain i,1 , m1 )satisfying|plain i,b | = PlainLenMi
and|mb | = ` − |Ci | − KEMMi .CipherLen − MACMi .OutLen − PlainLenMi
for b = 0, 1.
• The interactive encryption oracle chooses a uniformly random bit b ∈ {0, 1}, determinesC = stream L ⊕ (plain i,b || mb ) || Ciand
M = MACMi (KMAC , C),
and responds with the challenge ciphertext
Koracle || M || C.

4.2 Provable Security49

4. [Guess stage.] The adversary again makes a sequence of queries to a decryption oracle
as in stage 2, where this time the decryption oracle refuses being asked for the challenge
ciphertext Koracle || M || C from stage 3 (it returns invalid for this case).
5. The adversary outputs a bit eb ∈ {0, 1}.

The bit eb output by the adversary is its guess for the value of b.
The essential difference to the adaptive chosen ciphertext attack game for ordinary publickey encryption is that we have made the encryption oracle interactive to reflect the recursiveness of the encryption algorithm for mix chains, where encryption to mixes later in the chain
than Mi can have potentially arbitrary effects on a large part of the plaintext.
We look at illustrations for the ciphertext resulting from the invocation of the interactive
encryption oracle. As in previous illustrations, we have concatenation horizontally and XOR
vertically. The structure of the challenge ciphertext returned by the interactive encryption
oracle in the adaptive chosen ciphertext attack game is as follows:mb
stream L

plaini,b
KoracleM

Ci

Applying algorithm mix decrypt Mi from section 4.1.2 to this ciphertext would yield the following result:plain i,bmb

Ci
stream R

This can also be written as follows:
plain i,b

mb

Ci+1

Let A be any adversary (interactive probabilistic algorithm with bounded running time)in the above attack game. Its CCA advantage against Mi ’s instantiation of the mix encryption
scheme is








AdvCCAMi ,A = Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0= 2 · Pr[eb = b] −

4.2.3

1
.
2

Security Results

First let A be an adversary against the unlinkability of the mix encryption scheme, attacking
a mix Mi as described in section 4.2.1. It can be shown that there are adversaries A1 and A2
against KEMMi and STREAMMi , respectively, with essentially the same running time as A
such that
AdvLinkMi ,A ≤ 2 · AdvCCAKEMMi ,A1 + AdvSTREAMMi ,A2 .
Details of the proof of unlinkability follow below.
Now let A be an adversary against the CCA security of the mix encryption scheme,
attacking a mix Mi as described in section 4.2.2. It can be shown that there are adversaries
A1 , A2 , A3 against KEMMi , MACMi , STREAMMi all having essentially the same running timeas A such that

AdvCCAMi ,A ≤ 2 · AdvCCAKEMMi ,A1 + AdvForgeMACM ,A2 + AdvSTREAMMi ,A3 .
i

50

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

Details of the proof of CCA security follow below.
Proof of Unlinkability
We prove the security result for the unlinkability of the mix encryption scheme. Let G0 denotethe attack game from section 4.2.1. Let G1 be like G0 except that a uniformly random stringis used for Koracle , whereas Koracle is still generated by KEMMi .Encrypt(PK). Let G2 be like G1
except that the encryption oracle uses a uniformly random string stream instead of computing
STREAMMi (KSTREAM ).
Now we consider an adversary A as in section 4.2.1, exposed to these different
attackegames Gx , 0 ≤ x ≤ 2, and look at the respective success probabilities Pr Gx b = b . Basedon A, adversaries A1 and A2 against KEMMi and STREAMMi , respectively, will be built, eachwith essentially the same running time as A.
A1 attacks KEMMi as follows (cf. section 3.4.1; note that this A1 never actually uses its
decryption oracle). At first, it generates b ∈ {0, 1} uniformly at random. Then, it runs theadversary A; when A queries its encryption oracle, A1 queries its key encapsulation oracle toobtain a pair (Koracle , Koracle ) and performs stage 2 from section 4.2.1 using this pair and thepregenerated bit b. Finally, when A outputs its bit eb, A1 outputs 1 if eb = b and 0 otherwise.
Observe that

Pr G1 eb = b − Pr G0 eb = b = AdvCCAKEMMi ,A1(G0 corresponds to bKEM = 0, G1 corresponds to bKEM = 1 in section 3.4.1).
A2 attacks STREAMMi as follows (cf. section 3.4.3). First, it generates b ∈ {0, 1} and astring Koracle of length KEMMi .OutLen uniformly at random. Then, it runs the adversary A,
playing the role of the key generation oracle and the role of the encryption oracle, wherein it
substitutes the pregenerated string Koracle and the pregenerated bit b in stage 2 of section 4.2.1.
When A outputs its bit eb, A2 outputs 1 if eb = b and 0 otherwise. Observe that








Pr G2 eb = b − Pr G1 eb = b = AdvSTREAMMi ,A2(G1 corresponds to bSTREAM = 0, G2 corresponds to bSTREAM = 1 in section 3.4.3).
Finally observe that Pr G2 eb = b = 21 .
From this we obtain the inequality
AdvLinkMi ,A = 2 ·
=2·



1
− Pr G0 eb = b
2
X 

1≤x≤2







Pr Gx eb = b − Pr Gx−1 eb = b≤ 2 · AdvCCAKEMMi ,A1 + AdvSTREAMMi ,A2 ,which concludes the proof.
Proof of CCA Security
We prove the CCA security result given above. (This proof is similar to the security proof
for DHAES in section 3.4.4.) Let G0 denote the attack game from section 4.2.2. We will
modify it in multiple steps, essentially disabling the underlying cryptographic schemes (key

4.2 Provable Security

51

encapsulation mechanism, one-time message authentication code, and pseudo-random bit
string generator) one after another.
G1 is like G0 except that a uniformly random string is used for Koracle , whereas Koracle
is still generated by KEMMi .Encrypt(PK). In the decryption oracle, Koracle is substituted
whenever KEMMi .Decrypt(SK, Koracle ) would have to be computed. This applies to both thefind and the guess stage, i.e. stages 2 and 4 in the attack game from section 4.2.2. Thus,
the invocation of KEMMi .Encrypt(PK) to generate Koracle must be advanced from stage 3 toan earlier stage. In G0 , this is only a descriptive change and does not affect the behavior
observed by the adversary.
G2 is like G1 except that the decryption oracle always responds with invalid when facedwith any query prefixed with string Koracle .
G3 is like G2 except that the interactive encryption oracle uses a uniformly random string
stream instead of computing STREAMMi (KSTREAM ).
Now we consider an adversary A as in section 4.2.2, exposed to these different
attackgames Gx , 0 ≤ x ≤ 3, and look at the respective success probabilities Pr Gx eb = b . Basedon A, adversaries A1 , A2 , A3 against KEMMi , MACMi , STREAMMi will be built all having
essentially the same running time as A.
A1 attacks KEMMi as follows (cf. section 3.4.1). At first, it generates b ∈ {0, 1} uniformly at random and queries its key encapsulation oracle to obtain a pair (Koracle , Koracle ).
Then, it runs the adversary A, playing the roles of the decryption oracle and encryption
oracle: when A queries its decryption oracle, A1 uses its own decryption oracle to compute KEM.Decrypt(SK, K) when performing the decryption algorithm from section 4.1.2,
substituting Koracle when KEM.Decrypt(SK, Koracle ) would have to be computed; when A
queries its encryption oracle, A1 performs the encryption oracle stage using the pregenerated pair (Koracle , Koracle ) and the pregenerated bit b. Finally, when A outputs its bit eb, A1
outputs 1 if eb = b and 0 otherwise. Observe that








Pr G1 eb = b − Pr G0 eb = b = AdvCCAKEMMi ,A1(G0 corresponds to bKEM = 0, G1 corresponds to bKEM = 1 in section 3.4.1).
A2 attacks MACMi as follows (cf. section 3.4.2). At first, it generates b ∈ {0, 1} and a string
KSTREAM of length STREAMMi .KeyLen uniformly at random and uses KEMMi .Encrypt(PK) togenerate Koracle . Then, it runs the adversary A, playing the roles of the key generation oracle(so that A2 knows SK), decryption oracle, and interactive encryption oracle. Whenever A
submits any query K || M || C to the decryption oracle, A2 adds the pair (C, M) to its own
output; queries prefixed with Koracle are refused, all other questions are answered using SK. In
stage 3 of section 4.2.2 (encryption oracle), A2 substitutes the pregenerated string KSTREAM
and the pregenerated bit b, and it invokes its MAC oracle on C instead of using MACMi
directly to obtain M for the challenge ciphertext. A’s final output bit eb is ignored. Observe
that




Pr G2 eb = b − Pr G1 eb = b ≤ AdvForgeMACM ,A2i(A2 runs A as in game G2 , and A would observe different behavior in game G1 only in thecases where a forgery is produced).
A3 attacks STREAMMi as follows (cf. section 3.4.3). First, it generates b ∈ {0, 1} and astring Koracle of length KEMMi .OutLen uniformly at random. Then, it runs the adversary A,
playing the roles of the key generation oracle, interactive encryption oracle, and decryption

52

A Public-Key Cryptosystem for Length-Preserving Chaumian Mixes

oracle, substituting the pregenerated string Koracle and the pregenerated bit b in stage 3 ofsection 4.2.2 and refusing any decryption oracle query prefixed with Koracle (both in the findstage and in the guess stage). When A outputs its bit eb, A3 outputs 1 if eb = b and 0 otherwise.
Observe that
Pr G3 eb = b − Pr G2 eb = b = AdvSTREAMMi ,A3(G2 corresponds to bSTREAM = 0, G3 corresponds to bSTREAM = 1 in section 3.4.3).
Finally observe that Pr G3 eb = b = 12 .
From this we obtain the inequality
AdvCCAMi ,A = 2 ·
=2·



1
− Pr G0 eb = b
2
X 

1≤x≤3







Pr Gx eb = b − Pr Gx−1 eb = b≤ 2 · AdvCCAKEMMi ,A1 + AdvForgeMACM ,A2 + AdvSTREAMMi ,A3 ,iwhich concludes the proof.

Part II

Practice53

54

Chapter 5

Exponentiation andMulti-Exponentiation in
Public-Key Cryptography
Many schemes in public-key cryptography require computing powers
ge(exponentiation) or power products
Y

e

gj j

1≤j≤k

(multi-exponentiation) in a commutative semigroup G with neutral element 1G , e.g. in thegroup (Z/nZ)∗ or more generally in the multiplicative semigroup (Z/nZ) for some integer n,
in the group of rational points on an elliptic curve over a finite field [12], or in the class groupof an imaginary-quadratic order [40]. The exponents e, ej are non-negative integers with atypical length of a few hundred or a few thousand bits.
A specific example for the use of exponentiation that we have seen is Diffie-Hellman(protocols 2.2, 2.3 and 2.4), which can be used as an essential primitive in more complex
cryptographic schemes such as DHAES (see chapter 3) or the mix encryption scheme fromchapter 4. Another well-known example is RSA [76], which can be used both for public-key
encryption and for digital signatures. Multi-exponentiation with k = 2 is used e.g. for verification of DSA signatures [66] in groups (Z/nZ)∗ , and for verification of ECDSA signatures [4]in groups of rational points on elliptic curves over finite fields. Multi-exponentiation withk = 3 is used e.g. for verification of ElGamal signatures [35] in groups (Z/nZ)∗ . Larger valuesof k appear in protocols of Brands [16]. For k ≥ 2, in general it is unnecessarily inefficient tocompute the powers giei separately and then multiply them. Instead, specific algorithms for
multi-exponentiation can be applied.
Bases g, gj ∈ G sometimes are fixed between many computations. With fixed bases, it isoften advantageous to perform a single time a possibly relatively expensive precomputationin order to prepare a table that can be used to speed up exponentiations involving thosebases. (For multi-exponentiation, some of the bases may be fixed while others are variable:
for example, verifying a DSA [66] or ECDSA [4] signature involves computing the product of
two powers where one of the bases is part of domain parameters that can be shared betweena large number of signers while the other base is specific to a single signer.)55

56

Exponentiation and Multi-Exponentiation in Public-Key Cryptography

We assume that the exponents consist of independent random bits up to a respective
maximum bit-length; i.e., e and each ei is a uniformly distributed random integer in someinterval [0, 2L − 1]. In practice the actual distribution may differ, but for typical cases thissimplified assumption is reasonably close. In this setting, we consider general algorithms forarbitrary exponents; we do not examine algorithms based on tailor-made addition chains in
Zk for given e or e1 , . . ., ek (cf. [14]).
In the following chapters, we look at efficient algorithms for exponentiation and multiexponentiation based on either just multiplication in the given semigroup or optionally, inthe case of a group, on multiplication and division. This amounts to constructing addition
chains or addition-subtraction chains for the exponent e for exponentiation, and to constructing vector addition chains or vector addition-subtraction chains for the vector of exponents(e1 , . . ., ek ) for multi-exponentiation (see e.g. the survey [38]).
For purposes of performance analysis, we distinguish between squarings and general multiplications, as the former can often be implemented more efficiently. If we allow division,
our performance analysis does not distinguish between divisions and multiplications; this isreasonable e.g. for point groups of elliptic curves and for class groups of imaginary-quadratic
number fields, as inversion is almost immediate in such groups. If inversion is expensive (e.g. in(Z/nZ)∗ ), the group should be treated as a semigroup, i.e. inversion should be avoided.
Chapter 6 considers the case of a single exponentiation. Both left-to-right exponentiation
and right-to-left exponentiation methods are described. The sliding window and window NAF
technique and, as an improvement to the state of the art, the fractional window techniqueare presented. The fractional window technique is a generalization of the sliding window
and window NAF approach; it can be used to improve performance in devices with limited
storage.
Chapter 7 presents different approaches for computing power products. It looks at theconventional simultaneous exponentiation approach and presents an alternative strategy, interleaved exponentiation. The comparison shows that in general groups, sometimes the conventional method and sometimes interleaved exponentiation is more efficient. In groups where
inverting elements is easy (e.g. elliptic curves), the window-NAF based interleaved exponentiation method usually wins over the conventional method. Exponentiation and multiexponentiation with precomputation is also considered in that chapter.
Finally, chapter 8 considers specific techniques that can be used in elliptic curve cryptography if side-channel attacks are a concern. Following the convention to treat point groups asadditive rather than multiplicative, we speak of point multiplication (by a scalar) instead of
exponentiation. Two 2w -ary methods are presented that implement point multiplication ina fixed sequence of basic point operations to avoid exposing specific information on scalars:a left-to-right method based on special representations of scalars, and a right-to-left method
employing a special initialization stage.
Notational Conventions
We write e[j] for bit j of a non-negative integer e; thus e = j e[j]2j . For negative j, we
define that e[j] = 0. We write e[j 0 . . . j] for the integer consisting of the concatenation of bits
j 0 down to j of e; e.g., if
e = 101112 = 23,Pthene[3 . . . 1] = 0112 = 3

57

and
e[1 . . . −2] = 11002 = 12.
LSBm (e) = e[(m − 1) . . . 0] = e mod 2m is the integer formed by the m least significant bitsof c, and LSB(e) = LSB1 (e).
When writing digits, we use the convention that b denotes a digit of value −b where b isunderstood to be a positive integer; for example, 1012 = 22 − 20 = 3.

58

Exponentiation and Multi-Exponentiation in Public-Key CryptographyChapter 6

Efficient Exponentiation
In this chapter, we look at the basic case of exponentiation, computing g e . We will examine
methods for multi-exponentiation afterwards in chapter 7. Special strategies for exponentiation with precomputation where the base g is fixed for multiple exponentiations will also bepresented there (in section 7.4) because an important basic approach for exponentiation withprecomputation essentially turns exponentiations into multi-exponentiations.
Section 6.1 gives a framework for exponentiation algorithms. Section 6.2 describes within
the framework the sliding window exponentiation method and the window NAF exponentiation method. Section 6.3 presents an improvement to the state of the art, fractional windows,
a technique that closes a gap in the sliding window and window NAF methods and is usefulfor devices with limited storage: it can improve the performance by making use of memorythat would have to remain unused with the previously known methods. Then section 6.4
discusses how the exponent representations employed by this technique can be implemented
with small memory overhead.

6.1

A Framework for Exponentiation

Remember that we are interested in algorithms that compute g e using just multiplication in
the semigroup at hand, and optionally also division in the case of a group. (In specific groups,
additional useful efficiently computable endomorphisms may be available besides squaring andpossibly inversion; see e.g. [82]. This may lead to better exponentiation algorithms for thesegroups. We will not consider the special techniques for such groups.)
Many algorithms for computing g e for arbitrary large positive integers e in this setting fit
into one of two variants of a common framework, which we describe in this section. Exponents e are represented in base 2 ase=X

b i · 2i ,0≤i≤`using digits bi ∈ B ∪ {0} where B is some set of integers with 1 ∈ B. We call this a Brepresentation of e. Details of it are intrinsic to the specific exponentiation method. (Notethat for given B, B-representations are usually not canonical.) The elements of B must be
non-negative unless G is a group where inversion is possible in reasonable time. Given a
B-representation, left-to-right or right-to-left methods can be used for exponentiation. Leftto-right methods look at the elements bi starting at b` and proceed down to b0 ; right-to-left59

60

Efficient Exponentiation

methods start at b0 and proceed up to b` . Depending on how the values bi can be obtained
from an input value e, it may be easy to compute them on the fly instead of storing the Brepresentation beforehand. Left-to-right methods and right-to-left methods can be considereddual to each other (cf. the duality observation for representations of arbitrary addition chainsas directed multi-graphs in [47, p. 481]); both involve two stages.

6.1.1

Left-to-Right Methods

For left-to-right methods, first, in the precomputation stage, powers g b for all b ∈ B are
computed and stored; if division in G is permissible (because inversion is fast) and |b| ∈ B
for each b ∈ B, it suffices to precompute g b for those b ∈ B that are positive. We refer tothis collection of precomputed powers g b as the precomputed table. How to implement theprecomputation stage efficiently depends on the specific choice of B. In certain semigroups, inorder to accelerate the evaluation stage, precomputed elements can be represented in a special
way such that multiplications with these elements take less time (for example, precomputed
points on an elliptic curve may be converted from projective into affine representation [27]).
Note that if both the base element g and the digit set B are fixed, the precomputation stage
need not be repeated for multiple exponentiations if the precomputed table is kept in memory.
In cases without such fixed precomputation, B is usually a set consisting of small integers
such that the precomputation stage requires only a moderate amount of time. If


B = 1, 3, . . ., β

or

B=



± 1, ±3, . . ., ±βwith β ≥ 3 odd, the precomputation stage can be implemented with one squaring and (β−1)/2
multiplications as follows: first compute g 2 ; then iteratively compute g 3 = g · g 2 , . . . , g β =g β−2 · g 2 . This applies to all encoding techniques that will be presented in this chapter.
In the evaluation stage (or left-to-right stage) of a left-to-right method, given the precomputed table and the representation of e as digits bi , the following algorithm is executed tocompute the desired power from the precomputed elements g b :A ← 1G
for i = ` down to 0 do
A ← A2
if bi 6= 0 thenA ← A · g bi
return A
If division is permissible, the following modified algorithm can be used:A ← 1G
for i = ` down to 0 do
A ← A2
if bi 6= 0 thenif bi > 0 thenA ← A · g bielse
A ← A/g |bi |return A

6.1 A Framework for Exponentiation

61

Note that in these algorithms squarings can be omitted while A is 1G ; similarly, the firstmultiplication or division can be replaced by an assignment or an assignment followed byinversion of A.

6.1.2

Right-to-Left Methods

For right-to-left methods, no precomputed elements are used. Instead, first the right-to-leftstage yields values in a number of accumulators Ab , one for each positive element b ∈ B.
If division is permissible, B may contain negative digits; we require that |b| ∈ B for eachb ∈ B. Second, the result stage combines the accumulator values to obtain the final result.
The following algorithm description comprises both stages, but the result stage is condensed
into just the “return” line: how to implement it efficiently depends on the specific choice of B.
For brevity, we show just the algorithm with division (if B does not contain negative digits,
the “else”-branch will never be taken and can be left out).
{right-to-left stage}
for b ∈ B do
if b > 0 thenAb ← 1GA←g
for i = 0 to ` do
if bi 6= 0 thenif bi > 0 thenAbi ← Abi · A
else
A|bi | ← A|bi | /A
A ← A2{result stage}returnQb∈B Abb>0bThe squaring operation may be omitted in the final iteration as the resulting value of A will
not be used. For each Ab , the first multiplication or division can be replaced by an assignment
or an assignment followed by inversion (implementations can use flags to keep track which of
the Ab still contain the value 1G ). In case some Ab are still 1G at the end of the right-to-leftstage, operations can be saved in the result stage.
If
B = 1, 3, . . ., βor B = ± 1, ±3, . . ., ±βwith β odd (as in all encoding techniques that we will consider in this chapter), the result
stage can be implemented as follows ([90], [47, exercise 4.6.3-9]):for b = β to 3 step −2 doAb−3 ← Ab−3 · Ab
A1 ← A1 · A2b
return A1
This result stage algorithm requires (β − 1)/2 squarings and β − 1 multiplications.

62

6.2

Efficient Exponentiation

Sliding Window Exponentiation and Window NAF Exponentiation

A well-known method for exponentiation in semigroups is the sliding window technique(cf. [84, p. 912] and [38, section 3]). The encoding is parameterized by a small positive
integer w, the window size. The digit set is B = {1, 3, . . ., 2w − 1}. Encodings using these
digits can be computed on the fly by scanning the ordinary binary representation of the exponent either in left-to-right or in right-to-left direction: in the respective direction, repeatedly
look out for the first non-zero bit and then examine the sequence of w bits starting at thisbit position; one of the odd digits in B suffices to cover these w bits. For example, given
e = 88 = 10110002 , for window size w = 3, left-to-right scanning yields
101 10002→

510002 ,1 011 0002→

10030002 .

and right-to-left scanning yields

The length of the resulting representatione=X

b i · 2i

0≤i≤`

is at most that of the binary representation, i.e. a maximum index ` suffices to represent any(` + 1)-bit exponent. The average density of non-zero digits is 1/(w + 1) for e → ∞. (A more
precise analysis shows that the average number of non-zero digits in the representation for(` + 1)-bit exponents is`+1
w(w + 3)+1−
+ O(%−` )w+1
2(w + 1)2
for a real number % > 1 [26, Proposition 2.12]).
Including negative digits into B allows decreasing the average density: a {±1}-representation such that no two adjacent digits are non-zero (“property M” from [75]) is called a
non-adjacent form or NAF. More generally, letB=± 1, ±3, . . ., ±(2w − 1) ;then the following algorithm (from [82]) generates a B-representation of e such that at mostone of any w + 1 consecutive digits is non-zero. There is a unique representation with thisproperty, the width-(w + 1) NAF of e. We use the term window NAF (wNAF) if w isunderstood (a width-2 NAF can simply be called a NAF). This idea is also known as thesigned window approach; w + 1 can be considered the window size.
c←ei←0while c > 0 do
if LSB(c) = 1 thenb ← LSBw+1 (c)if b ≥ 2w thenb ← L − 2w+1

6.2 Sliding Window Exponentiation and Window NAF Exponentiation

63

c←c−b
else
b←0
bi ← b; i ← i + 1c ← c/2
return bi−1 , . . ., b0
Compared with the binary representation, the length can grow at most by one digit, so a
maximum index ` is sufficient to represent any `-bit exponent as a window NAF. Width(w + 1) NAFs have an average density of 1/(w + 2) for e → ∞ ([78], [81], [57], [82]). (Here amore precise analysis shows that the average number of non-zero digits in the representationfor `-bit exponents is`
w(w + 3)+1−
+ O(%−` )w+2
2(w + 2)2
for a real number % > 1 [26, Proposition 2.6]).
For left-to-right exponentiation using the sliding window or window NAF technique, theprecomputation stage has to compute g b for b ∈ {1, 3, . . ., 2w − 1}, which for w > 1 can beachieved with one squaring and 2w−1 − 1 multiplications (see section 6.1.1).
For right-to-left exponentiation using the sliding window or window NAF technique, theresult stage has to computeYAb bb∈{1,3,...,2w −1}

given accumulator values Ab resulting from the right-to-left stage. This can be done in 2w−1 −1squarings and 2w − 2 multiplications (see section 6.1.2).

6.2.1

Modified Window NAFs

The efficiency of exponentiation given a B-representation depends on the number of nonzero digits and the length of the representation (i.e. the minimum index I such that bi = 0
for i ≥ I). Window NAFs may have increased length compared with the ordinary binary
representation: e.g., the (width-2) NAF for 3 = 112 is 1012 , and the NAF for 7 = 1112 is10012 . (Remember that b denotes a digit of value −b.)
Such length expansion can easily be avoided in about half of the cases and thus exponentiation made more efficient by weakening the non-adjacency property (cf. [15] for the case ofwidth-2 NAFs). A modified window NAF (more precisely, a modified width-(w + 1) NAF) is a
B-representation obtained from a width-(w + 1) NAF as follows: if the w + 2 most significant
digits (ignoring any leading zeros) have the form
1 |0 0{z. . . 0} b,
w zerosthen substitute0 1 0| .{z. . 0} βw − 1 zeros

where β = 2w − b. For the above examples, we see that the modified (width-2) NAF for 3 is
112 , which is shorter than the NAF; however, the modified NAF for 7 remains 1001: this isa case where length expansion cannot be avoided without increasing the number of non-zerodigits.

64

Efficient Exponentiation

6.3

Fractional Windows

In small devices, the choice of w for exponentiation using the sliding window or window NAF
technique described in section 6.2 may be dictated by memory limitations. The exponentiation
algorithms given in section 6.1 need storage for 1+2w−1 elements of G, and thus memory may
be wasted: e.g., if sufficient storage is available for up to four elements, only three elements
can actually be used (w = 2).
In this section, we will see how the efficiency of exponentiation can be improved by using
fractional windows, a generalization of the sliding window and window NAF techniques.
Section 6.3.1 describes this new encoding technique for the case that negative digits areallowed (signed fractional windows). Section 6.3.2 describes a simpler variant for the casethat only non-negative digits are permissible (unsigned fractional windows).

6.3.1

Signed Fractional Windows

Let w ≥ 2 be an integer and m an odd integer such that 1 ≤ m ≤ 2w − 3. (We could
additionally allow the the border cases m = −1 and m = 2w − 1, which would turn out toyield the width-(w + 1) and width-(w + 2) NAF, respectively.) The digit set for the signed
fractional window representation with parameters w and m isB=

± 1, ±3, . . ., ±(2w + m) .

Let the mapping
digit : {0, 1, . . ., 2w+2 } → B ∪ {0}be defined as follows:• If x is even, then digit(x) = 0;
• otherwise if 0 < x ≤ 2w + m, then digit(x) = x;• otherwise if 2w + m < x < 3 · 2w − m, then digit(x) = x − 2w+1 ;• otherwise we have 3 · 2w − m ≤ x < 2w+2 and let digit(x) = x − 2w+2 .
Observe that if x is odd, then x−digit(x) ∈ {0, 2w+1 , 2w+2 }. The following algorithm encodes e
into signed fractional window representation:d ← LSBw+2 (e)c ← be/2w+2 ci←0while d 6= 0 ∨ c 6= 0 dob ← digit(d)bi ← b; i ← i + 1d←d−bd ← LSB(c) · 2w+1 + d/2
c ← bc/2c
return bi−1 , . . ., b0

6.3 Fractional Windows

65

This algorithm is a direct variant of the window NAF generation algorithm shown in section 6.2, but based on the new mapping digit. Here we have expressed the algorithm in a
way that shows that the loop is essentially a finite state machine (with 2w+1 + 1 states forstoring, after b has been subtracted from the previous value of d, the even number d with0 ≤ d ≤ 2w+2 ); new bits taken from c are considered input symbols and the generated digits bi
are considered output symbols.
The following table shows what can happen in the loop in the example case w = 2,
m = 1.
d
00012
00112
01012
01112
10012
10112
11012
11112

b = digit(d)
1
3
5
−1
1
−5
−3
−1

d−b
00002
00002
00002
10002
10002
100002
100002
100002

The average density achieved by the signed fractional window representation with parameters w and m is1
m+1
w + 2w + 2
for e → ∞. (Assume that an endless sequence of random bits is the input to the finite
state machine described above: whenever the state machine is about to output a non-zerodigit, the intermediate value d mod 2w+2 consists of w + 1 independent random bits plus theleast significant bit, which is necessarily set. Thus with probability p = 12 − 2m+1
w+1 , we haved − digit(d) = 2w+1 , and with probability 1 − p, we have d − digit(d) ∈ {0, 2w+2 }. In thefirst case, the next non-zero output digit will follow after exactly w intermediate zeros; inthe second case, the next non-zero output digit will follow after w + 2 intermediate zeros on
average. Thus the total average for the number of intermediate zeros is p·w+(1−p)·(w+2) =w + m+1
2w + 1, which yields the above expression for the density.) Comparing this with the1/(w + 2) density for width-(w + 1) NAFs, we see that the effective window size has been
increased by (m + 1)/2w , which is why we speak of “fractional windows”.
As in section 6.2.1, length expansion can be avoided in many cases by modifying therepresentation. The modified signed fractional window representation is obtained as follows:
if the w + 2 most significant digits are of the form
1 |0 0{z. . . 0} b,
w zerosthen substitute0 1 0| .{z. . 0} βw − 1 zeros

where β = 2w − b; if the w + 3 most significant digits are of the form
1 |0 0{z. . . 0} b
w + 1 zeros

66

Efficient Exponentiation

Table 6.1: Left-to-right exponentiation with window NAFs or signed fractional windows,` = 160
w=2
wNAF s. fract.
m=1
precomputation stage:table entries
squarings
multiplications
evaluation stage:squarings
multiplications

wNAF

w=3
s. fract. s. fract.
m=1
m=3

s. fract.
m=5

w=4
wNAF

2
1
1

3
1
2

4
1
3

5
1
4

6
1
5

7
1
6

8
1
7

≤ 160
≈ 40.0≤ 160≈ 35.6≤ 160≈ 32.0≤ 160≈ 30.5≤ 160≈ 29.1≤ 160≈ 27.8≤ 160≈ 26.7

with b > 2w , then substitute0 1 0| .{z. . 0} βw zeros

where β = 2w+1 − b; and if the w + 3 most significant digits are of the form
1 |0 0 0{z. . . 0} b
w + 1 zeros

with b < 2w , then substitute0 0 3 0| .{z. . 0} βw − 1 zeros

where β = 2w − b.

Precomputation for left-to-right exponentiation can be done in one squaring and 2w−1 +(m − 1)/2 multiplications (see section 6.1.1), and the result stage for right-to-left exponentiation can be implemented in 2w−1 + (m − 1)/2 squarings and 2w + m − 1 multiplications (seesection 6.1.2).
Table 6.1 shows expected performance figures for left-to-right exponentiation using thesigned fractional window method in comparison with the usual window NAF method for
160-bit scalars; a typical application is elliptic curve cryptography. (The expected number of
evaluation stage multiplications for `-bit scalars is approximately`
w + m+1
2w + 2for the signed fractional window method, and`w+2
for the window NAF method.) The signed fractional window method with w = 2, m = 1
achieves an evaluation stage speed-up of about 2.3 % compared with the window NAF methodwith w = 2, assuming that squarings take as much time as general multiplications. In fact,
squarings can be faster, which will increase the relative speed-up (this is usually the casewhen projective coordinates are used for representing points on an elliptic curve).
Table 6.2 is for right-to-left exponentiation; it takes into account the optimizations to
the right-to-left stage noted in section 6.1.2. (As one multiplication can be saved for each6.3 Fractional Windows

67

Table 6.2: Right-to-left exponentiation with window NAFs or signed fractional windows,` = 160

right-to-left stage:squarings
multiplications
result stage:
input variables
squarings
multiplications

w=2
wNAF s. fract.
m=1

wNAF

w=3
s. fract. s. fract.
m=1
m=3

s. fract.
m=5

w=4
wNAF

≤ 160
≈ 39.0≤ 160≈ 33.6≤ 160≈ 29.0≤ 160≈ 26.5≤ 160≈ 24.1≤ 160≈ 21.8≤ 160≈ 19.7

2
1
2

3
2
4

4
3
6

5
4
8

6
5
10

7
6
12

8
7
14

additional accumulator, usually in the right-to-left stage, the expected number of right-to-leftstage multiplications for `-bit scalars is approximately`+1−2
w + m+1
2w + 2

w−1

−

m−1
2

for the signed fractional window method, and`+ 1 − 2w−1
w+2
for the window NAF method.) The table shows that at this exponent bit length, for w = 3
fractional windows bring hardly any advantage for right-to-left exponentiation due to therelatively high computational cost of the result stage. For ` = 160, the fractional window
method with w = 2, m = 1 achieves a 1.2 % total speed-up compared with the window NAF
method with w = 2, assuming that squarings take as much time as general multiplications.

6.3.2

Unsigned Fractional Windows

The unsigned fractional window representation uses the digit set
B = {1, 3, . . ., 2w + m}
and can be obtained by a variant of the technique from section 6.3.1. Here, let the mapping
digit : {0, 1, . . ., 2w+1 } → B ∪ {0}be defined as follows:• If x is even, then digit(x) = 0;
• otherwise if 0 < x ≤ 2w + m, then digit(x) = x;• otherwise let digit(x) = x − 2w .
If x is odd, then x − digit(x) ∈ {0, 2w }. The following algorithm encodes e into unsigned
fractional window representation:

68

Efficient Exponentiation

Table 6.3: Left-to-right exponentiation with sliding windows or unsigned fractional windows,` = 1023
w=2
slid. w. u. fract.
m=1
precomputation stage:table entries
squarings
multiplications
evaluation stage:squarings
multiplications

slid. w.

w=3
u. fract. u. fract.
m=1
m=3

u. fract.
m=5

w=4
slid. w.

2
1
1

3
1
2

4
1
3

5
1
4

6
1
5

7
1
6

8
1
7

≤ 1023≈ 341.0≤ 1023≈ 292.3≤ 1023≈ 255.8≤ 1023≈ 240.7≤ 1023≈ 227.3≤ 1023≈ 215.4≤ 1023≈ 204.6d ← LSBw+1 (e)c ← be/2w+1 ci←0while d 6= 0 ∨ c 6= 0 dob ← digit(d)bi ← b; i ← i + 1d←d−bd ← LSB(c) · 2w + d/2
c ← bc/2c
return bi−1 , . . ., b0
Similarly to the signed case, it can be seen that the average density of the unsigned fractional
window representation is1
m+1
w + 2w + 1
for e → ∞. The precomputation or result stage is as before.
Table 6.3 shows expected performance figures for left-to-right exponentiation using theunsigned fractional window method in comparison with the usual sliding window method
for 1024-bit scalars; a typical application is exponentiation in the multiplicative semigroup(Z/nZ) for an integer n. (The expected number of evaluation stage multiplications for (`+1)bit scalars is approximately`
m+1
w + 2w + 1
for the unsigned fractional window method, and`w+1
for the sliding window method.) If squarings take as much time as general multiplications,the unsigned fractional window method with w = 2, m = 1 is approximately 3.7 % faster than
the sliding window method with w = 2.
Table 6.4 shows the figures for right-to-left exponentiation, taking into account the optimizations to the right-to-left stage noted in section 6.1.2. (As one multiplication can be saved

6.4 Compact Encodings

69

Table 6.4: Right-to-left exponentiation with sliding windows or unsigned fractional windows,` = 1023

right-to-left stage:squarings
multiplications
result stage:
input variables
squarings
multiplications

w=2
slid. w. u. fract.
m=1

slid. w.

w=3
u. fract. u. fract.
m=1
m=3

u. fract.
m=5

w=4
slid. w.

≤ 1023≈ 340.0≤ 1023≈ 290.3≤ 1023≈ 252.8≤ 1023≈ 236.7≤ 1023≈ 222.3≤ 1023≈ 209.4≤ 1023≈ 197.6

2
1
2

3
2
4

4
3
6

5
4
8

6
5
10

7
6
12

8
7
14

for each additional accumulator, usually in the right-to-left stage, the expected number ofright-to-left stage multiplications for (` + 1)-bit scalars is approximately`
m−1+ 1 − 2w−1 −m+1
2
w + 2w + 1
for the unsigned fractional window method, and`+ 1 − 2w−1
w+1
for the sliding window method.)

6.4

Compact Encodings

When storing a window NAF or fractional window representation where a single digit may
take w + 1 bits of memory (as it is the case for width-(w + 1) NAFs if we take into accountthat the digit may be zero, and for signed fractional window representations), then it is notnecessary to store digits separately in w + 1 bits each. If memory is scarce, it is possible
to exploit the properties of the representation to obtain a more compact encoding into bit
strings (cf. [45], where this technique is introduced for width-2 NAFs).
We can encode a zero digit as a single zero bit, and a non-zero digit as a one bit followed bya representation of the respective digit, which together takes w + 1 bits in the case of window
NAFs and w + 2 bits in the case of signed fractional window representations. After each
non-zero digit, there will be w zero digits (unless conversion into a modified window NAF hastaken place), and these can be omitted from the encoding. Thus, compared with the usual
binary representation of the number, in the case of window NAFs we only have growth by asmall constant; in the case of signed fractional window representations (and similarly in thecase of unsigned fractional window representations), we also have growth by an additional bit
for each non-zero digit of the representation.
This bit string encoding can easily be adapted to the case that the bit string will be readin the reverse of the direction in which it was written (for example, non-zero digits should beencoded as a representation of the respective digit followed by a one bit rather than the otherway around).

70

Efficient Exponentiation

Chapter 7

Efficient Multi-Exponentiation
In this chapter, we compare different approaches for computing power products
Y

giei

1≤i≤k

in commutative semigroups with neutral element where each ei is a uniformly chosen random
integer in an interval [0, 2Li − 1]. Let L be the bit-length of the longest of the ei (i.e., ei ∈[0, 2L − 1] for all i, and there is an i such that ei ≥ 2L−1 ). It is well known that thetrivial approach to perform multi-exponentiation by computing the powers giei separately andthen multiplying them is, in general, unnecessarily inefficient compared with specific methods
for multi-exponentiation. To illustrate how these methods work, the following alternative
notation for this power product will be employed (compare with the notation for matrix
products):
 
e1
 .
g1 , . . ., gk •  .. ek

Repeated single exponentiations with precomputation for a fixed base will also be consideredin this chapter because multi-exponentiation techniques can be used for this task.
Like left-to-right methods for single exponentiations (see section 6.1.1), the multi-exponentiation methods that we will look at work in two stages: first, in the precomputation
stage, an auxiliary table of semigroup elements is computed from the elements gi ; then, inthe evaluation stage (or left-to-right stage), the final result is computed using these auxiliary
values.
An often-used approach for multi-exponentiation combines all input elements gi witheach other in the precomputation stage ([35], [83], [91]); then the evaluation stage looks at all
exponents simultaneously. We refer to these multi-exponentiation methods as simultaneous
exponentiation. Section 7.1 describes two variants of simultaneous exponentiation: Straus’s
simultaneous 2w -ary method [83] and the simultaneous sliding window method of Yen, Laih,and Lenstra [91]. (The method described in [35], which is known as “Shamir’s trick”, appears
as a special case of both of these.) For these methods, we assume that Li is the same for all i.
Section 7.2 presents an alternative approach, interleaved exponentiation, which treats
the gi separately in the precomputation stage and where the evaluation stage uses an interleaving of the generators and exponents for the various i rather than handling multiple
i simultaneously. This approach can be used with the various encoding techniques that we71

72

Efficient Multi-Exponentiation

have examined in chapter 6. Specifically, the basic interleaved exponentiation method is the
combination of interleaved exponentiation with the left-to-right sliding window technique,and the window-NAF based interleaved exponentiation method is the combination of interleaved exponentiation with the window NAF technique. The former method can be used forarbitrary commutative semigroups with neutral element, the latter method is applicable forgroups where inverting elements is easy.
In section 7.3, we compare the efficiency of simultaneous exponentiation methods andinterleaved exponentiation methods. Our comparison shows that in general semigroups,
sometimes simultaneous exponentiation and sometimes interleaved exponentiation is more
efficient. In groups where inverting elements is easy (e.g. elliptic curves), window-NAF based
interleaved exponentiation usually wins over simultaneous exponentiation.
Section 7.4 discusses variants that can be advantageous when the bases gi are fixed formany multi-exponentiations. In such cases, precomputation need not be repeated, so it
can pay out to invest more work in precomputation to obtain speed-ups. Note that single
exponentiation is a special case of multi-exponentiation (k = 1), and that these variants canbe very useful for this case. One of the techniques presented there is window NAF splitting,which can be used for efficient exponentiation or multi-exponentiation with precomputationin groups where inversion is easy; it provides a convenient alternative to the patented Lim-Lee
method.

7.1

Simultaneous Exponentiation

We look at two multi-exponentiation methods using simultaneous exponentiation (as opposed
to interleaved exponentiation, which will be introduced in section 7.2): Straus’s 2w -ary method(section 7.1.1) and the sliding window method of Yen, Laih, and Lenstra (section 7.1.2).
As noted in the introduction to this chapter, all algorithms that we consider are related andwork in two stages: first, the precomputation stage prepares an auxiliary table of semigroupelements; then, the evaluation stage (left-to-right stage) computes the final result using thistable. For comparing different methods, we examine the two stages separately.
Parameter w is always a positive integer, the window size; larger window sizes make theprecomputation stage less efficient, but speed up the evaluation stage. It is not possible togive a general rule for selecting an optimal w (cf. section 7.3).
Relevant features of the precomputation stage are the number of squarings and generalmultiplications required for computing the auxiliary table, and the number of table entries.
The precomputed tables will always contain the values g1 , . . ., gk , all of which are triviallyavailable. It will be visible that computing each additional table entry requires one multiplication or, for some of the table entries in the simultaneous 2w -ary method, one squaring. In
addition to this, k squarings are needed by the simultaneous sliding window method if w > 1.
The evaluation stage requires both squarings and multiplications. For each multi-exponentiation method, we look at the number of squarings and the expected number of generalmultiplications for given k, L, and w. In this section, we assume that the maximum bit-length
Li is the same for all i.
The window size w is assumed to be small in comparison with the maximum bit-length L(otherwise the precomputation stage would become unreasonably expensive).
It should be noted that a slight optimization for the precomputation stage is possible in all
methods by first looking which table entries are actually needed (either during the evaluation

7.1 Simultaneous Exponentiation

73

stage, or because other precomputed table entries that are needed in the evaluation stage
depend on them) and limiting precomputation to these. As this optimization will usually
only have a small effect in practice, we neglect it in our comparisons.
For the number of squarings in the evaluation stage, we assume that the following optimization is used: as initially variable A is 1G (the neutral element of G) in all algorithms,
squarings can easily be avoided until a different value has been assigned to A.
Formulas for the expected number of multiplications during the evaluation stage givenin the following are actually asymptotics for large L/w rather than precise values (we donot take into account the special probability distributions encountered at both ends of the
exponents). As in practice w will be much smaller than L, the error can be neglected for our
purposes.
Just as squarings can be eliminated in the evaluation stage while A is 1G , the first multiplication of A by a table entry can be replaced by an assignment. This minor optimization is
not used in our figures below; note that it applies similarly to all algorithms discussed in thischapter (and does not affect asymptotics), so comparisons between different methods remain
just as valid.

7.1.1

Simultaneous 2w -Ary Exponentiation Method

Straus’s simultaneous 2w -ary exponentiation method [83] (see also [53]) looks at w bits ofeach of the exponents for each evaluation stage semigroup multiplication, i.e. kw bits in total.
The special case where w = 1 is also known as “Shamir’s trick” since it was described in [35]with a reference to Shamir (but note that [83] is a much earlier publication).
Precomputation Stage
Precompute 1≤i≤k giEi for all non-zero k-tuples (E1 , . . ., Ek ) ∈ {0, . . ., 2w − 1}k .
Number of table entries: 2kw − 1. Of these, k are trivially available; 2k(w−1) − 1 can becomputed by squaring other table entries (all the Ei are even); the remaining 2kw −2k(w−1) −k
entries require one general multiplication each.
Q

Evaluation StageFor the following algorithm, remember that for a non-negative integer e, e[j 0 . . . j] denotes theinteger consisting of the concatenation of bits j 0 down to j of e.
A ← 1G
for j = b(L − 1)/wc · w down to 0 step w dofor n = 1 to w do
A ← A2

if e1 [j + w − 1 . . . j], . . ., ek [j + w − 1 . . . j] 6= (0, . . ., 0) thenA←A·
return AQ

ei [j+w−1 ... j]i gi

Number of squarings:

j{multiply A by table entry}

L − 1 · w.
w
kExpected number of multiplications: L ·1
1 − 2kww .

74

Efficient Multi-Exponentiation

ExampleThe simultaneous 2w -ary exponentiation method can be illustrated as follows in a small toy
example for the case k = 3 with e1 = 10110102 , e2 = 110012 , e3 = 10010112 and window size
w = 2:


0
1
0
1
1
0
1
0
2
 

g1 , . . ., gk •  0 0 0 1 1 0 0 1 2 
0 1 0 0 1 0 1 12
Each box corresponds to one evaluation stage multiplication.

7.1.2

Simultaneous Sliding Window Exponentiation Method

The simultaneous sliding window exponentiation method of Yen, Laih, and A. Lenstra [91]is an improved variant of the 2w -ary method described in section 7.1.1. Due to the use of asliding window, table entries are required only for those tuples (E1 , . . . , Ek ) where at least
one of the Ei is odd. (Note that while values gi2 no longer appear in the precomputed table,
the precomputation stage now needs them as intermediate values unless w = 1.) Also the
expected number of multiplications required in the evaluation stage is reduced. Like the 2w ary method, this method looks at w bits of each of the exponents for each evaluation stage
semigroup multiplication (kw bits in total). For w = 1, this again is “Shamir’s trick”. For
k = 1, this is the usual sliding window method for a single exponentiation (see section 6.2).
Precomputation Stage
Precompute 1≤i≤k giEi for all k-tuples (E1 , . . ., Ek ) ∈ {0, . . ., 2w − 1}k where at least one of
the Ei is odd.
Number of table entries: 2kw − 2k(w−1) .
Number of squarings: k if w > 1; none otherwise.
Number of general multiplications: 2kw − 2k(w−1) − k.
Q

Evaluation StageA ← 1Gj ←L−1
while j ≥ 0 do
if ∀i ∈ {1, . . ., k} : ei [j] = 0 thenA ← A2 ; j ← j − 1else
jnew ← max(j − w, −1)
J ← jnew + 1
while ∀i ∈ {1, . . ., k} : ei [J] = 0 do
J ←J +1{now j ≥ J > jnew }for i = 1 to k do
Ei ← ei [j . . . J]
while j ≥ J do
A ← A2 ; j ← j − 1QA ← A · i giEi {multiply A by table entry}

7.2 Interleaved Exponentiation

75

while j > jnew do
A ← A2 ; j ← j − 1
return A
Number of squarings: L − w up to L − 1.
1
P1
Expected number of multiplications: L ·.
1 =L·
w + n≥1 2kn
w + 2k1−1
ExampleThe simultaneous sliding window exponentiation method can be illustrated as follows in asmall toy example for the case k = 3 with e1 = 10110102 , e2 = 110012 , e3 = 10010112 andwindow size w = 2:


1 0 1 1 0 1 02
 

g1 , . . ., gk •  0 0 1 1 0 0 1 2 
1 0 0 1 0 1 12
Each bold box corresponds to one evaluation stage multiplication. The thin box indicates arange of bits that is scanned by the algorithm as part of one window, and where the right-mostcolumn of bits is found to contain all zeros so that the case occurs that J > jnew + 1.

7.2

Interleaved Exponentiation

Let a Bj -representationej =X

bj,i · 2i

0≤i≤`jbe given for each of the exponents in a power productYegj j ,

1≤j≤kwhere each Bj is a digit set as in section 6.1. Then the multi-exponentiation can be performedeby interleaving the left-to-right algorithms for the individual exponentiations gj j . For each j,precomputed elements gjb are needed as in section 6.1.1.
Let ` be the maximum of the `j . We may assume that ` = `1 = . . . = `k (pad with leading
zeros where necessary). When the Bj -representations have been obtained by the sliding
window technique (section 6.2) or the unsigned fractional window technique (section 6.3), we
can assume ` = L − 1; when the Bj -representations have been obtained by the window NAF
technique (section 6.2) or the signed fractional window technique (section 6.3), we can assume` = L.
Qe
If division is permissible, interleaved exponentiation to compute 1≤j≤k gj j can be performed as follows:A ← 1G
for i = ` down to 0 do
A ← A2for j = 1 to k do
if bj,i 6= 0 thenif bj,i > 0 then

76

Efficient Multi-Exponentiationb

A ← A · gj j,i
else
|b |
A ← A/gj j,ireturn A
As in section 6.1.1, initial squarings can be omitted while A is 1G , and the first multiplication
or division can be replaced by an assignment possibly followed by inversion. The algorithm
variant without division is obvious.
In the following, we look at two specific interleaved exponentiation methods more closely:
the basic interleaved exponentiation method (section 7.2.1), which uses the sliding window
technique and is suitable for arbitrary commutative semigroups with neutral element, and thewindow-NAF based interleaved exponentiation method (section 7.2.2), which uses the window
NAF technique and can be applied for groups where inverting elements is easy.
The comments in the introduction to section 7.1 apply similarly, with the exception that
we no longer assume all the Li to be identical. Instead of a single window size w, in thissection we have k possibly different window sizes wi (1 ≤ i ≤ k) used for the respective partsof the multi-exponentiation; each wi is a small positive integer. Again we assume that initialsquarings are eliminated while A is 1G .
Note that for the algorithms described in this section, the precomputed table has disjoint
parts for different bases gi . If multiple multi-exponentiations have to be performed and someof the bases gi appear again, then the corresponding parts of earlier precomputed tables canbe reused.
Observe that it is easy to implement interleaved exponentiation for a variable parameter k.
As the the special case k = 1 of the basic and window-NAF based interleaved exponentiation
methods yields the usual sliding windows exponentiation method and window-NAF based
exponentiation method, respectively, this makes it unnecessary to implement these separately.

7.2.1

Basic Interleaved Exponentiation Method

The basic interleaved exponentiation method is a generalization of the left-to-right sliding
window method for a single exponentiation (see sections 6.1.1 and 6.2), to which it corresponds in the case k = 1. We show how it can be used without computing sliding window
representations of all exponents beforehand.
Precomputation StageFor i = 1, . . ., k, precompute giE for all odd E such that 1 ≤ E ≤ 2wi − 1.
P
Number of table entries: 1≤i≤k 2wi −1 .
Number of squarings: # i ∈ {1, . . ., k} | wi > 1 .
P
wi −1 − k.
Number of general multiplications:1≤i≤k 2
Evaluation StageA ← 1G
for i = 1 to k dowindow handle i ← nil
for j = L − 1 down to 0 do
A ← A2

7.2 Interleaved Exponentiation

77

for i = 1 to k do
if window handle i = nil and ei [j] = 1 thenJ ← j − wi + 1
while ei [J] = 0 do
J ←J +1{now j ≥ J > j − wi and J ≥ 0}
window handle i ← J
Ei ← ei [j . . . J]
if window handle i = j thenA ← A · giEi {multiply A by table entry}
window handle i ← nil
return A
Number of squarings: L − max1≤i≤k (wi ) up to L − 1.
Expected number of multiplications:
X

1≤i≤k

Li ·

1
wi +

1
n≥1 2n

P

=

X

Li ·

1≤i≤k

1
.
wi + 1

ExampleThe basic interleaved exponentiation method can be illustrated as follows in a small toy
example for the case k = 3 with e1 = 10110102 , e2 = 110012 , e3 = 10010112 and parameters
w1 = w2 = w3 = 3:


1 0 1 1 0 1 02

g1 , . . ., gk • 
0
1

0

1

1

0

0

0

0

1

0

1



1 2


12

Each bold box corresponds to one evaluation stage multiplication. Each thin box indicates arange of bits that is scanned by the algorithm as part of one window.

7.2.2

Window-NAF Based Interleaved Exponentiation Method

The window-NAF based interleaved exponentiation can be used in groups where elements
can be inverted very efficiently so that division is not significantly more expensive than multiplication: it applies the window NAF technique described in section 6.2 for interleaved
exponentiation. Note that modified window NAFs can be employed (see section 6.2.1).
Precomputation StageFor i = 1, . . ., k, precompute giE for all odd E such that 1 ≤ E ≤ 2wi − 1.
P
Number of table entries: 1≤i≤k 2wi −1 .
Number of squarings: # i ∈ {1, . . ., k} | wi > 1 .
P
wi −1 − k.
Number of general multiplications:1≤i≤k 2

78

Efficient Multi-Exponentiation

Evaluation StageSee page 75 for the interleaved exponentiation algorithm.
Number of squarings: L − max1≤i≤k (wi ) up to L.
Expected number of multiplications:11≤i≤k Li · wi + 2 .

P

The sliding window encoding technique used by the basic interleaved exponentiation
method in section 7.2.1 has an average density of 1/(wi + 1). With window NAFs, theaverage density goes down to 1/(wi + 2) for exactly the same precomputation. Thus using
window NAFs effectively increases window sizes by one.

7.3

Comparison of Simultaneous and Interleaved Exponentiation Methods

There is no general rule for selecting window sizes for the multi-exponentiation algorithms that
we have looked at. Various factors have to be considered: first of all, absolute memory constraints can impose limits on possible window sizes. Second, even if a particular window size
appears to minimize the total amount of computation for a multi-exponentiation, sometimes
slightly smaller windows may improve the actual performance; this is because larger window
sizes mean larger precomputed tables, i.e. possibly additional memory allocation overhead
and less effective memory caching. Last but not least, implementations can use different representations for semigroup elements during different stages of the multi-exponentiation: for
instance, extra effort may be spent during the precomputation stage in order to obtain representations of precomputed elements that speed up multiplication with them in the evaluation
stage (e.g. affine rather than projective representations of points on elliptic curves [27]).
These effects, however, do not mean that we cannot compare algorithms without looking
at concrete cases: we can compare different aspects separately (table size, precomputation
stage efficiency, evaluation stage efficiency) and look if an algorithm wins on all counts.
For the following comparisons, we assume that all maximum exponent lengths Li are thesame (an assumption that we made in section 7.1 on simultaneous exponentiation, but not
in section 7.2 on interleaved exponentiation). As before, let L be the length of the largest of
the exponents ei .
In section 7.3.1, we compare the simultaneous 2w -ary method with the basic interleaved
method and show that the latter is usually more efficient for k = 2 if squarings are about
as costly as multiplications. In section 7.3.2, we compare the simultaneous sliding window
method with the window-NAF based interleaved method and show that the latter is more
efficient for k = 2 and k = 3 (assuming that computing and storing the window NAFs is
not too costly). Section 7.3.3 briefly discusses the alternative multi-exponentiation methodfrom [34] and shows that is obviated by our interleaved exponentiation methods; section 7.3.4
shows an example for the use of fractional windows with interleaved multi-exponentiation. In
section 7.3.5, we look at some concrete figures for the number of multiplications required bydifferent methods for example values of k and L assuming that window size choices are notdictated by scarce memory. Section 7.3.6 gives conclusions.

7.3 Comparison of Simultaneous and Interleaved Exponentiation Methods

7.3.1

79

Comparison between the Simultaneous 2w -Ary Method and the Basic
Interleaved Method

While the simultaneous sliding window method is more efficient than the simultaneous 2w -arymethod, this section focuses on the latter. The reasons is that the 2w -ary method is often usedin practice (e.g. [18]), possibly because it is perceived to be simpler to implement. The basic
interleaved exponentiation method is quite simple (in particular, indexes into the precomputed
table are easy to handle), and as we will see, is often more efficient than the simultaneous
2w -ary exponentiation method. So when the intention is to avoid the simultaneous sliding
window method, the basic interleaved method appears preferable for many applications.
Assume that, given k and L, a certain w turns out to provide optimal efficiency forthe simultaneous 2w -ary exponentiation method (section 7.1.1) when performed in a specificenvironment. Then the precomputed table has 2kw − 1 entries (including the k trivial entries
g1 , . . ., gk ), 2k(w−1) − 1 of which can be computed with one squaring each, while each of theremaining 2kw − 2k(w−1) − k non-trivial entries requires one general multiplication.
For the basic interleaved exponentiation method (section 7.2.1), we can use uniform window sizes w1 = . . . = wk = kw. Then the precomputed table has k2kw−1 entries, k2kw−1 −k ofwhich require one general multiplication each; also k additional squarings are needed (unlessk = w = 1).
Thus in case k = 2, the number of table entries grows from 22w − 1 to 22w , and insteadof 22w − 3 semigroup operations of which 22(w−1) − 1 are squarings, we need 22w semigroup
operations of which only 2 are squarings. If squarings are about as expensive as generalmultiplications, then for k = 2 the overall cost of precomputation is comparable for these two
multi-exponentiation methods.
The number of squarings in the evaluation stage is always nearly L for both methods.
The expected number of general multiplications in the evaluation stage is smaller for theinterleaved method (except if k = w = 1, in which case both algorithms perform exactly thesame operations): dividing the value for the basic interleaved exponentiation method by thevalue for the simultaneous 2w -ary exponentiation method yields
k
w
kw
2kw
·
=
·
,
1
kw + 1 1 − 2kw
kw + 1 2kw − 1
and this is less than 1 for kw > 1 (the minimum is 64/75 at kw = 4).
Note that using w1 = . . . = wk = kw is not necessarily an optimal choice of window
sizes for the basic interleaved exponentiation method; using smaller or larger windows mightlead to better performance. (Indeed, if we look just at the number of operations and ignore
memory usage, then there is no reason why window sizes should depend on k.) While theabove proof only covers the case k = 2, there are actually many other cases where the basic
interleaved method is more efficient than the simultaneous 2w -ary method, even if generalmultiplications are much more expensive than squaring; see table 7.1 in section 7.3.5. Also
note that the precomputation effort grows exponentially in k for simultaneous methods, but
not for interleaved methods.

7.3.2

Comparison between the Simultaneous Sliding Window Method andthe Window-NAF Based Interleaved Method

Similarly to section 7.3.1, assume that a certain w provides optimal efficiency for the simultaneous sliding window exponentiation method (section 7.1.2) for given k and L. In the80

Efficient Multi-Exponentiation

following analysis, we require k > 1. The precomputed table has 2kw −2k(w−1) entries (including k trivial ones), 2kw − 2k(w−1) − k of which requires one general multiplication to compute.
In addition to this, k squarings are required for precomputation unless w = 1.
For the window-NAF based interleaved exponentiation method (section 7.2.2), we can use
window sizes w1 = . . . = wk = kw −1. This leads to a precomputed table with k2kw−2 entries,
where k of these are trivially available and the k2kw−2 − k non-trivial ones require one generalmultiplication each. In addition to this, we need k squarings unless kw = 2.
The difference between the number of tables entries (and between the number of generalmultiplications) for these two methods is

(2kw − 2k(w−1) ) − k2kw−2 = 2kw 1 − 2−k −k.
4This is positive for k ≤ 3 and negative for k ≥ 4. Thus, with the wi chosen like this, theprecomputation stage of the window-NAF based interleaved exponentiation method is more
efficient if k = 2 or k = 3 (except for the case k = 3, w = 1, where the window-NAF
based interleaved exponentiation method saves one general multiplication, but requires three
additional squarings).
The evaluation stage requires close to L squarings for both methods. The expected numberof general multiplications is smaller for the window-NAF based interleaved method: L/(w +1/k) instead of L/(w + 2k1−1 ).
The window-NAF based interleaved method with this choice of window sizes will often
provide better performance than the simultaneous sliding window method for k ≥ 4 as well:
if additional memory allocation is not a problem, then the efficiency gain of the evaluation
stage usually compensates for the growth of the precomputed table.
Similar to the situation in the preceding section, w1 = . . . = wk = kw −1 is not necessarily
an optimal choice, and smaller or larger window sizes might be better (see section 7.3.5).

7.3.3

Comparison between the Dimitrov-Jullien-Miller Multi-Exponentiation Method and Interleaved Exponentiation

A multi-exponentiation method for computing g1e1 g2e2 that requires a precomputed table containing four values (including g1 and g2 ) if inverting is easy, or eight values if inversions haveto be done during the precomputation stage to avoid them in the evaluation stage, was described by Dimitrov, Jullien, and Miller in [34]. This algorithm is related to the simultaneous
sliding window exponentiation method of Yen, Laih, and Lenstra [91] (see section 7.1.2), butuses a signed encoding of exponents in order to reduce the size of the precomputed table.
While the Yen-Laih-Lenstra method with a window size of 1 requires an expected numberof L · 0.75 general multiplications during the evaluation stage, the new method requires only
about L · 0.534 multiplications according to [34] (the number of squarings stays about thesame). Yen-Laih-Lenstra with a window size of 2 needs only L · 3/7 ≈ L · 0.429 multiplications(table 3 of [34] erroneously assumes a value of L · 0.625), but has the disadvantage of requiring
more precomputed elements, which may be a problem in constrained environments.
We do not examine the algorithm of [34] in detail; note that it is outperformed by thewindow-NAF based interleaved method of section 7.2.2 with w1 = w2 = 2 if inversion is cheap(precomputed table with four elements, L · 0.5 evaluation stage multiplications) and by thebasic interleaved method of section 7.2.1 with w1 = w2 = 3 otherwise (precomputed tablewith eight elements, L · 0.5 evaluation stage multiplications).

7.3 Comparison of Simultaneous and Interleaved Exponentiation Methods

7.3.4

81

Multi-Exponentiation with Fractional Windows

Assume we have to compute a power product g1e1 g2e2 in a group where inversion is easy,
and that we have storage for five precomputed elements. For using interleaved exponentiation as described in section 7.2, we can represent e1 as a width-3 NAF and e2 in signed
fractional window representation (section 6.3.1) with w = 2, m = 1. This means we use
precomputed elements g1 ,g13 , g2 , g23 , g25 . The evaluation stage needs at most L squarings and11
L = 17
approximately 14 + 4+1/2
36 L multiplications on average, compared with 2 L multiplications for interleaved exponentiation with width-3 NAFs for both exponents (precomputed
elements g1 , g13 , g2 , g23 ).
(A similar scenario is considered in [77], using a different multi-exponentiation algorithm;
for groups where inversion is easy, that technique using the same amount of storage as neededin our above example runs slightly slower according to the heuristical results in [77, table 12].)

7.3.5

ExamplesAs noted before, endless variations are possible for defining optimization goals. In this section,
we ignore memory usage and squarings and the issue of different element representations; wemake comparisons based just on the expected number of general multiplications requiredby the various methods, precomputation and evaluation stage combined. Window sizes arechosen such that this cost measure is minimized. Note that the number of squarings isapproximately the same for the simultaneous sliding window method, the basic interleaved
method, and the window-NAF based interleaved method: no more than k squarings areneeded in the precomputation stage, and close to L squarings are needed in the evaluation
stage. The simultaneous 2w -ary method requires 2k(w−1) − 1 squarings for precomputation
and again close to L evaluation stage squarings; so ignoring the cost of squaring tends tofavor this method.
Table 7.1 compares the number of general multiplications needed by these four methods
for various k and L values, using the following estimates:kw

c1 = 2k(w−1)−2

1
1 − 2kw−k+L·w

for the simultaneous 2w -ary exponentiation method,c2 = 2kw − 2k(w−1) − k + L ·1
w + 2k1−1

for the simultaneous sliding window exponentiation method,c3 = k · 2w−1 − 1 +

L 
w+1

for the basic interleaved exponentiation method, and

c4 = k · 2w−1 − 1 +

L 
w+2

for the window-NAF based interleaved exponentiation method, where interleaved exponentiation uses a uniform window size w1 = . . . = wk = w. The entries for the most efficientmethods in a particular configuration are printed in bold: for groups where inversion is easy

82

Efficient Multi-Exponentiation

so that the window-NAF based method can be used, it wins in all of these examples; forgeneral semigroups, sometimes the simultaneous sliding window method and sometimes thebasic interleaved method requires the least number of multiplications. (Remember that for
w = 1 there is no difference between the simultaneous 2w -ary method and the simultaneous
sliding window method; for w > 1, the former is always less efficient.)

7.3.6

Conclusions

In many cases, the basic interleaved exponentiation method compares favorably to the simultaneous 2w -ary method, in particular if k = 2 and squarings are about as costly as generalmultiplications. In groups where inverting elements is easy so that the window-NAF based
interleaved exponentiation method is available, its efficiency is superior even to the sliding
window variant of simultaneous exponentiation both in the precomputation stage and theevaluation stage if k = 2 or k = 3, and it is usually more efficient for larger k as well.
In all cases, interleaved exponentiation provides the following advantages over simultaneous
exponentiation:• Improved efficiency if the bit-lengths of the exponents ei differ significantly.
• More flexibility in choice of the size of the auxiliary table (and, hence, the time spenton precomputation), particularly if k is large.
• Better handling of situations where one or more of the gi are fixed while others arevariable between multiple multi-exponentiation: a corresponding part of the precomputation has to be done only once. (This is the case in DSA [66] and ECDSA [4] signature
verification if multiple signatures are verified that are based on the same underlying
parameters.)
Thus, depending on circumstances, either the simultaneous sliding window method or one of
the interleaved exponentiation methods may be advantageous.

7.4

Exponentiation and Multi-Exponentiation with Precomputation for Fixed Bases

When many multi-exponentiations use the same bases g1 , . . ., gk , it is sufficient to execute theprecomputation stage just once, and we can try to make the evaluation stage more efficientby investing more work in precomputation. (This also applies to the special case k = 1, i.e. torepeated single exponentiations use the same base.) We cannot easily reduce the number ofgeneral multiplications in the evaluation stage, but we can reduce the number of squarings
by using exponent splitting (section 7.4.1), the Lim-Lee “comb” method (section 7.4.2), or
window NAF splitting (section 7.4.3). Which approach is the most efficient depends on detailsof the situation such as exponent lengths, the permissible size of the precomputed table, therelative cost of squarings versus general multiplications, and whether inexpensive inversion isavailable so that window NAF methods are applicable.
Let m be an arbitrary positive integer. Assuming that fixed exponent length bounds Li areQ
known, we show how to evaluate power products 1≤i≤k giei with at most m − 1 evaluation
stage squarings (or occasionally m squarings in section 7.4.3), using a precomputed table
independent of the specific exponents ei .

7.4 Exponentiation and Multi-Exponentiation with Precomputation for Fixed Bases

83

Table 7.1: Expected number of general multiplications for a multi-exponentiation 1≤i≤k gieiwith exponents up to L bits (c1 : simultaneous 2w -ary method, c2 : simultaneous sliding window
method, c3 : basic interleaved method, c4 : window-NAF based interleaved method)
Q

k
1

2

3

4

5

6

7

8

9

10

c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4
c1
c2
c3
c4

L = 160
44.5 (w=4)
39.0 (w=4)
39.0 (w=4)
33.7 (w=4)
85.0 (w=2)
78.6 (w=2)
78.0 (w=4)
67.3 (w=4)
131.8 (w=2)
127.7 (w=2)
117.0 (w=4)
101.0 (w=4)
161.0 (w=1)
161.0 (w=1)
156.0 (w=4)
134.7 (w=4)
181.0 (w=1)
181.0 (w=1)
195.0 (w=4)
168.3 (w=4)
214.5 (w=1)
214.5 (w=1)
234.0 (w=4)
202.0 (w=4)
278.8 (w=1)
278.8 (w=1)
273.0 (w=4)
235.7 (w=4)
406.4 (w=1)
406.4 (w=1)
312.0 (w=4)
269.3 (w=4)
661.7 (w=1)
661.7 (w=1)
351.0 (w=4)
303.0 (w=4)
1172.8 (w=1)
1172.8 (w=1)
390.0 (w=4)
336.7 (w=4)

L = 25664.6 (w=5)
57.7 (w=5)
57.7 (w=5)
49.7 (w=4)
130.0 (w=2)
119.7 (w=2)
115.3 (w=5)
99.3 (w=4)
179.0 (w=2)
172.5 (w=2)
173.0 (w=5)
149.0 (w=4)
251.0 (w=1)
251.0 (w=1)
230.7 (w=5)
198.7 (w=4)
274.0 (w=1)
274.0 (w=1)
288.3 (w=5)
248.3 (w=4)
309.0 (w=1)
309.0 (w=1)
346.0 (w=5)
298.0 (w=4)
374.0 (w=1)
374.0 (w=1)
403.7 (w=5)
347.7 (w=4)
502.0 (w=1)
502.0 (w=1)
461.3 (w=5)
397.3 (w=4)
757.5 (w=1)
757.5 (w=1)
519.0 (w=5)
447.0 (w=4)
1268.8 (w=1)
1268.8 (w=1)
576.7 (w=5)
496.7 (w=4)

L = 512114.2 (w=5)
100.3 (w=5)
100.3 (w=5)
88.1 (w=5)
214.0 (w=3)
199.6 (w=3)
200.7 (w=5)
176.3 (w=5)
305.0 (w=2)
291.9 (w=2)
301.0 (w=5)
264.4 (w=5)
491.0 (w=1)
483.7 (w=2)
401.3 (w=5)
352.6 (w=5)
522.0 (w=1)
522.0 (w=1)
501.7 (w=5)
440.7 (w=5)
561.0 (w=1)
561.0 (w=1)
602.0 (w=5)
528.9 (w=5)
628.0 (w=1)
628.0 (w=1)
702.3 (w=5)
617.0 (w=5)
757.0 (w=1)
757.0 (w=1)
802.7 (w=5)
705.1 (w=5)
1013.0 (w=1)
1013.0 (w=1)
903.0 (w=5)
793.3 (w=5)
1524.5 (w=1)
1524.5 (w=1)
1003.3 (w=5)
881.4 (w=5)

L = 1024
199.0 (w=6)
177.3 (w=6)
177.3 (w=6)
159.0 (w=6)
382.0 (w=3)
353.2 (w=3)
354.6 (w=6)
318.0 (w=6)
557.0 (w=2)
530.9 (w=2)
531.9 (w=6)
477.0 (w=6)
746.0 (w=2)
731.5 (w=2)
709.1 (w=6)
636.0 (w=6)
1018.0 (w=1)
1018.0 (w=1)
886.4 (w=6)
795.0 (w=6)
1065.0 (w=1)
1065.0 (w=1)
1063.7 (w=6)
954.0 (w=6)
1136.0 (w=1)
1136.0 (w=1)
1241.0 (w=6)
1113.0 (w=6)
1267.0 (w=1)
1267.0 (w=1)
1418.3 (w=6)
1272.0 (w=6)
1524.0 (w=1)
1524.0 (w=1)
1595.6 (w=6)
1431.0 (w=6)
2036.0 (w=1)
2036.0 (w=1)
1772.9 (w=6)
1590.0 (w=6)

L = 2048
353.3 (w=7)
319.0 (w=7)
319.0 (w=7)
287.0 (w=6)
700.0 (w=4)
660.4 (w=3)
638.0 (w=7)
574.0 (w=6)
1061.0 (w=2)
1008.7 (w=2)
957.0 (w=7)
861.0 (w=6)
1256.0 (w=2)
1227.0 (w=2)
1276.0 (w=7)
1148.0 (w=6)
2010.0 (w=1)
1994.7 (w=2)
1595.0 (w=7)
1435.0 (w=6)
2073.0 (w=1)
2073.0 (w=1)
1914.0 (w=7)
1722.0 (w=6)
2152.0 (w=1)
2152.0 (w=1)
2233.0 (w=7)
2009.0 (w=6)
2287.0 (w=1)
2287.0 (w=1)
2552.0 (w=7)
2296.0 (w=6)
2546.0 (w=1)
2546.0 (w=1)
2871.0 (w=7)
2583.0 (w=6)
3059.0 (w=1)
3059.0 (w=1)
3190.0 (w=7)
2870.0 (w=6)

84

7.4.1

Efficient Multi-Exponentiation

Exponent Splitting

Exponent splitting (cf. [17] and [31]; the idea goes back to [73]) constructs a new power
product representation by rewriting each factor as follows:giei =

Y

(gi2

jm

)ei [jm+m−1 ... jm]

0≤j<dLi /meThis leads to power products consisting of 1≤i≤k dLi /me factors. Any multi-exponentiation
method can be used for evaluating these power products.
It is evident that for the multi-exponentiation methods that we have looked at, exponent
splitting does not help if k is already large and there are many large exponents: saving someevaluation stage squarings will not have a large overall impact in such cases. (Then, insteadof using precomputed table entries for additional bases, window sizes should be increased.
The evaluation stage will require more squarings, but fewer general multiplications than withexponent splitting.)
P

7.4.2

Lim-Lee Precomputation

To apply the Lim-Lee “comb” method [51], for every i we choose wi such that Li ≤ wi m andprecomputeP
Gi (S) := gi

j∈S

2j

for all subsets S ⊆ {0, m, 2m, . . ., (wi − 1)m}. Note that then every exponent up to Li bits oflength can be written asXei =bj,i · 2j0≤j<m

where each bj,i is an integer of the form j∈S 2j with S as above. Thus we can use theinterleaved exponentiation algorithm from section 7.2 (where we have no need for divisions
because all digits are non-negative) with the number of loop iterations reduced to m. The
bj,i values for each iteration need not be stored in advance, they can be extracted from the ei
by tapping their bits in comb-shaped patterns; hence the nickname of this method.
A refinement of this (also from [51]) is based on the observation that the precomputed table
can be reduced in size in exchange for additional evaluation stage multiplications: partition{0, m, 2m, . . ., (wi − 1)m} into vi subsets Ti,1 , . . ., Ti,vi ; now each of the above sets S can
QS
be written as 1≤n≤vi Sn with Sn = S ∩ Ti,n , and then we have Gi (S) = 1≤n≤vi Gi (Sn ).
Thus it suffices to precompute Gi (Sn ) for all non-zero subsets Sn ⊆ Ti,n for all n; from thisprecomputed data, Gi (S) can be computed in at most vi − 1 multiplications when it is neededin the evaluation stage.
While Lim-Lee precomputation reduces the number of squarings, the expected number ofgeneral multiplications is larger than for the basic interleaved exponentiation method witha similarly sized precomputed table. (In the basic interleaved method, 2wi −1 precomputed
table entries suffice to make sure that each evaluation stage multiplication covers wi exponent
bits, and we can skip many additional zero bits thanks to the sliding window. With Lim-Lee
precomputation, we need at least 2W − 1 precomputed table entries to be able to cover W
exponent bits with each evaluation stage multiplication, and we lose the advantage of a sliding
window.) Thus if k is large, using Lim-Lee precomputation is a disadvantage.
P7.4 Exponentiation and Multi-Exponentiation with Precomputation for Fixed Bases

85

Note that it is possible to use Lim-Lee precomputation for some of the bases and standard
precomputation (as in section 7.2) for others. This does not help for multi-exponentiationin these mixed cases, but precomputed data can then profitably be reused for pure Lim-Leecases.
The Lim-Lee method can be considered an application of exponent splitting using specificmulti-exponentiation algorithms suited for small exponents: for example, if k = 1, the simple
Lim-Lee method uses “Shamir’s trick”, i.e. simultaneous exponentiation with a window sizeof 1. Further algorithmic variations are possible.

7.4.3

Window NAF Splitting

For groups where inversion is easy, exponent splitting as described in section 7.4.1 could
be used with window-NAF based interleaved exponentiation: that is, each of the lengthm exponent parts is encoded as a window NAF as described in section 6.2, and then aninterleaved exponentiation using these windows NAFs is performed as described in section 7.2.
With width-(wi + 1) NAFs, this computation should take about m squarings and Li /(wi + 2)
multiplications using d(Li + 1)/me · 2wi −1 precomputed elements. However, if m is verysmall, the expected number of multiplications will be noticeably higher because the estimatethat the density of window NAFs is approximately 1/(wi + 2) becomes accurate only if theencoded number is sufficiently long. (Window NAFs usually waste part of one window; themore individual integers must be encoded into window NAFs, the more is wasted in total.)
An improved technique that avoids this drawback is window NAF splitting. Instead of
splitting the binary representation of an exponent ei into partial exponents of length m anddetermining window NAFs for these, we first determine the window NAF of ei and then split
this new representation into parts of length m. The computation continues as above, using
the interleaved exponentiation algorithm shown in section 7.2. To avoid length expansion
if possible, this technique should be used with modified window NAFs (section 6.2.1) The
leftmost part can be made large than the others if one more part would have to be added
otherwise; e.g. for integers up to 160 bits with m = 8:b160 b159 · · · b152|{z

9 digitsb151 · · · b144

} |

{z

8 digits}···

b7 · · · b 0|{z

8 digits}

Most of the time, the additional digit of the leftmost part will be zero since length expansion
is relatively rare (for modified window NAFs of positive integers up to a length of Li bitswith wi = 4, only about one out of five cases has a non-zero digit at maximum index Li ).
With window NAF splitting, single exponentiations (k = 1) for L1 -bit exponents canbe performed in m − 1 squarings and on average about L1 /(w1 + 2) multiplications, usingd(L1 +1)/me·2w1 −1 precomputed elements. If the leftmost part gets an extra digit as describedabove, dL1 /me · 2w1 −1 precomputed elements are sufficient, and the number of squarings goesup to m for some cases.
This method can compete with the Lim-Lee method even when much space is available forprecomputed elements (whereas exponent splitting with window-NAF based interleaved exponentiation is better than the Lim-Lee algorithm only for comparatively small precomputed
tables). For example, if L1 = 160, then with m = 8 and w1 = 4 (160 precomputed elements
if we allow an extra digit in the leftmost window NAF part), our exponentiation methodwith window NAF splitting needs about 7.2 squarings and 26.7 multiplications. The refined

86

Efficient Multi-Exponentiation

version of the Lim-Lee method (with v1 = 2 and #T (1,1 ) = #(T1,2 ) = w1 /2) can perform
such 160-bit exponentiations in 13 squarings and about 26.6 multiplications using 126 precomputed elements (m = 14, w1 = 12), or in 11 squarings and about 22.8 multiplications
using 254 precomputed elements (m = 12, w1 = 14).
It is possible to use window NAF splitting with a flexible window size: while generating
digits using the algorithm described in section 6.2, parameter wi can be changed. This should
be done only at the beginning of a new part of the window NAF (i.e., when the number ofdigits generated so far is a multiple of m). For example, if in the k = 1, L1 = 160 setting
we are using m = 8 and allowing an extra digit in the leftmost part, the (modified) window
NAF will be split into 20 parts; we can start with w1 = 5 for the first 12 of these, then switch
to w1 = 4 for the remaining 8. Then we need 12·24 +8·23 = 256 precomputed elements and can
8·8
perform exponentiations in about 7.2 squarings and 12·8
5+2 + 4+2 ≈ 24.4 multiplications, which
is usually (depending on the relative performance of squarings and general multiplications)better than the performance of the Lim-Lee method with 254 precomputed elements.

Chapter 8

Elliptic Curve Point Multiplication
with Resistance against
Side-Channel Attacks
A type of public-key cryptography that is gaining much popularity is elliptic curve cryptography, cryptography using the group of rational points on an elliptic curve over a finite field Fq .
For details on the mathematics and on implementation aspects, see e.g. [12] and [41]. An
elliptic curve is specified by a curve equation E over variables X, Y . The relevant group
E(Fq ) consists (when using the affine representation of points) of those pairs (X, Y ) of field
elements that fulfill said equation, plus the neutral element O, which is called the point at
infinity. Several styles of projective representations are often used for better efficiency (appropriate representations can significantly cut down the number of field inversions, and theseoften are rather slow).
The group operation is commutative. It is usually written additively rather than multiplicatively, and the present chapter follows this convention. The following operations arise:• Point addition, i.e. computing P + Q given a pair of points P , Q.
• Point doubling, i.e. computing 2P given a point P .
• Point inversion, i.e. computing −P given a point P .
Typically, point addition algorithms have to detect the cases where one of the points P, Q is
the point at infinity or where P = −Q (so that the sum of P and Q is the point at infinity)or where P = Q (so that the point addition is a point doubling) and treat them specially.
The algorithm for the remaining case of point addition where P, Q 6= O and P 6= ±Q is in
general not suitable for point doubling, and thus point addition and point doubling can beconsidered distinct operations as long as those special cases are avoided.
Point inversion is a very quick operation (it can be implemented by a field inversion in
the case of a field of odd characteristic, and by a field addition in the case of a field of
characteristic two), so computing P − Q is essentially the same work as computing P + Q.
As we switch from multiplicative to additive notation, exponentiation becomes multiplication of a point P by a scalar e, or point multiplication for short. The methods described in
the preceding chapters can be used to compute eP .
87

88

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

Elliptic curves used for cryptography are usually required to have a large prime-ordersubgroup. We denote its order by p and assume that only one order-p subgroup exists. In
this setting, cryptographic
protocols typically employ only points of order p. The integerh = # E(Fq ) /p, the cofactor, is typically very small, e.g. h ≤ 4 as required by [22].
The present chapter focuses on an additional aspect for point multiplication, namely sidechannel attacks ([48], [49]) where adversaries try to use power consumption measurements
or similar observations to derive information on secret scalars e in point multiplications eP .
Point P is usually not secret, and indeed may often be chosen by the adversary. Multiplier e
may either be ephemeral or serve as a long-time key.
One distinguishes between differential side-channel attacks, which require correlated measurements from multiple point multiplications, and simple side-channel attacks, which directlyinterpret data obtained during a single point multiplication. Since usually executions of thepoint addition algorithm can be distinguished from executions of the point doubling algorithm, elliptic curve cryptography is particularly vulnerable to this kind of attack when sidechannel information is available to an adversary unless point multiplication is implemented
with appropriate countermeasures.
Various side-channel attack countermeasures for elliptic curve point multiplication havebeen proposed in the literature. The contributions of the present chapter are two different
methods that use a uniform pattern of point doublings and point additions (avoiding thespecial cases listed above) in order not to reveal information on e. Both methods are very
general (instead of requiring specifically chosen elliptic curves as some other methods, theywork with conventional elliptic curve arithmetic implementations and can be used with standard curves such as the ones recommended by NIST and SECG in [67] and [23], whose use isoften encouraged in order to ease interoperability) and provide good efficiency (unlike earlier
proposals in the literature, they are 2w -ary rather than binary). The first method is a left-toright method based on special representations of scalars. The second method is a right-to-leftmethod employing a special initialization stage; in contrast with the first method, it does
not use an inherently fixed table, thus reducing potential information leakage available toadversaries, and it is easily parallelizable on two-processor systems, where it provides much
improved performance.
Section 8.1 presents some previous side-channel attack countermeasures for elliptic curve
cryptography. Section 8.2 discusses assumptions of the security model underlying the countermeasures in the present chapter and looks into certain implementation details. Section 8.3
describes the new 2w -ary left-to-right method, and section 8.4 describes the new 2w -ary rightto-left method. Section 8.5 provides efficiency comparisons. Section 8.6 shows an idea forscalar randomization in side-channel attack countermeasures.

8.1

Previous Side-Channel Attack Countermeasures

Randomization can be used as a countermeasure against differential side-channel attacks. In
particular, for elliptic curve cryptography, projective randomization is a simple and effective
tool [28]: if(X, Y, Z)
represents (in Jacobian projective coordinates) the point whose affine coordinates are(X/Z 2 , Y /Z 3 ),

8.1 Previous Side-Channel Attack Countermeasures

89

then another representation of the same point that cannot be predicted by the adversary is
obtained by substituting(r2 X, r3 Y, rZ)
with a randomly chosen secret non-zero field element r. When starting from an affine representation (X, Y ), this simplifies to (r2 X, r3 Y, r). Other countermeasures have been proposedthat randomize the computation without depending on the representation of group elements:• eP can be expressed as e(P − Q) + eQ where Q is a random point.
• eP can be expressed as (e + np)P or (e − n)P + nP where n is a random integer.
(Remember that p denotes of the order of the subgroup that is used. See section 8.6 fora new proposal for such scalar randomization.)
However, while these countermeasures may provide protection against differential side-channel
attacks, they are not likely to provide sufficient protection if simple side-channel attacks are
possible. Note that straightforward implementations of elliptic curve systems are particularly
vulnerable to simple side-channel attacks: as adding and doubling require different algorithms,
the bits of e may be plainly visible in a power consumption trace if a simple binary algorithm
is used for point multiplication and the adversary can tell apart point doublings from generalpoint additions. Improved point multiplication algorithms using other scalar representations(see e.g. section 6.2) will obscure e to some degree, but may still reveal plenty of information.
This vulnerability can be avoided by implementing point multiplication in a fixed sequenceof point operations that does not depend on the particular scalar. Note that it is reasonable
to assume that point addition and point subtraction are uniform to the adversary as point
inversion is nearly immediate (dummy inversions can be inserted to obtain the same sequenceof operations for point additions as for point subtractions).
Various point multiplication methods have been proposed that use an alternating sequenceof doublings and additions. The simplest approach is to use a binary point multiplication
method with dummy additions inserted to avoid dependencies on scalar bits [28]; however as
we will see in section 8.2.2, it may be easy for adversaries to determine which additions aredummy operations, so it is not clear that this method provides sufficient security. For odd
scalars, a variant of binary point multiplication can be used where the scalar is represented
in balanced binary representation (digits −1 and +1 without any digits of value zero otherthan leading zeros) [86]. Also Montgomery’s binary point multiplication method [65], which
maintains an invariant Q1 − Q0 = P while computing eP using two variables Q0 , Q1 , can beadapted for implementing point multiplication with a fixed sequence of point operations ([87],[69], [10], [43], [36]). With this approach, specific techniques can be used to speed up point
arithmetic: the doubling and addition steps can be combined; y-coordinates of points may
be omitted during the computation ([65], [10], [43], [36]); and on suitable hardware, parallel
execution can be conveniently used for improved efficiency ([43], [36]).
All of the above point multiplication methods are binary. Given sufficient memory, efficiency can be improved by using the 2w -ary point multiplication methods proposed in sections
8.3 and 8.4. In these methods, the uniform operation pattern in the main loop of the point
multiplication algorithm has one addition after each w doublings.
Multiple side-channel attack countermeasures can be combined; the new point multiplication methods proposed in the current chapter can be used together with one or multiple of therandomization methods mentioned above. In particular, randomized projective coordinates

90

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

should be used (cf. [70]) as noted in the following method descriptions. If the scalar e is along-time key, it should be randomized as described in section 8.6.

8.2

Security against Side-Channel Attacks

The goal to achieve security against side-channel attacks warrants some notes on the model
to be used for the security analysis. While a complete model of all side-channel information ishardly ever attainable (and, in any case, would be closely tied to a specific implementation),
it is possible to describe the workings of the point multiplication algorithm in enough detailto obtain reasonable assurance that information leakage will not be useful to an adversary.
Before looking at the actual point multiplication methods in sections 8.3 and 8.4, we discussdesired features and how to achieve them. The most prominent item to consider are elliptic
curve point operations, where certain special cases should be avoided; this is discussed in
section 8.2.1. At a lower level, we have the individual field operations used to implement
point operations. Section 8.2.2 shows that point multiplication implementations intended to
be secure against side-channel attacks should use randomized projective coordinates, and thatleft-to-right point multiplication methods with a fixed table should use certain extended point
representations. That section also explains why inserting dummy point additions to achieve
uniform behavior appears questionable.

8.2.1

Elliptic Curve Point Operations

As different algorithms are usually required for point doubling and point addition, we assume
that side-channel data reveals the sequence in which these operations take place. Thus thepoint multiplication algorithm should use doublings and additions in a uniform pattern independent of the specific multiplier. We also have to take into account certain special casesthat must be expected to be visible through side channels when they occur (if conventional
implementations of the point operations are employed):• Point doubling 2P requires conditional statements for the case that P is the point at
infinity or that P is a point of order two. If these cases are avoided, then, expressed infield operations, point doubling runs as a fixed routine.
• As mentioned before, point addition P + Q requires conditional statements for the casethat one of the points is the point at infinity, or that P = −Q, or that P = Q. For
other cases, it too can be implemented as a fixed routine.
Note that these special cases do also apply when projective coordinates are used (for example, an addition P + Q invokes a special case when P coincides with Q even it the projective
representations differ). Details of the sequences of field operations used for point doublingand point addition depend on the underlying field (odd characteristic or characteristic 2) andthe choice of point representations (e.g. either affine coordinates or one of multiple styles ofprojective coordinates, cf. [27]), so implementations may vary widely. The essential observation is that the respective algorithm always behaves the same as long as the above special
cases are avoided.

8.2 Security against Side-Channel Attacks

8.2.2

91

Field Operations

While it is reasonable to assume that side-channel observations for, say, a field multiplication
do not immediately reveal the factors involved, it would not be prudent to assume that all
multiplications look the same to an adversary. This is why projective randomization is useful([28], [70]): if, e.g., Jacobian projective coordinates are used, a representation (X, Y, Z) of thepoint with affine coordinates (X/Z 2 , Y /Z 3 ) can be replaced by (r2 X, r3 Y, rZ) for any field
element r 6= 0. If r is secretly chosen at random, then, provided that X 6= 0 and Y 6= 0,
none of the coordinates of the new representation will be predictable to the adversary. Point
doubling or point addition using projective coordinates results in a point represented witha Z-coordinate that is the product of the Z-coordinate(s) of the input point(s) and a shortpolynomial involving one or more other coordinates of the input points; thus the output pointis again in a randomized representation.
However, for a point with X = 0 or Y = 0, every equivalent projective representation
will have an according zero coordinate. An adversary who can choose the input point P toa point multiplication algorithm may be able to exploit the existance of such special points
by selecting P such that intermediate points during the point multiplication willl have a zero
coordinate if a guess for part of the scalar e is correct [39]. Assuming that the zero coordinate
becomes visible through side channels, then if e is constant for many point multiplications,this can be used to determine all of e. Similar attacks can be possible based on intermediate
field elements that appear during individual point operations [3]. A countermeasure for curves
where such attacks are possible is to randomize, if point P may be chosen by the adversary,
the point rather than just its projective representation, i.e. compute eP ase(P + Q) − eQ
for a random point Q. The points Q and eQ can be stored in memory constantly (Q must
be kept secret). As the full attacks require a constant e, they can also be countered by scalarrandomization (see section 8.6).
When randomized projective coordinates are used to prevent the adversary from guessing
the specific inputs to field operations (and thus from directly verifying, for example, which of
several known points are currently being added), the adversary may still be able to recognize
if the same field operation with the same input values is performed multiple times. Even if
these values are not known, this may leak essential information, so it should be avoided. We
now look what should be taken care of.
Many left-to-right algorithms for point multiplication eP , including the one that will bepresented in section 8.3, can be outlined as follows (cf. section 6.1.1):[Precomputation stage.] First, independently of the specific multiplier e, certain small
multiples of P are computed and stored in a table.
[Evaluation stage.] Second, the product eP is evaluated as follows: a variable A is initialized to one of the table values; then, many times, A either is doubled or a table value
is added to A, replacing the previous value of A. Finally, A contains the result eP .
Unless a projective randomization of the table value that has been used is performed whenever
the table is accessed (which will avoid a fixed table at the price of reduced efficiency), the useof a fixed table may allow for statistical attacks. For such algorithms with a fixed table, eachentry of the precomputed table should contain not only the representation of the point, but

92

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

additionally any field elements that would have to be computed each time the point is added
to A. If Jacobian projective coordinates are used, this means that (X, Y, Z, Z 2 , Z 3 ) should be
stored (Chudnovsky Jacobian coordinates, see [18]) rather than just (X, Y, Z) (cf. the addition
formulas in [12, Chapter IV.2] or [41]). If such extended point representations are not used
for the precomputed table, the adversary may be able to guess easily which point additions
involve the same table value.
There are point multiplication algorithms that can achieve a fixed pattern of doublings andadditions only if dummy additions are inserted into the evaluation stage. That is, sometimes
a table value is added to A, but the result is thrown away and A is left unchanged. The
problem with dummy additions is that the adversary may be able to tell that their result isignored: for Jacobian projective coordinates, each point operation requires squaring the Zcoordinate of A; if A is not changed, then two consecutive point operations involve the verysame squaring. The point multiplication algorithms presented in sections 8.3 and 8.4 achieve
uniform behavior without resorting to dummy additions.

8.3

2w -Ary Left-to-Right Method

Left-to-right point multiplication algorithms look at the digits of some representation of thescalar starting at the most significant position and proceed down to the least significant one(see section 6.1.1). A simple way to obtain a uniform sequence of doublings and additions(namely, one addition after each w doublings in the main loop of the point multiplication
algorithm) in left-to-right point multiplication is to use a 2w -ary scalar encoding and toinsert a dummy addition whenever a zero digit is encountered. However, as we have seen
in section 8.2.2, using dummy additions to achieve uniform behavior is questionable because
it may be visible to the adversary which additions are dummy additions. Here we will lookat a modified 2w -ary left-to-right point multiplication method that does not need dummy
additions for uniform behavior.
This method may fail in some cases in that an addition step may turn out to be a point
doubling or may involve the point at infinity (which both requires special treatment and ispotentially clearly visible through side channels). However, we will show that the probabilityof this happening is close to zero if multipliers are appropriately selected: randomly chosen e
is safe.
Section 8.3.1 describes how to encode the multiplier e into special signed-digit representations. Section 8.3.2 discusses the multiplication algorithms implied by these representations.
Section 8.3.3 shows that, unless e is ill-chosen, this point multiplication algorithm indeed
limits information leakage as intended.

8.3.1

Recoding Algorithms

Let the positive integer e be given in 2w -ary digits where w ≥ 2 is a small integer; namely,
0

e=

`
X

b0i · 2wii=0with b0i ∈ {0, 1, . . ., 2w − 1}. We demand that `0 be chosen minimal, i.e. b0`0 6= 0. For i > `0 , wedefine that b0i = 0.

8.3 2w -Ary Left-to-Right Method

93

The first (basic) recoding algorithm converts this into a representatione=X̀bi · 2wii=0such thatbi ∈ {−2w , 1, 2, . . ., 2w − 1}.
This means that we disallow digit value 0 and instead introduce the new value −2w . Intuitively, the recoding algorithm replaces 0 digits by −2w and increments the more significant
neighbor digit to adjust the value. A slightly more complicated variant of the multiplier
recoding algorithm produces digitsbi ∈ −2w , ±1, ±2, . . ., ±(2w−1 − 1), 2w−1instead. Note that the set of possible digit values still has 2w elements. As we will see insection 8.3.2, this alternative representation leads to improved efficiency.
It is easy to see that for both recoding techniques, b` is necessarily positive (otherwise ewould be negative) and that the representation of e needs to grow by at most one digit, i.e.
` = `0 or ` = `0 + 1.
We express the recoding algorithms recursively, using auxiliary values ci and ti such that0 ≤ ci ≤ 2 and 0 ≤ ti ≤ 2w + 1: let
c0 = 0,and for i = 0, . . ., `0 + 1, letti = b0i + ci
where for the basic recoding algorithm we have(ci+1 , bi ) =
(1, −2w )

(0, ti )
(2, −2w )

(1, 1)

if
if
if
if

ti = 0
0 < ti < 2w
ti = 2w
ti = 2w + 1

if
if
if
if
if

ti = 0
0 < ti ≤ 2w−1
2w−1 < ti < 2w
ti = 2w
ti = 2w + 1.

and for the variant we have(ci+1 , bi ) =
(1, −2w ) (0, ti )(1, −2w + ti )
(2, −2w )

(1, 1)

Note that ci+1 · 2w + bi = ti always holds.
If b`0 +1 6= −2w , then
e=

0 +1
`X

bi · 2wi ;i=0

in this case, we set ` = `0 + 1. Otherwise, we have
0

e=

`
X
i=0

bi · 2wi

94

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

and b0` 6= −2w , and we set ` = `0 .
Observe that if b` = 1 (and ` > 0), then b`−1 6= −2w .
As a countermeasure against side-channel attacks on the recoding algorithm itself, assignments can be implemented by table lookups instead of using conditional statements.
Storing the converted representation of e requires almost no additional memory comparedwith the original representation: digit values can be stored modulo 2w . If w is understood,
this new representation can be stored as an ordinary integer (leading 0 digits can simply beignored because b` is never −2w ). This integer is at most two bits longer than e; the maximum
possible length growth occurs if ` = `0 + 1 and b` = 2.
It may be desirable to ensure that the encoded form has a predetermined maximum
index `. For our point multiplication application, if `w is large enough compared with thebinary length of group order p, this is easy to do: if necessary, adjust e by adding p or amultiple of p.
If a random multiplier is required and a uniform distribution is not essential, then random
bits can be used directly to generate the recoded form of e. In this case, too, it should beensured that b`−1 6= −2w if b` = 1.

8.3.2

Point Multiplication Algorithm

Remember that we want to compute eP where point P should have order p, p being a large
prime that divides the order of the elliptic curve E(Fq ). For our point multiplication algorithm
to work as intended, ord(P ) may be any positive multiple of p.
If point P can be chosen by the adversary, we must be aware that it might have incorrect
order. In case that #E(Fq ) = p, then (besides testing that P is indeed a point on the curve)
we just have to verify that P is not the point at infinity, O. Otherwise, we need an additional
sanity check. Let h be the cofactor of the elliptic curve, i.e. the integer # E(Fq ) /p. Curves
used for cryptography are usually selected such that h is very small ([22] requires h ≤ 4).
Thus hP can be computed quickly; if it is not O, then we know that p divides ord(P ).
If P has incorrect order, computing eP must be rejected. Otherwise, given a representatione=X̀bi · 2wii=0of e as determined by one of the recoding algorithms from section 8.3.1, eP can be computed by the procedure shown in algorithm 8.1 in the case of the basic recoding algorithm
or algorithm 8.2 in the case of the variant. For both cases, what is shown is a high-leveldescription of the algorithm: as explained in section 8.2.2, implementations should use randomized projective coordinates, and values computed in the precomputation stage should be
stored in extended point representation. The algorithm for the basic case requires 2w−1 + `w
point doublings and 2w−1 − 1 + ` point additions; the algorithm for the variant, which makes
extended use of the ease of inversion in elliptic curve groups, requires 2w−2 + 1 + `w point
doublings and 2w−2 − 1 + ` point additions. (When comparing the efficiency, note that for
the variant a larger choice of w might be preferable.)
The obvious way to implement A ← 2w A in this procedure is w-fold iteration of thestatement A ← 2A, but depending on the elliptic curve, more efficient specific algorithms for
w-fold point doubling may be available (see [42]).
During the procedure shown in algorithm 8.1 or algorithm 8.2, a projective randomization should be performed twice. First, if the precomputed table of multiples of P is stored in8.3 2w -Ary Left-to-Right Method

Algorithm 8.1 ComputeP`95

wi P where b ∈ {−2w , 1, 2, . . ., 2w − 1}ii=0 bi · 2{Precomputation stage}
P1 ← P
for n = 2 to 2w − 2 step 2 doPn ← 2Pn/2
Pn+1 ← Pn + P{now Pn = nP , Pn+1 = (n + 1)P }P−2w ← −2P2w−1{now P−2w = (−2w )P }



{Evaluation stage}
A ← Pb`for j = ` − 1 down to 0 do
A ← 2w A
A ← A + Pbj
return A
projective coordinates, the representation of P should be randomized before the table is computed (if the table of multiples of P is stored in affine coordinates to speed up the evaluation
stage by using mixed addition of affine and projective points [27], this first randomization
obviously is not necessary; but using such fixed and predictable table entries may help differential side-channel attacks and thus cannot be recommended). Second, at the beginning of theevaluation stage, after the initial value has been assigned to A, the representation of A shouldbe randomized. For best assurance against statistical attacks, a projective randomization of
the table value that has just been used can be performed whenever the evaluation stage accesses the precomputed table. However, unless e is constant over many point multiplications,this should not be necessary; see section 8.6 for how a constant e can be avoided.

8.3.3

Uniformity of the Point Multiplication Algorithm

It is apparent that algorithms 8.1 and 8.2 use doublings and additions in a regular pattern.
As discussed in section 8.2, to show that the procedure has uniform behavior and thus issuitable for limiting information leakage during the computation of eP , we also have to showthat the following special cases of point doubling and point addition can be avoided:• 2O• 2A where ord(A) = 2• A + O or O + B• A+A• A + (−A)
We have required that ord(P ) be a positive multiple of p. Without loss of generality, here
we may assume that ord(P ) = p. (Otherwise, multiply P by the cofactor h = # E(Fq ) /p

96

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

Algorithm 8.2 ComputeP`

i=0 bi · 2{Precomputation stage}
P1 ← P
for n = 2 to 2w−1 − 2 step 2 doPn ← 2Pn/2
Pn+1 ← Pn + P
P2w−1 ← 2P2w−2
P2w ← 2P2w−1

wi P where bw
w−1 − 1), 2w − 1}i ∈ {−2 , ±1, ±2, . . ., ±(2{Evaluation stage}if b` > 0 thenA ← Pb`else
A ← −P|b` |for j = ` − 1 down to 0 do
A ← 2w A
if bj > 0 thenA ← A + Pbj
else
A ← A − P|bj |return A
to obtain a point of order p. In the algorithm performed for P , the above special cases canoccur only when one of them would occur in the algorithm performed for hP ; in particular,ord(A) = 2 would imply hA = O, so points of order 2 are not an issue if we can show that the
point at infinity can be avoided.) Then, as 2w can be expected to be much smaller than p, allprecomputed points Pbj = bj P in algorithms 8.1 and 8.2 will be of order p. Thus, initially wehave A 6= O; and as long as we avoid additions of the form A + (−A), it will remain like this.
So what is left to be checked is whether in the evaluation stage of algorithms 8.1 and 8.2 wecan avoid that A = bj P or A = −bj P before an addition or subtraction takes place.
With
ej =

X̀

bi · 2w(i−j) ,i=j

the point addition step in the evaluation stage loop of algorithm 8.1 or 8.2 performs the point
addition (2w · ej+1 )P + bj P . Thus we are safe if
2w · ej+1 6≡ ±bj(mod p).

Since |ej | ≤ 2(1+`−j)w and |bj | ≤ 2w , for many indices j we have |2w · ej+1 | + |bj | < p, meaningthat reduction modulo p does not matter and it suffices to check whether 2w · ej+1 6= ±bj .
The largest index to consider is j = ` − 1; for this case, the question is whether we canbe sure that 2w · e` 6= ±b`−1 . Indeed we can, as e` = b` and if b` = 1, then b`−1 6= −2w (seesection 8.3.1). It follows that ej ≥ 2(`−j)w , which shows that the incongruence is satisfied forindices j < ` − 1 too as long as we do not have to consider reduction modulo p.
For indices j so small such that this modular reduction is relevant, we argue that if e issufficiently random, then the probability of picking an e such that the above incongruence8.4 2w -Ary Right-to-Left Method

97

is not satisfied can be neglected: it is comparable to the probability that e mod p can beguessed in a modest number of attempts, which can be presumed to be practically impossible(otherwise, side-channel attacks should not be a concern since e could not really be consideredsufficiently secret in the first place).

8.4

2w -Ary Right-to-Left Method

Right-to-left point multiplication algorithms look at the digits of some representation of thescalar starting at the least significant position and proceed up to the most significant one(see section 6.1.2). A regular sequence of doublings and additions (with one addition after
each w doublings in the main loop of the point multiplication algorithm) can be obtained inright-to-left point multiplication by using a 2w -ary scalar encoding and treating 0 like anyother digit value. However, this approach is not fully sufficient for obtaining uniform behavior
because the special cases of point addition (see section 8.2.1) would reveal information on thescalars.
The 2w -ary right-to-left point multiplication method presented in the following is basedon the observation that a special randomized initialization stage can be used to avoid the
problematic special cases. The right-to-left method is easily parallelizable and can provide
much improved performance on two-processor systems.
The method for computing eP is parameterized by an integer w ≥ 2 and a digit set B
consisting of 2w integers of small absolute value such that every positive scalar e can be
represented in the formXe=bi 2wi0≤i≤`using digits bi ∈ B; for example
B = {0, 1, . . ., 2w − 1}orB = {−2w−1 , . . ., 2w−1 − 1}.
A representation of e using the latter digit set can be easily determined on the fly when
scanning the binary digits of e in right-to-left direction. If e is at most n bits long (i.e. 0 <e < 2n ), ` = bn/wc is sufficient.
Let B 0 denote the set {|b| | b ∈ B} of absolute values of digits, which has at least 2w−1 + 1
and at most 2w elements. The point multiplication method uses #(B 0 )+1 variables for storing
points on the elliptic curve in projective representation: one variable Ab for each b ∈ B 0 , andone additional variable Q.
The method works in three stages, which we call initialization stage, right-to-left stage,
and result stage. We will first look at a high-level view of these stages before discussing thedetails. Let AInit
denote the value of Ab at the end of the initialization stage, and let Asumbbdenote the value of Ab at the end of the right-to-left stage.
The initialization stage sets up the variables Ab (b ∈ B 0 ) in a randomized way such thatInit
Ab 6= O for each b, but
X

b∈B 0

bAInitb = O.

98

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

Then the right-to-left stage performs computations depending on P and the digits bi , yielding
new values Asumof the variables Ab satisfyingb
Asum= AInitbb +X

2wi P −

0≤i≤`
bi =b

X

2wi P

X

wi

0≤i≤`
bi =−bfor each b ∈ B 0 . Finally, the result stage computes
X

bAsum
b ,

b∈B 0 \{0}which yields the final result eP because
X

bAsum
b

X

=

b∈B 0 \{0}bAInit+bb∈B 0 \{0}

|

=

{z
O

X

X

b

b∈B 0 \{0}

}

0≤i≤`
bi =b

2 P−

X

wi

2 P

!

0≤i≤`
bi =−bbi 2wi P = eP .

0≤i≤`

Section 8.4.1 discusses the initialization stage, section 8.4.2 the right-to-left stage, andsection 8.4.3 the result stage. Section 8.4.4 presents some variants.

8.4.1

Initialization Stage

The initialization stage can be implemented as follows:
1. For each b ∈ B 0 \{1}, generate a random point on the elliptic curve and store it invariable Ab .
2. Compute the point −Pb∈B 0 \{0,1} bAb and store it in variable A1 .

3. For each b ∈ B 0 , perform a projective randomization of variable Ab .
The resulting values of the variables Ab are denoted by AInitb .
If the elliptic curve is fixed, precomputation can be used to speed up the initialization
stage: run steps 1 and 2 just once, e.g. during personalization of a smart card, and store theresulting intermediate values Ab for future use. We denote these values by Afix
b . Then only
step 3 (projective randomization of the values Afixtoobtainnewrepresentations
AInitbb ) has tobe performed anew each time the initialization stage is called for. The points Afixb must not
be revealed; they should be protected like secret keys.
Generating a random point on an elliptic curve is straightforward. For each element Xof the underlying field, there are zero, one or two values Y such that (X, Y ) is the affine
representation of a point on the elliptic curve. Given a random candidate value X, it ispossible to compute an appropriate Y if one exists; the probability for this is approximately
1/2 by Hasse’s theorem. If there is no appropriate Y , one can simply start again with a
new X.
Computing an appropriate Y given X involves solving a quadratic equation, which usually(depending on the underlying field) is computationally expensive. This makes it worthwhile
to use precomputation as explained above. It is also possible to reuse the values that have

8.4 2w -Ary Right-to-Left Method

99

remained in the variables Ab , b 6= 1, after a previous computation, and start at step 2 of theinitialization stage.
P
To determine − b∈B 0 \{0,1} bAb in step 2, it is not necessary to compute all the individual products bAb . Algorithm 8.3 can be used instead to set up A1 appropriately if
B 0 = {0, 1, . . ., β}, β ≥ 2. (Note that both loops will be skipped in the case β = 2.) This
Algorithm 8.3 Compute A1 ← −for i = β − 1 down to 2 do
Ai ← Ai + Ai+1
A1 ← 2A2
for i = 2 to β − 1 do
Ai ← Ai − Ai+1
A1 ← A1 + Ai+1
A1 ← −A1Pb∈{2,...,β} bAb in the initialization stagealgorithm takes one point doubling and 3β − 6 point additions. When it has finished, thevariables Ab for 1 < b < β will contain modified values, which are representations of thepoints originally stored in the respective variables. If sufficient memory is available, a faster
algorithm can be used to compute A1 without intermediate modification of the variables Ab
for b > 1 (use additional variables Qb instead; in this case, see section 8.4.3 for a possible
additional improvement if point doublings are faster than point additions).
The projective randomization of the variables Ab (b ∈ B 0 ) in step 3 has the purpose toprevent adversaries from correlating observations made during the computation of A1 in theinitialization stage with observations from the following right-to-left stage. If algorithm 8.3
has been used to compute A1 and the points are not reused for multiple invocations of theinitialization stage, then no explicit projective randomization of the variables Ab for 1 < b < β
is necessary; and if β > 2, no explicit projective randomization of A1 is necessary: the variables
have automatically been converted into new representations by the point additions used todetermine their final values.

8.4.2

Right-to-Left Stage

Algorithm 8.4 implements the right-to-left stage using a uniform pattern of point doublingsand point additions. Initially, for each b, variable Ab contains the value AInitb ; the final value isdenoted by Asum.
Due
tospecial
cases
that
must
be
handled
in
the
point
addition algorithmb
Algorithm 8.4 Right-to-left stageQ←P
for i = 0 to ` do
if bi ≥ 0 thenAbi ← Abi + Q
elseA|bi | ← − (−A|bi | ) + Q
Q ← 2w Q(see section 8.2.1), uniformity of this algorithm is violated if A|bi | is a projective representationof ±Q; the randomization in the initialization stage ensures that the probability of this is

100

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

close to zero. This is why in section 8.4.1 we required that precomputed values Afixb be kept
fix
secret: adversaries must not be able to choose P depending on the values Ab , or they might
be able to trigger the special cases.
If B contains no negative digits, the corresponding branch in the algorithm can be omitted.
Otherwise, implementations should use dummy point inversions to achieve uniform behavior
for the two conditional branches.1
The obvious way to implement Q ← 2w Q in this algorithm is w-fold iteration of thestatement Q ← 2Q, but depending on the elliptic curve, more efficient specific algorithms for
w-fold point doubling may be available (see [42]).
In the final iteration of the loop, the assignment to Q may be skipped (the value Q is not
used after the right-to-left stage has finished). With this modification, the algorithm uses `w
point doublings and ` + 1 point additions.
Observe that on two-processor systems the point addition and the w-fold point doublingin the body of the loop may be performed in parallel: neither operations depends on theother’s result.

8.4.3

Result Stage

Similarly to the computation of A1 in the initialization stage, the result stage computation
X

bAsum
b

b∈B 0 \{0}can be performed without computing all the individual products bAsum
b . In the result stage, it
is not necessary to preserve the original values of the variables Ab , so algorithm 8.5 (from [46,answer to exercise 4.6.3-9]) can be used if B 0 = {0, 1, . . ., β} when initially each variable Abcontains the value Asumb . This algorithm uses 2β − 2 point additions.
Algorithm 8.5 Computesum when initially A = Asumbb∈{1,...,β} bAbbP

for i = β − 1 down to 1 do
Ai ← Ai + Ai+1
for i = 2 to β do
A1 ← A1 + Ai
return A1
Elliptic curve point arithmetic usually has the property that point doublings are fasterthan point additions. Then the variant given in algorithm 8.6 is advantageous. This algorithm
uses bβ/2c point doublings and 2β − 2 − bβ/2c point additions.

8.4.4

Variants

In he following, we discuss some variations of the right-to-left point multiplication method.
1

In the publication [61], the second branch was written as A|bi | ← A|bi | − Q. Katsuyuki Okeya has pointed
out the problem that then if adversaries are able to predict the representations of Q and −Q, they may beable to distinguish between the two conditional branches even if dummy point inversions are used to let point
additions look like point subtractions. Note that this problem is avoided when a projective randomization of P
is performed before beginning the right-to-left stage.

8.4 2w -Ary Right-to-Left Method

Algorithm 8.6 Computefor i = β down to 1 do
if 2i ≤ β thenAi ← Ai + A2i
if i is even thenif i < β thenAi ← Ai + Ai+1
Ai ← 2Ai
else
if i > 1 thenA1 ← A1 + Ai
return A1

101

sum when initially A = Asum (variant)bb∈{1,...,β} bAbbP

Projective Randomization of P
While it does not appear to be strictly necessary, it can be recommended to perform a
projective randomization of P before beginning the right-to-left stage (algorithm 8.4). At
small computational cost, this will further reduce the side-channel information available topotential adversaries.
Avoiding Digit 0
In the point multiplication method as described in sections 8.4.2 and 8.4.3, if 0 ∈ B, thevariable A0 is essentially a dummy variable: its value does not affect the final result. Now
assume that an adversary is performing a fault attack [13] by purposefully inducing computation faults. If these faults occur only during computations affecting A0 , the result of thepoint multiplication will still be correct. Thus, verifying the result cannot reveal that a fault
attack has taken place. Therefore it may be useful to avoid the dummy variable.
The point multiplication method can be used with a digit set B that does not include thevalue 0, e.g.

B = −2w , ±1, ±2, . . ., ±(2w − 2), 2w − 1
as in the variant in section 8.3.1. Compared with digit set {−2w−1 , . . ., 2w−1 −1}, this requires
modifications to the algorithms used in step 2 of the initialization stage (section 8.4.1) and in
the result stage (section 8.4.3). If we assume that the initialization stage uses precomputed
points Afixb , only the changes to the result stage will increase the computational cost of a point
multiplication. The result stage for said digit set has to compute the sum
X

bAsum
b ;

b∈{1,...,2w−1 ,2w }the additional cost is one point doubling and one point addition (set A2w−1 ← A2w−1 + 2A2w
before running algorithm 8.5 or 8.6).
Variant for w = 1
The right-to-left point multiplication method as described before works only for w ≥ 2 becauseP0
Initof the requirement that AInitb∈B 0 bAb = O. The method can beb 6= O for each b ∈ B , but

102

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

adapted to the case w = 1 with
B = {0, 1}
by relinquishing the latter part of the requirement; instead, save the value AInit
1 and compute
sum
Init
2
Init
A1 − A1 in the result stage. If A1 is just a projective randomization of a precomputed
Init
sum −
random point Afix
1 , there is no need to save A1 : the result stage can simply compute A1Afix
1 .
Application to Modular Exponentiation
The right-to-left method with a randomized initialization stage can similarly be used formodular exponentiation. For this purpose, digit set B will only contain non-negative digits
as modular inversion is an expensive operation.

8.5

Efficiency Comparison

For elliptic curve cryptography over prime fields using Jacobian projective coordinates, apoint addition can be done in 16 field multiplications (here we count squarings as multiplications), and curves are usually chosen such that a point doubling can be done in 8 field
multiplications [41]. The cost for a projective randomization, transforming (X, Y, Z) into
(r2 X, r3 Y, rZ), is 5 field multiplications. Converting a point (X, Y, Z) into extended point
representation (X, Y, Z, Z 2 , Z 3 ), Chudnovsky Jacobian coordinates, takes 2 field multiplications. A point addition costs 14 field multiplications if one of the points to be added is given
in Chudnovsky Jacobian coordinates and the result is needed in Jacobian coordinates, or if
both points are given in Chudnovsky Jacobian coordinates and the result is needed in Chudnovsky Jacobian coordinates as well; a point doubling in Chudnovsky Jacobian coordinates
representation costs 9 field multiplications [18].
We first examine the efficiency of the algorithms for performing a point multiplication eP
in a small configuration with w = 2.
The 2w -ary left-to-right method from section 8.3 with digit set {−4, −1, 1, 2} (threepoints P , 2P , 4P to precompute) uses one projective randomization followed be two point
doublings for precomputation and then one projective randomization, 2` point doublings, and` point additions for determining the result.
Now one possibility is to use Chudnovsky Jacobian coordinates for the precomputed table.
Then the cost for the precomputation stage is 2 · 9 + 5 + 2 = 25 field multiplications, the costfor the evaluation stage is ` · 14 + 2` · 8 + 5 = 30` + 5 field multiplications, and the total costis30` + 30
field multiplications. Alternatively, to avoid concerns about keeping the table constant during
one point multiplication, we can use usual Jacobian coordinates for the precomputed tableand perform a projective randomization of the table value used after each except the very
last point addition. Then the cost for the precomputation stage is 2 · 8 + 5 = 21, the cost for
the evaluation stage is ` · 16 + 2` · 8 + ` · 5 = 37 · `, and the total cost becomes37` + 21
2This variant was suggested by Tsuyoshi Takagi.

8.5 Efficiency Comparison

103

field multiplications. Assuming 160-bit scalars (` = 80), we have 2430 field multiplications
for the first implementation choice or 2981 for the second.
For the 2w -ary right-to-left method from section 8.4 with digit set B = {−2, −1, 0, 1}
fix
fix
fix
fix
(i.e. four variables A0 , A1 , A2 , Q), we assume that points Afix
0 , A1 , A2 such that A1 = −2A2
have been precomputed since generating a random point on the curve would be rather expensive. In this scenario, the initialization stage has to perform three projective randomizations,i.e. 15 field multiplications; the right-to-left stage uses 2` point doublings and ` + 1 point
additions, i.e. (` + 1) · 16 + 2` · 8 = 32` + 16 field multiplications; and the result stage can be
implemented in one point doubling and one point addition, i.e. 16 + 8 = 24 field multiplications. The total cost is32` + 55
field multiplications; assuming 160-bit scalars (` = 80), we have 2615 field multiplications.
With two processors, in the loop of the right-to-left stage, the two point doublings (2 · 8 =16 field multiplications) can be performed in parallel with the one point addition (also 16 field
multiplications), and so we can remove 16` field multiplications from the tally. (We ignore
the small additional savings that can be achieved through parallelization in the other stages.)Only
16` + 55
field multiplications remain; for 160-bit scalars, this is 1335 field multiplications.
Now we consider similar scenarios with arbitrary window sizes w ≥ 2 and arbitrary scalar
bit lengths n. The left-to-right method from section 8.3 (again using the efficiency-improving
variant of the recoding algorithm) with Chudnovsky Jacobian coordinates for the precomputed table uses one projective randomization, one conversion into Chudnovsky Jacobian
coordinates, 2w−2 + 1 point doublings, and 2w−2 − 1 point additions for precomputation,i.e. 5 + 2 + (2w−2 + 1) · 9 + (2w−2 − 1) · 14 = 2w−2 · 23 + 2 field multiplications; and one projective randomization, bn/wc · w point doublings, and bn/wc point additions for computing
the result, i.e. 5 + bn/wc · w · 8 + bn/wc · 14 = bn/wc · (w · 8 + 14) + 5 field multiplications.
The total cost of this isjnk· (w · 8 + 14) + 2w−2 · 23 + 7
w
field multiplications. The left-to-right method with additional projective randomizations to
avoid a fixed table uses one projective randomization, 2w−2 + 1 point doublings, and 2w−2 − 1point additions for precomputation, i.e. 5 + (2w−2 + 1) · 8 + (2w−2 − 1) · 16 = 2w−2 · 24 − 3field multiplications; and bn/wc projective randomizations, bn/wc · w point doublings, andbn/wc point additions for computing the result, i.e. bn/wc · 5 + bn/wc · w · 8 + bn/wc · 16 =bn/wc · (w · 8 + 21) field multiplications. The total cost of this isjnkw· (w · 8 + 21) + 2w−2 · 24 − 3field multiplications.
For arbitrary window size w ≥ 2 and scalar bit length n, the right-to-left method fromsection 8.4 with a scalar encoding using digits from the set {−2w−1 , . . ., 2w−1 − 1} (with` = bn/wc, β = 2w−1 ) performs 2w−1 + 1 projective randomizations in the initialization stage(2w−1 · 5 + 5 field multiplications); bn/wc · w point doublings
and bn/wc + 1 point additions
in the right-to-left stage (bn/wc · w · 8 + bn/wc + 1 · 16 = bn/wc · (w · 8 + 16) + 16 field

104

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

Table 8.1: Number of field multiplications for a 160-bit point multiplication
w
2
3
4
5
6
L-to-R method, Chud. Jac. coordinates
2430 2067 1939 1919 1987
L-to-R method, proj. rand. to avoid fixed table 2981 2430 2213 2141 2175
R-to-L method
2615 2241 2173 2309 2709
R-to-L method, two processors
1335 1393 1533 1797 2293
multiplications); and 2w−2 point doublings and 3 · 2w−2 − 2 point additions in the result stage(2w−2 · 8 + (3 · 2w−2 − 2) · 16 = 2w−2 · 56 − 32 field multiplications). The total cost isjnkw· (w · 8 + 16) + 2w−2 · 66 − 11

field multiplications.
Note that for the right-to-left method in the case with parallelization, w = 2 provides
better performance than larger values of w (the right-to-left stage provides essentially thesame amount of work to both processors if w = 2). Compared with the one-processor variant,
we always save bn/wc · 16 field multiplications, andjnkw· w · 8 + 2w−2 · 66 − 11

field multiplications remain.
Table 8.1 compares the efficiency of the methods for various window sizes in the case of
160-bit scalars. Table 8.2 provides a similar comparison for 256-bit scalars. (Note that these
efficiency comparisons do not take into account the additional cost of generating random field
elements for projective randomization; only field multiplications are counted.) Table entries
are printed in bold if the respective window size w provides a lower field multiplication countthan smaller values of w, i.e. if w is optimal for certain bounds on memory usage.
The right-to-left method needs read-write memory for the same number of points as theleft-to-right method with the same window size. (The right-to-left method needs additional
read-only memory for the precomputed points Afixb .) The tables show that for the example
bit-lengths, when using a single processor, the left-to-right method with Chudnovsky Jacobian
coordinates is always the fastest; but remember that the table contains more field elements
because Chudnovsky Jacobian coordinates have the form (X, Y, Z, Z 2 , Z 3 ) rather than just
(X, Y, Z); so if memory is scarce, this method variant may not be applicable. The left-to-rightmethod with additional projective randomizations to avoid a fixed table can be faster than
the right-to-left method, but will need more read-write memory to achieve this: this variant of
the left-to-right method needs w = 5 (17 table values) to outperform the right-to-left methodwith w = 4.

8.6

Scalar Randomization

Okeya and Sakurai [71] describe a second-order power analysis attack on the fixed-table point
multiplication method of section 8.3 (as published in [59]). The attack requires power consumption traces from many point multiplications using the same scalar e (and thus the same
addition chain). The basis of the attack is to detect table-value reuse by observing side-channel

8.6 Scalar Randomization

105

Table 8.2: Number of field multiplications for a 256-bit point multiplication
w
2
3
4
5
6
L-to-R method, Chud. Jac. coordinates
3870 3283 3043 2945 2979
L-to-R method, proj. rand. to avoid fixed table 4757 3870 3485 3300 3279
R-to-L method
4151 3521 3325 3373 3733
R-to-L method, two processors
2103 2161 2301 2557 3061

7
3263
3537
4693
4117

data that leaks information on the Hamming weight of representations of points (cf. [54]):
to find out whether the i-th and j-th point addition use the same table value, compute foreach power consumption trace the difference between (normalized) power consumption measurements at the two points of time when the respective table entries are read from memory;
over sufficiently many point multiplications, the sample variance of these power consumption
differences should converge to one of two values depending on whether the i-th and j-th point
addition use the same table value or different table values.
No experimental results are given in [71]. If this attack is practical, similar attacks may bepossible against most point multiplication methods using a constant sequence of operations
as it may be possible to trace values based on their Hamming weight (i.e. determine whether
the output of the i-th operation is used as input to the j-th operation). A countermeasure isto randomize the addition chain. This can be done by randomizing the scalar e: compute ePwith two point multiplications and one point subtraction asee(e + mN + m)P− mP

e are one-time random numbers
where N is the order of the elliptic curve group and m, m(e.g. 32 bits long).
This can also be expressed as follows:ee(e + mN + m)P+ m(−P)

When computing this sum of products with the right-to-left point multiplication methodfrom section 8.4, the initialization stage and result stage need to be run just once; only theright-to-left stage needs to be run twice. The final result stage will automatically yield the
combined result.
(Adding a multiple of the group order was originally proposed in [48], but it leaves somebias in the least significant digits [70]. Scalar splitting in the form eP = (e + m)P − mP as
proposed in [25] avoids this bias, but is only sufficient if m is of the same length as e, which
would double the cost of a point multiplication. By combining these two ideas, we avoid thebias while keeping the overhead low.)

106

Elliptic Curve Point Multiplication with Resistance against Side-Channel Attacks

Bibliography[1] Abdalla, M., Bellare, M., and Rogaway, P. DHAES: An encryption scheme
based on the Diffie-Hellman problem. Submission to IEEE P1363a. http://grouper.
ieee.org/groups/1363/P1363a/Encryption.html, 1998.
[2] Abdalla, M., Bellare, M., and Rogaway, P. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In Progress in Cryptology – CT-RSA 2001 (2001),
D. Naccache, Ed., vol. 2020 of Lecture Notes in Computer Science, pp. 143–158.
[3] Akishita, T., and Takagi, T. Zero-value point attacks on elliptic curve cryptosystem.
In Information Security – ISC 2003 (2003), Lecture Notes in Computer Science. To
appear.
[4] American National Standards Institute (ANSI). Public key cryptography forthe financial services industry: The elliptic curve digital signature algorithm (ECDSA).
ANSI X9.62, 1998.
[5] Bellare, M., Canetti, R., and Krawczyk, H. Keying hash functions for message
authentication. In Advances in Cryptology – CRYPTO ’96 (1996), N. Koblitz, Ed.,
vol. 1109 of Lecture Notes in Computer Science, pp. 1–15.
[6] Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. A concrete security treatment of symmetric encryption. In 38th Annual Symposium on Foundations of Computer
Science (FOCS ’97) (1997), IEEE Computer Society, pp. 394–403.
[7] Bellare, M., Kilian, J., and Rogaway, P. The security of cipher block chaining. In
Advances in Cryptology – CRYPTO ’94 (1994), Y. G. Desmedt, Ed., vol. 839 of Lecture
Notes in Computer Science, pp. 341–358.
[8] Bellare, M., Kilian, J., and Rogaway, P. The security of the cipher block chaining
message authentication code. Journal of Computer and System Sciences 61 (2000), 362–
399.
[9] Bellare, M., and Rogaway, P. Random oracles are practical: A paradigm for designing efficient protocols. In First Annual Conference on Computer and Communications
Security (1993), ACM, pp. 62–73.
[10] Bier, É., and Joye, M. Weierstraß elliptic curves and side-channel attacks. In Public
Key Cryptography – PKC 2002 (2002), D. Naccache and P. Paillier, Eds., vol. 2274 of
Lecture Notes in Computer Science, pp. 335–345.
107

108

Bibliography[11] Black, J., Halevi, S., Krawczyk, H., Krovetz, T., and Rogaway, P. UMAC:
Fast and secure message authentication. In Advances in Cryptology – CRYPTO ’99(1999), M. Wiener, Ed., vol. 1666 of Lecture Notes in Computer Science, pp. 216–233.
[12] Blake, I. F., Seroussi, G., and Smart, N. P. Elliptic Curves in Cryptography,
vol. 265 of London Mathematical Society Lecture Note Series. Cambridge University
Press, 1999.
[13] Boneh, D., DeMillo, R. A., and Lipton, R. J. On the importance of eliminating
errors in cryptographic computations. Journal of Cryptology 14 (2001), 101–119.
[14] Bos, J., and Coster, M. Addition chain heuristics. In Advances in Cryptology –CRYPTO ’89 (1989), G. Brassard, Ed., vol. 435 of Lecture Notes in Computer Science,
pp. 400–407.
[15] Bosma, W. Signed bits and fast exponentiation. Department of Mathematics, Universityof Nijmegen, Report No. 9935, 1999.
[16] Brands, S. Rethinking Public Key Infrastructures and Digital Certificates – Buildingin Privacy. MIT Press, 2000.
[17] Brickell, E. F., Gordon, D. M., McCurley, K. S., and Wilson, D. B. Fast
exponentiation with precomputation. In Advances in Cryptology – EUROCRYPT ’92(1993), R. A. Rueppel, Ed., vol. 658 of Lecture Notes in Computer Science, pp. 200–207.
[18] Brown, M., Hankerson, D., López, J., and Menezes, A. Software implementationof the NIST elliptic curves over prime fields. In Progress in Cryptology – CT-RSA 2001
(2001), D. Naccache, Ed., vol. 2020 of Lecture Notes in Computer Science, pp. 250–265.
[19] Canetti, R. Personal communication, 2003.
[20] Canetti, R., Goldreich, O., and Halevi, S. The random oracle methodology,
revisited. In 30th ACM Symposium on Theory of Computing (STOC) (1998), pp. 209–
218.
[21] Canetti, R., Goldreich, O., and Halevi, S. The random oracle methodology,
revisited. E-print cs.CR/0010019, 2000. Available from http://arXiv.org/abs/cs/
0010019.
[22] Certicom Research. Standards for efficient cryptography – SEC 1: Elliptic curve
cryptography. Version 1.0, 2000. Available from http://www.secg.org/.
[23] Certicom Research. Standards for efficient cryptography – SEC 2: Recommended
elliptic curve cryptography domain parameters. Version 1.0, 2000. Available from http://www.secg.org/.
[24] Chaum, D. Untraceable electronic mail, return addresses, and digital pseudonyms.
Communications of the ACM 24 (1981), 84–88.
[25] Clavier, C., and Joye, M. Universal exponentiation algorithm – a first step towards
provable SPA-resistance. In Cryptographic Hardware and Embedded Systems – CHES
2001 (2001), Ç. K. Koç, D. Naccache, and C. Paar, Eds., vol. 2162 of Lecture Notes in
Computer Science, pp. 300–308.

Bibliography109[26] Cohen, H. Analysis of the flexible window powering algorithm. http://www.math.
u-bordeaux.fr/%7Ecohen/window.dvi, 1999.
[27] Cohen, H., Ono, T., and Miyaji, A. Efficient elliptic curve exponentiation using
mixed coordinates. In Advances in Cryptology – ASIACRYPT ’98 (1998), K. Ohta and
D. Pei, Eds., vol. 1514 of Lecture Notes in Computer Science, pp. 51–65.
[28] Coron, J.-S. Resistance against differential power analysis for elliptic curve cryptosystems. In Cryptographic Hardware and Embedded Systems – CHES ’99 (1999), Ç. K. Koçand C. Paar, Eds., vol. 1717 of Lecture Notes in Computer Science, pp. 292–302.
[29] Cottrell, L. Mixmaster & remailer attacks. http://web.archive.org/web/
19961112194057/http://www.obscura.com/%7Elok%i/remailer/remailer-essay.
html, 1996.
[30] Cramer, R., and Shoup, V. Design and analysis of practical public-key encryption
schemes secure against adaptive chosen ciphertext attack. Manuscript, http://shoup.
net/papers/, 2001.
[31] de Rooij, P. Efficient exponentiation using precomputation and vector addition chains.
In Advances in Cryptology – EUROCRYPT ’94 (1995), T. Helleseth, Ed., vol. 950 of
Lecture Notes in Computer Science, pp. 389–399.
[32] Diffie, W., and Hellman, M. E. Multiuser cryptographic techniques. In Proceedingsof AFIPS National Computer Conference (1976), pp. 109–112.
[33] Diffie, W., and Hellman, M. E. New directions in cryptography. IEEE Transactions
on Information Theory 22, 6 (1976), 644–654.
[34] Dimitrov, V. S., Jullien, G. A., and Miller, W. C. Complexity and fast algorithms
for multiexponentiation. IEEE Transactions on Computers 49 (2000), 141–147.
[35] ElGamal, T. A public-key cryptosystem and a signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory 31 (1985), 469–472.
[36] Fischer, W., Giraud, C., Knudsen, E. W., and Seifert, J.-P. Parallel scalarmultiplication on general elliptic curves over Fp hedged against non-differential sidechannel attacks. Cryptology ePrint Archive Report 2002/007, 2002. Available fromhttp://eprint.iacr.org/.
[37] Goldwasser, S., and Micali, S. Probabilistic encryption. Journal of Computer and
System Sciences 28 (1984), 270–299.
[38] Gordon, D. M. A survey of fast exponentiation methods. Journal of Algorithms 27(1998), 129–146.
[39] Goubin, L. A refined power-analysis attack on elliptic curve cryptosystems. In Public
Key Cryptography – PKC 2003 (2003), Y. G. Desmedt, Ed., vol. 2567 of Lecture Notes
in Computer Science, pp. 199–211.
[40] Hamdy, S., and Möller, B. Security of cryptosystems based on class groups ofimaginary quadratic orders. In Advances in Cryptology – ASIACRYPT 2000 (2000),
T. Okamoto, Ed., vol. 1976 of Lecture Notes in Computer Science, pp. 234–247.

110

Bibliography[41] Institute of Electrical and Electronics Engineers (IEEE). IEEE standard
specifications for public-key cryptography. IEEE Std 1363-2000, 2000.
[42] Itoh, K., Takenaka, M., Torii, N., Temma, S., and Kurihara, Y. Fast implementation of public-key cryptography on a DSP TMS320C6201. In Cryptographic
Hardware and Embedded Systems – CHES ’99 (1999), Ç. K. Koç and C. Paar, Eds.,
vol. 1717 of Lecture Notes in Computer Science, pp. 61–72.
[43] Izu, T., and Takagi, T. A fast parallel elliptic curve multiplication resistant againstside channel attacks. In Public Key Cryptography – PKC 2002 (2002), D. Naccache and
P. Paillier, Eds., vol. 2274 of Lecture Notes in Computer Science, pp. 280–296.
[44] Jakobsson, M., and Juels, A. An optimally robust hybrid mix network. In 20th
Annual ACM Symposium on Principles of Distributed Computing (PODC 2001) (2001),
ACM Press, pp. 284–292.
[45] Joye, M., and Tymen, C. Compact encoding of non-adjacent forms with applications
to elliptic curve cryptography. In Public Key Cryptography – PKC 2001 (2001), K. Kim,
Ed., vol. 1992 of Lecture Notes in Computer Science, pp. 353–364.
[46] Knuth, D. E. The Art of Computer Programming – Vol. 2: Seminumerical Algorithms(2nd ed.). Addison-Wesley, 1981.
[47] Knuth, D. E. The Art of Computer Programming – Vol. 2: Seminumerical Algorithms(3rd ed.). Addison-Wesley, 1998.
[48] Kocher, P. C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, andother systems. In Advances in Cryptology – CRYPTO ’96 (1996), N. Koblitz, Ed.,
vol. 1109 of Lecture Notes in Computer Science, pp. 104–113.
[49] Kocher, P. C., Jaffe, J., and Jun, B. Differential power analysis. In Advancesin Cryptology – CRYPTO ’99 (1999), M. Wiener, Ed., vol. 1666 of Lecture Notes in
Computer Science, pp. 388–397.
[50] Krovetz, T., Black, J., Halevi, S., Hevia, A., Krawczyk, H., and Rogaway, P. UMAC: Message authentication code using universal hashing. Internet-Draft
draft-krovetz-umac-01.txt, http://www.cs.ucdavis.edu/~rogaway/umac/, 2000.
[51] Lim, C. H., and Lee, P. J. More flexible exponentiation with precomputation. In
Advances in Cryptology – CRYPTO ’94 (1994), Y. G. Desmedt, Ed., vol. 839 of Lecture
Notes in Computer Science, pp. 95–107.
[52] Lipmaa, H., Rogaway, P., and Wagner, D. Comments to NIST concerning AES
modes of operation: CTR-mode encryption. http://csrc.nist.gov/encryption/
modes/workshop1/papers/lipmaa-ctr.pdf, 2000.
[53] Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A. Handbook of Applied
Cryptography. CRC Press, 1997.
[54] Messerges, T. S. Using second-order power analysis to attack DPA resistant software.
In Cryptographic Hardware and Embedded Systems – CHES 2000 (2000), Ç. K. Koç and
C. Paar, Eds., vol. 1965 of Lecture Notes in Computer Science, pp. 238–251.

Bibliography111[55] Miller, V. S. Use of elliptic curves in cryptography. In Advances in Cryptology –CRYPTO ’85 (1986), H. C. Williams, Ed., vol. 218 of Lecture Notes in Computer Science,
pp. 417–428.
[56] Mixmaster anonymous remailer software.
mixmaster/.

http://sourceforge.net/projects/[57] Miyaji, A., Ono, T., and Cohen, H. Efficient elliptic curve exponentiation. In
International Conference on Information and Communications Security – ICICS ’97(1997), Y. Han, T. Okamoto, and S. Qing, Eds., vol. 1334 of Lecture Notes in Computer
Science, pp. 282–290.
[58] Möller, B. Algorithms for multi-exponentiation. In Selected Areas in Cryptography –SAC 2001 (2001), S. Vaudenay and A. M. Youssef, Eds., vol. 2259 of Lecture Notes in
Computer Science, pp. 165–180.
[59] Möller, B. Securing elliptic curve point multiplication against side-channel attacks. In
Information Security – ISC 2001 (2001), G. I. Davida and Y. Frankel, Eds., vol. 2200 of
Lecture Notes in Computer Science, pp. 324–334.
[60] Möller, B. Securing elliptic curve point multiplication against side-channel attacks,
addendum: Efficiency improvement. http://www.informatik.tu-darmstadt.de/TI/
Mitarbeiter/moeller/ecc-sca-isc01.pdf, 2001.
[61] Möller, B. Parallelizable elliptic curve point multiplication method with resistanceagainst side-channel attacks. In Information Security – ISC 2002 (2002), A. H. Chan
and V. Gligor, Eds., vol. 2433 of Lecture Notes in Computer Science, pp. 402–413.
[62] Möller, B. Improved techniques for fast exponentiation. In Information Security and
Cryptology – ICISC 2002 (2003), P. J. Lee and C. H. Lim, Eds., vol. 2587 of Lecture
Notes in Computer Science, pp. 298–312.
[63] Möller, B. Provably secure public-key encryption for length-preserving chaumianmixes. In Topics in Cryptology – CT-RSA 2003 (2003), M. Joye, Ed., vol. 2612 of
Lecture Notes in Computer Science, pp. 244–262.
[64] Möller, U., and Cottrell, L. Mixmaster protocol version 2. http://www.eskimo.
com/~rowdenw/crypt/Mix/draft-moeller-v2-01.txt, 2000.
[65] Montgomery, P. L. Speeding the Pollard and elliptic curve methods of factorization.
Mathematics of Computation 48 (1987), 243–264.
[66] National Institute of Standards and Technology (NIST). Digital SignatureStandard (DSS). FIPS PUB 186-2, 2000.
[67] National Institute of Standards and Technology (NIST). Digital SignatureStandard (DSS). FIPS PUB 186-2, 2000.
[68] Ohkubo, M., and Abe, M. A length-invariant hybrid mix. In Advances in Cryptology– ASIACRYPT 2000 (2000), T. Okamoto, Ed., vol. 1976 of Lecture Notes in Computer
Science, pp. 178–191.

112

Bibliography[69] Okeya, K. Method of calculating multiplication by scalars on an elliptic curve andapparatus using same. European Patent EP1160661, 2001.
[70] Okeya, K., and Sakurai, K. Power analysis breaks elliptic curve cryptosystems
even secure against the timing attack. In Progress in Cryptology – INDOCRYPT 2000
(2000), B. K. Roy and E. Okamoto, Eds., vol. 1977 of Lecture Notes in Computer Science,
pp. 178–190.
[71] Okeya, K., and Sakurai, K. A second-order DPA attack breaks a window-method
based countermeasure against side channel attacks. In Information Security – ISC 2002
(2002), A. H. Chan and V. Gligor, Eds., vol. 2433 of Lecture Notes in Computer Science,
pp. 389–401.
[72] Pedersen, T., and Pfitzmann, B. Fail-stop signatures. SIAM Journal on Computing
26 (1997), 291–330.
[73] Pippenger, N. On the evaluation of powers and related problems (preliminary version).
In 17th Annual Symposium on Foundations of Computer Science (1976), IEEE Computer
Society, pp. 258–263.
[74] Rackoff, C. W., and Simon, D. R. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In Advances in Cryptology – CRYPTO ’91 (1992),
J. Feigenbaum, Ed., vol. 576 of Lecture Notes in Computer Science, pp. 433–444.
[75] Reitwiesner, G. W. Binary arithmetic. Advances in Computers 1 (1960), 231–308.
[76] Rivest, R. L., Shamir, A., and Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 2 (1978), 120–126.
[77] Sakai, Y., and Sakurai, K. Algorithms for efficient simultaneous elliptic scalar multiplication with reduced joint Hamming weight representation of scalars. In Information
Security – ISC 2002 (2002), A. H. Chan and V. Gligor, Eds., vol. 2433 of Lecture Notes
in Computer Science, pp. 484–499.
[78] Schroeppel, R., Orman, H., O’Malley, S., and Spatscheck, O. Fast key exchange with elliptic curve systems. In Advances in Cryptology – CRYPTO ’95 (1995),
D. Coppersmith, Ed., vol. 963 of Lecture Notes in Computer Science, pp. 43–56.
[79] Shannon, C. E. Communication theory of secrecy systems. Bell System Technical
Journal 28 (1949), 656–715.
[80] Shoup, V. A proposal for an ISO standard for public key encryption. Version 2.1,
December 20, 2001. http://shoup.net/papers/.
[81] Solinas, J. A. An improved algorithm for arithmetic on a family of elliptic curves.
In Advances in Cryptology – CRYPTO ’97 (1997), B. S. Kaliski, Jr., Ed., vol. 1294 of
Lecture Notes in Computer Science, pp. 357–371.
[82] Solinas, J. A. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography
19 (2000), 195–249.

Bibliography113[83] Straus, E. G. Problems and solutions: Addition chains of vectors. American Mathematical Monthly 71 (1964), 806–808.
[84] Thurber, E. G. On addition chains l(mn) ≤ l(n) − b and lower bounds for c(r). Duke
Mathematical Journal 40 (1973), 907–913.
[85] Tsiounis, Y., and Yung, M. On the security of ElGamal-based encryption. In Public
Key Cryptography – PKC ’98 (1998), H. Imai and Y. Zheng, Eds., vol. 1431 of Lecture
Notes in Computer Science, pp. 117–134.
[86] Vadekar, A., and Lambert, R. J. Timing attack resistant cryptographic system.
Patent Cooperation Treaty (PCT) Publication WO 00/05837, 2000.
[87] Vanstone, S. A., and Gallant, R. P. Power signature attack resistant cryptography.
Patent Cooperation Treaty (PCT) Publication WO 00/25204, 2000.
[88] Vernam, G. S. Cipher printing telegraph systems for secret wire and radio telegraphic
communications. Journal of the American Institute of Electrical Engineers XLV (1926),
109–115.
[89] Wegman, M. N., and Carter, J. L. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22 (1981), 265–279.
[90] Yao, A. C.-C. On the evaluation of powers. SIAM Journal on Computing 5 (1976),
100–103.
[91] Yen, S.-M., Laih, C.-S., and Lenstra, A. K. Multi-exponentiation. IEE Proceedings– Computers and Digital Techiques 141 (1994), 325–326.

114

Bibliography

Indexpublic-key, 18
symmetric, 17

adaptive chosen-ciphertext attack, 28, 33,
47
Adv, 21, 35
advantage, 21
CCA, 29, 34, 49
CPA, 21
pseudo-random bit string generator, 35
unlinkability, 47
AdvCCA, 29, 34, 49
AdvCPA, 21
AdvForge, 34
affine representation, 87
almost strongly universal hash function, 31
asymmetric cryptography, 18
asymptotic security, 23

decryption oracle, 28, 29, 33, 34, 48, 49
DH, 19, 55
DHAES, 27, 32
DHIES, 27
Diffie-Hellman, 19, 55
digital signature, 18
domain parameters, 20, 55
DSA, 55, 82
ECDSA, 55, 82
ElGamalencryption, 20, 29
signatures, 55
elliptic curve cryptography, 56, 87
encryption oracle, 21, 29, 46
evaluation stage, 60, 71, 72, 95, 96
exponentiation, 55
fractional windows, 64interleaved, 71, 75
basic, 76
window-NAF based, 77
left-to-right, 60
Lim-Lee, 84
multi-exponentiation, 71
right-to-left, 61
Shamir’s trick, 71
signed fractional windows, 64
signed windows, 62
simultaneous, 71
sliding windows, 62
unsigned fractional windows, 67
with precomputation, 55

basic interleaved exponentiation method,76
bit string oracle, 35
CCA advantage, 29, 34, 49
challenge, 34, 35
ciphertext, 21, 29, 48
chosen-ciphertext attack, 28
adaptive, 28, 33, 47
chosen-plaintext attack, 21
Chudnovsky Jacobian projective representation, 92
CipherLen, 30
ciphertext, 17, 18, 29
challenge, 21, 29, 48
cofactor, 88
collision, 24
computational security, 20
concrete security, 21
counter mode, 32
CPA advantage, 21
cryptography
asymmetric, 18

fail-stop signature schemes, 20
find stage, 28, 29, 48
flexible window size, 86
fractional windows, 64
115

116

generic attack, 24
guess stage, 28, 29, 49
hash function, 19, 24
almost strongly universal, 31
collision, 24
HMAC, 31
hybrid encryption, 27
IND-CCA, 29
IND-CPA, 21
indistinguishability
under chosen-ciphertext attack, 29
under chosen-plaintext attack, 21
information-theoretic security, 18
initialization stage, 97interactive encryption oracle, 48
interleaved exponentiation, 71, 75
Jacobian projective representation, 88
KEM, 18, 30
key, 17
public, 18, 28, 30
secret, 18, 28, 30
key derivation function, 31
key encapsulation mechanism, 18, 30
key encapsulation oracle, 34
key generation algorithm, 28, 30
key generation oracle, 21, 29, 33, 46, 47
left-to-right exponentiation, 60
left-to-right stage, 60, 71, 72
length-expanding decryption, 40
length-preserving mix, 39
Lim-Lee exponentiation, 84
LSB, 57
LSBm , 57
MAC, 31
MAC oracle, 34
message authentication code, 31
mix, 39
modified signed fractional window representation, 65
modified width-(w + 1) NAF, 63
modified window NAF, 63
multi-exponentiation, 55, 71

Index

NAF, 62
negligible, 23
non-adjacent form, 62
one-time message authentication code, 31
one-time pad, 17
oraclebit string, 35
decryption, 28, 29, 33, 34, 48, 49
encryption, 21, 29, 46
interactive, 48
key encapsulation, 34
key generation, 21, 29, 33, 46, 47
MAC, 34
random, 24
OTP, 17
plaintext, 17, 18, 29
point
addition, 87
at infinity, 87
doubling, 87
inversion, 87
multiplication, 87
precomputation, 55
precomputation stage, 60, 71, 72, 95, 96
precomputed table, 60
primitives, 22, 30
projective randomization, 88
projective representation, 87
Chudnovsky Jacobian, 92
Jacobian, 88
pseudo-random bit string generator, 31
public key, 18, 28, 30
public-key cryptography, 18
public-key encryption, 18
public-key encryption scheme, 28
random oracle model, 24
reduction-based security proof, 22
representation
affine, 87
projective, 87
Chudnovsky Jacobian, 92
Jacobian, 88
result stage, 61, 98
right-to-left exponentiation, 61
right-to-left stage, 61, 98

Index

RSA, 55
secret key, 18, 28, 30
security parameter, 23
Shamir’s trick, 71
side-channel attacks, 88
signed fractional windows, 64
signed windows, 62
simultaneous exponentiation, 71
sliding windows, 62
source routing,, 39
STREAM, 31
symmetric cryptography, 17
UHASH, 31
unlinkability, 45
unsigned fractional windows, 67
Vernam encryption, 17
width-(w + 1) NAF, 62
modified, 63
window NAF, 62
modified, 63
window NAF splitting, 85
window size, 62, 72
flexible, 86
window-NAF based interleaved exponentiation method, 77
wNAF, 62117