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.
[ Parent
| on HN ]
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.