Paper 2003/232

The Statistical Zero-knowledge Proof for Blum Integer Based on Discrete Logarithm

Chunming Tang, Zhuojun Liu, and Jinwang Liu

Abstract

Blum integers (BL), which has extensively been used in the domain of cryptography, are integers with form $p^{k_1}q^{k_2}$, where $p$ and $q$ are different primes both $\equiv 3\hspace{4pt}mod\hspace{4pt}4$ and $k_1$ and $k_2$ are odd integers. These integers can be divided two types: 1) $M=pq$, 2) $M=p^{k_1}q^{k_2}$, where at least one of $k_1$ and $k_2$ is greater than 1.\par In \cite{dbk3}, Bruce Schneier has already proposed an open problem: {\it it is unknown whether there exists a truly practical zero-knowledge proof for $M(=pq)\in BL$}. In this paper, we construct two statistical zero-knowledge proofs based on discrete logarithm, which satisfies the two following properties: 1) the prover can convince the verifier $M\in BL$ ; 2) the prover can convince the verifier $M=pq$ or $M=p^{k_1}q^{k_2}$, where at least one of $k_1$ and $k_2$ is more than 1.\par In addition, we propose a statistical zero-knowledge proof in which the prover proves that a committed integer $a$ is not equal to 0.\par