How do multi-message signature schemes achieve selective disclosure and unlinkability?
The issuer signs many messages at once; the holder never shows that signature but derives a zero-knowledge proof that they hold a valid issuer signature over the messages, revealing only the messages they choose, and each proof is fresh and unlinkable.
* With BBS the holder proves an issuer signature exists without showing it, so every proof is new. *
A zero-knowledge proof (ZKP) is a cryptographic proof that a statement is true without giving the verifier any information beyond that fact.
Applied to signatures:
- The issuer signs a list of messages (one per attribute: name, birth date, nationality, …) with one multi-message signature, for example BBS.
- To present, the holder takes the messages, the issuer's public key and the signature, and generates a proof. They mark each message as revealed or hidden.
- The verifier receives the revealed messages and the proof. It learns that the issuer really signed a set of messages containing these values, and nothing else: not the hidden values, and not the signature itself.
Because a new, randomised proof is generated for each presentation, two presentations of the same credential share no common value. They are unlinkable proofs: verifiers cannot tell that they came from the same credential.
Go deeper:
Zero-knowledge proof (Wikipedia) — the classic intuitions (the cave, the colour-blind friend) behind ZKPs.- IRTF draft: The BBS Signature Scheme — the multi-message signature scheme and its proof generation.