News for hackers. Stuff that matters.
Re:The puzzle that started complexity theory. by eru on Monday December 20, 2010 @04:02PM (#2025758)
And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.
Re:The puzzle that started complexity theory. by cdavidcash on Monday December 20, 2010 @09:30PM (#2026664)
The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squari...

(And we'd use a cryptographic hash function anyway.)

Re:The puzzle that started complexity theory. by eru on Tuesday December 21, 2010 @01:50PM (#2028842)
Thanks!
Re:The puzzle that started complexity theory. by sirclueless on Monday December 20, 2010 @11:25PM (#2026939)
No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break.

A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.