Cryptography Reference
In-Depth Information
1. the security-critical information in a pairing-based cryptographic scheme is often
one of the inputs to the pairing, and
2. a suitably implemented pairing uses no data-dependent branches (or at least none
based on security-critical information).
Pairing evaluation is now computationally efficient enough to be deployed on smart
cards [366], thus posing the question of resilience to fault attacks that take the above
features into account.
Chapter Overview
A wide range of fault attacks against Elliptic Curve Cryptography (ECC) exist [44,
54, 90, 143]; Otto [315, Chap. 4] gives a concise overview. However, although ECC
underpins the concrete use of pairing-based cryptography (by virtue of using elliptic
curve groups), direct application of ECC-oriented attacks is usually ineffective. In
part, this is because said attacks focus on recovering a scalar multiplier; in the context
of pairings, the security-critical information is instead an input point. As such, one
is typically required to focus on the security of pairing evaluation itself rather than
on scalar multiplication.
This approach presents both a problem and an opportunity. The opportunity for
attack is made wider by the complex parametrizations and algorithms used in pairing-
based cryptography. One can, for example, easily identify the potential for faults in
1. precomputed values or parameters, for example, group parameters such as the
order or generator,
2. inputs to the pairing, for example, the input points, and may not reside in the
correct group,
3. intermediate values, for example, the so-called “Miller variable”, which acts as
an accumulator during the pairing computation.
Our focus in this chapter is fault attacks on pairing-based cryptography: we aim to
describe the state of the art in relation to the challenges outlined above, and describe
open problems and issues. Note that we strictly consider fault attacks only, i.e.,
numerous results relating to side-channel attack are, although sometimes related, out
of our scope.
13.2 Background and Notation
F
q
, with
O
Let
E
be an elliptic curve over a finite field
denoting the identity element
of the associated group of rational points
E
(
F
q
)
. For a positive integer
r
|
#
E
(
F
q
)
coprime to
q
,let
F
q
k
be the smallest extension field of
F
q
which contains the
r
th roots
of unity in
F
q
; the extension degree
k
is called the security multiplier or embedding
