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).
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
