# Private set supporting adding elements and proving elements exist

Is it possible to construct such a set that parties can

1. Add elements to the set without revealing the elements or knowing the elements presently in the set.

2. Proving to other parties that a certain element exists in the set in a way that doesn't reveal at which point it was added.

For example, I want Alice, Bob, Cindy and David to start with an empty set. I want Alice to be able to add 5 to the set without revealing 5, Bob to be able to add 6 to the set without knowing 5 is there or revealing 6, and then Cindy, who cooperates with Alice and has access to any necessary information from Alice, to prove to David that 5 is in the set without revealing whether it was Alice or Bob who put it there.

Is there any protocol that would enable such scenario?

If we put in the set $H(x||r)$ instead of x where $r$ is a large enough random value (w.l.o.g assume each x is in the same length). Then, each player can add values without revealing it and the same item can be inserted by different players without knowing it (a collision might happen with negligible probability). Then with access of the third player, one can prove that the value is indeed in that group.