IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1949

PAPER

An Identification Scheme with Tight Reduction
Seiko ARITA†a) , Member and Natsumi KAWASHIMA† , Nonmember

SUMMARY
There are three well-known identification schemes: theFiat-Shamir, GQ and Schnorr identification schemes. All of them areproven secure against the passive or active attacks under some numbertheoretic assumptions. However, eﬃciencies 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 exchangesof 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 forprover’s commitment. In the proof of security, the simulator can open thecommitment in two diﬀerent ways: one by the non-black-box extractor of
the KEA1 assumption and the other through the simulated transcript. Thismeans that we don’t need to rewind a cheating prover and can prove thesecurity without loss of the eﬃciency of reduction.
key words: identification scheme, rewinding, KEA1 assumption, tight reduction

against impersonation by an active adversary based on thediﬃculty of the integer factorization problem. However, itneeds rather long secret keys. The GQ identification scheme
is an extension of the Fiat-Shamir scheme, which reduces
both the number of messages exchanged and memory requirements for secret keys. The GQ identification scheme
is proven to be secure against the passive and concurrent attacks under the RSA and One-More-Inversion assumptions,
respectively [3]. The Schnorr identification scheme is analternative to the Fiat-Shamir and GQ schemes. It is also
proven to be secure against the passive and concurrent attacks under the DLA (Discrete Logarithmic Assumption)
and One-More-DL assumptions, respectively [3].
1.2 Provable Security of Identification Schemes

1.

Introduction

1.1 Zero-Knowledge Identification Schemes
The zero-knowledge identification scheme is a triple(K, P, V) of probabilistic polynomial-time algorithms. A
key-generator K generates a pair (pk, sk) of public and private keys on input of the security parameter k. A prover
P with the secret key sk (and the public key pk) proves its
identity to a verifier V (with the public key pk) through interactions showing its possession of sk in (honest-verifier)zero-knowledge.
The major security goal of identification schemes is toprevent an adversary A with no secret key sk from impersonating the authentic prover P. Such an adversary A is called
passive if A only eavesdrops the message-flow between honest P and V (to impersonate P after that). If A acts as a cheating prover or verifier beyond eavesdropping, A is called an
active adversary. In particular, if A can act as a cheating verifier concurrently against plural prover clones with the same
secret key, it is called a concurrent attack, in which interest
has been growing.
There are three well-known identification schemes: theFiat-Shamir [6], GQ [9] and Schnorr [11] identification
schemes. The Fiat-Shamir scheme is proven to be secure
Manuscript received November 17, 2006.
Manuscript revised March 5, 2007.
Final manuscript received May 16, 2007.
†
The authors are with Institute of Information Security,
Yokohama-shi, 221-0835 Japan.
a) E-mail: arita@iisec.ac.jp
DOI: 10.1093/ietfec/e90–a.9.1949

Let us briefly recall how the proof of the security against
impersonation does work in the case of the Schnorr scheme.
In the Schnorr scheme, P has a secret key x and V has apublic key q, g, h(= g x ). First, P randomly chooses a from
Zq , computes a commitment t = ga and sends t to V, which,in turn, randomly chooses a challenge c from Zq and sends
c to P. Then, P responds y = a + xc to V. Finally, V sees
whether y can correctly open hc t or not, that is, it checks theequality of gy = hc t.
Suppose there is an adversary A that can impersonate aprover in the Schnorr scheme with a non-negligible successprobability. Using A we can construct the following simulator S which computes the discrete logarithm x of a given
element h(= g x ). A simulator S invokes a copy of A, gives
h to A as a public key of a prover in the Schnorr scheme,
and plays the role of a verifier against A. That is, the simulator S , receiving a cheating commitment t∗ from A, sends
a random challenge c to A and gets a cheating response y∗ .
∗Then, we have gy = hc t∗ with probability of A’s success.
Now, S rewinds A to the point receiving a challenge andsends a new random challenge c1 once more to get a new re∗sponse y∗1 from A. We have gy1 = hc1 t∗ also with probabilityof A’s success. Using the two equations, S can compute thediscrete logarithm x of h by x = (y∗ −y∗1 )(c−c1 )−1 with probability of the square of A’s success. Thus, we have the folimp
lowing relation between the advantage AdvID,A of A againstdlof S against DLP (Discrete
ID and the advantage AdvG,S
Logarithmic Problem) (on G = g):
impdl
AdvID,A (k) ≤AdvG,S(k) + η(k)c 2007 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 20071950

with some negligible function η (of security parameter k).
This means a contradiction to DLA. Here, the running time
tS of S is around the twice the running time tA of A: tS (k) ≤2tA (k) + O(k3 ).
The above (standard) proof depends on the well-known
technique “rewinding to extract.” As seen above, the technique sacrifices eﬃciency of the reduction. The probability
to extract the secret is only the square of probability of thesuccessful attack.
The similar situation holds also for the Fiat-Shamir and
GQ schemes.
1.3 Our Results
We show an identification scheme IDKEA1, which is an enhanced version of the Schnorr scheme. Although it needs
four messages exchanged and slightly more exponentiations
for both a prover and a verifier than the Schnorr scheme, the
IDKEA1 is proved to be secure under the two assumptionsof KEA1 [4], [10] and DLA with tight reduction. Here, by
the term “tight reduction” under two assumptions A1 and A2
we mean a reduction in which an adversary who breaks thescheme with probability  in time t can be used to breakthe underlying problems of the assumption Ai with probability i in time ti (i = 1, 2), and we have  ≈ 1 + 2 andt ≤ Min(O(t1 ), O(t2 )).
The idea underlying the IDKEA1, which is inspired by
Barak’s generic non-back-box techniques [1], [2], is to use
an extractable commitment for prover’s commitment. The
extractable commitment is actually extractable only by thesimulator who can use the non-black-box extractor of the
KEA1 assumption. In the proof of security, the simulator
can open the commitment in two diﬀerent ways: one by thenon-black-box extractor and the other through the simulatedtranscript. This means that we don’t need to depend on therewind technique and can prove the security without loss ofthe eﬃciency of reduction.
Our first theorem is as follows.
Theorem 1 If the generator G is both (t ,   )-DLA and(t ,   )-KEA1, then the IDKEA1 scheme ID with the generator G is (t, )-secure under the passive attack with


1 

t ≤ Min (t − 6.4texp ), t2 ≥  +
(texp denotes the time to compute an exponentiation in thegroup generated by G).
In addition, using a variant OMDL+ of the OMDL assumption [3], we can prove the IDKEA1 is secure even under
the concurrent attack also with tight reduction:
Theorem 2 If the generator G is both (t , n + 1,   )-OMDL+
and (t ,   )-KEA1, then the IDKEA1 scheme ID with thegenerator G is (t, n, )-secure under the concurrent attack
with



1 
(t − (4.2 + n)texp ), t2 ≥   +   .

t ≤ Min

1.4 Related Works
A signature scheme whose security can be tightly reduced todiﬃculty of the discrete logarithm problem in the standard
model is proposed by Cramer and Damgard [5]. [5] built
the signature scheme based on Σ-protocol, which can beviewed as a generalization of identification schemes treatedin the presented paper. However, note that the security of
Σ-protocol itself is not tightly reduced to diﬃculty of thediscrete logarithm problem in [5]. Our aim here is at the security of an identification scheme itself, not at the resulting
signature scheme.
Bellare and Palacio [4] show a 3-Round ZeroKnowledge protocol in which the KEA3 assumption (a variant of KEA1) is used to prove its soundness. The role playedby the KEA3 assumption is diﬀerent from ours. In fact, theproof of the soundness in [4] needs the rewinding techniqueto extract the secret of the cheating prover.
Fischlin [7] shows a non-interactive proof of knowledge with online extractors. The online extractor plays thesimilar role as extractors (without rewinding) in the proofof our scheme. The online extractor needs the random oracle model and unfortunately the communication complexity(i.e., the length of the proof) in the scheme is rather highalthough it can be said feasible. Our scheme can be viewed
as an interactive and practical (but restricted) version of [7]based on the non-black-box assumption instead of the random oracle.
2.

Definitions and Assumptions

In this section, following [3], we state the definitions of the
security of identification schemes under the passive and concurrent attacks and introduce the KEA1 and OMDL+ assumptions.
2.1 Security Definitions of Identification Schemes
Let a triple ID = (K, P, V) of probabilistic polynomial-timealgorithms be an identification scheme. A key-generator K
generates a pair (pk, sk) of public and private keys on inputof the security parameter k. A prover P with the secret key
sk (and the public key pk) proves its identity to verifier V(with the public key pk) through interactions showing its
possession of sk.
The security of an identification scheme ID under thepassive attack is defined as follows. In the following A1
acts as an eavesdropper of conversations between an honest
prover and an honest verifier. After halting A1 with an output
St, A2 tries to impersonate the prover using St.
Definition 1 (Security under passive attacks) Let a triple

ARITA and KAWASHIMA: AN IDENTIFICATION SCHEME WITH TIGHT REDUCTION

1951

ID = (K, P, V) of probabilistic polynomial-time algorithms
be an identification scheme. Let A = (A1 , A2 ) be any probabilistic polynomial-time adversary. For ID and A, an exper−pa
is defined as follows (λ denotes the empty
iment Expimp
ID,Astring).

any probabilistic polynomial-time adversary A that runs intime at most t, and makes interactions with at most n prover−ca
is upper bounded by .
clones, the advantage Advimp
ID,A
2.2 Assumptions on Groups

imp−paExpID,A :(pk, sk) ← K;
Invoke A1 (pk);When A1 makes a query λ, reply with an honest
transcript between P(sk, pk) and V(pk);
Let St be an output of A1 ;Invoke A2 (St);
Play the role of honest verifier V(pk) to A2 (St);
Output 1 if the V accepts; otherwise output 0.
In the above, A is assumed to make a query λ at most once.
The advantage of adversary A against ID under thepassive attack is defined as−pa−pa
Advimp= Pr[Expimp
= 1].
ID,A
ID,A

ID is called (t, )-secure under the passive attack if for any
probabilistic polynomial-time adversary A that runs in time−pa
at most t, the advantage Advimp
is upper bounded by .
ID,A
The security of an identification scheme ID under the
concurrent attack is defined as follows. In the following A1
acts as a cheating verifier that can take place in concurrent
sessions with plural prover clones Pi (sk) with the same secret key sk. Those sessions can be interleaved in any ways.
After halting A1 with an output St, A2 with St tries to impersonate the prover P(sk).
Definition 2 (Security under concurrent attacks) Let atriple ID = (K, P, V) of probabilistic polynomial-time algorithms be an identification scheme. Let A = (A1 , A2 ) be
any probabilistic polynomial-time adversary. For ID and−ca
is defined as follows.
A = (A1 , A2 ), an experiment Expimp
ID,A
imp−caExpID,A :(pk, sk) ← K;
Invoke A1 (pk);Play the role of prover clones Pi (sk)concurrently to A1 ;Let St be an output of A1 ;Invoke A2 (St);
Play the role of honest verifier V(pk) to A2 ;Output 1 if the V accepts; otherwise output 0.
(In the above, A1 is assumed to play the role of verifier at
most once with each of prover clone Pi . So, if there are nprover clones invoked, A1 plays the verifier at most n times.)
The advantage of adversary A against ID under the concurrent attack is defined as
imp−caAdvID,A

imp−ca= Pr[ExpID,A= 1].

ID is called (t, n, )-secure under the concurrent attack if for

We use three number-theoretic assumptions on groups: theDLA, KEA1 and OMDL+ assumptions. The DLA is thestandard Discrete Logarithmic Assumption. We use the
DLA in the concrete manner as follows. The group generator G that outputs a generator g of a group of order q, iscalled to satisfy (t, )-DLA if for any adversary A that runsin time at most t, we have$Pr[(q, g) ← G; x ← Zq ; y = g x ; x̂ ← A(q, g, y) | x = x̂] < .
The probability is taken over the coins of G, randomness
choosing x and the coins of A as usual.
The definitions of the KEA1 and OMDL+ assumptions
are as follows.
2.2.1 The KEA1 Assumption
The KEA1 assumption [4], [10] for a group G = g meansthat it is possible only when one knows b to generate a DHpair (gb , gab ) for a randomly selected ga .
Definition 3 (The KEA1 Assumption [4]) Let G be aprobabilistic polynomial-time algorithm which on input of
the security parameter k, outputs a prime number q of kbits and a generator g of a group of order q. Let H be any
probabilistic polynomial-time algorithm which on input ofq, g, A(∈ g) and an auxiliary input w, outputs a pair (B, W)
of elements in G. Let H ∗ be an extractor for H, that is, any
probabilistic polynomial-time algorithm which on input ofq, g, A and an auxiliary input w, outputs b.
For any string w and such G, H, H ∗ , an experimentw
ExpG,H,H ∗ is defined as follows.
w
ExpG,H,H∗ :$(q, g) ← G(1k ); a ← Zq ; A = ga ;(B, W) ← H(q, g, A, w);b ← H ∗ (q, g, A, w);
If W = Ba and B  gb then return 1;
Otherwise return 0.
Then, the advantage of adversary H in G for extractor H ∗ isdefined asww
AdvG,H,H∗ (k) = Pr[ExpG,H,H ∗ (k) = 1].

G is called to satisfy (t, )-KEA1 if any adversary H thatruns in time at most t, there exists an extractor H ∗ that runsw
also in time at most t and the AdvG,H,H∗ is upper boundedby  for any w.
The KEA1 assumption in [4] is stated only in terms of
the asymptotic behavior. The above concrete version of thedefinition seems to be natural with respect to the intrinsic
meaning of the assumption.

IEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1952

2.2.2 The OMDL+ Assumption
The OMDL+ assumption is a stronger version of the OMDL
assumption used in [3]. The OMDL assumption means that
it is diﬃcult to solve one more DLP (Discrete Logarithmic
Problem) instance even if one is provided with several randomly selected DLP instances with their answers, all sharing the same base element. The OMDL+ assumption isstronger in the sense that the challenge problems are given
with some hints.
Definition 4 (OMDL+ Assumption) Let G be a probabilistic polynomial-time algorithm which on input of the security parameter k, outputs a prime number q of k bits anda generator g of a group of order q. Let I be any probabilistic polynomial-time algorithm which on input of q, g outputs
x1 , . . . , xn using the challenge oracle CO and the DL oracle
DL. The challenge oracle COg given query h answers witha pair of g x and h x , where x is randomly chosen from Zq
independently by every query. The DL oracle DLg , given
query h, answers with x satisfying h = g x .
omdl+
is defined as
For such G and I, an experiment ExpG,I
follows.
omdl+
ExpG,I:(q, g) ← G(1k );Invoke I COg ,DLg (q, g);
When I makes a query h to COg ,let COg reply with such (gi , hi );When I makes a query h to DLg ,let DLg reply with logg (h);Let (x1 , . . . , xn ) be an output of I;
Let (g1 , h1 ), . . . , (gn , hn ) be challenges issued by COg ;Let m be the number of answers given by DLg ;If gi = g xi for all i = 1, . . . , n and m < nthen return 1;
Otherwise return 0.

The advantage of adversary I against G is defined as
omdl+
omdl+
= Pr[ExpG,I= 1].
AdvG,I

G is called to satisfy (t, n, )-OMDL+ if for any probabilistic
polynomial-time adversary I that runs in time at most t andmakes at most n queries to the challenge oracle CO, theomdl+
is upper bounded by .
advantage AdvG,I
It is easily seen that the OMDL+ assumption means the
OMDL assumption and that the OMDL assumption means
the CDH assumption or the OMDL+ assumption.
3.

The Identification Scheme IDKEA1

We describe our identification scheme IDKEA1= {K, P, V}.
Let G be a probabilistic polynomial-time algorithm which
given the security parameter k outputs a prime number q ofk bits and a generator g of a group of order q.

A key-generation algorithm K of the IDKEA1 on input
k runs G(k) to get q, g1 , chooses x randomly from Zq , computes h1 = g1x and outputs x and q, g1 , h1 as a secret key anda public key, respectively.
In the IDKEA1, a prover P (with a secret key x) proves
its identity to a verifier V (with a public key q, g1 , h1 ) as
follows.
1◦ V randomly selects a from Zq and computes g2 = ga1 . V
sends g2 to P.
2◦ P randomly selects m0 from Zq and computes c1 =m00gm
1 , c2 = g2 . P sends c1 , c2 to V.
◦
3 V sees whether c2 = ca1 or not. If not, V aborts. Otherwise V randomly selects r from Zq and sends r to P.
4◦ P computes m = m0 − rx and sends m to V.
r5◦ V sees whether c1 = gm
1 h1 does hold or not. If it does, V
accepts. Otherwise V rejects.
As seen above, the IDKEA1 needs two exponentiations
for a prover and two exponentiations and a two-exponent
multi-exponentiation for a verifier, and it needs four messages exchanged. (Assuming (as in [8]) that a two-exponent
multi-exponentiation takes 1.2 texp , the time for a verifier isdominated by 3.2 texp , where texp denotes the time to compute an exponentiation.) Thus, the IDKEA1 is not so eﬃcient as the Schnorr scheme in computations and communications. However, the IDKEA1 has the security proof withtight reduction without loss of the security.
4.

Security of the IDKEA1

We prove the security of the IDKEA1. In the proof, the simulator can open the cheating prover’s commitment in two
diﬀerent ways: one by the non-black-box extractor of the
KEA1 assumption and the other through the simulated transcript. This means we don’t need to rewind the cheating
provers.
4.1 Security under the Passive Attack
Security of the IDKEA1 under the passive attack is provenunder the DLA and KEA1 assumptions with tight reduction.
Theorem 1 If the generator G is both (t ,   )-DLA and(t ,   )-KEA1, then the IDKEA1 scheme ID with the generator G is (t, )-secure under the passive attack with


1 

t ≤ Min (t − 6.4texp ), t2 ≥   +  
(texp denotes the time to compute an exponentiation in thegroup generated by G).
Proof Assume we have a passive adversary A = (A1 , A2 )against ID = {K, P, V}, running in time at most t, which
succeeds in impersonating the honest prover P with probability at least . We use A to construct a KEA1-adversary H

ARITA and KAWASHIMA: AN IDENTIFICATION SCHEME WITH TIGHT REDUCTION

1953

running in time at most t and we use A and H to construct a
DL-extractor E running in time at most t with the advantage
AdvE at least  −   (≥   ). The stated result follows.
Let q, g1 , h1 be generated as in K:

By the second equation of Eq. (1) and Eq. (2), we see
x = (m∗0 − m∗ )r−1 = x̂.
Thus,

$

q, g1 ← G; x ← Zq ; h1 = g1x .
On inputs q, g1 , h1 , the DL-extractor E proceeds as follows.
1◦ E starts the adversary A1 with inputs q, g1 , h1 . When A1
makes a query , E computes$

AdvE = Pr[ x̂ = x] ≥ Pr[Imp ∧ Ext]
≥ Pr[Imp] − Pr[¬Ext ∧ Imp].
So,
Pr[Imp] ≤ AdvE + Pr[¬Ext ∧ Imp].
By the definition of Ext and Imp,a ← Zq ; g2 = ga1m∗$m , r ← Zq

r

 a
c1 = gm
1 h1 ; c2 = c1

Pr[¬Ext ∧ Imp] ≤ Pr[c∗2 = c∗1 a ∧c∗1  g1 0 ] ≤ AdvH . (4)and answers A1 with a transcript (g2 , (c1 , c2 ), r , m ).
Note the simulated transcript is distributed just as thereal one between an honest P and V. Suppose A1 halts
and outputs a string St.
2◦ E starts the adversary A2 with the input St and with random coins R. E randomly selects a from Zq , computes
g2 = ga1 , and gives g2 to A2 . Suppose A2 replies with themessage c∗1 , c∗2 . If c∗1 a  c∗2 , then E aborts. Otherwise
E randomly selects r from Zq and sends r to A2 . Then,∗r
A2 is supposed to output m∗ and halt. If c∗1  gm
1 h1 , E
aborts. Note the messages given to A2 are distributed justas the real ones given by an honest V.
3◦ Consider the following KEA1 adversary H on inputs (ofthe above) q, g1 , g2 and w = St, R:
KEA1 adversary H(q, g1 , g2 , (St, R)):
Invoke A2 (St; R);
Give g2 to A2 ;Get c∗1 , c∗2 from A2 ;Output c∗1 , c∗2 .
E invokes the corresponding extractor H ∗ to H on thesame inputs and gets m∗0 :m∗0 ← H ∗ (q, g1 , g2 , (St, R));
4◦ E outputs x̂ = (m∗0 − m∗ )r−1 .
In the above, note that the extractor E opens the commitment c∗1 made by the adversary A2 in the two diﬀerent
ways: the one is m∗0 obtained by the KEA1-extractor H ∗ andthe other is m∗ through the simulated transcript.
Now we evaluate the advantage AdvE = Pr[ x̂ = x] of
the DL extractor E. Let Imp be an event that A2 successfully
impersonates P in the above simulation by E and Ext be anm∗event the equation c∗1 = g1 0 does hold. Note that Pr[Imp] ≥ and if Imp holds, we have∗rc∗2 = c∗1 a , c∗1 = gm
1 h1 .

(1)

If Ext holds, we havem∗c∗1 = g1 0 .

(3)

(2)

Now since the running time of H is bounded by therunning time of A2 , it is not greater than t . So, by the assumption of G being (t ,   )-KEA1, we have
AdvH <   .

(5)

Then, by Eqs. (3), (4) and (5), we have ≤ Pr[Imp] ≤ AdvE +   ,andAdvE ≥  −   .
Here, as easily seen from the description of E, the running time time(E) of E includes the running time of A, therunning time of H (which is less than the one of A) andis otherwise dominated by the four exponentiations and thetwo two-exponent multi-exponentiations. Assuming (as in[8]) that a two-exponent multi-exponentiation takes time
1.2texp , we have time(E) ≤ 2 · t + (4 + 2.4)texp ≤ t , as desired.

4.2 Security under the Concurrent Attack
Under the OMDL+ and KEA1 assumptions, IDKEA1 isproven to be secure even under the concurrent attack alsowith tight reduction.
Theorem 2 If the generator G is both (t , n + 1,   )-OMDL+
and (t ,   )-KEA1, then the IDKEA1 scheme ID with thegenerator G is (t, n, )-secure under the concurrent attack
with


1 

t ≤ Min (t − (4.2 + n)texp ), t2 ≥  + .
Proof Assume we have an adversary A = (A1 , A2 ) against
ID = {K, P, V} in the concurrent attack, running in timeat most t and making interactions with at most n proverclones, which succeeds in impersonating the honest proverIEICE TRANS. FUNDAMENTALS, VOL.E90–A, NO.9 SEPTEMBER 2007

1954

P with probability at least . We use A to construct a KEAadversary H running in time at most t and we use A and H
to construct an OMDL+ solver I that runs in time at most t ,making at most n + 1 queries to the challenge oracle, withthe advantage AdvI at least  −   (≥   ). The stated result
follows.
Let q, g1 be generated bythat A2 successfully impersonates P in the above simulationm∗by I and Ext be an event the equation c∗1 = g1 0 does hold.
Note that Pr[Imp] ≥  and if Imp holds, we have∗rc∗2 = c∗1 a , c∗1 = gm
1 h1 .

If Ext holds, we havem∗c∗1 = g1 0 .

q, g1 ← G(k).
On inputs q, g1 , the OMDL+ solver I proceeds as follows.

1 I randomly chooses a from Zq and computes g2 = ga1 . I
sends g2 to the challenge oracle COg1 to get the responseh1 (= g1x0 ), h2 (= g2 x0 ). I starts the adversary A1 with inputs q, g1 , h1 .
2◦ When A1 sends the message g∗2 (i) to some prover clone(in the i-th session), I forwards the message g∗2 (i) tothe challenge oracle COg1 and get the response c1(i) (=x
g1xi ), c2(i) (= g∗2 (i) i ). I delivers c1(i) , c2(i) to A1 . When A1
∗(i)

◦

(6)

By the second equation of Eq. (6) and Eq. (7), we see
x0 = (m∗0 − m∗ )r−1 = xˆ0 ,

sends the response r to the prover clone, I makes a∗(i)to the DL oracle DLg1 and gets the requery c1(i) h−r
1(i)sponse m , which is transferred to A1 by I. Suppose
A1 halts and outputs a string St after performing concurrently such n sessions (i = 1, . . . , n) with the simulated
prover clones. It is easy to see that the above simulationof prover clones for A1 is perfect.
3◦ I starts the adversary A2 with the input St and with random coins R. I randomly selects a from Zq , computes
g2 = ga1 , and gives g2 to A2 . Suppose A2 replies withthe message c∗1 , c∗2 . If c∗1 a  c∗2 , then I aborts. Otherwise
I randomly selects r from Zq and sends r to A2 . Then,∗r
A2 is supposed to output m∗ and halt. If c∗1  gm
1 h1 , I
aborts. Note the above simulation of the honest verifieris perfect for A2 .
4◦ Consider the following KEA1 adversary H on inputs (ofthe above) q, g1 , g2 and w = St, R:
KEA1 adversary H(q, g1 , g2 , (St, R)):
Invoke A2 (St; R);
Give g2 to A2 ;Get c∗1 , c∗2 from A2 ;Output c∗1 , c∗2 .
I invokes the corresponding extractor H ∗ to H on thesame inputs and gets m∗0 :m∗0 ← H ∗ (q, g1 , g2 , (St, R));
5◦ I outputs xˆ0 = (m∗0 − m∗ )r−1 and x̂i = m(i) + xˆ0 r∗(i) fori = 1, . . . , n.

In the above, note that the solver I opens the commitment c∗1 made by the adversary A2 in the two diﬀerent ways:
the one is m∗0 obtained by the KEA1-extractor H ∗ and theother is m∗ through the simulated transcript.
Now we evaluate the advantage AdvI = Pr[ x̂i = xi (i =0, 1, . . . , n)] of the OMDL+ solver I. Let Imp be an event

(7)

∗(i)

, we haveand since g1 m = c1(i) h−r
1
(i)

(i)
∗(i)
xi = DLg1 (c(i)= x̂i .
1 ) = m + x0 r

Thus,
AdvI = Pr[ x̂i = xi (i = 0, 1, . . . , n)]≥ Pr[Imp ∧ Ext]
≥ Pr[Imp] − Pr[¬Ext ∧ Imp]So,
Pr[Imp] ≤ AdvI + Pr[¬Ext ∧ Imp].

(8)

By the definition of Ext and Imp,m∗

Pr[¬Ext ∧ Imp] ≤ Pr[c∗2 = c∗1 a ∧c∗1  g1 0 ] ≤ AdvH . (9)Now since the running time of H is bounded by therunning time of A2 , it is not greater than t . So, by the assumption of G being (t ,   )-KEA1, we have
AdvH <   .

(10)Then, by Eqs. (8), (9) and (10), we have ≤ Pr[Imp] ≤ AdvI +   ,andAdvI ≥  −   .
Here, as easily seen from the description of I, the number of queries made by I to the challenge oracle is at mostn + 1 (one in generating the simulated public key and n
in generating the commitments for A1 ). The running timetime(I) of I includes the running time of A, the running
time of H (which is less than the one of A) and is otherwise dominated by the (3+n) exponentiations and the one
two-exponent multi-exponentiation. Assuming (as in [8])that a two-exponent multi-exponentiation takes time 1.2texp ,
we have time(I) ≤ 2 · t + (4.2 + n)texp ≤ t , as desired.

ARITA and KAWASHIMA: AN IDENTIFICATION SCHEME WITH TIGHT REDUCTION

1955

5.

Natsumi Kawashimareceived her B.E.
from Hosei University in 2004 and M.E. from
Institute of Information Security in 2007.

Conclusion

The paper has shown an identification scheme IDKEA1
which is an enhanced version of the Schnorr scheme bymaking the prover’s commitment extractable. Although it
needs four exchanges of messages and slightly more exponentiations than the Schnorr scheme, IDKEA1 is proved
to be secure under the KEA1 and DLA assumptions withtight reduction. Moreover, using the variant OMDL+ of the
OMDL assumption, we proved IDKEA1 is secure even under the concurrent attack also with tight reduction.
References[1] B. Barak, “How to go beyond the black-box simulation barrier,”
Proc. 42nd FOCS, pp.106–115, IEEE, 2001.
[2] B. Barak and Y. Lindell, “Strict polynomial-time in simulation andextraction,” Proc. 34th Annual Symposium on Theory of Computing, ACM, pp.484–493, 2002.
[3] M. Bellare and A. Palacio, “GQ and Schnorr identification schemes:
Proofs of security against impersonation under active and concurrent
attacks,” Proc. Crypto 2002, LNCS 2442, pp.162–177, 2002.
[4] M. Bellare and A. Palacio, “The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols,” Proc. Crypto 2004,
LNCS 3152, pp.273–289, 2004.
[5] R. Cramer and I. Damgard, “Secure signature schemes based on interactive protocols,” CRYPTO 1995, pp.297–310, 1995.
[6] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions
to identification and signature problems,” Proc. Crypto’86, LNCS
263, pp.171–185, 1986.
[7] M. Fischlin, “Communication-eﬃcient non-interactive proofs ofknowledge with online extractors,” CRYPTO 2005, pp.152–168,
2005.
[8] E.-J. Goh and S. Jarecki, “A signature scheme as secure as the DiﬃeHellman problem,” EUROCRYPT 2003, pp.401–415, 2003.
[9] L. Guillou and J.J. Quisquater, “A “paradoxical” identity-based signature scheme resulting from zero-knowledge,” Proc. Crypto’88,
LNCS 403, pp.216–231, 1988.
[10] S. Hada and T. Tanaka, “On the existence of 3-round zeroknowledge protocols,” Proc. Crypto’98, LNCS 1462, pp.408–423,
1998.
[11] C.P. Schnorr, “Eﬃcient signature generation by smart cards,” J.
Cryptol., vol.4, no.3, pp.161–174, 1991.

Seiko Arita
received his B.E. and M.E.
from Kyoto University, and Ph.D. from Chuo
Universesity in 2000. He has been interested inprime numbers, algebraic curves and cryptography. He is with Institute of Information Security,
Kanagawa, Japan. He is a member of JMS.