Re:The Factoring Cryptopocalypse
by mjn on Sunday August 11, 2013 @06:24AM
(#6194607)
To expand on why it's non-practical: the gap between the "easy" and "hard" directions is only quadratic, whereas key-exchange protocols based on integer factorization and other such unproven candidates for one-way functions are conjectured to have a super-polynomial gap. With such a small gap it's much harder to produce a setup that is on the one hand actually usable by the parties, but on the other hand intractable for the attacker.
You might wonder if something closer to Merkle's approach could be improved to produce a larger gap, but the answer turns out to be no: http://www.boazbarak.org/Papers/merkle.pdf
You might wonder if something closer to Merkle's approach could be improved to produce a larger gap, but the answer turns out to be no: http://www.boazbarak.org/Papers/merkle.pdf