TY - GEN
T1 - Any language in IP has a divertible ZKIP
AU - Itoh, Toshiya
AU - Sakurai, Kouichi
AU - Shizuya, Hiroki
PY - 1993
Y1 - 1993
N2 - A notion of “divertible” zero-knowledge interactive proof systems was introduced by Okamoto and Ohta, and they showed that for any commutative random self-reducible relation, there exists a divertible (perfect) zero-knowledge interactive proof system of possession of information. In addition, Burmester and Desmedt proved that for any language L ∈ NP, there exists a divertible zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist. In this paper, we classify the notion of divertible into three types, i.e., perfectly divertible, almost perfectly divertible, and computationally divertible, and investigate which complexity class of languages has a perfectly (almost perfectly) (computationally) divertible zero-knowledge interactive proof system. The main results in this paper are: (1) there exists a perfectly divertible perfect zero-knowledge interactive proof system for graph non-isomorphism (GNI) without any unproven assumption; and (2) for any language L having an interactive proof system, there exists a computationally divertible computational zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist.
AB - A notion of “divertible” zero-knowledge interactive proof systems was introduced by Okamoto and Ohta, and they showed that for any commutative random self-reducible relation, there exists a divertible (perfect) zero-knowledge interactive proof system of possession of information. In addition, Burmester and Desmedt proved that for any language L ∈ NP, there exists a divertible zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist. In this paper, we classify the notion of divertible into three types, i.e., perfectly divertible, almost perfectly divertible, and computationally divertible, and investigate which complexity class of languages has a perfectly (almost perfectly) (computationally) divertible zero-knowledge interactive proof system. The main results in this paper are: (1) there exists a perfectly divertible perfect zero-knowledge interactive proof system for graph non-isomorphism (GNI) without any unproven assumption; and (2) for any language L having an interactive proof system, there exists a computationally divertible computational zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist.
UR - http://www.scopus.com/inward/record.url?scp=0003056823&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0003056823&partnerID=8YFLogxK
U2 - 10.1007/3-540-57332-1_33
DO - 10.1007/3-540-57332-1_33
M3 - Conference contribution
AN - SCOPUS:0003056823
SN - 9783540573326
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 382
EP - 396
BT - Advances in Cryptology ─ ASIACRYPT 1991 - International Conference on the Theory and Application of Cryptology, Proceedings
A2 - Imai, Hideki
A2 - Matsumoto, Tsutomu
A2 - Rivest, Ronald L.
PB - Springer Verlag
T2 - 1st International Conference on the Theory and Application of Cryptology, ASIACRYPT 1991
Y2 - 11 November 1991 through 14 November 1991
ER -