楕円曲線暗号

1985年にニール・コブリッツとビクター・ミラーが独立に提案したが、普及したのは2000年代になってからだ。特許の状況が1990年代を通じて不透明だったことも一因である。安全性の根拠は、曲線上で点を自分自身に何度も加算するのは簡単でも、何回加算したかを逆算するのは難しいという事実にある。つまり離散対数問題が別の衣装を着ただけだ。

利点はサイズで、256ビットの曲線は約3072ビットのRSAに相当する。スマートフォンやスマートカードなど電池で動くものにはうってつけだ。曲線の選択は政治的な問題をはらむ。業界の一部は、出所を説明できない定数を持つNISTのP-256を信用していない。2005年にダニエル・バーンスタインが発表したCurve25519は、設計上の判断をすべて説明したことで普及した。ECCもRSAと同様にShorのアルゴリズムで破られるため、ポスト量子暗号はここにも当てはまる。