Subject: [Cfrg] Algebraic Eraser - cryptanalysis

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 13 Nov 2015 10:07:40 +0000

Dear CFRG,

Some of you may recall that we had a presentation from the SecureRF team
on the Algebraic Eraser key agreement protocol at the Dallas meeting back
in March this year (slides here:
https://www.ietf.org/proceedings/92/slides/slides-92-cfrg-2.pdf). Some
discussion followed on the list:

https://www.ietf.org/mail-archive/web/cfrg/current/msg06565.html

My colleague Simon Blackburn and his collaborators have just published an
attack on the Algebraic Eraser scheme, breaking the scheme at the
designers' claimed 128-bit security level. Their attack recovers the
shared key using 8 CPU hours and 64MB of memory. Their paper is here:

http://arxiv.org/abs/1511.03870

Regards,

Kenny