Fwd: Tor security advisory: DH handshake flaw

[astiglic at okiok.com]

> One algorithm that results in a polynomially verifiable witness is:
>
> Almost All Primes Can be Quickly Certified
> http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf

That's a very old algorithm.  It was an intersting result at the time
(1986) because it is a primality proving algorithm that is not based on
any hypothesis and runs in *expected polynomial time* on almost all inputs
(note the *expected*).  It uses elliptic curves.  However, the algorithm
is not efficient in practice, and we have better theoretical results today
(Agrawal-Kayal-Saxena that is a true primality test that works in
polynomial time on all inputs.  Note that such a deterministic
polynomial-time primality testing algorithm implicitly provides a trivial
certificate of primality, which simply consists of the prime number
itself).

Goldwasser and Kilian's result was extended by ADleman and Huang, later
Atkin developed a simialr algorithm known as the Elliptic Curves for
Primality Proving (ECPP), which I also referred to in my initial post.
Morain worked on implementing Atkin's algorithm.  This is efficient. 
Morain has a web page with lot's of info and nice working code:
http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html

The advantage of Maurer's construction, however, is that it is much
simpler to code.

--Anton


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com