Fast Monte-Carlo Primality Evidence Shown in the Dark

Wenbo Mao
HP Labs, Bristol

We construct an efficient proof of knowledge protocol for demonstrating Monte-Carlo evidence that a number $n$ is the product of two odd primes of roughly equal size. The evidence is shown ``in the dark'', which means that the structure is verified without the prime factors of $n$ disclosed. The cost of a proof is the same as that of performing eight instances of Monte-Carlo primality test for non-secret numbers of $n$'s size. This amounts to $12k\log_2n$ multiplications of integers of size of $n$ and $k$ proof iterations which result in an error probability bounded by $\max(1/2^k, \, 24/n^{1/4})$. Previous protocols for proving two-prime-product structure can achieve cost and error probability comparable to above under two additional requirements: (1) a mutually trusted random source of $k\log_2n$ bits long is accessible by the proving/verification participants, and (2) $n$ is a Blum integer. In absence of (1), an additional $k\log_2n$ iterations are needed for the participants to agree on the needed random input. In failure of (2), $k$ must be increased substantially in order to keep error probability comparably small (e.g., $k$ at 3000 level for an error probability at $1/2^{60}$ level). These two requirements become obsolete from now on.