Today’s blog post from the world of secret codes revolves around digital signatures. It is a concept which itself is a lot easier to grasp than the topics that I talked about in my previous blog posts, but I’ll still explore some directions which are less intuitive from a real-world point of view. This post is losely connected to my work with Huang Lin and Sabine Oechsner on linkable ring signatures. Sabine also helped me to write this blog post.
Seals and Signatures are part of our everyday life. The word for formally acknowledging a contract or transaction is to “sign” it, as we associate it with the process of putting a signature on some paper. Signatures are everywhere, for example on your insurance contract, credit card or even formal letters that you send to someone such as job applications.
But what does a signature mean? Well, in most cases it is used to attest that the signer has seen a document and agrees with its content. You sign a contract to show that you understand the terms and will adhere to them. Your doctor signs your prescription to show that a medical professional says you should receive certain medication. But in cases such as credit cards and letters, the real meaning is as a proof of origin: only the signer of the credit card can make certain transactions. A letter is truly from me if it bears my signature, as only I know how to make it. Signatures get their versatility from being perceived as unforgeable. We believe that only the true signer can recreate his true signature, and forging a signature on formal document is punishable by law.
The electronic equivalent to the aforementioned object are digital signatures. They are a bit more difficult to obtain: in the digital world, every string of bits and bytes can simply be copied and pasted onto something new. That is exactly what is impossible about physical signatures which cannot simply be taken from one piece of paper and placed on another (at least that wasn’t possible before the invention of high resolution scanners and printers…).
Instead, digital signatures work differently: they ensure that copies of a document are still legitimate, but every change to the original document will invalidate that assurance. Think about this as making a document safe against tampering by writing it on magic paper, where your signature would vanish as soon as you just put a single drop of ink somewhere else on the paper.
In the digital world, this works as follows: the signer of a message has a secret signing key which only she herself knows (in the above picture, that is symbolized by the special pen). Every receiver has a special verification key which allows him to inspect the document and determine if a signature was made with the signing key or not. The crucial point is that multiple verifiers can share the same key of Alice.
The assurance that digital signatures provide is the intuitive unforgeability. That means that it is impossible for a bad actor, even when having seen the verification key and some already signed documents, to put signatures on previously unsigned data. This is exactly as we imagine signatures to work in the real world where we recognize them if they are made by the right person, but see if someone attempted to forge them.
All doctors are known to have to swear two oaths to be allowed to practice medicine. The most famous one is the so-called Oath of Hippocrates, while the lesser-known (but universally acknowledged) is the Oath of Hieroglyphos. The latter makes sure that each doctors’ handwriting is uniquely recognizable as being done by a medical expert (where no non-doctor can actually understand what it means). At the same time, it is impossible to a non-expert to find out from the handwriting of any two doctors on this planet who actually wrote the prescription, even if they have been trained in different countries by entirely different people.
In cryptography, we have a similar notion which experts call ring signatures. Here, a number of people is allowed to sign a document in the name of all of them. At the same time, it is impossible to find out who actually signed. Verification is possible for anyone who knows the verification keys of all the possible signers. A depiction of this can be found in the figure above.
While we’re at it, there are actually two different types of such signatures which are closely related: ring and group signatures. For a ring signature, we assume that the signers did never coordinate and did not obtain information from some trusted third party. In group signatures, that is indeed possible. There, a group manager is allowed to add and remove potential signers at will, and he may have a special algorithm to identify the signer at his will. They have very distinct security guarantees and are used in different settings.
A direct application of ring signatures (where group signatures are not applicable) is for permission-less anonymous online payments. If Alice wants to send money to Bob electronically, she signs a document saying “The signer pays X money to Bob” and posts it publicly. This allows everybody to see that someone gave X money to Bob. Now obviously such a document must be signed, as Alice would otherwise be able to spend her money twice.
At the same time, a signature would tie the payment directly to Alice. If she really wants to spend her money anonymously, then this is not possible using digital signatures only. Instead, making payments using ring signatures and adding other participants (who do not have to agree to this) to a payment successfully disguises her identity. This is for example used in Monero, a well-known only payment system. The use of ring signatures in this setting is necessary as we cannot assume that tens of thousands of users coordinate to generate keys, as in group signatures.
But using ring signatures opens up new problems, the biggest one being that Alice may now make multiple payments with the same money. These transactions cannot be traced back to her — that is why we want to use ring signatures to begin with! A solution to this are linkable ring signatures where every party can make only one signature with their key. If Alice now attempts to make a second payment, this can then be detected as fraudulent behavior by anyone who looks at the signatures, so these can safely be ignored.
To quickly mention what we did: in our work, we construct such a linkable ring signature scheme with very low signature size and from post-quantum assumptions (the security proof is not post-quantum, though). The signature size is linear in the size of the ring (meaning if the ring has n members, then the size of the signature is a*n for some constant a) but this competes favorably with schemes that are sub-linear: for small sizes of the ring (think n<100) our simpler approach is more efficient. While this bound on the ring size seems to be a strong constraint, observe that in practice Monero uses a ring size of n=5. Moreover, to write down a ring signature one also has to send in the signature which parties are members of the ring, which itself is inherently linear anyway.