Designated Verifier signatures are weaker than advertised, but still useful

Alice sends a message m to Bob over an insecure channel. Bob reads it, and has no idea who wrote it: even if part of m states that Alice wrote it, Bob has no reason to believe it was genuinely written by Alice. As far as he's concerned, this is an anonymous note.

Alice sends m to Bob, and additionally sends a digital signature s, signed by her signing key sk_a that's associated with her long-term public verification key vk_a. Bob verifies s against m and vk_a and is convinced that someone with Alice's corresponding private signing key authored and signed m at some point in time. In the land of cryptography, whoever knows a private signing key is that identity, and so this proves the authorship of m to Bob.

But Alice may not want there to be a permanent record of her authoring m. She may only want Bob to know she wrote it, but Bob might leak both m and s to others like Judy. Or m and s could be leaked from long term storage by either party. It feels like the signature scheme she's using is, strangely, too strong: anyone who sees s and m will think that someone who knows sk_a authored m.

Alice sends m to Bob, but this time doesn't send a plain ol' digital signature. Instead, she sends a designated verifier signature s' tailored specifically to Bob: now, only someone who knows the private key counterpart of Bob's public key will be able to verify that she sent m.

This should be enough, right? I mean, sure, Bob might be so eager to prove to Judy that Alice wrote m that he willingly shares his private key, but that's an extreme action: Bob won't be able to use that private key anymore now that he's shared it. Or maybe Judy might somehow coerce Bob into handing over his long-term private keys. Or Judy could sneakily compromise Bob's device and exfiltrate his private key from it.

But ruling out these exceptional scenarios of private key sharing and coercion and device compromise... Alice should be safe from others being confident in her authorship of m, right?

Unfortunately no, due to zero knowledge proofs: with them, anything that Bob can share by revealing his private key is something he can also share without needing to reveal it.

This means that the only scenario where a designated verifier signature uniquely helps is where Alice or Bob accidentally leak s' without leaking their own private key too. There are many papers in the literature claiming that Bob would be somewhat unwilling to hand over his private key even if he's cooperating with Judy, but as far as I can tell, they haven't addressed this zero knowledge proof issue at all. Designated verifier signatures are still useful, but weaker than advertised given this.


The authors of these systems do have a trick to partially ameliorate this issue: designated verifier signatures aren't merely upgraded versions of plain digital signatures; they're upgraded versions of 2-party ring signatures.

Alice sends m to Bob and instead of a digital signature, she uses a 2-party ring signature s''. s'' proves that either Alice or Bob authored m (using the notion of authorship we sketched above). Bob is convinced that Alice wrote m, just like with digital signatures, because he doesn't have dementia: he remembers that he didn't send m, and so he's confident that the message came from the only other ring member, Alice. If s'' and m ever land in Judy's hands, Alice now also has an immediate rejoinder to any claims she authored m: nah, Bob did.

As I implied by mentioning dementia, this logic only works if Bob has a functional memory, and this logic can't transfer his confidence that Alice sent him m to other people: if Bob tries to prove that his device only sent m' and m'' but not m, Judy wouldn't be convinced because Bob could've just been using a different device.

Aside: I do wonder what other cryptographic properties can be achieved by taking advantage of the fact that humans have this memory bank with interesting properties. Your memory's recording ~24/7, and so you can confidently convince yourself (as long as you don't have dementia) that "if I don't remember writing m, I didn't write m". Your memory's private (with the exception of advanced interrogation techniques, polygraphs and other lie detectors, etc), and is (rightfully imo) trusted far less by other people than it is by yourself.

But anyways, the final scenario is as follows: Alice sends m to Bob with a designated verifier signature s'''. Like a ring signature, Bob becomes convinced that Alice wrote m because he doesn't remember authoring m. Judy or anyone else who gets their hands on m and s''' can't immediately verify that one of Alice or Bob authored m, which's the designated verifier part. Someone with access to Bob's private key needs to help Judy, by sharing that private key or writing a zero knowledge proof, for her to become convinced that one of them authored m.

What's been achieved here is deniable authentication. Deniable authentication with designated verifiers is a pretty good thing to have for private communications.


... Some stuff is private to the point where it's unacceptable for there to even be cryptographic evidence that either Alice or Bob wrote m. Which would exist if Bob decided to create a zero knowledge proof p to be sent around with m and s'''.

I don't know how to solve this perfectly. My first instinct is key rotation: for example, by having each m sent in a chat carry an ephemeral signing keypair, and then having each signature claim (in a designated verifier way) that one of the last N keypairs sent in the chat was used to sign the message. But this naive version doesn't work because then it's possible for Alice to hand over an ephemeral key to some third party Charlie, and for Charlie to send messages into that previously two party conversation; Bob's logic for deducing that Alice (or someone holding her key) must have authored the message gets thrown out the window.