TY - JOUR

T1 - Characterization of languages in constant round perfect zero-knowledge interactive proofs

AU - Sakurai, Kouichi

PY - 1993/4/1

Y1 - 1993/4/1

N2 - In this paper, we consider a class of the languages that have (constant round) perfect zero-knowledge interactive proofs without assuming any complexity assumptions. Especially, we investigate the interactive protocol with the restricted prover who runs in probabilistic polynomial time and knows the complete factorization as a trapdoor information of the integer associated with the input. We give a condition of the existence of constant round perfect zero-knowledge interactive proofs without assuming any complexity assumptions. The bit commitment based on the quadratic residuosity has an important role in our protocol and the simulation is based on the technique developed by Bellare, Micali, and Ostrovsky in Ref. (9), so call double running process. However, the proof of perfect zero-knowledgeness needs a more powerful simulation technique. Our simulation extracts more knowledge, the complete factorization of the integer associated with the input, from a (cheating) verifier than Bellare-Micali-Ostrovsky's simulation does. Furthermore, our main result implies that Blum integer has a five move perfect zero-knowledge interactive proof without assuming any complexity assumptions. (All previous known zero-knowledge protocols for Blum integer required either unproven cryptographic assumptions or unbounded number of rounds of message exchange.)

AB - In this paper, we consider a class of the languages that have (constant round) perfect zero-knowledge interactive proofs without assuming any complexity assumptions. Especially, we investigate the interactive protocol with the restricted prover who runs in probabilistic polynomial time and knows the complete factorization as a trapdoor information of the integer associated with the input. We give a condition of the existence of constant round perfect zero-knowledge interactive proofs without assuming any complexity assumptions. The bit commitment based on the quadratic residuosity has an important role in our protocol and the simulation is based on the technique developed by Bellare, Micali, and Ostrovsky in Ref. (9), so call double running process. However, the proof of perfect zero-knowledgeness needs a more powerful simulation technique. Our simulation extracts more knowledge, the complete factorization of the integer associated with the input, from a (cheating) verifier than Bellare-Micali-Ostrovsky's simulation does. Furthermore, our main result implies that Blum integer has a five move perfect zero-knowledge interactive proof without assuming any complexity assumptions. (All previous known zero-knowledge protocols for Blum integer required either unproven cryptographic assumptions or unbounded number of rounds of message exchange.)

UR - http://www.scopus.com/inward/record.url?scp=0027583113&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027583113&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0027583113

SN - 0916-8508

VL - E76-A

SP - 546

EP - 554

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 4

ER -