Outline

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

Classical Attacks on Elliptic Curve Cryptosystems
An Overview
Mehdi Tibouchi

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves

NTT Secure Platform Laboratories

ECC Workshop 2018, Osaka University, 2018–11–17©2018 NTT Secure Platform Laboratories

1/39

Outline

3/39©2018 NTT Secure Platform Laboratories

2/39

OutlineGroups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves©2018 NTT Secure Platform Laboratories

4/39©2018 NTT Secure Platform Laboratories

Groups

Examples of groups▸ The set Z of integers is a group under +▸A group G is a set together with some operation ∗ sending twoelements a, b to another element a = b ∗ c, such that:(resp. real numbers) is a group under ×▸

1. ∗ is associative: (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c

modulo n is a group, denoted Z/nZ
▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if
and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.

′

3. all elements are invertible: for all a, there exists a such thata ∗ a′ = a′ ∗ a = e
Easy properties: e is unique; each element a has a unique inverse,
denoted a−1©2018 NTT Secure Platform Laboratories©2018 NTT Secure Platform Laboratories

6/39

Examples of groups

Examples of groups▸ The set Z of integers is a group under +▸▸ The set Z of integers is a group under +but not under ×!

▸ The set Q

∗

▸

∗

(resp. real numbers) is a group under ×

we have to remove 0, which has no inverse▸

we have to remove 0, which has no inverse▸ For any integer n, the set {0, 1, . . . , n − 1} under addition▸ For any integer n, the set {0, 1, . . . , n − 1} under addition▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if

▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if

modulo n is a group, denoted Z/nZ

modulo n is a group, denoted Z/nZ

and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.
6/39

but not under ×!

▸ The set Q∗ (resp. R∗ ) of non-zero rational numbers(resp. R ) of non-zero rational numbers(resp. real numbers) is a group under ×▸

we have to remove 0, which has no inverse▸ For any integer n, the set {0, 1, . . . , n − 1} under addition

2. there exists an identity element e: e ∗ a = a ∗ e = a for all a

5/39

but not under ×!

▸ The set Q∗ (resp. R∗ ) of non-zero rational numbers©2018 NTT Secure Platform Laboratories

and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.
6/39©2018 NTT Secure Platform Laboratories

Examples of groups

Examples of groups▸ The set Z of integers is a group under +▸▸ The set Z of integers is a group under +but not under ×!

▸▸ The set Q∗ (resp. R∗ ) of non-zero rational numbers(resp. real numbers) is a group under ×▸(resp. real numbers) is a group under ×

we have to remove 0, which has no inverse▸▸ For any integer n, the set {0, 1, . . . , n − 1} under addition©2018 NTT Secure Platform Laboratories

we have to remove 0, which has no inverse▸ For any integer n, the set {0, 1, . . . , n − 1} under addition

modulo n is a group, denoted Z/nZ
▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if
and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.
6/39

but not under ×!

▸ The set Q∗ (resp. R∗ ) of non-zero rational numbers

modulo n is a group, denoted Z/nZ
▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if
and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.
©2018 NTT Secure Platform Laboratories

6/39

Examples of groups

Finite groups▸ The set Z of integers is a group under +▸but not under ×!

▸ The set Q∗ (resp. R∗ ) of non-zero rational numbers▸ From now on, we restrict attention to finite groups (i.e. the(resp. real numbers) is a group under ×▸

underlying set G is finite). The number N of elements is also
called the order of the group

we have to remove 0, which has no inverse▸ For any integer n, the set {0, 1, . . . , n − 1} under addition▸ For now, we denote the group operation multiplicatively: a ∗ b

modulo n is a group, denoted Z/nZ
▸ The set Z/nZ ∖ {0} is stable under multiplication modulo n if
and only if n = p is prime. In that case, it is a group, denoted(Z/pZ)× or F∗p .
▸ Elliptic curves are groups! (more about this later)▸ In all these examples, the groups are commutative: for all a, b,
a ∗ b = b ∗ a. There are also non-commutative groups, likegroups of invertible matrices. Not so important for
cryptography.
6/39©2018 NTT Secure Platform Laboratories

is just a ⋅ b or ab, and the identity is 1. We will switch toadditive notation later▸ Accordingly, for any positive integer m and any group elementmg , we denote by g the group element g ⋅ g ⋯g (m times).
We also let g 0 = 1 and g −m = (g −1 )m

7/39©2018 NTT Secure Platform Laboratories

Finite groups

Finite groups▸ From now on, we restrict attention to finite groups (i.e. the▸ From now on, we restrict attention to finite groups (i.e. theunderlying set G is finite). The number N of elements is also
called the order of the group

underlying set G is finite). The number N of elements is also
called the order of the group▸ For now, we denote the group operation multiplicatively: a ∗ b▸ For now, we denote the group operation multiplicatively: a ∗ b

is just a ⋅ b or ab, and the identity is 1. We will switch toadditive notation later

is just a ⋅ b or ab, and the identity is 1. We will switch toadditive notation later▸ Accordingly, for any positive integer m and any group elementm▸ Accordingly, for any positive integer m and any group elementmg , we denote by g the group element g ⋅ g ⋯g (m times).
We also let g 0 = 1 and g −m = (g −1 )m©2018 NTT Secure Platform Laboratories

7/39

g , we denote by g the group element g ⋅ g ⋯g (m times).
We also let g 0 = 1 and g −m = (g −1 )m©2018 NTT Secure Platform Laboratories

7/39

Orders of elements, cyclic groups

Orders of elements, cyclic groups▸ For each g in a finite group, there is a smallest positivem

integer m such that g▸ For each g in a finite group, there is a smallest positivem= 1. This is the order of gn′integer m such that g

n′

′

▸

▸ For a fixed g , the set of all elements of the form g m is stable▸ For a fixed g , the set of all elements of the form g m is stable

under the group law and under inversion, and it contains 1: it
is a subgroup of G denoted by ⟨g ⟩▸ If G = ⟨g ⟩, we say that the group G is cyclic and g is a
generator of G

under the group law and under inversion, and it contains 1: it
is a subgroup of G denoted by ⟨g ⟩▸ If G = ⟨g ⟩, we say that the group G is cyclic and g is a
generator of G

▸

8/39

= 1. This is the order of gindeed, by finiteness, there exists n > n′ > 0 such that g n = g n ;′then g n−n = 1. This shows the existence of an m > 0 such thatg m = 1; just take the smallest▸ the order m of g always divides the order N of the entire group(Legendre)

indeed, by finiteness, there exists n > n > 0 such that g = g ;′then g n−n = 1. This shows the existence of an m > 0 such thatg m = 1; just take the smallest▸ the order m of g always divides the order N of the entire group(Legendre)▸a cyclic group is clearly always commutative!

©2018 NTT Secure Platform Laboratories

▸

8/39

a cyclic group is clearly always commutative!

©2018 NTT Secure Platform Laboratories

Orders of elements, cyclic groups

The discrete logarithm problem▸ Let G be a cyclic group of order N with generator g . By

▸ For each g in a finite group, there is a smallest positivem

integer m such that gdefinition, for all h ∈ G , there exists some integer x such thath = gx.
▸ By analogy with real logarithms, x is called the discrete
logarithm of h wrt g= 1. This is the order of g′indeed, by finiteness, there exists n > n′ > 0 such that g n = g n ;′then g n−n = 1. This shows the existence of an m > 0 such thatmg = 1; just take the smallest▸ the order m of g always divides the order N of the entire group(Legendre)▸▸▸ For a fixed g , the set of all elements of the form g m is stable▸ The discrete logarithm problem is the problem of computing x

under the group law and under inversion, and it contains 1: it
is a subgroup of G denoted by ⟨g ⟩▸ If G = ⟨g ⟩, we say that the group G is cyclic and g is a
generator of G▸

given G , N, g , h▸ This assumes that we can compute in G : there exist concrete

representations of the elements of G as bit strings, andefficient algorithms to compute the group law in G andinversion. We assume that from now ona cyclic group is clearly always commutative!

©2018 NTT Secure Platform Laboratories

8/39©2018 NTT Secure Platform Laboratories

9/39

The discrete logarithm problem

The discrete logarithm problem▸ Let G be a cyclic group of order N with generator g . By

▸ Let G be a cyclic group of order N with generator g . By

definition, for all h ∈ G , there exists some integer x such thath = gx.
▸ By analogy with real logarithms, x is called the discrete
logarithm of h wrt gdefinition, for all h ∈ G , there exists some integer x such thath = gx.
▸ By analogy with real logarithms, x is called the discrete
logarithm of h wrt g▸

x is unique up to addition of a multiple of N (i.e. uniquemodulo N)▸▸ The discrete logarithm problem is the problem of computing x

x is unique up to addition of a multiple of N (i.e. uniquemodulo N)▸ The discrete logarithm problem is the problem of computing x

given G , N, g , hgiven G , N, g , h▸ This assumes that we can compute in G : there exist concrete▸ This assumes that we can compute in G : there exist concrete

representations of the elements of G as bit strings, andefficient algorithms to compute the group law in G andinversion. We assume that from now on

9/39

x is unique up to addition of a multiple of N (i.e. uniquemodulo N)©2018 NTT Secure Platform Laboratories

representations of the elements of G as bit strings, andefficient algorithms to compute the group law in G andinversion. We assume that from now on

9/39©2018 NTT Secure Platform Laboratories

The discrete logarithm problem

Outline▸ Let G be a cyclic group of order N with generator g . By

definition, for all h ∈ G , there exists some integer x such thath = gx.
▸ By analogy with real logarithms, x is called the discrete
logarithm of h wrt g▸Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

x is unique up to addition of a multiple of N (i.e. uniquemodulo N)

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves▸ The discrete logarithm problem is the problem of computing x

given G , N, g , h▸ This assumes that we can compute in G : there exist concrete

representations of the elements of G as bit strings, andefficient algorithms to compute the group law in G andinversion. We assume that from now on©2018 NTT Secure Platform Laboratories

9/39

Solving the discrete logarithm problem

Solving the discrete logarithm problem▸ The hardness of the discrete logarithm problem (DLP) is at▸ The hardness of the discrete logarithm problem (DLP) is at

the core of the security arguments for all cryptography basedon groups, incl. elliptic curve cryptography

the core of the security arguments for all cryptography basedon groups, incl. elliptic curve cryptography▸ Hence, if we can solve DLP efficiently, we can break all▸ Hence, if we can solve DLP efficiently, we can break allgroup-based crypto

group-based crypto▸ Various approaches to attack the DLP depending on the▸ Various approaches to attack the DLP depending on thegroup we considergroup we consider▸ However, arguably the most important approaches are those▸ However, arguably the most important approaches are thosethat are generic: work in all group, independently of theparticular group law or representation of group elementsthat are generic: work in all group, independently of theparticular group law or representation of group elements▸ We now discuss those approaches

11/39©2018 NTT Secure Platform Laboratories

10/39▸ We now discuss those approaches©2018 NTT Secure Platform Laboratories

11/39©2018 NTT Secure Platform Laboratories

Solving the discrete logarithm problem

Solving the discrete logarithm problem▸ The hardness of the discrete logarithm problem (DLP) is at▸ The hardness of the discrete logarithm problem (DLP) is at

the core of the security arguments for all cryptography basedon groups, incl. elliptic curve cryptography

the core of the security arguments for all cryptography basedon groups, incl. elliptic curve cryptography▸ Hence, if we can solve DLP efficiently, we can break all▸ Hence, if we can solve DLP efficiently, we can break allgroup-based crypto

group-based crypto▸ Various approaches to attack the DLP depending on the▸ Various approaches to attack the DLP depending on thegroup we considergroup we consider▸ However, arguably the most important approaches are those▸ However, arguably the most important approaches are thosethat are generic: work in all group, independently of theparticular group law or representation of group elementsthat are generic: work in all group, independently of theparticular group law or representation of group elements▸ We now discuss those approaches▸ We now discuss those approaches©2018 NTT Secure Platform Laboratories

11/39

Solving the discrete logarithm problem

A trivial discrete log algorithm▸ Here is a trivial algorithm for the DLP▸ The hardness of the discrete logarithm problem (DLP) is at▸ Given g and h, the goal is to find x such that h = g x

the core of the security arguments for all cryptography basedon groups, incl. elliptic curve cryptography▸ Simple way:

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again▸ Hence, if we can solve DLP efficiently, we can break allgroup-based crypto▸ Various approaches to attack the DLP depending on the▸ We know for sure that this algorithm will find a solution.

group we consider

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity is
O(1))▸ However, arguably the most important approaches are thosethat are generic: work in all group, independently of theparticular group law or representation of group elements▸ Note that this algorithm is exponential in the bit size of the▸ We now discuss those approaches

11/39©2018 NTT Secure Platform Laboratories

11/39

group (which is log2 N)©2018 NTT Secure Platform Laboratories

12/39©2018 NTT Secure Platform Laboratories

A trivial discrete log algorithm

A trivial discrete log algorithm▸ Here is a trivial algorithm for the DLP▸ Here is a trivial algorithm for the DLP▸ Given g and h, the goal is to find x such that h = gx▸ Given g and h, the goal is to find x such that h = g x▸ Simple way:

▸ Simple way:

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again▸ We know for sure that this algorithm will find a solution.

▸ We know for sure that this algorithm will find a solution.

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))▸ Note that this algorithm is exponential in the bit size of the▸ Note that this algorithm is exponential in the bit size of thegroup (which is log2 N)group (which is log2 N)©2018 NTT Secure Platform Laboratories

12/39

A trivial discrete log algorithm

A trivial discrete log algorithm▸ Here is a trivial algorithm for the DLP▸ Here is a trivial algorithm for the DLP▸ Given g and h, the goal is to find x such that h = g x▸ Given g and h, the goal is to find x such that h = g x▸ Simple way:

▸ Simple way:

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again▸ We know for sure that this algorithm will find a solution.

▸ We know for sure that this algorithm will find a solution.

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))▸ Note that this algorithm is exponential in the bit size of the▸ Note that this algorithm is exponential in the bit size of thegroup (which is log2 N)

12/39©2018 NTT Secure Platform Laboratories

12/39

group (which is log2 N)©2018 NTT Secure Platform Laboratories

12/39©2018 NTT Secure Platform Laboratories

A trivial discrete log algorithm

A trivial discrete log algorithm▸ Here is a trivial algorithm for the DLP▸ Here is a trivial algorithm for the DLP▸ Given g and h, the goal is to find x such that h = gx▸ Given g and h, the goal is to find x such that h = g x▸ Simple way:

▸ Simple way:

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again▸ We know for sure that this algorithm will find a solution.

▸ We know for sure that this algorithm will find a solution.

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))▸ Note that this algorithm is exponential in the bit size of the▸ Note that this algorithm is exponential in the bit size of thegroup (which is log2 N)group (which is log2 N)©2018 NTT Secure Platform Laboratories

12/39

A trivial discrete log algorithm

Baby step, giant step (I)▸ Here is a trivial algorithm for the DLP▸ We can do much better with some memory: the baby step,▸ Given g and h, the goal is to find x such that h = g x

giant step (BSGS) algorithm√▸ Let m = ⌈ N⌉. One can write the discrete log x of h as
x = y + mz, with 0 ≤ y , z < m. This gives:▸ Simple way:

1. x ← 0
2. if h = g x , we are done
3. otherwise, x ← x + 1 and try again

h = g y +mz = g y ⋅ g mz hence h ⋅ g −y = g mz√√
̃ N) and space O( N), construct the following▸ In time O(
list and sort it (so that we can search through it efficiently):▸ We know for sure that this algorithm will find a solution.

Since there is such a solution x such that 0 ≤ x < N, timecomplexity is O(N) in the worst case (and space complexity isO(1))

L = {g 0 , g m , g m⋅2 , ⋯, g m⋅(m−1) }▸ Note that this algorithm is exponential in the bit size of the

By construction, g mz is in the list

group (which is log2 N)

12/39©2018 NTT Secure Platform Laboratories

12/39©2018 NTT Secure Platform Laboratories

13/39©2018 NTT Secure Platform Laboratories

Baby step, giant step (I)Baby step, giant step (I)▸ We can do much better with some memory: the baby step,▸ We can do much better with some memory: the baby step,

giant step (BSGS) algorithm√▸ Let m = ⌈ N⌉. One can write the discrete log x of h as
x = y + mz, with 0 ≤ y , z < m. This gives:

giant step (BSGS) algorithm√▸ Let m = ⌈ N⌉. One can write the discrete log x of h as
x = y + mz, with 0 ≤ y , z < m. This gives:

h = g y +mz = g y ⋅ g mz hence h ⋅ g −y = g mz√√
̃ N) and space O( N), construct the following▸ In time O(
list and sort it (so that we can search through it efficiently):h = g y +mz = g y ⋅ g mz hence h ⋅ g −y = g mz√√
̃ N) and space O( N), construct the following▸ In time O(
list and sort it (so that we can search through it efficiently):

L = {g 0 , g m , g m⋅2 , ⋯, g m⋅(m−1) }L = {g 0 , g m , g m⋅2 , ⋯, g m⋅(m−1) }By construction, g mz is in the list

By construction, g mz is in the list

©2018 NTT Secure Platform Laboratories

13/39

Baby step, giant step (II)Baby step, giant step (II)▸ Now do a similar search as before:▸ Now do a similar search as before:

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach̃▸ Total time complexity is O(̃▸ Total time complexity is O(▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ By choosing a different value for m, we can obtain different▸ By choosing a different value for m, we can obtain different

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

N ≈ 2 , the 2
space is not!

14/39

©2018 NTT Secure Platform Laboratories

13/39

N ≈ 2 , the 2
space is not!

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

14/39

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

Baby step, giant step (II)Baby step, giant step (II)▸ Now do a similar search as before:▸ Now do a similar search as before:

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach̃▸ Total time complexity is O(̃▸ Total time complexity is O(▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ By choosing a different value for m, we can obtain different▸ By choosing a different value for m, we can obtain different

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

N ≈ 2 , the 2
space is not!

N ≈ 2 , the 2
space is not!

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

14/39©2018 NTT Secure Platform Laboratories

14/39

Baby step, giant step (II)Baby step, giant step (II)▸ Now do a similar search as before:▸ Now do a similar search as before:

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach̃▸ Total time complexity is O(̃▸ Total time complexity is O(▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ By choosing a different value for m, we can obtain different▸ By choosing a different value for m, we can obtain different

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

N ≈ 2 , the 2
space is not!

14/39

time complexity is manageable, but 2

N ≈ 2 , the 2
space is not!

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

14/39

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

Baby step, giant step (II)Baby step, giant step (II)▸ Now do a similar search as before:▸ Now do a similar search as before:

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again

1. y ← 0
2. search for h ⋅ g −y in the list L
3. if it is found as g mz , return x = y + mz as the discrete log
4. otherwise, y ← y + 1 and try again√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach√N) and space complexity is√O( N). Still exponential, but exponentially faster than thetrivial approach̃▸ Total time complexity is O(̃▸ Total time complexity is O(▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ In practice the space complexity is usually prohibitive: e.g. if
128
64
64

▸ By choosing a different value for m, we can obtain different▸ By choosing a different value for m, we can obtain different

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

time-memory trade-offs. Not necessary though: same timecomplexity is achievable without memory!

N ≈ 2 , the 2
space is not!

N ≈ 2 , the 2
space is not!

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

14/39©2018 NTT Secure Platform Laboratories

14/39

Pollard’s rho algorithm (I)Pollard’s rho algorithm (I)▸ The best generic algorithm for discrete logarithms is Pollard’s▸ The best generic algorithm for discrete logarithms is Pollard’s▸ Basic ingredient: cycle-finding for random functions. If▸ Basic ingredient: cycle-finding for random functions. If√
rho: it uses O( N) time and constant space.

√rho: it uses O( N) time and constant space.

f ∶ X → X is a random function of a set of cardinality N toitself, and we iterate f on a random element x0 :f ∶ X → X is a random function of a set of cardinality N toitself, and we iterate f on a random element x0 :x1 = f (x0 );x2 = f (x1 ); ⋯√then there are integers s, t = O( N) whp such that xt = xt+s .
A well-known
algorithm (Floyd) then allows to find s, t in time√O( N) and constant memory

15/39

time complexity is manageable, but 2©2018 NTT Secure Platform Laboratories

x1 = f (x0 );x2 = f (x1 ); ⋯√then there are integers s, t = O( N) whp such that xt = xt+s .
A well-known
algorithm (Floyd) then allows to find s, t in time√O( N) and constant memory

15/39©2018 NTT Secure Platform Laboratories

Pollard’s rho algorithm (II)Pollard’s rho algorithm (II)▸ Now consider the set X = G , and fix a random elementx0 = g a0 ⋅ hb0 . Moreover, we construct f in such a way that f▸ Now consider the set X = G , and fix a random elementx0 = g a0 ⋅ hb0 . Moreover, we construct f in such a way that f

acts on each element by multiplication by some known powersof g and h. As a result, for all i, we know ai , bi such thatacts on each element by multiplication by some known powersof g and h. As a result, for all i, we know ai , bi such thatxi = f i (x0 ) = g ai ⋅ hbi√▸ Apply cycle-finding. In time O( N) and constant space, wefind whp integers a, b, a′ , b ′ such that:xi = f i (x0 ) = g ai ⋅ hbi√▸ Apply cycle-finding. In time O( N) and constant space, wefind whp integers a, b, a′ , b ′ such that:′g a ⋅ hb = xt = xt+s = g a ⋅ hb′′

g a ⋅ hb = xt = xt+s = g a ⋅ hb

Then, if b − b ′ is coprime to N (happens with good
probability), we deduce:
h = gα

16/39

where

α≡−

a − a′
b − b′

Then, if b − b ′ is coprime to N (happens with good
probability), we deduce:
h = gα(mod N)©2018 NTT Secure Platform Laboratories

′

where

α≡−

a − a′
b − b′(mod N)©2018 NTT Secure Platform Laboratories

16/39

Pollard’s rho algorithm

Pohlig–Hellman (I)▸ There is one last thing we can do to speed up generic discrete

logarithm computations: use the factorization of the grouporder N▸ Suppose N factors as a product N1 N2 of two coprime
N2

integers. Then for a generator g of G , g
g N1 is of order N2 .

is of order N1 and▸ We look for x such that h = g x . Raising both sides to thepower N2 , we get: hN2 = (g N2 )x , DLP in the group ⟨g N2 ⟩ oforder N1 .

▸ Solve this DLP with Pollard’s rho to obtain x mod N1 .
N1
N1Similarly, solve the DLP between g and h to findx mod N2 . Then apply the Chinese remainder theorem (CRT)
to compute x

Picture of the ρ in Pollard’s rho (from Wikimedia Commons)
17/39©2018 NTT Secure Platform Laboratories

▸

18/39

√
√
time complexity O( N1 + N2 ) and constant space©2018 NTT Secure Platform Laboratories

Pohlig–Hellman (I)Pohlig–Hellman (I)▸ There is one last thing we can do to speed up generic discrete▸ There is one last thing we can do to speed up generic discrete

logarithm computations: use the factorization of the grouporder N

logarithm computations: use the factorization of the grouporder N▸ Suppose N factors as a product N1 N2 of two coprime
N2▸ Suppose N factors as a product N1 N2 of two coprime
N2▸ We look for x such that h = g x . Raising both sides to thepower N2 , we get: hN2 = (g N2 )x , DLP in the group ⟨g N2 ⟩ of

▸ We look for x such that h = g x . Raising both sides to thepower N2 , we get: hN2 = (g N2 )x , DLP in the group ⟨g N2 ⟩ ofintegers. Then for a generator g of G , g
g N1 is of order N2 .

integers. Then for a generator g of G , g
g N1 is of order N2 .

is of order N1 andorder N1 .
▸ Solve this DLP with Pollard’s rho to obtain x mod N1 .
Similarly, solve the DLP between g N1 and hN1 to findx mod N2 . Then apply the Chinese remainder theorem (CRT)
to compute x▸order N1 .
▸ Solve this DLP with Pollard’s rho to obtain x mod N1 .
Similarly, solve the DLP between g N1 and hN1 to findx mod N2 . Then apply the Chinese remainder theorem (CRT)
to compute x√√
time complexity O( N1 + N2 ) and constant space©2018 NTT Secure Platform Laboratories

18/39

is of order N1 and

▸

18/39

Pohlig–Hellman (I)√√time complexity O( N1 + N2 ) and constant space©2018 NTT Secure Platform Laboratories

Pohlig–Hellman (II)▸ There is one last thing we can do to speed up generic discrete

logarithm computations: use the factorization of the grouporder N

▸ More generally, if N = p e1 ⋯prer is the prime factorization of N,
1

that decomposition approach reduces the DLP in G to DLPs
in groups of order p1e1 , . . . , prer .

▸ Suppose N factors as a product N1 N2 of two coprime
N2

integers. Then for a generator g of G , g
g N1 is of order N2 .

is of order N1 and▸ Then, a similar trick reduces the DLP in a group of order p e

to e instances of DLPs in groups of order p (relying on
Pollard’s kangaroo)▸ We look for x such that h = g x . Raising both sides to thepower N2 , we get: hN2 = (g N2 )x , DLP in the group ⟨g N2 ⟩ of

▸ Conclusion: can solve discrete logs in G in time√√O(e1 p1 + ⋯ + er pr ) and polynomial space.
√▸ For most N, this simply reduces to O( p) time, p largest
prime factor

order N1 .
▸ Solve this DLP with Pollard’s rho to obtain x mod N1 .
Similarly, solve the DLP between g N1 and hN1 to findx mod N2 . Then apply the Chinese remainder theorem (CRT)
to compute x
▸

18/39

√
√
time complexity O( N1 + N2 ) and constant space©2018 NTT Secure Platform Laboratories

19/39©2018 NTT Secure Platform Laboratories

Pohlig–Hellman (II)Pohlig–Hellman (II)▸ More generally, if N = p e1 ⋯prer is the prime factorization of N,
1▸ More generally, if N = p e1 ⋯prer is the prime factorization of N,
1▸ Then, a similar trick reduces the DLP in a group of order p e▸ Then, a similar trick reduces the DLP in a group of order p ethat decomposition approach reduces the DLP in G to DLPs
in groups of order p1e1 , . . . , prer .

that decomposition approach reduces the DLP in G to DLPs
in groups of order p1e1 , . . . , prer .

to e instances of DLPs in groups of order p (relying on
Pollard’s kangaroo)

to e instances of DLPs in groups of order p (relying on
Pollard’s kangaroo)▸ Conclusion: can solve discrete logs in G in time

▸ Conclusion: can solve discrete logs in G in time√√O(e1 p1 + ⋯ + er pr ) and polynomial space.
√▸ For most N, this simply reduces to O( p) time, p largest
prime factor

19/39©2018 NTT Secure Platform Laboratories√√
O(e1 p1 + ⋯ + er pr ) and polynomial space.
√▸ For most N, this simply reduces to O( p) time, p largest
prime factor

Pohlig–Hellman (II)Shoup’s lower bound▸ More generally, if N = p e1 ⋯prer is the prime factorization of N,
1▸ Shoup proved that a generic algorithm for the DLP in a cyclic▸ Then, a similar trick reduces the DLP in a group of order p e▸ Therefore, among generic algorithms, Pollard’s rho is optimal√group of prime order p had to carry out Ω( p) group
operations

that decomposition approach reduces the DLP in G to DLPs
in groups of order p1e1 , . . . , prer .

(up to a constant) for groups of prime order, and Pollard’s rho+ Pohlig–Hellman optimal in generalto e instances of DLPs in groups of order p (relying on
Pollard’s kangaroo)▸ On most elliptic curves, no better algorithm than those is▸ Conclusion: can solve discrete logs in G in time√√O(e1 p1 + ⋯ + er pr ) and polynomial space.
√▸ For most N, this simply reduces to O( p) time, p largest
prime factor

19/39©2018 NTT Secure Platform Laboratories

19/39©2018 NTT Secure Platform Laboratories

known for the discrete log!
▸ Caveat: this is only about attacks on classical computers.

Quantum computers generically break the DLP in polynomial
time with Shor’s algorithm

20/39©2018 NTT Secure Platform Laboratories

Shoup’s lower boundShoup’s lower bound▸ Shoup proved that a generic algorithm for the DLP in a cyclic▸ Shoup proved that a generic algorithm for the DLP in a cyclic▸ Therefore, among generic algorithms, Pollard’s rho is optimal▸ Therefore, among generic algorithms, Pollard’s rho is optimal(up to a constant) for groups of prime order, and Pollard’s rho+ Pohlig–Hellman optimal in general(up to a constant) for groups of prime order, and Pollard’s rho+ Pohlig–Hellman optimal in general√group of prime order p had to carry out Ω( p) group
operations√group of prime order p had to carry out Ω( p) group
operations▸ On most elliptic curves, no better algorithm than those is▸ On most elliptic curves, no better algorithm than those is

known for the discrete log!

known for the discrete log!

▸ Caveat: this is only about attacks on classical computers.

▸ Caveat: this is only about attacks on classical computers.

Quantum computers generically break the DLP in polynomial
time with Shor’s algorithm©2018 NTT Secure Platform Laboratories

20/39

Quantum computers generically break the DLP in polynomial
time with Shor’s algorithm©2018 NTT Secure Platform Laboratories

20/39

Shoup’s lower boundOutline▸ Shoup proved that a generic algorithm for the DLP in a cyclic√
group of prime order p had to carry out Ω( p) group
operations

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

▸ Therefore, among generic algorithms, Pollard’s rho is optimal(up to a constant) for groups of prime order, and Pollard’s rho+ Pohlig–Hellman optimal in general

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves▸ On most elliptic curves, no better algorithm than those is

known for the discrete log!
▸ Caveat: this is only about attacks on classical computers.

Quantum computers generically break the DLP in polynomial
time with Shor’s algorithm

20/39©2018 NTT Secure Platform Laboratories

21/39©2018 NTT Secure Platform Laboratories

Additive group DLP

Additive group DLP▸ There are of course some groups when the DLP can be solved▸ There are of course some groups when the DLP can be solved

much faster than by generic techniquesmuch faster than by generic techniques▸ Example: the cyclic group Z/NZ of integers modulo N under▸ Example: the cyclic group Z/NZ of integers modulo N under

addition

addition▸ This is an additive group. The DLP is to find, given two▸ This is an additive group. The DLP is to find, given twoelements a, b ∈ Z/NZ, a value x such that b ≡ ax (mod N)

elements a, b ∈ Z/NZ, a value x such that b ≡ ax (mod N)▸ This is just a division! Simply compute x as:

x≡

b
a

▸ This is just a division! Simply compute x as:(mod N)x≡(mod N)(computation done using the extended Euclidean algorithm)(computation done using the extended Euclidean algorithm)▸ In Z/NZ, DLP can be solved in polynomial time (in log N),▸ In Z/NZ, DLP can be solved in polynomial time (in log N),even though generic algorithms are all exponential©2018 NTT Secure Platform Laboratories

22/39

even though generic algorithms are all exponential©2018 NTT Secure Platform Laboratories

22/39

Additive group DLP

Additive group DLP▸ There are of course some groups when the DLP can be solved▸ There are of course some groups when the DLP can be solved

much faster than by generic techniquesmuch faster than by generic techniques▸ Example: the cyclic group Z/NZ of integers modulo N under▸ Example: the cyclic group Z/NZ of integers modulo N under

addition

addition▸ This is an additive group. The DLP is to find, given two▸ This is an additive group. The DLP is to find, given twoelements a, b ∈ Z/NZ, a value x such that b ≡ ax (mod N)

elements a, b ∈ Z/NZ, a value x such that b ≡ ax (mod N)▸ This is just a division! Simply compute x as:

x≡

b
a

▸ This is just a division! Simply compute x as:(mod N)x≡ba(mod N)(computation done using the extended Euclidean algorithm)(computation done using the extended Euclidean algorithm)▸ In Z/NZ, DLP can be solved in polynomial time (in log N),▸ In Z/NZ, DLP can be solved in polynomial time (in log N),even though generic algorithms are all exponential
22/39

b
a

©2018 NTT Secure Platform Laboratories

even though generic algorithms are all exponential
22/39©2018 NTT Secure Platform Laboratories

Additive group DLPMultiplicative group DLP▸ There are of course some groups when the DLP can be solved▸ Fix p a prime. The multiplicative group G = (Z/pZ)× is cyclic

much faster than by generic techniquesof order p − 1 with some generator g▸ Example: the cyclic group Z/NZ of integers modulo N under▸ We do not know how to solve the DLP in G in polynomial

additiontime, but we can still do much better than generic algorithms.
The best known algorithms are subexponential▸ This is an additive group. The DLP is to find, given twoelements a, b ∈ Z/NZ, a value x such that b ≡ ax (mod N)▸ More precisely, if p is n-bit long, the best algorithm (GNFS)̃ 1/3 )O(n▸ This is just a division! Simply compute x as:b
x≡a

has a complexity of 2√
Pollard’s p − 1 ≈ 2n/2

(mod N), which is considerably less than

▸ In the next slide, brief description of a simpler subexponential

algorithm, index calculus, based on similar principles.
̃ 1/2
Complexity of 2O(n )(computation done using the extended Euclidean algorithm)▸ In Z/NZ, DLP can be solved in polynomial time (in log N),even though generic algorithms are all exponential©2018 NTT Secure Platform Laboratories

22/39

Multiplicative group DLPMultiplicative group DLP▸ Fix p a prime. The multiplicative group G = (Z/pZ)× is cyclic▸ Fix p a prime. The multiplicative group G = (Z/pZ)× is cyclic▸ We do not know how to solve the DLP in G in polynomial▸ We do not know how to solve the DLP in G in polynomialof order p − 1 with some generator gof order p − 1 with some generator gtime, but we can still do much better than generic algorithms.
The best known algorithms are subexponential

time, but we can still do much better than generic algorithms.
The best known algorithms are subexponential▸ More precisely, if p is n-bit long, the best algorithm (GNFS)̃ 1/3 )
O(n▸ More precisely, if p is n-bit long, the best algorithm (GNFS)̃ 1/3 )
O(n▸ In the next slide, brief description of a simpler subexponential▸ In the next slide, brief description of a simpler subexponential

has a complexity of 2√
Pollard’s p − 1 ≈ 2n/2

, which is considerably less thanhas a complexity of 2√
Pollard’s p − 1 ≈ 2n/2

algorithm, index calculus, based on similar principles.
̃ 1/2
Complexity of 2O(n )23/39©2018 NTT Secure Platform Laboratories

23/39©2018 NTT Secure Platform Laboratories, which is considerably less thanalgorithm, index calculus, based on similar principles.
̃ 1/2
Complexity of 2O(n )23/39©2018 NTT Secure Platform Laboratories

Index calculus in (Z/pZ)×

Multiplicative group DLP▸ Start by collecting all the small prime numbersℓ1 = 2, ℓ2 = 3, ⋯, ℓr up to some bound B in a list F called thefactor base. One can easily check if an integer has all its prime
factors in F (and then factor it), and estimate the probability
that this happens. Such a number is called B-smooth▸ Now we will try to find the discrete logs x1 , . . . , xr of all theelements of F wrt g . To do so, pick random numbers kj andcheck if g kj mod p is B-smooth. If so, we can factor it andget a relation:▸ Fix p a prime. The multiplicative group G = (Z/pZ)× is cyclicof order p − 1 with some generator g▸ We do not know how to solve the DLP in G in polynomial

time, but we can still do much better than generic algorithms.
The best known algorithms are subexponential▸ More precisely, if p is n-bit long, the best algorithm (GNFS)̃ 1/3 )O(n, which is considerably less thanhas a complexity of 2√
Pollard’s p − 1 ≈ 2n/2eeg kj ≡ ℓ1j,1 ⋯ℓr j,r▸ In the next slide, brief description of a simpler subexponential(mod p)or after taking discrete logs:

algorithm, index calculus, based on similar principles.
̃ 1/2
Complexity of 2O(n )kj ≡ ej,1 x1 + ⋯ + ej,r xr(mod p − 1)

If we find more than r such relations, applying Gaussianelimination allows to find x1 , . . . , xr
©2018 NTT Secure Platform Laboratories

23/39©2018 NTT Secure Platform Laboratories

24/39

Index calculus in (Z/pZ)×

Index calculus in (Z/pZ)×▸ Start by collecting all the small prime numbersℓ1 = 2, ℓ2 = 3, ⋯, ℓr up to some bound B in a list F called thefactor base. One can easily check if an integer has all its prime
factors in F (and then factor it), and estimate the probability
that this happens. Such a number is called B-smooth▸ Now we will try to find the discrete logs x1 , . . . , xr of all theelements of F wrt g . To do so, pick random numbers kj andcheck if g kj mod p is B-smooth. If so, we can factor it andget a relation:eeg kj ≡ ℓ1j,1 ⋯ℓr j,r▸ After that, finding the discrete log of any h ∈ G iscomparatively easy. Just find a single random s such thatg s ⋅ h mod p is B-smooth, and factor it to get:h ≡ g −s ⋅ ℓe11 ⋯ℓer r≡ g −s+e1 x1 +⋯+er xr (mod p)(mod p)▸ For a well-chosen B, smoothness probability estimates allow
̃ 1/2 )O(nto show that the overall complexity is 2

or after taking discrete logs:
kj ≡ ej,1 x1 + ⋯ + ej,r xr(mod p − 1)

If we find more than r such relations, applying Gaussianelimination allows to find x1 , . . . , xr
24/39

©2018 NTT Secure Platform Laboratories

25/39©2018 NTT Secure Platform Laboratories

Index calculus in (Z/pZ)×

DLP in finite fields▸ The group (Z/pZ)× is the multiplicative group of the finite

field Fp

▸ After that, finding the discrete log of any h ∈ G is

▸ One can also consider the DLP in the multiplicative group oflarger finite fields Fq , q = p m . The GNFS algorithm extends tõ 1/3 )
O(ncomparatively easy. Just find a single random s such thatg s ⋅ h mod p is B-smooth, and factor it to get:that setting, and always gives algorithms in 2
where n is
the bit size of q
▸ Recent breakthrough [BGJT14]: if p is very small(e.g. constant), a refinement of the algorithm gives
quasipolynomial complexityh ≡ g −s ⋅ ℓe11 ⋯ℓer r≡ g −s+e1 x1 +⋯+er xr (mod p)▸ For a well-chosen B, smoothness probability estimates allow
̃ 1/2 )O(nto show that the overall complexity is 2©2018 NTT Secure Platform Laboratories

25/39

one of the most important advances in number-theoretic
algorithms in the past decade▸ with consequences on some flavors of elliptic curve crypto▸

DLP in finite fields

DLP in finite fields▸ The group (Z/pZ)× is the multiplicative group of the finite▸ The group (Z/pZ)× is the multiplicative group of the finite▸ One can also consider the DLP in the multiplicative group oflarger finite fields Fq , q = p m . The GNFS algorithm extends tõ 1/3 )
O(n▸ One can also consider the DLP in the multiplicative group oflarger finite fields Fq , q = p m . The GNFS algorithm extends tõ 1/3 )O(nfield Fp

field Fpthat setting, and always gives algorithms in 2
where n is
the bit size of q
▸ Recent breakthrough [BGJT14]: if p is very small(e.g. constant), a refinement of the algorithm gives
quasipolynomial complexitythat setting, and always gives algorithms in 2
where n is
the bit size of q
▸ Recent breakthrough [BGJT14]: if p is very small(e.g. constant), a refinement of the algorithm gives
quasipolynomial complexity

one of the most important advances in number-theoretic
algorithms in the past decade▸ with consequences on some flavors of elliptic curve crypto

one of the most important advances in number-theoretic
algorithms in the past decade▸ with consequences on some flavors of elliptic curve crypto

▸

26/39

©2018 NTT Secure Platform Laboratories

26/39©2018 NTT Secure Platform Laboratories

▸

26/39

©2018 NTT Secure Platform Laboratories

Outline

OutlineGroups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves©2018 NTT Secure Platform Laboratories

27/39

Elliptic curves

Elliptic curves

Elliptic curve: plane curve E of the form y 2 = x 3 + ax + b
29/39©2018 NTT Secure Platform Laboratories

28/39©2018 NTT Secure Platform Laboratories

Must be non-singular, so not this
29/39

©2018 NTT Secure Platform Laboratories

Elliptic curves

Elliptic curves
P
Q

Take two points P, Q on E

. . . nor this©2018 NTT Secure Platform Laboratories

29/39©2018 NTT Secure Platform Laboratories

29/39

Elliptic curves

Elliptic curves
P

P

Q

Q
P +Q

R

R

Because E is of degree 3, the line through P, Q intersects E atexactly one other point (with coordinates in the same field)
29/39©2018 NTT Secure Platform Laboratories

We define a group law on the points of E
by defining P + Q as the mirror image of R
29/39

©2018 NTT Secure Platform Laboratories

Elliptic curves

Elliptic curves
P
Q
P +Q

−R

R

R

Commutative group: P + Q = Q + P = −R.
Associativity? Not so obvious but can be checked

The identity element is at infinity along the y -axis; R + (−R) = 0©2018 NTT Secure Platform Laboratories

29/39©2018 NTT Secure Platform Laboratories

29/39

Elliptic curves

The ECDLP▸ Consider E ∶ y 2 = x 3 + ax + b elliptic curve with coefficientsPa, b in the finite field Fq▸ As we saw, the set E (Fq ) of points on E with coordinates in
Fq (incl. the point at infinity) is a finite commutative group

Q
P +Q

▸

√
its order is always of the form q + O( q) (Hasse bound)▸ Given a point P ∈ E (Fq ) and an integer x, one can efficiently

compute the scalar multiplication [x]P = P + P + ⋯ + P (usual
group exponentiation)R▸ The elliptic curve discrete logarithm problem (ECDLP), on

which all elliptic curve crypto is based, is the DLP in cyclic
subgroups of E (Fq ).

▸ Namely: given P, Q ∈ E (Fq ) such that there exists x with

These pictures are over the reals,
but everything works over finite fields too!
29/39

©2018 NTT Secure Platform Laboratories

Q = [x]P, find x

30/39©2018 NTT Secure Platform Laboratories

The ECDLPThe ECDLP▸ Consider E ∶ y 2 = x 3 + ax + b elliptic curve with coefficients▸ Consider E ∶ y 2 = x 3 + ax + b elliptic curve with coefficientsa, b in the finite field Fqa, b in the finite field Fq▸ As we saw, the set E (Fq ) of points on E with coordinates in▸ As we saw, the set E (Fq ) of points on E with coordinates in

Fq (incl. the point at infinity) is a finite commutative group▸

Fq (incl. the point at infinity) is a finite commutative group√
its order is always of the form q + O( q) (Hasse bound)▸▸ Given a point P ∈ E (Fq ) and an integer x, one can efficiently▸ Given a point P ∈ E (Fq ) and an integer x, one can efficiently▸ The elliptic curve discrete logarithm problem (ECDLP), on▸ The elliptic curve discrete logarithm problem (ECDLP), on

which all elliptic curve crypto is based, is the DLP in cyclic
subgroups of E (Fq ).

which all elliptic curve crypto is based, is the DLP in cyclic
subgroups of E (Fq ).

compute the scalar multiplication [x]P = P + P + ⋯ + P (usual
group exponentiation)

compute the scalar multiplication [x]P = P + P + ⋯ + P (usual
group exponentiation)▸ Namely: given P, Q ∈ E (Fq ) such that there exists x with

▸ Namely: given P, Q ∈ E (Fq ) such that there exists x with

Q = [x]P, find x©2018 NTT Secure Platform Laboratories

30/39

Q = [x]P, find x©2018 NTT Secure Platform Laboratories

30/39

The ECDLPThe ECDLP▸ Consider E ∶ y 2 = x 3 + ax + b elliptic curve with coefficients▸ Consider E ∶ y 2 = x 3 + ax + b elliptic curve with coefficientsa, b in the finite field Fq▸ As we saw, the set E (Fq ) of points on E with coordinates in
Fq (incl. the point at infinity) is a finite commutative groupa, b in the finite field Fq▸ As we saw, the set E (Fq ) of points on E with coordinates in
Fq (incl. the point at infinity) is a finite commutative group▸√
its order is always of the form q + O( q) (Hasse bound)▸√
its order is always of the form q + O( q) (Hasse bound)▸ Given a point P ∈ E (Fq ) and an integer x, one can efficiently▸ Given a point P ∈ E (Fq ) and an integer x, one can efficiently▸ The elliptic curve discrete logarithm problem (ECDLP), on▸ The elliptic curve discrete logarithm problem (ECDLP), on

which all elliptic curve crypto is based, is the DLP in cyclic
subgroups of E (Fq ).

which all elliptic curve crypto is based, is the DLP in cyclic
subgroups of E (Fq ).

compute the scalar multiplication [x]P = P + P + ⋯ + P (usual
group exponentiation)

compute the scalar multiplication [x]P = P + P + ⋯ + P (usual
group exponentiation)▸ Namely: given P, Q ∈ E (Fq ) such that there exists x with

▸ Namely: given P, Q ∈ E (Fq ) such that there exists x with

Q = [x]P, find x

30/39

√
its order is always of the form q + O( q) (Hasse bound)©2018 NTT Secure Platform Laboratories

Q = [x]P, find x

30/39©2018 NTT Secure Platform Laboratories

Security of ECDLP

Security of ECDLP▸ For most elliptic curves, we know no better (classical) attacks▸ For most elliptic curves, we know no better (classical) attacks

on the ECDLP than the generic oneson the ECDLP than the generic ones√
▸ In particular, the complexity should be O( ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)√ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)▸ In particular, the complexity should be O(▸ In other words, to get e.g. 128 bits of security, simply use an▸ In other words, to get e.g. 128 bits of security, simply use an

elliptic curve over a field of ≈ 256 bits

elliptic curve over a field of ≈ 256 bits

▸ In contrast, due to the subexponential attacks, to get the×▸ In contrast, due to the subexponential attacks, to get the×▸ This is why elliptic curves are generally much more efficient▸ This is why elliptic curves are generally much more efficient▸ However, weak elliptic curves do exist!

▸ However, weak elliptic curves do exist!

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

©2018 NTT Secure Platform Laboratories

31/39

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

Security of ECDLP

Security of ECDLP▸ For most elliptic curves, we know no better (classical) attacks▸ For most elliptic curves, we know no better (classical) attacks

on the ECDLP than the generic oneson the ECDLP than the generic ones√
▸ In particular, the complexity should be O( ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)√ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)▸ In particular, the complexity should be O(▸ In other words, to get e.g. 128 bits of security, simply use an▸ In other words, to get e.g. 128 bits of security, simply use an

elliptic curve over a field of ≈ 256 bits

elliptic curve over a field of ≈ 256 bits

▸ In contrast, due to the subexponential attacks, to get the×▸ In contrast, due to the subexponential attacks, to get the×▸ This is why elliptic curves are generally much more efficient▸ This is why elliptic curves are generally much more efficient▸ However, weak elliptic curves do exist!

▸ However, weak elliptic curves do exist!

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

31/39

©2018 NTT Secure Platform Laboratories

31/39©2018 NTT Secure Platform Laboratories

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

31/39

©2018 NTT Secure Platform Laboratories

Security of ECDLP

Security of ECDLP▸ For most elliptic curves, we know no better (classical) attacks▸ For most elliptic curves, we know no better (classical) attacks

on the ECDLP than the generic oneson the ECDLP than the generic ones√
▸ In particular, the complexity should be O( ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)√ℓ) where ℓ is thelargest prime factor of the order #E (Fq ). If we choose√#E (Fq ) as a prime or almost a prime, this is simply O( q)▸ In particular, the complexity should be O(▸ In other words, to get e.g. 128 bits of security, simply use an▸ In other words, to get e.g. 128 bits of security, simply use an

elliptic curve over a field of ≈ 256 bits

elliptic curve over a field of ≈ 256 bits

▸ In contrast, due to the subexponential attacks, to get the×▸ In contrast, due to the subexponential attacks, to get the×▸ This is why elliptic curves are generally much more efficient▸ This is why elliptic curves are generally much more efficient▸ However, weak elliptic curves do exist!

▸ However, weak elliptic curves do exist!

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

©2018 NTT Secure Platform Laboratories

31/39

Transporting discrete logs under homomorphism

same level of security for the DLP in (Z/pZ) , one needs p of
≈ 3000 bits

Transporting discrete logs under homomorphism▸ Recall that a homomorphism ϕ between two groups G and H▸ Recall that a homomorphism ϕ between two groups G and H

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x▸ Of course, this can only be done for curves E verifying some▸ Of course, this can only be done for curves E verifying somespecial properties

special properties▸ The condition that ϕ is efficiently computable is essential
▸

32/39

©2018 NTT Secure Platform Laboratories

31/39▸ The condition that ϕ is efficiently computable is essential

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

▸

32/39

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

Transporting discrete logs under homomorphism

Transporting discrete logs under homomorphism▸ Recall that a homomorphism ϕ between two groups G and H▸ Recall that a homomorphism ϕ between two groups G and H

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x▸ Of course, this can only be done for curves E verifying some▸ Of course, this can only be done for curves E verifying somespecial properties

special properties▸ The condition that ϕ is efficiently computable is essential▸▸ The condition that ϕ is efficiently computable is essential

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

32/39

Transporting discrete logs under homomorphism▸©2018 NTT Secure Platform Laboratories

32/39

Transporting discrete logs under homomorphism▸ Recall that a homomorphism ϕ between two groups G and H▸ Recall that a homomorphism ϕ between two groups G and H

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x▸ Of course, this can only be done for curves E verifying some▸ Of course, this can only be done for curves E verifying somespecial properties

special properties▸ The condition that ϕ is efficiently computable is essential
▸

32/39

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!

▸ The condition that ϕ is efficiently computable is essential

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

▸

32/39

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

Transporting discrete logs under homomorphism

Outline▸ Recall that a homomorphism ϕ between two groups G and H

is a mapping G → H such that for g1 , g2 ∈ G ,ϕ(g1 g2 ) = ϕ(g1 )ϕ(g2 )▸ Most of the non-generic attacks on the ECDLP take thefollowing form:

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

1. Suppose we want to solve the ECDLP for points P, Q ∈ E (Fq )of prime order ℓ
2. Construct an efficiently computable homomorphismϕ∶ ⟨P⟩ → G such that the DLP in G is “easy” (and ϕ(P) ≠ 1)
3. Then, the relation Q = [x]P gives ϕ(Q) = ϕ(P)x and solving
the DLP in G reveals x

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves▸ Of course, this can only be done for curves E verifying somespecial properties▸ The condition that ϕ is efficiently computable is essential▸

indeed, the discrete logarithm function ⟨P⟩ → Z/ℓZ itself is ahomomorphism!
©2018 NTT Secure Platform Laboratories

32/39©2018 NTT Secure Platform Laboratories

33/39

The Menezes–Okamoto–Vanstone attack

The Menezes–Okamoto–Vanstone attack▸ The epitome of attacks on ECDLP by transporting discrete▸ The epitome of attacks on ECDLP by transporting discretelogs to a weaker group is the MOV attack, relying on theexistence of pairings on elliptic curves▸ Weil: E elliptic curve over Fq , ℓ prime not dividing q. Thereexists a non-degenerate bilinear pairing:logs to a weaker group is the MOV attack, relying on theexistence of pairings on elliptic curves▸ Weil: E elliptic curve over Fq , ℓ prime not dividing q. Thereexists a non-degenerate bilinear pairing:e∶ E [ℓ] × E [ℓ] → µℓe∶ E [ℓ] × E [ℓ] → µℓ

where E [ℓ] is the group of points on E of order dividing ℓ,
and µℓ is the group of ℓ-th roots of unity (both possibly insome extension of Fq )where E [ℓ] is the group of points on E of order dividing ℓ,
and µℓ is the group of ℓ-th roots of unity (both possibly insome extension of Fq )bilinearity: e(P + P ′ , Q) = e(P, Q) ⋅ e(P ′ , Q) and similarly on
the right▸ non-degeneracy: for any P of exact order ℓ, there exists Q
such that e(P, Q) ≠ 1

bilinearity: e(P + P ′ , Q) = e(P, Q) ⋅ e(P ′ , Q) and similarly on
the right▸ non-degeneracy: for any P of exact order ℓ, there exists Q
such that e(P, Q) ≠ 1▸▸▸ Miller: we can compute e(P, Q) in polylog(ℓ) operations in▸ Miller: we can compute e(P, Q) in polylog(ℓ) operations in

the fields of definition of P, Q and µℓ
34/39

the fields of definition of P, Q and µℓ©2018 NTT Secure Platform Laboratories

34/39©2018 NTT Secure Platform Laboratories

The Menezes–Okamoto–Vanstone attack

The Menezes–Okamoto–Vanstone attack (desc.)▸ The epitome of attacks on ECDLP by transporting discretelogs to a weaker group is the MOV attack, relying on theexistence of pairings on elliptic curves▸ Weil: E elliptic curve over Fq , ℓ prime not dividing q. Thereexists a non-degenerate bilinear pairing:▸ Given any elliptic curve E and any P of order ℓ on E , wetherefore get an efficient(?) homomorphism ⟨P⟩ → µℓ as
follows:
1. Find Q ∈ E [ℓ] satisfying non-degeneracy wrt P;
2. Then R ↦ e(R, Q) is a homomorphism ⟨P⟩ → µℓ , “efficient”
by Miller’s algorithme∶ E [ℓ] × E [ℓ] → µℓ

Since µℓ is a subgroup of the multiplicative group of a finite
field, and those multiplicative groups have subexponential
DLP, this gives a subexponential algorithm for the ECDLP?!
▸ Of course, there is a catch! The field of definition of µℓ and
Q are usually very large—exponentially so in fact!

where E [ℓ] is the group of points on E of order dividing ℓ,
and µℓ is the group of ℓ-th roots of unity (both possibly insome extension of Fq )bilinearity: e(P + P ′ , Q) = e(P, Q) ⋅ e(P ′ , Q) and similarly on
the right▸ non-degeneracy: for any P of exact order ℓ, there exists Q
such that e(P, Q) ≠ 1▸▸▸ Miller: we can compute e(P, Q) in polylog(ℓ) operations inµℓ ⊂ F∗qk implies that ℓ divides q k − 1, and for a “random” ℓ,the smallest such k is roughly as large as ℓ itself!

the fields of definition of P, Q and µℓ©2018 NTT Secure Platform Laboratories

34/39©2018 NTT Secure Platform Laboratories

35/39

The Menezes–Okamoto–Vanstone attack (desc.)

The Menezes–Okamoto–Vanstone attack (desc.)▸ Given any elliptic curve E and any P of order ℓ on E , we

▸ Given any elliptic curve E and any P of order ℓ on E , wetherefore get an efficient(?) homomorphism ⟨P⟩ → µℓ as
follows:

therefore get an efficient(?) homomorphism ⟨P⟩ → µℓ as
follows:

1. Find Q ∈ E [ℓ] satisfying non-degeneracy wrt P;
2. Then R ↦ e(R, Q) is a homomorphism ⟨P⟩ → µℓ , “efficient”
by Miller’s algorithm

1. Find Q ∈ E [ℓ] satisfying non-degeneracy wrt P;
2. Then R ↦ e(R, Q) is a homomorphism ⟨P⟩ → µℓ , “efficient”
by Miller’s algorithm

Since µℓ is a subgroup of the multiplicative group of a finite
field, and those multiplicative groups have subexponential
DLP, this gives a subexponential algorithm for the ECDLP?!
▸ Of course, there is a catch! The field of definition of µℓ and
Q are usually very large—exponentially so in fact!

Since µℓ is a subgroup of the multiplicative group of a finite
field, and those multiplicative groups have subexponential
DLP, this gives a subexponential algorithm for the ECDLP?!
▸ Of course, there is a catch! The field of definition of µℓ and
Q are usually very large—exponentially so in fact!

▸

35/39

µℓ ⊂ F∗qk implies that ℓ divides q k − 1, and for a “random” ℓ,the smallest such k is roughly as large as ℓ itself!

©2018 NTT Secure Platform Laboratories

▸

35/39

µℓ ⊂ F∗qk implies that ℓ divides q k − 1, and for a “random” ℓ,the smallest such k is roughly as large as ℓ itself!

©2018 NTT Secure Platform Laboratories

The Menezes–Okamoto–Vanstone attack (desc.)

Practical cases of MOV▸ Given any elliptic curve E and any P of order ℓ on E , we

▸ However, in some cases, the MOV attack is actually efficient

therefore get an efficient(?) homomorphism ⟨P⟩ → µℓ as
follows:▸ Example: E ∶ y 2 = x 3 + ax over a field Fp with p ≡ 3

mod 4.
It is an easy exercise (using the fact that −1 is not a square in
Fp and that the polynomial x 3 − ax is odd) to check that
#E (Fp ) = p + 1

1. Find Q ∈ E [ℓ] satisfying non-degeneracy wrt P;
2. Then R ↦ e(R, Q) is a homomorphism ⟨P⟩ → µℓ , “efficient”
by Miller’s algorithm▸ Thus, for any ℓ∣#E (Fp ), we have ℓ∣p 2 − 1. Hence, the entire

Since µℓ is a subgroup of the multiplicative group of a finite
field, and those multiplicative groups have subexponential
DLP, this gives a subexponential algorithm for the ECDLP?!
▸ Of course, there is a catch! The field of definition of µℓ and
Q are usually very large—exponentially so in fact!
▸

Weil pairing is defined over the field Fp 2 : easy computations▸ This allows to transfer the ECDLP on E to the discrete
logarithm in F∗p 2 , which can be solved in subexponential timeusing GNFS.

µℓ ⊂ F∗qk implies that ℓ divides q k − 1, and for a “random” ℓ,the smallest such k is roughly as large as ℓ itself!

©2018 NTT Secure Platform Laboratories

35/39▸ That curve E is dangerous...

Practical cases of MOV

Practical cases of MOV▸ However, in some cases, the MOV attack is actually efficient▸ However, in some cases, the MOV attack is actually efficient▸ Example: E ∶ y 2 = x 3 + ax over a field Fp with p ≡ 3▸ Example: E ∶ y 2 = x 3 + ax over a field Fp with p ≡ 3▸ Thus, for any ℓ∣#E (Fp ), we have ℓ∣p 2 − 1. Hence, the entire▸ Thus, for any ℓ∣#E (Fp ), we have ℓ∣p 2 − 1. Hence, the entire▸ This allows to transfer the ECDLP on E to the discrete
logarithm in F∗p 2 , which can be solved in subexponential time

▸ This allows to transfer the ECDLP on E to the discrete
logarithm in F∗p 2 , which can be solved in subexponential time

▸ That curve E is dangerous...

▸ That curve E is dangerous...

mod 4.
It is an easy exercise (using the fact that −1 is not a square in
Fp and that the polynomial x 3 − ax is odd) to check that
#E (Fp ) = p + 1

mod 4.
It is an easy exercise (using the fact that −1 is not a square in
Fp and that the polynomial x 3 − ax is odd) to check that
#E (Fp ) = p + 1

Weil pairing is defined over the field Fp 2 : easy computations

Weil pairing is defined over the field Fp 2 : easy computations

using GNFS.

36/39©2018 NTT Secure Platform Laboratories

36/39©2018 NTT Secure Platform Laboratories

using GNFS.

36/39©2018 NTT Secure Platform Laboratories

Practical cases of MOV

Practical cases of MOV▸ However, in some cases, the MOV attack is actually efficient▸ However, in some cases, the MOV attack is actually efficient▸ Example: E ∶ y

2

3▸ Example: E ∶ y 2 = x 3 + ax over a field Fp with p ≡ 3= x + ax over a field Fp with p ≡ 3 mod 4.
It is an easy exercise (using the fact that −1 is not a square in
Fp and that the polynomial x 3 − ax is odd) to check that
#E (Fp ) = p + 1

mod 4.
It is an easy exercise (using the fact that −1 is not a square in
Fp and that the polynomial x 3 − ax is odd) to check that
#E (Fp ) = p + 1▸ Thus, for any ℓ∣#E (Fp ), we have ℓ∣p 2 − 1. Hence, the entire▸ Thus, for any ℓ∣#E (Fp ), we have ℓ∣p 2 − 1. Hence, the entire▸ This allows to transfer the ECDLP on E to the discrete
logarithm in F∗p 2 , which can be solved in subexponential time

▸ This allows to transfer the ECDLP on E to the discrete
logarithm in F∗p 2 , which can be solved in subexponential time

▸ That curve E is dangerous...

▸ That curve E is dangerous...

Weil pairing is defined over the field Fp 2 : easy computations

Weil pairing is defined over the field Fp 2 : easy computations

using GNFS.

©2018 NTT Secure Platform Laboratories

36/39

using GNFS.

Pairing-friendly curve

Pairing-friendly curve▸ The only case where one would use such a curve E is when we▸ The only case where one would use such a curve E is when we

specifically want to compute the pairing: pairing-based
cryptography

specifically want to compute the pairing: pairing-based
cryptography▸ The curves used in this case are said to be pairing-friendly▸ The curves used in this case are said to be pairing-friendly▸ MOV is an unavoidable, but “useful”, consequence of the▸ MOV is an unavoidable, but “useful”, consequence of theexistence of the pairingexistence of the pairing▸ For other applications, easy to rule out: just verify that k suchk

▸ For other applications, easy to rule out: just verify that k suchkthat ℓ∣p − 1 is exponentially large

37/39©2018 NTT Secure Platform Laboratories

36/39©2018 NTT Secure Platform Laboratories

that ℓ∣p − 1 is exponentially large

37/39©2018 NTT Secure Platform Laboratories

Pairing-friendly curve

Pairing-friendly curve▸ The only case where one would use such a curve E is when we▸ The only case where one would use such a curve E is when we

specifically want to compute the pairing: pairing-based
cryptography

specifically want to compute the pairing: pairing-based
cryptography▸ The curves used in this case are said to be pairing-friendly▸ The curves used in this case are said to be pairing-friendly▸ MOV is an unavoidable, but “useful”, consequence of the▸ MOV is an unavoidable, but “useful”, consequence of theexistence of the pairingexistence of the pairing▸ For other applications, easy to rule out: just verify that k suchk

▸ For other applications, easy to rule out: just verify that k suchkthat ℓ∣p − 1 is exponentially large©2018 NTT Secure Platform Laboratories

37/39

that ℓ∣p − 1 is exponentially large©2018 NTT Secure Platform Laboratories

37/39

OutlineOther weak elliptic curves

Groups and discrete logarithms
Basic definitions
Generic algorithms for the discrete log
Some groups with non-generic discrete logs

▸ Anomalous curves: #E (Fp ) = p. Poly-time ECDLP via p-adic

analysis▸ GHS attack for curves over extension fields; not stable underisogenies▸ Attempts to adapt index calculus-style attacks to the elliptic

Elliptic curves and the ECDLP
Elliptic curve groups
Pairings and the MOV attack
Other weak elliptic curves

38/39

curve setting (Diem et al.). Give subexponential asymptotic
complexity in some cases (but not practical)©2018 NTT Secure Platform Laboratories

39/39©2018 NTT Secure Platform Laboratories

Other weak elliptic curves

Other weak elliptic curves▸ Anomalous curves: #E (Fp ) = p. Poly-time ECDLP via p-adic▸ Anomalous curves: #E (Fp ) = p. Poly-time ECDLP via p-adic▸ GHS attack for curves over extension fields; not stable under▸ GHS attack for curves over extension fields; not stable underanalysisanalysis

isogenies

39/39

isogenies▸ Attempts to adapt index calculus-style attacks to the elliptic▸ Attempts to adapt index calculus-style attacks to the elliptic

curve setting (Diem et al.). Give subexponential asymptotic
complexity in some cases (but not practical)

curve setting (Diem et al.). Give subexponential asymptotic
complexity in some cases (but not practical)©2018 NTT Secure Platform Laboratories

39/39©2018 NTT Secure Platform Laboratories