IEICE TRANSACTIONS on Fundamentals
An Identification Scheme with Tight Reduction
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.9 pp.1949-1955
- Publication Date
- 2007/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e90-a.9.1949
- Type of Manuscript
- PAPER
- Category
- Information Security
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
Seiko ARITA, Natsumi KAWASHIMA, "An Identification Scheme with Tight Reduction" in IEICE TRANSACTIONS on Fundamentals,
vol. E90-A, no. 9, pp. 1949-1955, September 2007, doi: 10.1093/ietfec/e90-a.9.1949.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.9.1949/_p
Copy
@ARTICLE{e90-a_9_1949,
author={Seiko ARITA, Natsumi KAWASHIMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Identification Scheme with Tight Reduction},
year={2007},
volume={E90-A},
number={9},
pages={1949-1955},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e90-a.9.1949},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - An Identification Scheme with Tight Reduction
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1949
EP - 1955
AU - Seiko ARITA
AU - Natsumi KAWASHIMA
PY - 2007
DO - 10.1093/ietfec/e90-a.9.1949
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2007
AB - 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.
ER -
English
