🚀 go-pugleaf

In <5845@brl-smoke.ARPA>, gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
> "Sufficient cleverness" was mostly an oblique reference to the widely-
> held idea that one would have to factor the product of two large
> primes to crack a public-key system.  Some people have maintained that
> any algorithm for cracking such a system amounts to an algorithm for
> the factorization, but I haven't been convinced that this conclusion
> is warranted.

For RSA I agree with you, but there is for instance a cryptosystem such
that ability to break it is provably equivalent to testing for quadratic
residuosity modulo a certain number (the public key).  Galil, Haber, and
Yung, FOCS 1985.  This is not quite the same as factoring, but actually
taking square roots rather than merely knowing whether one exists is in
fact random time equivalent to factoring, so this is evidence that
residuosity is hard.

Of course this depends on interaction rather than the more common method
of one party encrypting, sending the whole thing at once, and then the
other party decrypting.  And it's not very practical.  But it is provable.
So in this case "sufficient cleverness" would have to involve some
breakthroughs in number theory, not just in cryptology.

Disclaimer: Galil is my advisor, and I also work with Haber and Yung.
There may be other systems provably equivalent to simple number
theoretic functions, but this is the one I'm most familiar with.

Note to people who think they know a little number theory: residuosity
is only the same as the Jacobi symbol when n is prime.  The Jacobi symbol
is easy to compute, but residuosity modulo composites is (apparently) not.
-- 
David Eppstein, eppstein@cs.columbia.edu, Columbia U. Computer Science Dept.