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.