Generating Zerocoin parameters

All Zerocoin clients in a given deployment must be configured with a trusted non-secret integer N of at least 1,026 bits in length. This is a minimum, however. We strongly recommend N be at least 3,072 bits. N is computed by multiplying together two random safe prime numbers p and q. Once N has been computed, the factors p, q should be destroyed. They are not needed for Zerocoin operation.

Security Warning: It is critical that the modulus N be generated properly and that the factors p, q and all related information be destroyed. These factors are not needed in the protocol. Moreover, any party who learns these factors will be able to double-spend zerocoins. Note however that knowledge of p, q does not jeopardize the anonymity of Zerocoin.

We provide a utility called paramgen to generate N values. This utility tries to wipe p, q from memory as soon as it's finished, but it doesn't try that hard. We provide this program mainly as an example and do not certify it as bulletproof (the computer you're running it on matters as much as the code!) You should be very careful generating N if you plan to use Zerocoin with real money.

For this reason we provide a brief overview of the parameter generation process in case you choose to re-implement it in your own code.

How to generate a trusted parameter N

The following pseudocode generates a k-bit parameter for Zerocoin.

1. Initialize your random number generator well!
2. Generate a random number p' of length (k/2)-1 bits.
3. Test to see if p' is prime (you can use a probabilistic primality test such as the one in OpenSSL). Alternatively you can use an algorithm designed to find prime numbers. If p' is not prime, go back to step 2.
4. Compute p = 2p' + 1 and test to see if p is prime. If not, go back to step 2.
5. Generate a random number q' of length (k/2)-1 bits.
6. Test to see if q' is prime. If q' is not prime, go back to step 5.
7. Compute q = 2q' + 1 and test to see if q is prime. If not, go back to step 5.
8. Compute N = p * q.
9. Utterly obliterate p, q, p', q' (and all seeds used in their generation) from memory.
10. Output N.

Our paramgen utility uses the BN_generate_prime_ex() call to generate the primes p, q. This routine takes a flag safe to specify the generation of safe prime numbers.

Future work

In future releases we plan to provide support for multiple distinct parameters. This provides redundancy, as the protocol will be proof against double spending as long as one parameter is honestly generated. This will slightly increase the proof size, however.

A second project (not currently planned) is to implement distributed multiparty generation of the modulus N. Some protocols exist in the literature to do this. We are not aware of any that have been implemented.

• http://eprint.iacr.org/2001/008.pdf