Simple homomorphic crypto for 32-bit integers

Question

I'm looking for a simple way to perform homomorphic crypto on 32-bit integers. My only requirement is that I can add and subtract from the plaintext value without actually decrypting it. The crypto need not be particularly strong - the implementation is designed to be a deterrent rather than something more concrete.

Are there any simple algorithms to do such a thing? I'm looking for something that's easy to understand and implement.

Answer 1

It depends on what you mean by "32-bit integer". If you want to add integers which will never exceed the range -2³¹..2³¹-1 (i.e. integers which fit in 32 bits), then Paillier cryptosystem will be fine. It uses mathematics which can be viewed as "slightly complex" so you could also rely on a simpler ElGamal encryption. With ElGamal, you do not add; you multiply. So you would have to represent integer value x with value g^x, and, upon decryption, you would have to solve the discrete logarithm, which can be done with cost about 2¹⁶ if you are sure that the exponent resides in a 32-bit range (2³² is low enough that this can practically be sped up a lot with precomputed tables; e.g., store hashes of all g^y where y is a multiple of 2¹²: you only need to store a million hash values, and you do the discrete log step in an average of two thousands multiplications and hashing).

If by "32-bit integer" you mean modular integers, which "wrap around" at 32 bits, then things become much more complex. You could choose the group parameters for ElGamal such that the generator g has order 2³² exactly, but security would have been quite nullified in the process. It would deter only low-grade attackers who indiscriminately balk at mathematics.

Answer 2

I have made good experiences with Paillier. You will find several existing implementations for it on the net. Personally I'm using an enhanced version of this one: The Homomorphic Encryption Project The offered standard package is working fine and above all well documented. Homomorphic operations are completely transparent - you don't need to know anything about it. There is just a catch with negative numbers but you will find a solution in the FAQ.