0
$\begingroup$

The hardest part about this question is explaining what I mean by simple. I'm measuring simplicity as, simply, the amount of lines of code it takes to implement that algorithm in a simple programming language - say, the untyped lambda calculus, Scheme, vanilla ES5 JavaScript. Of course, this is not possible to measure directly, but some things are just obvious. For example, any algorithm depending on any kind of algebra (multiplication, exponentiation, division, modulus, whatever) is not simple because implementing Bignum takes an obscene ton of lines itself!

For example, this wikipedia article claims the Schnorr signature is the simplest known scheme, polluting the Google results with such a blatantly wrong claim, because this proposal can clearly be implemented with much less code in absolutely any language without native big-integers.

That is why ECDSA, DSA, RSA aren't simple, they depend on way too many number-theoretic functions. I'm looking for a signature scheme that emerges from some kind of natural process, for example, L-systems, cellular automatas. Those are truly simple to implement in any kind of language, no dependencies!

So, what is the simplest digital signature algorithm known?

$\endgroup$
2
  • $\begingroup$ This should just be a comment, but I'm forced to make a full post to say anything at all. First, I've created very small bignum libraries so don't rule that out. As to satisfy your restrictions though, I think you can implement Ring-LWE signatures by only manipulating polynomials stored as short arrays of integers. (Though, again, that is also all that's required for bignums, too.) $\endgroup$ Jan 26 '17 at 17:03
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Jan 27 '17 at 12:54
2
$\begingroup$

Let's first clear up one thing. We want a secure signature scheme. (And by secure, we mean a scheme that is widely accepted as being secure by experts in the field, that is, cryptologists.) That means we can restrict attention schemes from the cryptographic literature that have reasonable security arguments, which rules out most stuff based on cellular automata etc.

There are as you say many notions of simplicity.

If you want to measure lines of code, you could begin by noting that any reasonable signature scheme will almost certainly employ a hash function. Which means that signature schemes based on hash functions should be fairly compact, especially schemes like Lamport one-time signatures. If you want to move beyond one-time schemes, things become more complicated, but perhaps not too much as measured by lines of code.

However, many languages today provide built-in (or nearly built-in) bignum arithmetic, which means that a scheme like Schnorr suddenly becomes extremely easy to implement, once you have a hash function implementation.

An even simpler scheme (probably) is RSA-FDH, which is nearly trivial once you have a hash function implementation and bignum arithmetic.

Another interesting metric is understanding, either the mechanics of the system or its security. On both of those metrics, RSA-FDH scores extremely high. All you need to understand the mechanics of the system is basic number theory. The intuitive security argument is easy to understand. The security proof is also fairly easy to understand (once you understand the intuition behind security proofs and random oracles).

The mechanics of Schnorr signatures are somewhat more complicated, especially if you use elliptic curves. I hesitate to say anything at all about the intuitive security of Schnorr signatures (I find that the only intuition is that its security is non-obvious). The security proof is much more complicated than the RSA-FDH proof.

Some schemes based on bilinear pairings are deceptively easy to describe, but only if you hide most of the complexity involved.

The mechanics of hash-based signatures are often fairly involved and complicated, and the security proofs I have seen have been fairly complicated.

A third metric is how easy it is to make a secure implementation. This is equivalent to a huge can of worms, which among other things involves your entire tool chain. You may suddenly find that your actual cryptographic schemes matters much less than the language you write in. Historically, Schnorr-like schemes have proven very difficult to implement, while something like RSA-FDH should be much easier. (However, I am not an implementation expert, so don't trust me here.)

$\endgroup$
8
  • $\begingroup$ I appreciate the inputs and upvoted your answer, but I think you skipped the question. You started by discarding simpler schemes by assuming they're inherently insecure while not really arguing why that would be the case. $\endgroup$
    – MaiaVictor
    Jan 26 '17 at 10:42
  • $\begingroup$ @MaiaVictor Why would you even think about using a new algorithm until it has received significant amounts of review by good cryptographers? The vast majority of those gets broken. $\endgroup$ Jan 26 '17 at 10:57
  • $\begingroup$ @MaiaVictor Did you read poncho's comment to your question? It is really good. And the reason we "obsess" with number theory (and other kinds of difficult mathematics) is that we get a lot of powerful analysis tools that way. And it is analysis that gives us confidence in security. $\endgroup$
    – K.G.
    Jan 26 '17 at 11:00
  • 1
    $\begingroup$ @MaiaVictor If you do not care about security, that's your business. But you will not find much interest here for such systems. On the contrary, you will find much hostility towards such systems. For good reasons, I hasten to add. $\endgroup$
    – K.G.
    Jan 26 '17 at 21:15
  • 1
    $\begingroup$ @MaiaVictor: and how would your "experiment" give any you any understanding whether a particular signature method is secure or not? $\endgroup$
    – poncho
    Jan 26 '17 at 22:51

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.