Description
This talk is about computing discrete logarithms in non-prime finite fields. These fields arise in pairing-based cryptography. In this setting, the pairing-friendly curve is defined over GF(q) and the pairing takes its values in an extension GF(q^k), where k is the embedding degree.<br/> Fr example, GF(p^2) is the embedding field of supersingular elliptic curves in large characteristic; GF(p^3), GF(p^4), GF(p^6) are the embedding fields of MNT curves, and GF(p^12) is the embedding field of the well-known Barreto-Naehrig curves. In small characteristic, GF(2^(4*n)), GF(3^(6*m)) are considered. To compute discrete logarithms in these fields, one uses the Number Field Sieve algorithm (NFS) in large characteristic (e.g. GF(p^2)), the NFS-High-Degree variant (NFS-HD) in medium characteristic (e.g. GF(p^12)) and the Quasi Polynomial-time Algorithm (QPA) in small characteristic when applicable. These algorithms are made of four steps: polynomial selection, relation collection, linear algebra modulo the prime order of the target group and finally, individual logarithm computation.<br/> All these finite fields are extensions, hence have subfields. We use their structure to speed-up the individual discrete logarithm computation. We obtain an important speed-up in practice and the best case is when the embedding degree k is even. We will illustrate the improvements with the practical case of GF(p^4) with p^4 of 400 bits (120 decimal digits).
Prochains exposés
-
Lightweight (AND, XOR) Implementations of Large-Degree S-boxes
Orateur : Marie Bolzer - LORIA
The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. In cryptography, the focus is on small functions, especially on S-boxes which are classically the only non-linear functions in iterated block ciphers. In this work, we propose new ad-hoc automatic tools to look for lightweight implementations of non-linear functions on up to 5 variables for[…]-
Cryptography
-
Symmetrical primitive
-
Implementation of cryptographic algorithm
-
-
Algorithms for post-quantum commutative group actions
Orateur : Marc Houben - Inria Bordeaux
At the historical foundation of isogeny-based cryptography lies a scheme known as CRS; a key exchange protocol based on class group actions on elliptic curves. Along with more efficient variants, such as CSIDH, this framework has emerged as a powerful building block for the construction of advanced post-quantum cryptographic primitives. Unfortunately, all protocols in this line of work are[…] -
Endomorphisms via Splittings
Orateur : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-