How to prove membership of a list without disclosing the list members?

Question

I'm designing a messaging system where the sender A sends a message m with a signature s to n Receivers.

A Receiver Ri should then be able to prove to a Verifier V that he is one of the receivers of the message without disclosing m and the identity of the other receivers. He will however disclose A and Ri.

Question: how could this be done ? What must A store along with m and sign with s for this to be possible ?

The solution I have now is that A would computes hash(m) and hash(A || Ri || hash(m)) for each receiver Ri. The signature s uses a hash computed over all hash values and nothing else. All these hash values are then send along with m and the signature s to all receivers.

To prove that a receiver Ri is member of the list the receiver sends to the verifier A, all the hash values, s and Ri. The verifier can then verify the signature s and that hash(A || Ri || hash(m)) is in the list of hashes of the receivers.

This solution uses hashes to obfuscate the identity of the receivers and the message.

Is there another solution which would not need to generate and send the list of hashes ?

Is there a risk that something could be deduced about R2 knowing A, R1, hash(m), hash(A || R1 || hash(m)) and hash(A || R2 || hash(m)) ? I guess no if the hash is secure.

Edit : As signaled by poncho this proposed solution is not optimal because the Verifier could easily test if R2 is member of the list. Prior knowledge of potential members of the list would then expose their presence.

Another solution I found that solves this problem, but is unfortunately very inefficient, is for A to generate random numbers and encrypt them with the public key of each receiver Ri. A would then sign the list of encrypted random numbers and sent both with the message to each receiver.

With its secret key, a receiver can decrypt the random number and pass it to the verifier. The verifier can then encrypt the random number and check that the encryption matches the one found in the list and signed by A.

This algorithm is very bad in term of computation complexity for A and in size for the message m. But this proves at least that one solution exist.

Apparently the principle of accumulators would be the way to go. Here is a reference article on this subject: http://www.cs.stevens.edu/~nicolosi/tech-reports/FaNi00.pdf which could be of interest.

Edit 2: Following David Cary's which is technically valid, I must make clear that A (Alice) can't interact with the verifier V. The reason is because the verification process is very infrequent compared to the sending process. Also the verifier's role is strictly limited to verification. It doesn't relay the message. Thus Ri must be able to prove that it is one of the receivers as stated by A by only using information sent along with m.

The only viable solution I found so far is for A to send a list of random numbers, each one encrypted by the public key of one of the Ri. A would sign the list of encrypted random numbers. Each Ri can decrypt its random number and can use this knowledge to prove its identity. Because the numbers are random and encrypted with public key, the identity of the other receivers is perfectly sealed.

Unfortunately it requires one public key encryption for each receiver of each message. This is expensive in processing time and in amount of data to transmit along with the message m.

Answer 1

I think your original idea could be tweaked slightly to avoid the problem Poncho pointed out.

Alice generates 3 files and a signature.

• The message m1 (possibly including the recipient list).
• a file m2, a list of true random numbers Ti (one per recipient).
• a file m3, containing only a list of hashes -- for each recipient, Alice calculates a hash value, hash( A || Ri || Ti || hash(m) ).
• Alice signs m3 with signature s.

Alice sends exactly bit-for-bit the same bundle of messages m1, m2, m3, and s to each recipient Ri. (Alice doesn't send or receive anything directly to or from Victor).

For receiver R7 to prove to Victor that he is a member of the list, R7 sends to the verifier the hash H1 of the m1 message, the signed message m3 and s, and the special random number T7 from m2.

The verifier can then verify the signature s on message m3, and that hash(A || R7 || T7 || H1 ) is somewhere in the list of hashes in m3.

Since each recipient is given the full list of random numbers m2, then each recipient can confirm for himself whether or not the list of recipients (if any) in the message m1 is the complete list, with no additions or removals.

Answer 2

Have a look at Zero Knowledge sets and paragraph 4.3 from here

Answer 3

Here is one way for a Receiver Ri to prove to Verifier V that it received some message m from Alice, and is therefore a member of a the set of people who directly received that message m from Alice, without disclosing the message m or the identity of any other Receiver.

Alice and R7

Alice composes a message something like "To whom it may concern. If someone who has public encryption key PE7 and public signing key PS7 claims they got a message from me that hashes to H, then you can believe it -- yes, I, Alice, the one with public encryption key PEA and public signing key PSA, directly sent them that message.". That message literally includes the public encryption key PE and public signing key PS for one particular Receiver R7 and for Alice. Then Alice signs that message using her private signing key, producing signed message M7.

Then over some secure channel Alice sends the message m to Receiver R7, and once Alice is sure that Receiver R7 has the message m, Alice sends the above signed message M7 to the same Receiver.

R7 and the Verifier

Later Receiver R7 can prove to V that he got that message m from Alice. The Receiver hashes m to produce H, then sets up a secure channel to Verifier V, then somehow proves to the verifier V that he does have the private keys corresponding to PE7 and PS7, and then sends the hash H and forwards the message M7 to that verifier.

From the 2 messages m and M7 that Alice sends to Receiver R7, and the communication between R7 and the Verifier,

• it is not possible for R7 to figure out how many other people (if any) that Alice has sent that same message to.
• After N people have come to the Verifier and proven to the Verifier that they got message m from Alice, it is not possible for the Verifier to figure out the message m, or to figure out how many other people (if any) Alice has sent that message to.

Caveats

I'm interpreting "A Receiver Ri should then be able to prove to a Verifier V that he is one of the receivers of the message" as "A Receiver Ri should then be able to prove to a Verifier V that Ri is one of the receivers that has already received the message m directly from Alice". Did you really mean something more like "Alice gives the message m and a 'encrypted distribution list for message m' to the Verifier V, and the Verifier V only forwards the message m to the receivers that specifically ask for any messages from Alice and can prove they are on the distribution list, but it's impossible to figure out who exactly is on the distribution list from the encrypted distribution list alone"?

I'm assuming that the message m is either long enough or includes enough random padding that it's not possible for anyone to deduce m given only H, the hash of that message.

I'm assuming that when Alice sets up a secure channel to R7, it's not possible for Mallory to set up some sort of man-in-the-middle attack between Alice and the Verifier.

I'm assuming that when R7 sets up a secure channel to the Verifier, it's not possible for Mallory to set up some sort of man-in-the-middle attack between R7 and the Verifier.

EDIT: With this scheme, Alice does not interact with the Verifier. Alice never sends or receives any messages from any Verifier. There may be multiple Verifiers; Alice doesn't even need to know which Verifier that Receiver R7 picks to verify the message.

Answer 4

Here is one way for a Receiver Ri to prove to Verifier V that it received some message m from Alice, and is therefore a member of a the set of people who directly or indirectly received that message m from Alice, without disclosing the message m or the identity of any other Receiver.

Alas, this assumes the receivers and the verifiers are trustworthy.

Alice and R7

Alice composes a message something like "To whom it may concern. If someone claims they got a message from me that hashes to H, then you can believe it -- yes, I, Alice, the one with public signing key PSA, once wrote a message that hashes to H. The timestamp on this message is YYYY-MM-DD.". That message literally includes Alice's public signing key PSA. Then Alice signs that message using the corresponding private signing key, producing signed message M.

Then over some secure channel Alice sends the message m to Receiver R7. Once Alice is sure that Receiver R7 has the message m, Alice sends over some secure channel the above signed message M to the same Receiver.

Alice sends bit-for-bit identical files m and M to every person on her mailing list, always over a secure channel.

With this scheme, Alice does not interact with the Verifier. Alice never sends or receives any messages from any Verifier. There may be multiple Verifiers; Alice doesn't even need to know which Verifier that Receiver R7 picks to verify the message.

R7 and the Verifier

R7 hashes the message m to generate the hash H, and makes sure it matches the hash H mentioned in message M. R7 sends message M and the hash H to the Verifier. The Verifier checks the signature on the the message M to confirm that it is Alice's signature, and confirms that the hash H mentioned in that message matches the hash H generated by R7.

Caveats

Alas, this protocol fails if the receivers are untrustworthy. In other words, once Rob receives a message from Alice, this protocol allows Rob collude with Mallory by leaking the message m and M (or even just the message M) to Mallory. Then Mallory can trick the verifier V into thinking that Alice sent that message directly to Mallory.

Alas, this protocol fails if the verifiers are untrustworthy. Once Rob verifies to Vincent that he got a message from Alice, Vincent could leak that message M and hash H (even though Vincent doesn't know the actual message m or who any of the other recipents are) to Mallory. Once Mallory has those messages, Mallory could trick Victor or any other verifier (perhaps even Vincent) into thinking that Alice sent that message directly to Mallory.

I'm assuming that the message m is either long enough or includes enough random padding that it's not possible for anyone to deduce m given only H, the hash of that message.

I'm assuming that when Alice sets up a secure channel to R7, it's not possible for Mallory to set up some sort of man-in-the-middle attack between Alice and the Verifier.

I'm assuming that when R7 sets up a secure channel to the Verifier, it's not possible for Mallory to set up some sort of man-in-the-middle attack between R7 and the Verifier.