A Characterization of Languages in Constant Round Perfect Zero-Knowledge Interactive Proofs
Summary :
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.)
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.4 pp.546-554
- Publication Date
- 1993/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kouichi SAKURAI, "A Characterization of Languages in Constant Round Perfect Zero-Knowledge Interactive Proofs" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 4, pp. 546-554, April 1993, doi: .
Abstract: 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.)
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_4_546/_p
Copy
@ARTICLE{e76-a_4_546,
author={Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Characterization of Languages in Constant Round Perfect Zero-Knowledge Interactive Proofs},
year={1993},
volume={E76-A},
number={4},
pages={546-554},
abstract={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.)},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - A Characterization of Languages in Constant Round Perfect Zero-Knowledge Interactive Proofs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 546
EP - 554
AU - Kouichi SAKURAI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1993
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.)
ER -
English
