15
$\begingroup$

In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.

Pairing-based cryptography using binary fields currently relies on fields such as $\mathbb{F}_{2^{4\times353}}$ (80-bit level of security) and $\mathbb{F}_{2^{4\times1223}}$ (128-bit level of security).

Do these new attacks apply for these fields? How much security loss is expected for them? (It seems to me that they are not heavily impacted since there is a "large" prime factor in the exponent, but I don't know how much safer they are.)


While I believe the issue is not yet settled, here are some comments about the issue:

"This should signal the death knell for pairing based cryptography on Type-1 curves in small characteristic." - Nigel Smart

"it is not clear how well Joux's method applies for quasi prime extensions $2^{2\cdot r}$" - Francisco Rodríguez Henríquez

"one consequence of the new algorithms may be that characteristic 2 and 3 fields are not appropriate for pairing-based cryptography." - Steven Galbraith

$\endgroup$
2
  • 4
    $\begingroup$ This might answer some questions bristolcrypto.blogspot.com/2013/02/discrete-logarithms.html $\endgroup$
    – mikeazo
    Feb 22, 2013 at 14:13
  • 1
    $\begingroup$ @Conrado The important thing about this post, no matter that it is quite old, is that it brings attention to how suddenly an idea in cryptography can hit the waste bin. $\endgroup$
    – Patriot
    Aug 4, 2019 at 1:24

1 Answer 1

7
$\begingroup$

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography.

According to Joux, "a direct consequence of this record is that supersingular curves (of genus 1 or 2) defined over GF(2^257) cannot be used securely for pairing-based cryptography."

It seems now that pairing-based cryptography over binary fields is dead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.