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.

  • 1
    $\begingroup$ One thing that comes to mind is the Pallier cryptosystem, which is additively homomorphic. But I would also be interested in lightweight schemes to achieve this. The small 32-bit space might be a problem for public key schemes, though. $\endgroup$ – Thomas Jan 6 '13 at 13:59

It depends on what you mean by "32-bit integer". If you want to add integers which will never exceed the range -231..231-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 gx, and, upon decryption, you would have to solve the discrete logarithm, which can be done with cost about 216 if you are sure that the exponent resides in a 32-bit range (232 is low enough that this can practically be sped up a lot with precomputed tables; e.g., store hashes of all gy where y is a multiple of 212: 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 232 exactly, but security would have been quite nullified in the process. It would deter only low-grade attackers who indiscriminately balk at mathematics.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.