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:

  • 1
    $\begingroup$ The OP asks for signature scheme, and NTRUSign is broken and pqNTRUSign didn't advance into round 2. There is however Falcon which builds on the idea of NTRU and GVP in round 2 receiving contribution from Zhenfei Zhang and William Whyte who I believe are affiliated with NTRU. $\endgroup$ – DannyNiu Jan 29 '20 at 9:11

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.

  • 2
    $\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.