Feature Request: Proof of Membership

[phayes]

I was wondering if it would be possible to add support for "proof of membership" in addition to the current existing range proof.

Details on implementing a proof-of-membership is here: https://paillier.daylightingsociety.org/Paillier_Zero_Knowledge_Proof.pdf

As an example of why this is useful, consider using Paillier homomorphic addition as part of a voting system where votes are kept anonymous.

Consider an example where we have three candidates. Each voter would encode their vote in the form: 0001 0000 0000 to vote for candidate-1, 0000 0001 0000 for candidate-2, and 0000 0000 0001 for candidate 3. Using Paillier, we could sum all the encrypted votes together and obtain a result, while keeping each individual vote secret. However, without a "proof of membership", a malicious voter might cast a malicious vote 01110 0000 0000. A "proof of membership" would allow us to verify a vote is within the set ['0001 0000 0000', '0000 0000 1000', '0000 0000 0001'] and thwart malicious votes.

[omershlo]

Is it possible that this is the same as ZenGo-X/zk-paillier#3 ?
I think the right place for that is in zk-paillier library.
Voting is a cool application! If I recall that is not a very complex proof.

[phayes]

Yes that's the same proof!

[omershlo]

@phayes do you want to take the lead on that?

[phayes]

Hi @omershlo,

I'm honestly not super familiar with paillier internals, and would rather leave it to someone who does.

However, looking at the paper it doesn't look terribly difficult.

[phayes]

Regardless of who does it though, it might be a good idea to have @tfdahlin review it, as they were the one that authored the referenced paper.

[omershlo]

good point.
Anyway - I will start working on it on zk-paillier library.

[tfdahlin]

I'd be happy to take a look at it for you when it's written, but it might take me a while.

It's been a while since I worked on that project, so I'd need to refamiliarize myself with it, and I've never touched Rust so getting used to that code might take a bit.

You might also reference https://github.com/DaylightingSociety/Paillier/blob/master/lib/paillier/zkp.rb#L163 for my implementation in Ruby.

[omershlo]

HI @phayes I wrote the rust version of the proof in the zk-paillier library (@tfdahlin your ruby code was a really valuable reference):
https://github.com/KZen-networks/zk-paillier/blob/master/src/zkproofs/correct_message.rs
I added one test for correctness and one test for soundness.
I will close this issue but you are more than welcome to review and add to the code in zk-paillier. Plenty optimisations are possible.

I do want to give a disclaimer:
I did not find a security proof anywhere for this protocol. I cannot attest to its security (until I will write the proof myself)

cheers.

[phayes]

Thank you! 🎉