Re: Recipient-verifiable messages

["David P. Kemp" <[e-mail]>]

Jon Callas wrote:
> The obvious difference is this:
> 
> If the shared secret (shared by, say, Alice and Bob) used to generate a MAC
> is leaked -- suppose Charlie learns it -- then anyone, Alice, Bob, or
> Charlie can rewrite the MAC undetectably.
> 
> On the other hand if Alice generates one of these signatures and sends it
> to Bob, a third party, Teresa can verify the signature but:
> 
>  * not be able to create one of her own and
>  * cannot tell from the signature itself whether Alice or Bob made it.
> 
> I'm not sure how useful it is in the real world, but it's a fascinating thing.
> 
> I could sign a message to this list combining a dozen keys and thus create
> a presumption that I made it without explicit demonstration of it.


Thanks, Jon.  I'm still missing something though.

If the algorithm requires 1 private key and n-1 public keys to verify
(so that only the recipients can verify it), then Teresa, not being a
recipient of the original encrypted message but having a forwarded copy
of the decrypt, would not be able to verify it.

Thus by elimination you are talking about an algorithm that requires n
public keys to verify, and anyone can verify that one of n people
generated it without being able to tell which one. 
"Recipient-verifiable" seems like a misnomer for something that
recipients and not-recipients alike can verify.

Now assume that Alice gives something to Charlie, or a bug in her
software allows him to steal it.  Your job is to figure out whether
Charlie got hold of Alice's private key or the shared secret that Alice
derived from her private key and Bob's public key.

There are two possible algorithms: a
"signature-algorithm-that-is-not-a-MAC" that Teresa can verify, and a
MAC function whose key input is derived from Alice's private key and n-1
public keys.  What is the difference between those two algorithms with
respect to what they tell you about what Charlie got from Alice?  (Or
what they tell you about any other question you care to ask?)

In other words, the algorithm is a black box.  You can't see it, you can
only see the g'zoutas and you can do whatever you want with the
g'zintas.  Does the algorithm use a MAC or not?

If it walks like a MAC and it quacks like a MAC, then ...