Java Program for Benaloh Homomorphic Encryption

Introduction

Josh Benaloh, then a graduate student at Yale, presented his homomorphic encryption scheme at CRYPTO 1988 (the construction was joint work with Lea Fischer in 1985). The Benaloh cryptosystem supports additive homomorphic encryption over a restricted message space of size r, where r is a small prime dividing both p-1 and q-1 in the RSA-like modulus N=pq. Unlike Paillier's later scheme which is fully additively homomorphic over Z_N, Benaloh's allows messages up to r-1 with r at the system designer's choice.

For Java learners, Benaloh's scheme is an excellent example of modular residue-class cryptography. It introduces the higher-residuosity problem, exercises lcm computation for the Carmichael function, and demonstrates a brute-force discrete-log decryption loop suitable for small r. The construction is also a building block for several e-voting protocols because the small message space matches a ballot choice of {yes, no, abstain}.

What is the Benaloh Cryptosystem?

The Benaloh cryptosystem is a public-key probabilistic encryption scheme in the higher-residuosity family. Like RSA, it uses a composite modulus N=pq, but unlike RSA it requires an additional small prime r that divides both p-1 and q-1 (with gcd(r, (p-1)/r) = gcd(r, (q-1)/r) = 1 to ensure smooth r-th roots). It also requires a public base y whose (lambda/r)-th residue modulo N is a primitive r-th root of unity. Encryption of a message m in {0, 1, ..., r-1} is c = y^m * u^r mod N for random u in Z_N^*, which is probabilistic because of the randomizer u.

Benaloh differs from Paillier in three ways. First, the message space is {0, ..., r-1} instead of all of Z_N. Second, the public modulus is N instead of N^2, so ciphertexts are smaller. Third, the homomorphic operation is multiplication of ciphertexts mod N, and the corresponding plaintext operation is addition mod r. This makes Benaloh suitable for sealed-bid auction aggregation and voting where the message space is naturally small.

How Benaloh Works - Step by Step

Step 1: Key generation. Pick primes p, q such that a small prime r divides both p-1 and q-1, and gcd(r, (p-1)/r) = gcd(r, (q-1)/r) = 1. For the demo we use p=7, q=31 (since r=3 divides 6 and 30, and gcd(3, 2) = gcd(3, 10) = 1). Compute N = pq = 217, lambda = lcm(p-1, q-1) = lcm(6, 30) = 30. Find y in Z_N^* such that y^(lambda/r) is not 1 mod N (we use y = 3, since 3^10 mod 217 = 25, a primitive cube root of unity). The public key is (y, r, N); the private key is (lambda, the factorization of N).

Step 2: Encryption. To encrypt m in {0, ..., r-1}, pick a random u coprime to N. Compute c = y^m * u^r mod N. Send c. The random u hides m probabilistically: even if m is fixed, two different u produce two different c.

Step 3: Decryption. Compute t = c^(lambda/r) mod N. By Euler-Carmichael, u^(r * lambda/r) = u^lambda = 1 mod N, so t = y^(m * lambda/r) mod N. Let omega = y^(lambda/r) mod N (a primitive r-th root of unity). Then t = omega^m mod N. Brute-force search 0..r-1 for m such that omega^m = t mod N. For r=3 this is at most 3 comparisons; for larger r use baby-step giant-step.

Step 4: Homomorphic property. For two ciphertexts c1 = y^m1 * u1^r and c2 = y^m2 * u2^r, the product c1 * c2 mod N equals y^(m1+m2) * (u1*u2)^r mod N, which is a valid encryption of (m1+m2) mod r. This is the additive homomorphism over Z_r.

Java Program for Benaloh Homomorphic Encryption

import java.math.BigInteger;
import java.security.SecureRandom;

public class BenalohCryptosystemDemo {

    // p=7, q=31, r=3, N=217, lambda=lcm(6,30)=30, y=3
    private static final BigInteger P = BigInteger.valueOf(7);
    private static final BigInteger Q = BigInteger.valueOf(31);
    private static final BigInteger N = P.multiply(Q);              // 217
    private static final BigInteger R = BigInteger.valueOf(3);
    private static final BigInteger LAMBDA = lcm(
        P.subtract(BigInteger.ONE), Q.subtract(BigInteger.ONE));    // 30
    private static final BigInteger LAMBDA_OVER_R = LAMBDA.divide(R); // 10
    private static final BigInteger Y = BigInteger.valueOf(3);
    private static final BigInteger OMEGA = Y.modPow(LAMBDA_OVER_R, N); // 25

    private static BigInteger lcm(BigInteger a, BigInteger b) {
        return a.multiply(b).divide(a.gcd(b));
    }

    // c = y^m * u^r mod N
    public static BigInteger encrypt(BigInteger m, BigInteger u) {
        return Y.modPow(m, N).multiply(u.modPow(R, N)).mod(N);
    }

    // Decrypt by matching c^(lambda/r) to omega^m
    public static BigInteger decrypt(BigInteger c) {
        BigInteger t = c.modPow(LAMBDA_OVER_R, N);
        BigInteger candidate = BigInteger.ONE;
        for (int m = 0; m < R.intValue(); m++) {
            if (candidate.equals(t)) {
                return BigInteger.valueOf(m);
            }
            candidate = candidate.multiply(OMEGA).mod(N);
        }
        throw new IllegalStateException("decryption failed: corrupt c");
    }

    public static void main(String[] args) {
        System.out.println("Setup: p=" + P + " q=" + Q + " N=" + N
            + " r=" + R);
        System.out.println("lambda=" + LAMBDA + " lambda/r="
            + LAMBDA_OVER_R);
        System.out.println("y=" + Y + " omega=y^(lambda/r)=" + OMEGA);

        // Encrypt each of {0, 1, 2} with the same u=5 for reproducibility
        BigInteger u = BigInteger.valueOf(5);
        for (int m = 0; m < 3; m++) {
            BigInteger c = encrypt(BigInteger.valueOf(m), u);
            BigInteger d = decrypt(c);
            System.out.println("m=" + m + " -> c=" + c
                + " -> decrypt=" + d);
        }

        // Homomorphic property: c1 * c2 = E(m1 + m2 mod r)
        BigInteger m1 = BigInteger.ONE;
        BigInteger m2 = BigInteger.valueOf(2);
        BigInteger c1 = encrypt(m1, u);
        BigInteger c2 = encrypt(m2, u);
        BigInteger cProd = c1.multiply(c2).mod(N);
        BigInteger dProd = decrypt(cProd);
        System.out.println("E(m1=" + m1 + ") * E(m2=" + m2 + ") = "
            + cProd);
        System.out.println("Decrypted homomorphic sum mod r -> " + dProd
            + " (expected (1+2) mod 3 = 0)");
    }
}

Code Explanation - Line by Line

The constants P, Q, N, R, LAMBDA, LAMBDA_OVER_R, Y, OMEGA encode the demo parameters. We pick p=7, q=31 because 3 divides both 6 = p-1 and 30 = q-1 and because gcd(3, 2) = gcd(3, 10) = 1. LAMBDA = lcm(6, 30) = 30 is the Carmichael function of N. LAMBDA_OVER_R = 10 is the exponent that maps y to a primitive r-th root of unity.

Y is the chosen non-r-th residue. We picked y = 3 because 3^10 mod 217 = 25, and 25 is a primitive cube root of unity (25^1 = 25, 25^2 = 191, 25^3 = 1 mod 217, with 25 and 191 both not equal to 1). OMEGA = y^(lambda/r) = 25 is precomputed once during class initialization because it is used in every decryption.

The encrypt method computes y^m * u^r mod N in two modular exponentiations and one multiply. The random u must be coprime to N, otherwise the proof that u^lambda = 1 mod N fails; in production we loop until gcd(u, N) = 1. The decrypt method first computes t = c^(lambda/r) mod N, then walks through omega^0, omega^1, ..., omega^(r-1) looking for a match. For r=3 this is at most 3 iterations.

The main method demonstrates three things: encrypt and decrypt each of the three possible plaintexts 0, 1, 2; verify that decryption recovers the original m for each; multiply the ciphertexts for m1=1 and m2=2 and decrypt the product to obtain (m1+m2) mod r = 0, demonstrating the additive homomorphic property.

Sample Input and Output

Setup: p=7 q=31 N=217 r=3
lambda=30 lambda/r=10
y=3 omega=y^(lambda/r)=25
m=0 -> c=125 -> decrypt=0
m=1 -> c=158 -> decrypt=1
m=2 -> c=40 -> decrypt=2
E(m1=1) * E(m2=2) = 27
Decrypted homomorphic sum mod r -> 0 (expected (1+2) mod 3 = 0)

The output confirms both correctness of individual encryption and the additive homomorphism modulo r=3.

Common Mistakes to Avoid

1. Picking p, q such that gcd(r, (p-1)/r) is not 1. This condition is needed to ensure that the r-th power map is a bijection on the r-torsion subgroup. If the gcd is r, the primitive r-th root of unity does not exist mod p, and the decryption lookup fails. Always test gcd(r, (p-1)/r) = 1 during key generation.

2. Choosing y such that y^(lambda/r) = 1 mod N. If y is itself an r-th residue, then omega = 1 and the decryption loop only ever matches m=0. Always test that omega = y^(lambda/r) is not 1 mod N during key generation. Pick random y values until one works.

3. Using a small r that does not divide (p-1)(q-1). Without r | (p-1) and r | (q-1), the entire scheme collapses because there is no primitive r-th root of unity mod N. For larger r, search primes p with p = 1 mod r using Miller-Rabin primality testing.

4. Forgetting that the homomorphic sum wraps around mod r. Encrypting m1 and m2 and multiplying their ciphertexts produces an encryption of (m1 + m2) mod r, not m1 + m2. If the application expects a true integer sum, use Paillier instead, or carry a counter mod r alongside the ciphertext.

Real-World Applications

Benaloh designed his cryptosystem specifically for end-to-end verifiable electronic voting. The scheme is the foundation of Prêt-à-Voter and several academic voting systems, where each ballot is an encryption of 0 (no) or 1 (yes). The tally is the homomorphic product of all ballots, decrypting only to the count of yes votes without revealing individual choices.

Sealed-bid auctions benefit from the small message space. Each bidder commits to a price by encrypting an integer in {0, ..., r-1} where r is the price resolution; the auctioneer computes the homomorphic histogram and reveals the highest count without decrypting individual bids.

In medical research, Benaloh encryption has been used to aggregate patient counts in cohort studies. Each hospital encrypts the number of patients matching a query (a small non-negative integer), the central aggregator multiplies to obtain the encrypted total, and a designated decryptor reveals only the aggregate.

Academic prototypes for privacy-preserving smart metering use Benaloh for tiered consumption reporting: each meter encrypts the bucket index (e.g., 0=low, 1=medium, 2=high consumption) and the utility aggregates the encrypted bucket counts to compute a histogram without learning any individual meter's tier.

Conclusion

Benaloh's cryptosystem trades Paillier's full Z_N message space for a tighter, smaller ciphertext size (mod N instead of mod N^2) and a configurable message space Z_r. Our Java program demonstrated encrypt, decrypt, and the additive homomorphism modulo r. Next study the original Benaloh-Fisher 1985 paper for the proof of security under the higher-residuosity assumption, the Naccache-Stern generalization, and verifiable e-voting schemes built on Benaloh.