tight reduction. The idea underlying the IDKEA1 is to use an extractable commitment for prover's commitment. In the proof of security, the simulator can open the commitment in two different ways: one by the non-black-box extractor of the KEA1 assumption and the other through the simulated transcript. This means that we don't need to rewind a cheating prover and can prove the security without loss of the efficiency of reduction." />


An Identification Scheme with Tight Reduction

Seiko ARITA  Natsumi KAWASHIMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.9   pp.1949-1955
Publication Date: 2007/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.9.1949
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
Keyword: 
identification scheme,  rewinding,  KEA1 assumption,  tight reduction,  

Full Text: PDF(179.1KB)>>
Buy this Article




Summary: 
There are three well-known identification schemes: the Fiat-Shamir, GQ and Schnorr identification schemes. All of them are proven secure against the passive or active attacks under some number-theoretic assumptions. However, efficiencies of the reductions in those proofs of security are not tight, because they require "rewinding" a cheating prover. We show an identification scheme IDKEA1, which is an enhanced version of the Schnorr scheme. Although it needs the four exchanges of messages and slightly more exponentiations, the IDKEA1 is proved to be secure under the KEA1 and DLA assumptions with tight reduction. The idea underlying the IDKEA1 is to use an extractable commitment for prover's commitment. In the proof of security, the simulator can open the commitment in two different ways: one by the non-black-box extractor of the KEA1 assumption and the other through the simulated transcript. This means that we don't need to rewind a cheating prover and can prove the security without loss of the efficiency of reduction.