Guide to pairing-based cryptography

GUIDE TO

PAIRING-BASED

CRYPTOGRAPHY

CHAPMAN & HALL/CRC

CRYPTOGRAPHY AND NETWORK SECURITY

Series Editors

Douglas R. Stinson and Jonathan Katz

Published Titles

Lidong Chen and Guang Gong, Communication System Security

Shiu-Kai Chin and Susan Older, Access Control, Security, and Trust:

A Logical Approach

M. Jason Hinek, Cryptanalysis of RSA and Its Variants

Antoine Joux, Algorithmic Cryptanalysis

Jonathan Katz and Yehuda Lindell, Introduction to Modern

Cryptography, Second Edition

Nadia El Mrabet and Marc Joye, Guide to Pairing-Based Cryptography

Sankar K. Pal, Alfredo Petrosino, and Lucia Maddalena, Handbook on

Soft Computing for Video Surveillance

Burton Rosenberg, Handbook of Financial Cryptography and Security

María Isabel González Vasco and Rainer Steinwandt, Group Theoretic

Cryptography

Chapman & Hall/CRC

CRYPTOGRAPHY AND NETWORK SECURITY

GUIDE TO

PAIRING-BASED

CRYPTOGRAPHY

Edited by

Nadia El Mrabet

SAS - Ecole des Mines de Saint Etienne

Gardanne, France

Marc Joye

NXP Semiconductors

San Jose, USA

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

© 2017 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed on acid-free paper

Version Date: 20161102

International Standard Book Number-13: 978-1-4987-2950-5 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been

made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid￾ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright

holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this

form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may

rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti￾lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy￾ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the

publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://

www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923,

978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For

organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for

identification and explanation without intent to infringe.

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

Contents

Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Symbol Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix

1 Pairing-Based Cryptography Sébastien Canard and Jacques Traoré . 1-1

2 Mathematical Background Jean-Luc Beuchat, Nadia El Mrabet, Laura

Fuentes-Castañeda, and Francisco Rodríguez-Henríquez . . . . . . . . 2-1

3 Pairings Sorina Ionica and Damien Robert . . . . . . . . . . . . . . . 3-1

4 Pairing-Friendly Elliptic Curves Safia Haloui and Edlyn Teske . . . 4-1

5 Arithmetic of Finite Fields Jean Luc Beuchat, Luis J. Dominguez Perez,

Sylvain Duquesne, Nadia El Mrabet, Laura Fuentes-Castañeda, and Fran￾cisco Rodríguez-Henríquez . . . . . . . . . . . . . . . . . . . . . . . . . 5-1

6 Scalar Multiplication and Exponentiation in Pairing Groups Joppe Bos,

Craig Costello, and Michael Naehrig . . . . . . . . . . . . . . . . . . . 6-1

7 Final Exponentiation Jean-Luc Beuchat, Luis J. Dominguez Perez, Laura

Fuentes-Castaneda, and Francisco Rodriguez-Henriquez . . . . . . . . 7-1

8 Hashing into Elliptic Curves Eduardo Ochoa-Jiménez, Francisco Rodríguez￾Henríquez, and Mehdi Tibouchi . . . . . . . . . . . . . . . . . . . . . . 8-1

9 Discrete Logarithms Aurore Guillevic and François Morain . . . . . 9-1

10 Choosing Parameters Sylvain Duquesne, Nadia El Mrabet, Safia Haloui,

Damien Robert, and Franck Rondepierre . . . . . . . . . . . . . . . . . 10-1

11 Software Implementation Diego F. Aranha, Luis J. Dominguez Perez,

Amine Mrabet, and Peter Schwabe . . . . . . . . . . . . . . . . . . . . 11-1

12 Physical Attacks Nadia El Mrabet, Louis Goubin, Sylvain Guilley, Jacques

Fournier, Damien Jauvart, Martin Moreau, Pablo Rauzy, and Franck Ron￾depierre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I-1

v

Foreword

The field of elliptic curves is an old and well-studied part of number theory. Until the 1980s

it was rather arcane outside of a small community of specialists. This changed, abruptly, after

Hendrik Lenstra showed how elliptic curves could be used in an efficient algorithm to factor large

integers, and Miller and Koblitz showed how they could be used in a version of the Diffie-Hellman

key exchange protocol, replacing the multiplicative group of non-zero elements of a finite field.

This version was argued to be invulnerable to the so-called “Factor Base” attacks against the

original system. Elliptic curves also have an extra feature that the multiplicative groups lack —

a pairing.

Pairings are ubiquitous in mathematics. They range from the ordinary inner product in

vector spaces, to integration of cycles against differential forms, and to many fundamental uses

in algebraic topology. A particular analytic pairing, defined on points of finite order in elliptic

curves and abelian varieties over the complex numbers, was given an algebraic definition in 1948

by André Weil. This algebraic version proved to be important in the arithmetic theory of elliptic

curves and abelian varieties.

In 1985, Miller and Koblitz independently proposed that the group of an elliptic curve over

a finite field be used as a replacement for the group of invertible residues in a finite field in the

Diffie-Hellman protocol. Motivated by an attempt to relate the discrete logarithm problem in

the two different kinds of groups, Miller recalled that the Weil pairing (if it could be efficiently

calculated) would relate the arithmetic in an elliptic curve with multiplication in a finite field.

This led him to devise an efficient algorithm to calculate the Weil pairing. This was later shown

to give an attack against the discrete logarithm problem for supersingular elliptic curves over a

finite field by Menezes, Okamoto, and Vanstone, and over a small set of other classes of curves

by Frey and Rück.

Meanwhile, in 1984, Adi Shamir had proposed an interesting thought experiment he called

“Identity-Based Cryptosystems.” If it could be realized it could allow, for example, using a

person’s email address as their public key in a public key cryptosystem. However, it was not

clear how this could be practically implemented. In 1999, Antoine Joux took the first steps in

work that was completed the next year by by Dan Boneh and Matt Franklin. These three authors

used the Weil pairing algorithm of Miller as an essential building block. Thus the burgeoning

field of Pairing-Based Cryptography was born.

The security of various cryptosystems is usually predicated on the presumed difficulty of

specific computational problems. As cryptographic protocols have grown more sophisticated,

the number of such assumptions has multiplied.

If G is a finite cyclic group (written additively) with generator P, the Computational Diffie￾Hellman (CDH) problem is to recover abP when given P, aP and bP. The discrete logarithm

(DL) problem is to recover a when given P and aP. The presumed difficulty of the Diffie-Hellman

problem is the basis for the security of the Diffie-Hellman cryptosystem. If one can solve DL one

can solve CDH, and, to date, this has been the only approach. The closely related distinguishing

Diffie-Hellman problem (DDH) is to distinguish a triple of the form (aP, bP, abP) from a triple

of the form (aP, bP, cP) where c is random.

In its abstract form, a pairing is a map e : M × N → R, where M, N, R are abelian groups,

and e is bilinear and non-degenerate (meaning that if 0 6= P ∈ M there is a Q ∈ N such that

e(P, Q) 6= 0). By bilinearity we have e(aP, bQ) = abe(P, Q). One can see that in the case where

M = N, if CDL is easy in R, then we can solve the DDH in M.

Boneh and Franklin realized that if we were in the above situation (along with a slightly more

technical assumption called the bilinear Diffie-Hellman assumption — BDH), we could leverage

vii

viii Foreword

this disparity into creating a viable IBE. Indeed, this was the case for elliptic curves defined over

certain fields (assuming standard conjectures). Since then many other applications of pairings

have been found, many of which are detailed in this volume. As with any new field there are

many subsidiary technical problems that arise and practicalities concerning implementation. A

number of these are detailed here.

In conclusion, it is a pleasure to see a comprehensive survey of this important field in the

present volume.

Victor S. Miller

Princeton, New Jersey

Symbol Description

δ A non-zero integer

p A prime number

q A power of a prime number

Fp The finite field of characteristic p

πp The Frobenius automorphism

Fpδ The extension of degree δ of Fp

Fp The algebraic closure of Fp

E(Fp) An elliptic curve E defined over Fp

P∞ The point at infinity of an elliptic

curve E

#E(Fp) The order of E(Fp) (also denoted n)

r A prime number dividing #E(Fp)

E(Fp)[r] The subgroup of E(Fp) with order r

k The embedding degree of E(Fp) with

respect to r

E0 A twisted elliptic curve of E

d The degree of the twist between E

and E0

G1 A subgroup of order r of E(Fp)

G2 A subgroup of order r of E(Fpk ) \

E(Fp)

G3 A subgroup of order r of Fpk

e A pairing e : G1 × G2 → G3

eT The Tate pairing

eA Ate pairing

etA twisted Ate pairing

Ker The kernel of a morphism

Im The image of a morphism

card(G) The cardinal of the set G

O An order in an imaginary quadratic

field

ix

1

Pairing-Based Cryptography

Sébastien Canard

Orange

Jacques Traoré

Orange

1.1 Introduction ...................................... 1-1

1.2 Preliminaries on Pairings ........................ 1-2

Pairing and Bilinear Environment • Types of

Pairings • Choice of Parameters

1.3 Preliminaries on Cryptography.................. 1-4

Cryptography in a Nutshell • Hash Function •

Encryption • Signature • Security Model for

Cryptography and Pairings

1.4 Short Signatures ................................. 1-7

Use Cases • Related Work: Pairing or Not Pairing •

An Example

1.5 Group Signature Schemes ....................... 1-10

General Presentation and Short Model • Use Cases

• Related Work: Pairing or Not Pairing • An

Example

1.6 Identity-Based Encryption....................... 1-14

General Presentation and Short Model • Use Cases

• Related Work: Pairing or Not Pairing • An

Example

1.7 Broadcast Encryption and Traitor Tracing ..... 1-16

General Presentation and Short Model • Use Cases

• Related Work: Pairing or Not Pairing • An

Example

1.8 Conclusion........................................ 1-20

References .............................................. 1-21

1.1 Introduction

Initially used in cryptography to break the discrete logarithm problem in the group of points of

some elliptic curves, by providing a reduction to the discrete logarithm in finite fields [37] (where

subexponential attacks are known), pairings are now considered to be one of the most suitable

mathematical tools to design secure and efficient cryptographic protocols. The cryptography

relying on pairings is known under the generic term of “pairing-based cryptography.”

In this chapter, we review the cryptographic building blocks where the use of a bilinear

pairing is definitely an advantage, compared to the historical use of finite fields as in traditional

constructions. For each of these blocks, we also explain how they can be used in practice for

real-world applications.

1-1

1-2 Guide to Pairing-Based Cryptography

1.2 Preliminaries on Pairings

We first give some preliminaries on pairings. More details will be given throughout this book,

and here we only sketch some properties and notation that we will need in order to introduce

the necessary notions.

1.2.1 Pairing and Bilinear Environment

We first define three groups: G1, G2 (each with additive notation), and GT (with multiplicative

notation), all of prime order denoted r. In this chapter, a pairing e is then defined as a map

e : G1 × G2 → GT having the following properties:

1. bilinearity, i.e., for all P1 ∈ G1, P2 ∈ G2 and a, b ∈ Zr we have:

e([a]P1, [b]P2) = e(P1, P2)

ab ; and

2. non-degeneracy, i.e., for P1 6= 0G1 and P2 6= 0G2

, e(P1, P2) 6= 1GT

;

where 0G1

(resp. 0G2 and 1GT

) is the neutral element of the group G1 (resp. G2 and GT ). The

notation [a]P1 here corresponds to the scalar multiplication (in an additive group) of a generator

P1 ∈ G1 by a scalar a ∈ Zr (i.e., P + P + · · · + P, a times when a > 0 or −P − P − . . . − P, a

times when a < 0). Additionally to these mathematical properties, cryptographers most of the

time want a pairing to be efficiently computable and hard to inverse, so that these two

notions sometimes directly appear in the definition of a pairing.

The above bilinear property can be derived into a lot of equalities, permitting us to play

with the scalars and moving them from one “group” to another. We have, for example:

e([a]X1, [b]X2) = e([b]X1, [a]X2) = e([ab]X1, X2) = e([a]X1, X2)

b = e([b]X1, X2)

a = · · ·

In the sequel, we then consider a bilinear environment as a tuple

(r, G1, G2, GT , P1, P2, e),

where r, G1, G2, GT , and e are defined as above, and where P1 (resp. P2) is a generator of G1

(resp. G2).

1.2.2 Types of Pairings

There are several ways to describe a pairing, but today the most efficient ones are defined when

the groups G1 and G2 are elliptic curves, and the group GT is the multiplicative group of a finite

field. Galbraith, Patterson and Smart [32] have defined three types of pairings:

• type 1, when G1 = G2;

• type 2, when G1 6= G2 but an efficiently computable isomorphism φ : G2 → G1 is

known, while none is known in the other direction;

• type 3, when G1 6= G2 and no efficiently computable isomorphism is known between

G1 and G2, in either direction.

Although type 1 pairings were mostly used in the early age of pairing-based cryptography,

they have gradually been discarded in favor of type 3 pairings. Indeed, today type 1 is not

attractive enough from an efficiency point of view, since it involves very large curves.

The constructions given in this chapter all require the use of asymmetric pairings (i.e., of

type 2 or type 3). For simplicity, we will only consider pairings of type 3, which is not a strong

restriction (see [22]) since these pairings offer the best efficiency. They are moreover compatible

Pairing-Based Cryptography 1-3

TABLE 1.1 Comparison of the size of parameters, in bits, for different types of cryptography.

Security level 96 128 256

RSA-based factorization module 1776 3248 15424

Discrete logarithm-based

key 192 256 512

group 1776 3248 15424

group (elliptic curve) 192 256 512

Pairing-based

scalar 192 256 512

group G1 192 256 512

group G2 384 512 1024

group GT 1776 3248 15424

with several computational assumptions, such as the Decision Diffie-Hellman (DDH) in G1 or G2,

also known as the XDH assumption [14], which does not hold in type 1 pairings (see Remark 1.1

in Section 1.3.3 for some details).

1.2.3 Choice of Parameters

We now consider the size of the parameters that need to be manipulated when using a pairing

(some details will also be given throughout the book). Generally speaking, the size of the

security parameters is related to the infeasibility of executing best-known attacks on the studied

cryptographic system. By convention, a security level corresponds to the minimum size for an

exhaustive search among the set of all possible secret keys. The figures given for “RSA-based,”

“discrete logarithm-based,” and “pairing-based” are computed by using, in particular, the best

algorithms to solve the related problems. One can refer to Chapter 10 for more details on the

choice of parameters.

Focusing on pairing-based cryptography, for a given security level, minimal sizes for r (the

size of the elliptic curve subgroup) and q

k

(the size of the finite field underlying GT ) have to

be chosen. The integers r and q are prime numbers, and k is called the embedding degree. For

128-bit security, the most relevant choice for an elliptic curve today is the Barreto-Naerhig [8],

of equation Y

2 = X3 + 5 over Fq. With such a curve, the most suitable pairing seems to be the

optimal Ate [41], which can be written

e : E(Fq) × E(Fq

2 ) −→ F

∗

q

12

where E(Fq) (resp. E(Fq

2 )) denotes the elliptic curve defined over the finite field Fq (resp. Fq

2 ).

For a 128-bit security level, this then gives us the following parameters:

• size of the order q = 256 bits (for scalars);

• size of G1 = 256 bits;

• size of G2 = 512 bits; and

• size of GT = 3248 bits.

Table 1.1 then compares the size of the different parameters for different types of cryptography.

The scores are given based on a work by the ECRYPT II [1].

1-4 Guide to Pairing-Based Cryptography

1.3 Preliminaries on Cryptography

1.3.1 Cryptography in a Nutshell

Cryptography, the art of secret writing, has historically been used to hide the communication

between parties. It is today known to address the needs of several important security services:

• confidentiality, to be convinced that only the intended receiver of a message can

read it;

• authentication, to be convinced that a person with whom one is communicating is

the right person;

• integrity, to be convinced that a received message has not been modified; and

• non-repudiation, to be convinced that the origin of a message cannot repudiate it.

But nowadays, cryptographers, most of the time by using techniques from public key cryptogra￾phy, design much more sophisticated tools that permit them to solve modern (and more complex)

problems arising from our digital society:

• perform computations over encrypted data;

• share confidential data;

• guarantee both anonymity and accountability of customers;

• ensure both privacy protection and profiling...

The construction of these new cryptographic solutions requires the use of new mathematical

tools, and, in this context, pairings are the most important and most often used ones in the

current literature.

Before giving some details about pairings, we start by introducing more formally the notions

of hash function, encryption, and signature that will be used in this chapter.

1.3.2 Hash Function

Algorithms. Generally speaking, a hash function is a mathematical function defined by

H : {0, 1}

∗ −→ {0, 1}

k

where k is a “small” parameter. It is then a function that permits us to transform data of arbi￾trary size into a representative data with a fixed size. In cryptography, a hash function mecha￾nism Hash only needs to define the above mathematical function and, in the sequel, we most of

the time only use the mathematical notation H. Sometimes, the output of H is not an element

in {0, 1}

k but a group element, and the hash function is then defined as, e.g., H : {0, 1}

∗ −→ G.

Security. Regarding security, a cryptographically secure hash function should verify the fol￾lowing properties.

• Pre-image resistance, which means that for a given output h ∈ {0, 1}

k

, it is com￾putationally infeasible to find a value m ∈ {0, 1}

∗

such that H(m) = h.

• 2nd pre-image resistance, saying that for a given input m ∈ {0, 1}

∗

, it is compu￾tationally infeasible to find a value m0 ∈ {0, 1}

∗

such that H(m) = H(m0

).

• Collision resistance, which says that it is computationally infeasible to find two

values m, m0 ∈ {0, 1}

∗

such that H(m) = H(m0

).

Based on these security properties, and due to the birthday paradox [43], the value k should be

taken to be equal to 256 for 128-bit security. One can refer to Chapter 8 for more details on

hash functions.