[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.
>>
>> http://www.pcworld.com/businesscenter/article/257902/researchers_set_new_cryptanalysis_world_record_for_pairingbased_cryptography.html
>>
>
> 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.



More information about the cryptography mailing list