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

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.

-
What does hash(a, b, c) mean? Is it just hash(a || b || c), or some other, possibly keyed construction? –  Thomas Nov 27 '12 at 14:55
It means hash(a || b || c). Sorry for not using the conventional notation. –  chmike Nov 27 '12 at 16:12
Actually, the data $A, hash(m), hash(A || R2 || hash(m))$ does leak information about R2; if the attacker has a candidate $R2'$, he can compute $hash( A || R2' || hash(m))$, and so deduce whether $R2' = R2$ –  poncho Nov 28 '12 at 15:56
@poncho or we just found a collision for hash... –  Alexandre Yamajako Nov 28 '12 at 22:01
@AlexandreYamajako: no; it is extremely plausible that the attacker has a short list of plausible $R2'$ values; allowing him to test those values, and determine (with 99.9999% certainty) whether those are on the list) is a very practical leak. –  poncho Nov 29 '12 at 14:21

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.

-
I assigned you the answer because this is the solution I was looking for. Congratulation. I'm very impressed. Not only by the result, also because you didn't gave up. I was about to give up. Your solution uses only hashes with random number for perfect obfuscation to the verifier and one signature per sent message. It's PERFECT! Thank you very much. –  chmike Dec 9 '12 at 14:19

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

-
If I understood correctly, a zero knowledge set is like an accumulator and is equivalent to my list of hashes. It allows a third party to probe membership and may thus indirectly leak information on the membership. However its power is to provide a much more compact member set representation than my hash list. –  chmike Dec 4 '12 at 16:26
Yes you are correct. Another possibility would be to use modified bloom filters to support the security you want. This comes with a cost of false positive replies by the bloom filter for membership queries. fkerschbaum.org/dbsec11.pdf –  curious Dec 5 '12 at 10:16

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.

-
Thank you very much for this answer proposal which is technically valid. Unfortunately it requires that Alice interacts with the verified which is not desirable in the messaging schema I'm implementing. Sorry for not making it clear when I presented the problem. The main reason is because the frequency of verification requests is much much lower than message sending operations and the other reason is to benefit from locality when considering a world wide communication system. Ri will communicate with a verifier close to him. –  chmike Dec 3 '12 at 8:53

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.

-
I'm not sure I understood your protocol. I'm afraid there is a confusion by what I called receiver. I'm French, sorry for the inaccuracy of my language. When Alice writes the message m, she also provides a list of receivers (recipients?). These are the address list we find in the To: field of a mail. Alice will sign the message content the the address list in the To: field. The receiver Rob, will have its address in this list. Other users will too. How could Rob prove to a verifier that he is in the To: list without disclosing the other list member and the message ? –  chmike Dec 4 '12 at 16:00
An obvious solution is for Alice to send one distinct signed message with the same text to each member in her To: list. But this requires that Alice provides as many signatures as there are receivers (recipients) of her message. This also requires to send as many copies of the same text as there are receiver of the message. This isn't green ;) So I was searching a solution where Alice could produce one signed message with the list of receivers and send this unique message to each receiver. The receivers need that list anyway for the reply-all. The verifier must not see the message and the list –  chmike Dec 4 '12 at 16:07