# Is there a way to sign a message so that any subset can be verified?

I would like to know if there's a scheme that can allow something like the following:

1. Alice signs a message $$M$$ with signature $$S$$ and gives it to Bob and Mallory.
2. Bob can present any subset of $$M$$, along with $$S$$, to Victor, who can verify that the subset matches $$M$$.
3. If Mallory changes some bits of $$M$$, then sends a subset of the bits to Victor, Victor can know that the message has been tampered with. (Of course, Mallory should not be able to construct a valid signature that would allow her tampered-with bits to be verified).

For example, say

• Alice's message $$M$$ is $$100100$$, and the signature is $$101$$.
• Bob will send Victor $$M=1, M=0, signature=101$$, and Victor will verify that those bits match $$M$$.
• Mallory will send Victor $$M=1, M=1, signature=101$$ (this is malicious, since $$M$$ does not equal $$1$$ in $$M$$). Victor will notice this and refuse to verify.

Does a scheme like this exist?

I think that there are somewhat naive solutions (for example, perhaps the signature could consist of several sub-signatures: each bit and its index in $$M$$ are signed, and the results are concatenated), but I am hoping for something where the signature is short relative to the size of the message.

• What is the origin of this question? What is the aim? Apr 26, 2021 at 20:52

We can easily see that the signature must be at least as large as the message. Otherwise, it would be impossible to verify any arbitrary single bit. Signing a message with n bits must necessarily must involve a signature that can validate n unrelated 1 bit message subsets.

However, if we assume Bob and Mallory are given copies of the message, there may be opportunities where computations are done over the entire message, but not transmitting the entire message. This could help reduce the signature size.

You may be interested in Merkle Trees. I don't know if they are exactly what you are looking for, but they provide some interesting approaches for proving things about contiguous subsets of messages. In a worst case scenario, you would have to send Victor effectively the entire Merkle tree. However, for revealing small fractions of the tree, you may be able to keep a large portion of the information out of the message. You only have to reveal the sibling leaves for every bit you send, which would not reveal the whole message, while still authenticating it as a subset.

There are a few cryptocurrency algorithms out there which leverage this for micropayments. Alice generates a list of coins, puts them in a Merkle tree, and then gets the top of the tree signed by Victor. She then gives this signed top to Bob, who authenticates it with Victor (online or offline). After this point, Alice can send Bob a coin simply by revealing it, and all of the sibling internal nodes required to prove it was part of her list of coins. These algorithms, of course, strive to be efficient. They expose the coins in order, so they only ever have to reveal contiguous subsets, not the arbitrary ones you might need. This keeps the message traffic down to O(n log m) for n coins transferred out of m coins minted.

Another approach would be to carefully select the message that Alice constructs to have the properties you desire, rather than being an arbitrary message. Zero Knowledge Proofs are full of clever situations where Bob has to demonstrate information about a message while carefully controlling how much information is transmitted.

One thing you should definitely watch out for is whether there is any issue with Eve computing the message from just S and the message traffic between Bob and Victor. The content of the message could start getting leaked. If you know the internal node over a group of n bytes, you can brute force those n bytes, recovering a part of the message that hadn't been revealed by Bob. But if the goal is simply to provide subsets of a verified message to Victor, that may be acceptable.

• Many thanks for the informative response! I feel silly for not anticipating your first paragraph. However, could the signature be shorter than M if we required each request from Alice to Victor to contain at least m bits of M? Finally, M is not actually a secret; the motivation to send only a subset to Victor is network bandwidth, not secrecy, so Eve computing the message is of no concern. Apr 28, 2021 at 19:53

Proposition: the signature consists of the message $$M$$ and a standard signature $$S$$ of $$M$$ as an appendix, e.g. $$S$$ is per Ed25519. This allows to verify any subset of $$M$$ (by checking the subset of $$M$$ against the full $$M$$, and the full $$M$$ against it's signature $$S$$).

This proposal reveals $$M$$, but that's unavoidable: if one can verify any subset of $$M$$, then one can trivially find $$M$$ anyway, bit by bit.

For the same reason, the size penalty of this proposal would be minimal, if the size of $$S$$ was minimal.

• Thank you for the response! "Checking the subset of M against the full M" is something I'm trying to avoid. That is, I'd like to avoid sending the full M to Victor in the example above. However, revealing M is not a concern. Apr 28, 2021 at 19:36