Paillier is a type of keypair-based cryptography. This means each user gets a public and a private key, and messages encrypted with their public key can only be decrypted with their private key.
Paillier is not as widely used as other algorithms like RSA, and there are few implementations of it available online. To that end, we have released our own implementation of Paillier in Ruby.
WARNING: Our implementation of Paillier has not been audited by any professional cryptographers. Use it at your own risk.
Unlike many other keypair cryptosystems, Paillier provides “additive homomorphism.” This means that messages can be added together while they are encrypted, and they will decrypt correctly.
Specifically, if Bob has two messages (x and y) encrypted with Alice’s public key (creating cx and cy) he can add them together and send them to Alice. When Alice decrypts the message she will have the result of x + y.
Our implementation of Paillier also includes a zero-knowledge proof, that can verify an encrypted message follows a specific format without decrypting the message.
You can read more about how Paillier’s homomorphic addition, and our zero-knowledge proof, works on our crypto page.
Additive homomorphism makes anonymous counting possible. For example, consider a voting system:
We want to encrypt all ballots for an election board so third parties can’t read the votes
We want the election board to be able to tell us who won the election
We do not want the election board to tell us which elector voted for which candidate
With traditional encryption and decryption there is no way for the election board to know who won the election without decrypting every vote.
With additive homomorphism however, we can re-design the voting system as follows:
Voters encrypt their ballots with the election board’s public key
Voters send their encrypted ballots to a counting server
The counting server adds all the ballots together and sends them to the election board
The election board decrypts the ballot sum, announces who won the election without ever reading a voter’s ballot
If there are only a small number of valid messages, and you can make a complete list of them, then the zero-knowledge proof can be performed between a server and a client. This involves the server challenging the client, and the client proving that their message is in the list of valid messages, without revealing which one.
To re-visit the voting example, the zero-knowledge proof allows the counting server to verify that a ballot is filled out correctly (with only a single vote for a single candidate), without revealing who the elector has voted for.
Note that a zero-knowledge proof is only possible if you can make a list of every valid plaintext message. The more valid plaintext messages there are, the slower the proof will be.
The Daylighting Society is a non-profit devoted to protecting the public from surveillance and censorship through developing positive technology.
That’s great! Please write to us at firstname.lastname@example.org.