HP Labs Technical Reports

Fast Monte-Carlo Primality Evidence Shown in the Dark

Mao, Wenbo

HPL-1999-30R1

Keyword(s): interactive protocols; proof of knowledge; Monte-Carlo primality test

Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. 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 amounts to 12k log2n multiplications of integers of size of n where k is the number of the iterations in the proof and relates to an error probability bounded by max(1/2k, 24/n 1/4). To achieve cost and error probability similar to these, previous techniques require two additional conditions; (1) n is a Blum integer, and (2) a mutually trusted k log n-bit long random source is accessible by the proving /verification participants. In failure of (1), k must be increased substantially in order to keep error probability comparably small (e.g., k should be increased to 3000 for an error probability to remain at the level of 1/2 60). In absence of (2), an additional k log2 n iterations are needed for the participants to agree on the needed random input. We note that the drop of (1) due to this work will have a significance on applications.

20 Pages

Back to Index