Presentation 1995/11/16
A Note on Communication Complexity of a Zeroknowledge Interactive Proof System for a Promise Problem
Masahiro MAMBO, Eiji OKAMOTO,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) The communication cost is sometimes much more expensive than the computation cost. On the other hand, a credit card company, which uses a zero-knowledge interactive proof system, ZKIP, for user authentication, might want to increase the number of users it can dealt with in one day without newly investing into communication equipments. Then the company has to reconstruct a more efficient ZKIP in terms of the number of communicated bits. In this paper an efficient ZKIP for the quadratic residuosity, which is a ZKIP for a promise problem, is presented. It decreases the communication complexity about 5/6 of that of the standard ZKIP.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Communication complexity / Promise problem / ZKIP / Quadratic residuosity / Perfect ZK
Paper # ISEC95-26
Date of Issue

Conference Information
Committee ISEC
Conference Date 1995/11/16(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Note on Communication Complexity of a Zeroknowledge Interactive Proof System for a Promise Problem
Sub Title (in English)
Keyword(1) Communication complexity
Keyword(2) Promise problem
Keyword(3) ZKIP
Keyword(4) Quadratic residuosity
Keyword(5) Perfect ZK
1st Author's Name Masahiro MAMBO
1st Author's Affiliation School of Information Science Japan Advanced Institute of Science and Technology()
2nd Author's Name Eiji OKAMOTO
2nd Author's Affiliation School of Information Science Japan Advanced Institute of Science and Technology
Date 1995/11/16
Paper # ISEC95-26
Volume (vol) vol.95
Number (no) 353
Page pp.pp.-
#Pages 10
Date of Issue