The Lamport signature scheme, for example, doesn't rely on the difficulty of any problem and it only depends on the existence of one-way functions.
Is there an alternative scheme which also doesn't rely on the difficulty of factoring/discrete logarithm, but provides shorter signatures?


As @YehudaLindell says, since Shor's Quantum Factoring Algorithm kills factoring and discrete log based cryptosystems, almost everything in the "Post-Quantum" crypto world will meet your requirement.

SPHINCS is similar to the Lamport scheme in that it only relies on hash functions.

There's also the realm of lattice-based cryptosystems such as NTRU. Also systems based on isogenies on supersingular elliptic curves produce small signatures.

Links to overview reports on various post-quantum crypto primitives:


There are actually quite a few of these. Interest has been raised on this topic mainly due to the "post-quantum" security of such schemes. Also, Lamport is only a one-time signature, and we want a full-blown signature schemes.

For just one example see, SPHINCS: https://sphincs.cr.yp.to/sphincs-20150202.pdf.

  • 1
    $\begingroup$ MaiaVictor asked for 'short signatures'; it's hard to claim that Sphincs generates short signatures with a straight face... $\endgroup$ – poncho Jan 4 '17 at 0:22
  • $\begingroup$ Well, it's shorter than Lamport, and the question does say "shorter", not "short". $\endgroup$ – Yehuda Lindell Jan 4 '17 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.