The Weird World of (Joint) Signatures

Signing a physical document guarantees the signer’s approval of the document. This is ensured by the hardness of seamlessly physically transferring a signature from a document to another one, and of reproducing someone else’s handwriting. In fact, the verification of the authenticity of a signature is similar to assessing the authenticity of a painting. To officially list a newly found painting as a Picasso’s, one has to consult a Picasso expert, who verifies that the piece bears all the distinctive signs of Picasso’s style by comparing it with other works by him. Similarly, to authenticate a contested (physical) signature, an expert compares it to many other signatures by the same signer to verify its consistency with the signer’s handwriting (their “style”).

When implementing such a functionality for electronic documents, we find ourselves in a pickle: First, we need a digital equivalent of the signer’s handwriting (and a way to authenticate it). Second, signatures on electronic documents (think of emails or PDFs) can be easily copy-pasted on other documents: digital signatures should include a way to tie a signature to a file. To address the first issue, a digital-signature scheme equips signers with a signing key and a verification key: The signing key is a bit string that the signer keeps secret, and that represents its personal style (handwriting). The verification key is a different bit string that is available to the public, and that can be used to verify a signature, corresponding to the handwriting authenticity verification by an expert. A digital signature is then a bit string $\sigma$ computed from both the secret key and the (bit–string representation of) the document to be signed. In this way the signature $\sigma$ is linked to both: different messages yield different values of $\sigma$ (as different signing keys would). To verify a signature authenticity requires to get the verification key of the alleged signer, and to check that there is a specific relation between the key, the signature, and the message. This relation is public and depends on the specific scheme. In general, it should be easy to verify, so that anyone that knows the verification key can do it: it turns out that verifying the authenticity of digital signatures is easier than for physical signatures! Exactly as in real life, each verification key is tied to just one signing key: verifying a signature against a different verification key than the signer’s never yields that the signature is authentic (in our painting analogy terms: comparing a Picasso’s to Raffaello’s body of work should not result in classifying the former as part of the latter). This ensures unforgeability of a signature: it should be impossible to generate a signature that passes verification without knowing the secret signing key⁴⁴4There are different flavors of unforgeability, depending on which resources the attacker has (e.g., whether the attacker sees signatures generated by the targeted honest signers). For an overview cf. [7]..

Let us start from the signature length: it would be nice if the signers could come up with just one signature, generated so that it still guarantees that they approve the document. This is what multisignatures[2] do. Multisignatures are a generalization of digital signatures that allow a bunch of users to generate one (somewhat short) joint signature on a message. Verifying such signature requires the verification keys of all the signers: this ensures that everyone actually participated in generating it. Such signatures can be produced either through interactions between the signers, or by simply aggregating partial signatures produced locally by each signer⁵⁵5These are called non-interactive multisignatures, which can be confusing to the inexperienced cryptographer: generating the joint signature still requires some kind of interaction, as there has to be a party that collects all the partial signatures and aggregate them together to produce the joint signature. However, such task can be performed by anyone (even the adversary): the only interaction required is when the signers send the partial signatures to the aggregator.. Obviously, such schemes guarantee that a group of signers is not able to produce a joint signature unless all members agree.

Procedures that require inputs from different parties are usually slow. It would be desirable if a joint signature could be generated by just one of the required signers. Such a signature should not leak the identity of the signer: its goal is just to ensure that the group approved the document.

This is the idea behind group [1, 3] and ring signatures [4]: there is a ring (or group) of signers, each of which can generate a signature on behalf of the others, without interacting with them. Both protocols hide the identity of the signer that actually generated a signature (as long as there are more than two signers in the group/ring). Their main difference lies in how they deal with rogue-signers attacks: signer’s anonymity could allow a corrupted user to get away with signing unapproved documents on behalf of the group! To detect potential rogue members, anonymity is conditional in group signatures: the scheme includes a (somewhat) trusted party called group manager that can ‘‘open’’ a signature to reveal which member of the group generated it. On the other hand, ring signatures remain vulnerable to these attacks: a corrupted user Eve could sign on behalf of herself and Alice, as long as she knows her verification key. Alice has no way to detach herself from it⁶⁶6This can be mitigated using a variant of ring signatures called linkable ring signatures [6], whose disculpability property allows signers to prove that they did not produce a given signature..

This difference translates in less flexibility for the group signature, starting from the key generation. While ring signatures allow for each signer to generate their keys by themselves, in a group signature the group manager has to participate in the process, thus generating the keys always requires some level of interaction. The signing process is less flexible too. Ring signatures allow for the ring of signers to be formed only when the signature is generated (as the signer only needs the verification key of the other ring members), and to vary between signatures. On the contrary, a signature generated through a group signature scheme is always on behalf of all the signers that participated in the key generation protocol (i.e., of the entire group). Generating a signature on behalf of a different group requires to run the key generation protocol (or some analogous key-update protocol) again.

So far we have been pretty pessimist about cosigners, assuming that everyone is trying to frame the one honest signer in the group. However, our daily life is full of nice and trustworthy people! It is a natural question then to ask whether we can relax the security definitions, and assume that there can only be at most $t-1$ misbehaving parties out of the $n$ possible signers. Under this assumption, to prevent rogue-signers attacks it is enough to ensure that a joint signature can only be produced through a collaboration of more than $t$ signers. Such signing protocols are called threshold signatures [9]: given a group of $n$ signers, any subset of more than $t$ of them can generate a signature which is guaranteed to be unforgeable assuming at most $t-1$ rogue signers. This is a compromise, in that it preserves some flexibility in the composition of the group of signers, while still guaranteeing some protection against rogue members.