What is this?

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.

What’s special about Paillier?

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.

Why is additive homomorphism useful?

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

What does the zero-knowledge proof do?

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.

Great, how do I use it?

See our API page to learn how to use the library, then install it from the downloads page.

Who are you?

The Daylighting Society is a non-profit devoted to protecting the public from surveillance and censorship through developing positive technology.

I have more questions, or would like to audit your code

That’s great! Please write to us at paillier@daylightingsociety.org.