# [cryptography] cryptanalysis of 923-bit ECC?

James A. Donald jamesd at echeque.com
Fri Jun 22 04:11:09 EDT 2012

On 2012-06-21 12:07 AM, James Muir wrote:
> On 12-06-19 08:51 PM, Jonathan Katz wrote:
>> Anyone know any technical details about this? From the news reports I've
>> seen, it's not even clear to me what, exactly, was broken.
>>
>>
>
> There is more detail here:
>
>    http://www.nict.go.jp/en/press/2012/06/18en-1.html
>
> See the subsection "Target problem and the solution" about halfway down.
>
> The field was GF(3^97) and the curve was y^2=x^3-x+1.  The discrete log
> problem was created using the eta pairing and the constants \pi and e.
>
> -James
>

If I understand this correctly, they did not break an 923 bit elliptic
curve.  The elliptic points themselves, the size of one's actual public
key, are only 153 bits, contrary to the press release, which fairly
ordinary size for ec encryption.

They broke bilinear elliptic curve that was 923 bits in the bilinear
extension field, which again is fairly ordinary size for pairing based
cryptography.

Thus this is not an indication that pairing based cryptography is
unreasonably or unusually fragile.  Breaking a 153 bit pairing based
curve is not extravagantly out of line with breaking a regular elliptic
curve, for which the record currently is 112 bits.