[cryptography] cryptanalysis of 923-bit ECC?

Samuel Neves sneves at dei.uc.pt
Fri Jun 22 14:20:51 EDT 2012


On 22-06-2012 18:54, Jon Callas wrote:
>
> On Jun 22, 2012, at 2:01 AM, James A. Donald wrote:
>
> > On 2012-06-22 6:21 PM, James A. Donald wrote:
> >>> Is this merely a case where 973 bits is equivalent to ~60 bits
symmetric?
>
> > As I, not an authority, understand this result, this result is not
"oops, pairing based cryptography is broken"
>
> > It is "oops, pairing based cryptography requires elliptic curves
over a slightly larger field than elliptic curve based cryptography does"
>
> Indeed. So kudos to the Fujitsu guys, and we make the curves bigger.
Even 77 bits is really too small for serious work.

Not exactly. If the target is ~80-bit security, ~160-bit elliptic curves
are still fine, even for pairing-based crypto. The failure there was the
choice of the particular *field* and *curve parameters*. Namely,
choosing both the characteristic (3) and the embedding degree (6) to be
small left it open to faster attacks.

>
> Does anyone know what the ratio is for equivalences, either before or
after?

If you use *ordinary* pairing-friendly curves, it remains basically the
same. For example, consider BN curves. They have an embedding degree k =
12. If you want 128-bit security, you choose an elliptic curve over a
256-bit prime field GF(p). This leaves us with the following attack costs:

 - 2^128 to solve discrete logs over the elliptic curve over the GF(p)
(by rho);
 - 2^128 to solve discrete logs over the 3072-bit finite field GF(p^12) 
(by number field sieve**).

Therefore, for appropriately chosen curves, the key sizes remain similar.

** There are the so-called "medium-prime function field sieve" attacks,
but for large enough primes and small enough extension degrees they
don't seem to matter.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120622/7506652f/attachment.html>


More information about the cryptography mailing list