
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A New 'On the Fly' Identification Scheme: An Asymptoticity TradeOff between ZK and Correctness
Bagus SANTOSO Kazuo OHTA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.1
pp.122136 Publication Date: 2009/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.122
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Secure Protocol Keyword: identification scheme, zeroknowledge, impersonation under serial active attack,
Full Text: PDF>>
Summary:
GPS is an efficient identification (ID) scheme based on Schnorr ID scheme designed for applications where low cost devices with limited resources are used and a veryshort authentication time is required. Let P and V be a prover and a verifier in GPS and < g > be a multiplicative group. P holds a secret key S∈[0,S) and publishes I=g^{s}. In each elementary round: (1) P sends to V_{x}=g^{r} where r is chosen randomly from [0,A), (2) V sends to P a random C∈[0,B), and (3) P sends y=r+cs (no modulus computation). Since there is no modular reduction on y, a key issue is whether GPS leaks information about s. It has been proved that GPS is statistical zeroknowledge, if in asymptotic sense, BS/A is negligible, where is the number of elementary rounds in one complete identification trial. In this paper, first we will show the followings. (1) We can construct a concrete attack procedure which reveals one bit of secret key s from the specified value range of y unless BS/A is negligible. We reconfirm that we must set A extremely large compared to BS. (2) This drawback can be avoided by modifying GPS into a new scheme, GPS^{+}, in which P does not send the value of y in the specified range where y reveals some information about s. GPS^{+} ensures perfect ZK only by requiring both A > BS and A being a multiple of the order of g, while it allows an honest P to be rejected with probability at most BS/(2A) in one elementary round. Under the standard recommended parameters for 80bit security where =1, S=160, and B=35, A=275 is recommended for GPS in GPS' paper. On the other hand, GPS^{+} can guarantee 80bit security and less than one false rejection on average in 100 identifications with only A=210 with the same parameters as above. In practice, this implies 275210=65 bits (≈24%) reductions on storage requirement. We have confirmed that the reduce of A also reduces approximately 4% of running time for online response using a certain implementation technique for GPS^{+} by machine experiment.

