paillierp.key
Class KeyGen

java.lang.Object
  paillierp.key.KeyGen

public class KeyGen
extends java.lang.Object

Generates key pairs for the Paillier encryption scheme. This set of static methods creates, writes, and retrieves keys used for both the generalized and threshold versions of the Paillier scheme. Other utilities for primes and factorials are included.

Generalized Paillier Key Creation

The generalized version only has one method to create a single private key, due to its limited use. It randomly generates the distinct primes p, q and also generates the master key d to return a private key. The public key is retrievable by calling getPublicKey() from the returned key.

Paillier Threshold Key Creation

There are three methods to create the Paillier threshold keys. Each method requires the l and w parameters, indicating that l private keys will be produced such that any w≥l/2 can decrypt ciphertexts encrypted with the public key.

The methods are either given or randomly generate four distinct primes: p and q of the same length s, and p₁ and q₁ of length s-1. p and q must be strong primes where p=2p₁+1 and q=2q₁+1. The public key is then pq=n

The method then either is given or randomly generates the master private key, d which can decrypt any message encrypted with the above n. It chooses (is given) d where d=0 mod p₁q₁ and d=1 mod pq. The method constructs a (w-1)-degree polynomial f(x) with all random coefficients and fixes the last coefficient (a₀) at d. From f do we construct the l private keys and the public verification keys (used to verify correct share decryption).

The public key is retrievable by calling getThresholdKey() or getPublicKey() from any of the returned keys.

Note that due to the construction of this system, all the threshold keys must be created simultaneously; after l keys are created, no more can be generated without redistributing the private keys again. l cannot change as the value Δ used in the distributed verification keys remains the same, and w cannot change because it is used in the one-time-use function f which is again used in the distributed verification keys.

Given the nature of the threshold version of the scheme, an array of private keys is passed around and returned by this class. For this reason, it is assumed only for the key distributor. After creating an array of private keys (one for each decryption servers), it is expected that the key distributor will distribute the private keys and then destroy all evidence; a collection of any w private keys can create a master private key, capable of single handedly decrypting any ciphertext, loosing all thresholding features.

Other methods

There are other provided methods to write out the Paillier threshold keys to a file for primarily private, testing use only.

Author:

Murat Kantarcioglu, Sean Hall, James Garrity

Constructor Summary

KeyGen()

Method Summary

static java.math.BigInteger	factorial(int n) Computes the factorial of n.
private static java.math.BigInteger[]	genSafePrimes(int s, java.util.Random rnd) This function returns 2 safe primes p (s bits long) and p1 (s-1 bits long) such that p=2p1+1.
static java.math.BigInteger	getPrime(int length, java.util.Random random) Returns a BigInteger that is probably a prime number of length length.
static PaillierPrivateKey	PaillierKey(int s, long seed) This function return the keys for the Paillier class given the number of bits required for the construction.
static PaillierPrivateThresholdKey[]	PaillierThresholdKey(java.math.BigInteger p1, java.math.BigInteger q1, java.math.BigInteger p, java.math.BigInteger q, java.math.BigInteger d, java.math.BigInteger v, int l, int w, long seed) This function generates keys for the Paillier Threshold version.
static PaillierPrivateThresholdKey[]	PaillierThresholdKey(int s, int l, int w, long seed) This function generates keys for the Paillier Threshold version.
static void	PaillierThresholdKey(java.lang.String fname, int s, int l, int w, long seed) This function generates keys for the Paillier Threshold version and stores them in a file.
static PaillierPrivateThresholdKey[]	PaillierThresholdKeyLoad(java.lang.String fname) This function loads keys for the Paillier Threshold version from a file.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KeyGen

public KeyGen()

Method Detail

PaillierKey

public static PaillierPrivateKey PaillierKey(int s,
                                             long seed)

This function return the keys for the Paillier class given the number of bits required for the construction.

This function randomly generates two primes p, q of length s, and creates the key (n, d) where n=pq and d=lcm(p,q), as in Paillier's original scheme.

Parameters:

s - Specifies the number of bits required for the prime factor of n.

seed - Specifies the seed for the random number generator used.

Returns:

Private key for the generalized Paillier cryptosystem

PaillierThresholdKey

public static PaillierPrivateThresholdKey[] PaillierThresholdKey(int s,
                                                                 int l,
                                                                 int w,
                                                                 long seed)

This function generates keys for the Paillier Threshold version. This function randomly generates the four distinct primes p, q, p₁, and q₁, and chooses the master private key d to construct l partial keys where any w of them can correctly decode a ciphertext.

Parameters:

s - Specifies the number of bits required for the prime factor of n.

l - Number of decryption servers.

w - Threshold number of decryption servers. Must be ≤½l

seed - Specifies the seed for the random number generator used.

Returns:

An array of l private threshold keys.

See Also:

KeyGen

PaillierThresholdKey

public static PaillierPrivateThresholdKey[] PaillierThresholdKey(java.math.BigInteger p1,
                                                                 java.math.BigInteger q1,
                                                                 java.math.BigInteger p,
                                                                 java.math.BigInteger q,
                                                                 java.math.BigInteger d,
                                                                 java.math.BigInteger v,
                                                                 int l,
                                                                 int w,
                                                                 long seed)

This function generates keys for the Paillier Threshold version.

This function accepts the four distinct primes and the integer d to create l private keys.

Parameters:

p1 - Prime number

q1 - Prime number, different from p1

p - Prime number, equal to 2*p1+1

q - Prime number, equal to 2*q1+1

d - Master private key

v - Verification key

l - Number of decryption servers.

w - Threshold number of decryption servers. Must be ≤½l

seed - Specifies the seed for the random number generator used.

Returns:

An array of l private threshold keys.

See Also:

KeyGen

PaillierThresholdKey

public static void PaillierThresholdKey(java.lang.String fname,
                                        int s,
                                        int l,
                                        int w,
                                        long seed)
                                 throws java.io.IOException

This function generates keys for the Paillier Threshold version and stores them in a file.

Parameters:

fname - String of the file name where the private keys will be stored

s - Specifies the number of bits required for the prime factor of n.

l - Number of decryption servers.

w - Threshold number of decryption servers. Must be ≤½l

seed - Specifies the seed for the random number generator used.

Throws:

java.io.IOException

PaillierThresholdKeyLoad

public static PaillierPrivateThresholdKey[] PaillierThresholdKeyLoad(java.lang.String fname)

This function loads keys for the Paillier Threshold version from a file.

The public values and public key are retrievable by calling getThresholdKey() or getPublicKey(), respectively, from any of the returned keys.

Parameters:

fname - String of the file name where the private keys are stored

Returns:

An array of preconstructed private keys

getPrime

public static java.math.BigInteger getPrime(int length,
                                            java.util.Random random)

Returns a BigInteger that is probably a prime number of length length.

Parameters:

length - length of prime number

random - Random number generator

Returns:

BigInteger that is probably a prime

See Also:

BigInteger.probablePrime(int,Random)

genSafePrimes

private static java.math.BigInteger[] genSafePrimes(int s,
                                                    java.util.Random rnd)

This function returns 2 safe primes p (s bits long) and p₁ (s-1 bits long) such that p=2p₁+1.

This function implements Algorithm 4.86 of Handbook of Applied Cryptography

Parameters:

s - Specifies the number of bits required for the prime factor p and q

rnd - Random number generator.

Returns:

returns a BigInteger array where BigInteger[0] is p₁, BigInteger[1] is p

factorial

public static java.math.BigInteger factorial(int n)

Computes the factorial of n.

Parameters:

n - the integer

Returns:

n! = n(n-1)(n -2)(n-3)...(2)(1).