On 22 Jun 2001, Derek Atkins wrote: > the set {Alice,Bob,Charlie,Daniel,Eve,Fred,Greg}, there is no way to > know which of them sent it. All members of the set must be mutually > trusted, which means there is no way to sign a document that a set of > people can verify comes EXACTLY from you. Good point. There's always the approach of Alice sending each of Bob,Charlie,Daniel,Eve,Fred,Greg a separate individual DVP, but this incurs undesirable overhead. Plus Alice could send them all slightly different messages and they'd be unable to prove to each other that she was trying to trick them. The original Impagliazzo, Jakobsson, Sako paper partially adresses this. Their method of implementing designated verifier proofs is to perform proofs of the form "Either A is true OR I know secret key K." In the peer-to-peer case, A is "document signed by Alice" and K is Bob's private key. So Bob knows the document is real (assuming he hasn't lost K), but no one else can be sure that he has not faked the proof/forged a signature. Their suggestion for multiple recipients is to have all the recipients share a key K. Following your example, Bob,Charlie,Daniel,Eve,Fred, and Greg generate a secret key using some distributed algorithm such that they each have a share of the key and all shares are required to reconstruct. Now when Alice sends the document to them, each one knows, given that their share is safe, that the document really did come from Alice. An outside observer, on the other hand, has to consider the possibility that the group got together to forge a signature with their knowledge of K. (This forgery can also be done in a distributed manner, so faking one signature doesn't reveal the full key K to anyone). There are at least two flaws with this approach. The first is that it seems to require a new key K for each group of receipients. This may be adressable through the use of group signatures. I haven't thought about it much. I suspect this flaw is closest to the objection you raised. The second flaw is tangential, but I think worth noting. The flaw is that the members of the group must collaborate in order to forge a signature. Whether or not the designation "works" depends on whether or not it is plausible that the group members would collaborate. For instance, suppose that a message is designated to Bob and Carol, who are the heads of state of two warring countries? (The scene from "13 Days" with its "these assurances can never be made public" comes to mind, but isn't quite right). It is not plausible that Bob and Carol would create a shared key K in the first place, never mind collaborate to forge a signature. If the message leaks and is published, Alice cannot convincingly argue that Bob and Carol signed the message instead of her. This might be bad. So the issue becomes not so much one of efficiency, but repudiation. So how do you do designated verifier proofs with multiple non-collaborating verifiers? I think this may be partially adressed as follows: Suppose Alice wants to designate a message to Bob and Carol. Alice sends to Bob M, X_B := E_C( DVS(M,Carol)) , DVS("X_B := E_C(DVS(M,Carol))", Bob) and to Carol sends M, X_C := E_B(DVS(M,Bob)), DVS( "X_C := E_B(DVS(M, Bob))", Carol) Here M is the message, and by "X :=" I am giving a definition of X. DVS(E,F) stands for "A non-interactive designated verifier proof of E which is designated to F." E_B and E_C are public-key encryption using Bob and Carol's public keys respectively. The notation is slightly inconsistent as written, because by "DVS(M, Carol)" I really mean a signature of M designated to Carol, while by "DVS( "X := E_C(DVS(M, Carol))", Bob) I mean a proof that X is a valid encryption of a designated verifier signature. I claim that this gives us a signature in which 1) Carol can determine that M is signed by Alice 2) Carol can determine that M will be verified by Bob as being signed by Alice if she presents X to Bob and he decrypts it to find M 3) Carol cannot prove 1) or 2) to anyone else. Proof: 1) The DVS("X_C := DVS(M,Bob)", Carol) proves that Alice knows a signature from Alice designated to Bob on M. If Carol is willing to assume Alice does not know Bob's private key, this is enough. Otherwise she can require a separate DVS(M, Carol). 2) The DVS(X_C := E_B(DVS(M,Bob)), Carol) convinces Carol that Bob can decrypt X_C to obtain a valid designated verifier signature of M. This is required to prevent Alice from sending different messages to Bob and Carol; while it won't catch Alice immediately, it will allow Bob and Carol to determine that such cheating has occured (they exchange their X values and find that they are different messages). 3) All these signatures are designated verifier for Carol. and the above is similar for Bob. For three designees, Bob, Carol, and David, Alice prepares Bob M, X_B1 := E_C(DVS(M, Carol)), DVS (X_B1 := E_C(DVS(M,Carol)),Bob) M, X_B2 := E_D(DVS(M, David)), DVS (X_B1 := E_C(DVS(M,David)),Bob) Carol M, X_C1 := E_B(DVS(M, Bob)), DVS(X_C1 := E_C(DVS(M,Bob)),Carol) M, X_C2 := E_D(DVS(M, David)), DVS(X_C2 := E_C(DVS(M,David)),Carol) David M, X_D1 := E_B(DVS(M, Bob)), DVS(X_D1 := E_B(DVS(M,Bob)),David) M, X_D2 := E_C(DVS(M, Carol)), DVS(X_D2 := E_C(DVS(M,Carol)),David) For four or more the construction is similar. Note that the length of the signature grows linearly in the number of designees. So if there are n designees, Alice has the pleasurable job of computing n^2 messages, none of which are nice by themselves. My guess is that there's some cute combinatorial result I don't know which will make this easier or show it optimal. The issue now is proving that a string X is a valid encryption of a designated verifier signature. Note that this is a statement with a succinct polynomial time certificate, namely the transcript of the program used to create these messages. So by the generic GMW theorem that all NP statements have ZKPs, plus random oracles to make them noninteractive, we know this can be done. by foolhardy masochists, anyway. A better solution seems to be to note that the IJS paper implements designated verifier signatures as ordinary signature schemes + a chameleon commitment function. I will consider chameleon hash functions (introduced by Rabin and Krawczyk) instead. A chameleon hash function is a public hash function with a secret key; knowing the key allows you to produce arbitrary hash collisions easily, while finding collisions remains intractable without the key. Chameleon hash functions are randomized, so they take the form CHAM-HASH(Key,M,r), where "Key" is the public description of a particular entity's hash. For example, CHAM-HASH(Alice,M,r1) means "the string resulting from a hash of M with Alice's chameleon hash and random value r1". Alice would be able to find a collision for this value, but no one else. A designated verifier signature from Bob to Alice then consists of SIG(CHAM-HASH(Alice,M,r1)), where SIG() is any ordinary signature scheme. Because Alice can create arbitrary collisions in CHAM-HASH, Alice cannot credibly claim that this signature refers to a particular M. (it occurs to me that this still shows that Bob sent Alice *a* message). The idea is that we can leverage this to use existing protocols for verifiable encryption of signatures. Alice tells Carol how to obtain the same hash string S for M as the one Alice used for her DVS for Bob. Then Alice just needs to show that a string X is a proper encryption of an *ordinary* signature. More formally, if Alice wishes to construct X_C := E_B(DVS(M,Bob)), DVS(X_C := E_B(DVS(M,Bob)),Carol) then she does the following 1) Computes S := CHAM-HASH(Bob,M,r1) 2) Computes SIG(S) 3) Computes X_C := E_B(SIG(S)). Sends X_C to Carol. 4) Sends r1 to Carol. Carol computes S := CHAM-HASH(Bob,M,r1) 5) Alice proves that X_C := E_B(SIG(S)) to Carol Note that under the assumption that Alice does not know Bob's private key, she must send Carol the correct r1 for M in step 4. Otherwise Alice could compute a collision on S. Now for step 5, we need a protocol for verifiable encryption of signatures, i.e. a way to show X_C := E_B(SIG(S)) without needing D_B(). Reuben Sumner pointed out Asokan, Shoup, and Waidner made use of these protocols in their fair exchange protocol. Giuseppe Atienese has a few of them as well. I think that may do it. Now the members of the group can all verify that they received the same message M from Alice by exchanging their X values, yet none of them can claim to outside parties that Alice signed M. I'm sure there's a better way; this feels a little bit inelegant/obvious... -David --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

- Re: crypto flaw in secure mai... Bram Cohen
- Re: crypto flaw in secur... Ian BROWN

- Re: crypto flaw in secure mai... Radia Perlman - Boston Center for Networking
- Re: crypto flaw in secur... Eric Rescorla
- Re: crypto flaw in secur... Ian BROWN

- crypto flaw in secure mail st... Don Davis
- Re: crypto flaw in secure mai... lcs Mixmaster Remailer
- Re: crypto flaw in secure mai... Bram Cohen
- Re: crypto flaw in secur... Ian BROWN

- Re: crypto flaw in secure mai... Derek Atkins
- Re: crypto flaw in secur... dmolnar

- Re: crypto flaw in secure mai... dmolnar
- Re: crypto flaw in secure mai... Jeffrey I. Schiller
- Re: crypto flaw in secur... John Kelsey

- Re: crypto flaw in secure mai... Peter Gutmann
- Re: crypto flaw in secure mai... Enzo Michelangeli
- Re: crypto flaw in secur... P.J. Ponder

- Re: crypto flaw in secure mai... Greg Broiles
- Re: crypto flaw in secur... Peter Fairbrother
- Re: crypto flaw in secur... Bill Frantz

- Re: crypto flaw in secure mai... lcs Mixmaster Remailer