Damgârd-Jurik Cryptosystem

Package: libdj.zip
License: GPL
Developer: Frederick Douglas
Contact: fed2@illinois.edu
Added to ACSC: September 12, 2012
Last updated: September 12, 2012


The Damgârd-Jurik cryptosystem is an extension of the Paillier public key cryptosystem (and libdj is an extension of libpaillier). DJ has additive homomorphism, and the ability to control the plain/ciphertext spaces that a given public key is currently encrypting from/to. Specifically, for a public key n, the plain/ciphertext spaces can be Zns, Zns+1 for any s. This lets a single key encrypt arbitrarily large messages - in particular, nested encryptions with only linear growth of the ciphertext are possible. This property, together with the homomorphism, enables e.g. an efficient private information retrieval scheme. libdj also includes a threshold version: rather than a single private key, many key shares capable of producing decryption shares exist, and some threshold of decryption shares must be gathered to decrypt. This version also has the homomorphism and size control.


There are nice comments in the header file. As with libpaillier, this should hopefully be enough, since it's a pretty simple library.

Bugs and Limitations

The same warnings from libpaillier about the library not preventing private keys and plaintexts from being paged out or similarly sloppily handled apply here as well. This system does pick strong primes, though, since it's necessary for correct operation. ("Strong" is here defined as p must be 2p' + 1 for prime p').

As mentioned in the header file, I didn't include the zero-knowledge proofs of faithful decryption that are necessary if you don't trust the decryption servers. As also mentioned in the header file, this is a good opportunity to contribute, since you'd just have to add some new functions without modifying existing code!


The scheme is implemented as described in the following paper.