Cryptanalysis of ECC

To make sure that your cryptosystem is secure, then you have to do cryptanalysis.

The known attacks for ECC are:

  • The Pohlig-Hellman algorithm (which reduces the problem to subgroups of prime order)
  • Shanks’ baby-step-giant-step method
  • Pollard’s methods, the rho method and the kangaroo method, both of which have parallel versions due to van Oorschot and Wiener
  • The Menezes-Okamoto-Vanstone (MOV) attack using the Weil pairing
  • The Frey-Rueck attack using the Tate pairing
  • The attacks on anomalous elliptic curves (i.e., elliptic curves over F_p which have p points) due to Semaev, Satoh-Araki and Smart
  • Weil descent (for some special finite fields)
  • Algebro-geometric attack

Next step will be to choose which attacks to be used for measuring the level of security of ECC.