[cryptography] cryptanalysis of 923-bit ECC?

Samuel Neves sneves at dei.uc.pt
Wed Jun 20 17:39:34 EDT 2012


On 20-06-2012 22:12, Jon Callas wrote:
> Is this merely a case where 973 bits is equivalent to ~60 bits symmetric? If so, what's equivalent to
AES-128 and 256? Is there something inherently weak in pairing-friendly
curves, like there are in p^n curves?
>

Disclaimer: I'm not an authority either, but here's what I know:

Yeah, pretty much. This is a supersingular curve in the field GF(3^97),
or roughly 154 bits. Being a pairing-friendly curve with an embedding
degree of 6, there is a map from the group of points of an elliptic
curve E(GF(3^97)) to the finite field GF((3^97)^6), which is 923 bit
long. So we can solve the logarithm wherever it is the most convenient.

Now, low characteristic (3 in this case) fields are vulnerable to a
specialized index-calculus attack called the function field sieve (FFS).
This method has the same asymptotic complexity of the special number
field sieve, i.e., L[1/3, (32/9)^(1/3)]. Therefore, 923 bits is not
really that much for the FFS, asymptotically speaking; to put it in
perspective, a 911-bit integer was factored back in 2006 by the SNFS,
and a 1039-bit one in 2007.

For pairing-friendly curves to achieve the 128-bit security level, it is
a good idea to increase the characteristic to prevent FFS-style attacks,
and to increase the embedding degree to something higher than 6.
Barreto-Naehrig curves are defined over (large) prime fields, have
embedding degree 12, and are generally a good choice for the 128-bit
level. 256-bit security requires even larger embedding degrees, on the
order of 24 or so.

If you really must stick with the crazy GF(3^n) curves, then take a look
at the estimates of the folks that broke this curve:
http://eprint.iacr.org/2012/042 (this is where the 2^53 figure came from).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120620/59ee08d7/attachment.html>


More information about the cryptography mailing list