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

*Chunming Tang and 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

**Category / Keywords: **cryptographic protocols / cryptography, Blum integer, statistical zero-knowledge

**Date: **received 3 Nov 2003, last revised 7 Nov 2003

**Contact author: **ctang at mmrc iss ac cn

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20031108:072704 (All versions of this report)

**Short URL: **ia.cr/2003/232

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]