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).
Next sessions
-
Chiffrement homomorphe à l'aide des groupes après Nuida
Speaker : Pierre Guillot - Ravel Technologies/Université de strasbourg
Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]-
Cryptography
-
-
Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head
Speaker : Dung Bui - Northwestern University
The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…] -
Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask
Speaker : Michael Schaller - University of Zürich, Applied Algebra group
Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…] -
Nouveaux doctorants
Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)