Description
Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS).<br/> These pairings take as input two points on an elliptic curve E over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12,18,24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.<br/> In 2013-2016, new variants of the function field sieve and the number field sieve algorithms turned out to be faster in certain finite fields related to pairing-based cryptography. Now small characteristic settings (with GF(2^(4*n)), GF(3^(6*m))) are discarded, and the situation of GF(p^k) where p is prime and k is small (in practice from 2 to 54) is unclear.<br/> The asymptotic complexity of the Number Field Sieve algorithm in finite fields GF(p^k) (where p is prime) and its Special and Tower variants is given by an asymptotic formula of the form A^(c+o(1)) where A depends on the finite field size (log p^k), o(1) is unknown, and c is a constant between 1.526 and 2.201 that depends on p, k, and the choice of parameters in the algorithm.<br/> In this work we improve the approaches of Menezes-Sarkar-Singh and Barbulescu-Duquesne to estimate the cost of a hypothetical implementation of the Special-Tower-NFS in GF(p^k) for small k (k <= 24), and update some parameter sizes for pairing-based cryptography. This is a joint work with Shashank Singh, IISER Bhopal, India. lien: http://desktop.visio.renater.fr/scopia?ID=721273***5165&autojoin
Next sessions
-
Post-Quantum Public-Key Pseudorandom Correlation Functions for OT
Speaker : Mahshid Riahinia - ENS, CNRS
Public-Key Pseudorandom Correlation Functions (PK-PCF) are an exciting recent primitive introduced to enable fast secure computation. Despite significant advances in the group-based setting, success in the post-quantum regime has been much more limited. In this talk, I will introduce an efficient lattice-based PK-PCF for the string OT correlation. At the heart of our result lie several technical[…] -
Predicting Module-Lattice Reduction
Speaker : Paola de Perthuis - CWI
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as `Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens[…]-
Cryptography
-