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.