Identification Schemes of Proofs of Ability Secureagainst Concurrent Man-in-the-Middle Attacks
Hiroaki Anada and Seiko Arita
Institute of Information Security, Yokohama, Japanhiroaki.anada@gmail.com, arita@iisec.ac.jp

Abstract. We give a series of three identification schemes. All of them
are basically 2-round interactive proofs of ability to complete DiﬃeHellman tuples. Despite their simple protocols, the second and the thirdschemes are proven secure against concurrent man-in-the-middle attacks
based on tight reduction to the Gap Computational Diﬃe-Hellman Assumption without the random oracle. In addition, they are more eﬃcientthan challenge-and-response 2-round identification schemes from previously known EUF-CMA signature schemes in the standard model.
Our first scheme is similar to half the operation of Diﬃe-Hellman
Key-Exchange. The first scheme is secure only against two-phase attacks based on strong assumptions. Applying the tag framework, andemploying a strong one-time signature for the third scheme, we get thepreferable schemes above.
Keywords: Identification Scheme, Concurrent Man-in-the-Middle Attack, the Gap Computational Diﬃe-Hellman Assumption, tight reduction

1

Introduction

An identification (ID) scheme enables a prover to convince a verifier thatthe prover is certainly itself by proving possession of some secret identifying information. In public key framework the prover holds a secret key
and the verifier refers to a matching public key. They interact for somerounds doing necessary computations until the verifier feels certain.
Most of ID schemes, such as the Guillou-Quisquater scheme [14] andthe Schnorr scheme [21], are proofs of knowledge which belong to a classcalled Σ-protocols [8]. A Σ-protocol consists of 3-round interaction andsatisfies the special soundness property. By the property it is possible toextract witness of the prover via its adversary (the Reset Lemma [5]).
But when we depend on the property we must give up tight reduction tocomputational hardness assumptions in its security proofs.
As for attacks on ID schemes, if someone malicious can impersonate
a prover then the ID scheme collapses. So the prime requirement for ID

schemes is robustness against impersonation by adversaries who attack
various cheating ways. Among attacks a concurrent man-in-the-middle
attack is one of the strongest threat. In concurrent man-in-the-middle
composition, while trying to impersonate a prover, an adversary may
interacts with prover clones in arbitrarily interleaved order of messages.
1.1

Our Contribution

This paper addresses to the problem to construct ID schemes secureagainst concurrent man-in-the-middle attacks. Unlike the known schemes,
our principle is neither Σ-protocols nor proofs of knowledge, but are
proofs of ability ([13]) to complete Diﬃe-Hellman tuples.
The first scheme is like half the operation of Diﬃe-Hellman KeyExchange and consists of 2-round interaction. Three exponentiations andone multiplication are build into the first scheme along the idea for the
tag-based encryption scheme of Kiltz [17]. A string “tag” is assumed to
be given to a prover and a verifier by the first round. To leave the tag
framework, the CHK transformation [9] is applied to the second scheme;a strong one-time signature is build in to get the third scheme. The second and the third schemes are proven secure against concurrent man-inthe-middle attacks based on tight reduction to the Gap ComputationalDiﬃe-Hellman (Gap-CDH) Assumption in the standard model.
As for eﬃciency, our schemes need less computational amount thanthat of EUF-CMA signature schemes in the standard model. More precisely, using EUF-CMA signature schemes or IND-CCA encryption schemes,
we can construct challenge-and-response 2-round ID schemes secure against
concurrent man-in-the-middle attacks ([3]). However, note that known efficient such schemes are proven secure only in the random oracle model,or, in the standard model, they need heavy exponentiations or pairing
computations under some artificial number theoretic assumptions, suchas the Strong Diﬃe-Hellman (SDH) Assumption ([2, 24, 18]).
Though each technique is already known, the second and the thirdschemes are so secure and eﬃcient that we establish them in this paper.
1.2

Related Works

Our first, prototype scheme is similar to the scheme of Stinson and Wu[22, 23]. They proved it secure in the random oracle model under the
CDH and the Knowledge-of-Exponent Assumption (KEA) [11]. Unlike
theirs, we provide a security proof in the standard model. Although the2assumptions utilized, the KEA and the Gap Discrete Logarithm (GapDL) Assumption, are fairly strong, we stress that the first scheme is a
steppingstone towards the second and the third schemes.
Concerning man-in-the-middle attacks, Katz [15] constructed a nonmalleable proof of knowledge. It is basically a Σ protocol. It utilizes theso-called OR-Proof technique and is rather complicated.
Gennaro [12] constructed a concurrently non-malleable proof of knowledge. It is also a Σ protocol. The security proof is based on “strong-type”
assumption (the SDH or the Strong RSA).
Concerning tight reduction to computational hardness assumptions,
Arita and Kawashima [1] proposed an ID scheme whose security proof
is based on tight reduction to the One More Discrete Log (OMDL) [5]type assumption and the KEA. Here the KEA is considered a strong
assumption and our first scheme also depends on the KEA. But our second
and third schemes succeed in leaving the KEA.
1.3

Organization of This Paper

In the next section we fix some notations. We briefly review the modelof attacks on ID schemes, then we describe computational hardness assumptions. In Section 3 we discuss the first, prototype ID scheme. Our
main results, the second and the third schemes and their security, arepresented in Section 4 and 5, respectively. In Section 6 we conclude our
work.

2

Preliminaries

The empty string is denoted ϕ. The security parameter is denoted k.
On input 1k a group parameter generater Grp runs and outputs (q, g),where q is a prime of bit length k and g is a base element of order q ina multiplicative cyclic group Gq . Gq is a general cyclic group of order qthroughout this paper. The ring of exponent domain of Gq , which consistsof integers from 0 to q − 1 with modulo q operation, is denoted Zq .
When an algorithm A on input a outputs z we denote it as z ← A(a).
When A on input a and B on input b interact and B outputs z we denote itas ⟨A(a), B(b)⟩ = z. When A does oracle-access to an oracle O we denote
it as AO . When A does concurrent oracle-access to n oracles O1 , . . . , On wedenote it as AO1 |···|On . Here concurrent means that A accesses to oracles
in arbitrarily interleaved order of messages.
A probability of an event X is denoted Pr[X]. A probability of an event
X on conditions Y1 , . . . , Ym is denoted Pr[Y1 ; · · · ; Ym : X].
3

2.1

ID Schemes

An ID scheme ID is a triple of probabilistic polynomial time (PPT) algorithms (K, P, V). K is a key generater which outputs a pair of a public
key and a matching secret key (pk, sk) on input 1k . P and V implement a
prover and a verifier, recpectively. We require ID to satisfy the completeness condition that boolean decision output by V(pk) after interaction
with P(sk) is one with probability one. We say that V(pk) accepts if its
boolean decision is one.

2.2

Attacks on ID Schemes

The aim of an adversary A on an ID scheme ID is impersonation. We saythat A wins when A(pk) succeeds in making V(pk) accept.
Attacks on ID schemes are divided into two kinds. One is passive
and the other is active. We are concentrating on active attacks. Active
attacks are divided into four patterns according to whether they are serial
or concurrent and whether they are two-phase or man-in-the-middle.
Firstly a concurrent attack ([3, 5]) means that an adversary A(pk)interacts with polynomially many clones Pi (sk)s of the prover P(sk) inarbitrarily interleaved order of messages. Here all prover clones Pi (sk)sare given independent random tapes and independent inner states. A
serial attack is a special case that an adversary A(pk) interacts with theprover clone P(sk) arbitrary times, but with only one clone at a time. So
concurrent attacks are stronger than serial attacks.
Secondly a two-phase attack ([3, 5]) means that an adversary A consists of two algorithms (A1 , A2 ). In the first phase, the learning phase, A1starts with input pk, interacts with prover clones Pi (sk)s and outputs its
inner state. In the second phase, the impersonation phase, A2 starts with
input the state, interacts with the verifier V(pk) and tries to make V(pk)accept. On the other hand, a man-in-the-middle attack means that anadversary A starts with input pk, interacts with both Pi (sk)s and V(pk)simultaneously in arbitrarily interleaved order of messages. So man-inthe-middle attacks are stronger than two-phase attacks.
Note that man-in-the-middle adversary A is prohibited from relaying
a transcript of a whole interaction. This is the standard and naturalrule when we consider a man-in-the-middle attack. Denote the set oftranscripts between Pi (sk)s and A(pk) as Π and a transcript between
A(pk) and V(pk) as π, then the rule is described as π ̸∈ Π.
4

We define imp-2pc (impersonation by two-phase concurrent attack)advantage of A = (A1 , A2 ) over ID as;def

P (sk)|···|Pn (sk)Advimp-2pc(k) = Pr[(pk, sk) ← K(1k ); st ← A11
ID,A

(pk)

: ⟨A2 (st), V(pk)⟩ = 1].
We say that ID is secure against two-phase concurrent attacks if, for any
PPT algorithm A, Advimp-2pc(k) is negligible in k.
ID,A
In an analogous way, we define imp-cmim (impersonation by concurrent man-in-the-middle (cmim) attack) advantage of A over ID as;
def

Advimp-cmim(k) = Pr[(pk, sk) ← K(1k )ID,A: ⟨AP1 (sk)|···|Pn (sk) (pk), V(pk)⟩ = 1 ∧ π ̸∈ Π].
We say that an ID is secure against concurrent man-in-the-middle attacks
if, for any PPT algorithm A, Advimp-cmim(k) is negligible in k.
ID,A
2.3

Tag-Based ID Schemes

A tag-based ID scheme TagID works in the same way as an ordinary
scheme ID except that a string tag t is a priori given to P and V by the
first round. An interaction depends on the given tag t.
As for attacks, the selective-tag attack is considered in this paper,
referring to the line of Kiltz [17]. That is, an attack on TagID by anadversary A is modeled in the same way as on ID except that, an adversary
A designates a target tag t∗ firstly, and then A gets a public key pk. A
gives a tag ti (̸= t∗ ) to each Pi (sk) and t∗ to V(pk)
We define selective-tag imp-cmim advantage of A over TagID as;
Advstag-imp-cmim(k) = Pr[(pk, sk) ← K(1k ); t∗ ← A(1k )TagID,Adef: ⟨AP1 (t1 ,sk)|···|Pn (tn ,sk) (pk), V(t∗ , pk)⟩ = 1 ∧ (ti ̸= t∗ , ∀i)].
We say that TagID is secure against selective-tag concurrent man-in-themiddle attacks if, for any PPT algorithm A, Advstag-imp-cmim(k) is negTagID,Aligible in k.
2.4

Computational Hardness Assumptions

We say a solver S, an algorithm, wins when S succeeds in solving acomputational problem instance.
5

The Gap-CDH Assumption A quadruple (g, X, Y, Z) of elements in
Gq is called a Diﬃe-Hellman (DH) tuple if (g, X, Y, Z) is written as(g, g x , g y , g xy ) for some elements x and y ∈ Zq . A CDH problem instanceconsists of (q, g, X = g x , Y = g y ), where the exponents x and y are hidden.
The CDH oracle CDH is an oracle which, queried about a CDH problem
instance (q, g, X, Y ), answers Z = g xy . A DDH problem instance consists of (q, g, X, Y, Z). The DDH oracle DDH is an oracle which, queried
about a DDH problem instance (q, g, X, Y, Z), answers a boolean decision
whether (g, X, Y, Z) is a DH-tuple or not. A CDH problem solver is a PPT
algorithm which, given a random CDH problem instance (q, g, X, Y ) as
input, tries to return Z = g xy . A CDH problem solver S that is allowed
to access DDH arbitrary times is called a Gap-CDH problem solver. We
consider the following experiment.
kExperimentgap-cdh
Grp,S (1 )(q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := g y
If S DDH (q, g, X, Y ) outputs Z = g xy then return WIN else LOSE.
Then we define Gap-CDH advantage of S over Grp as;def

gap-cdh k
Advgap-cdh
Grp,S (k) = Pr[ExperimentGrp,S (1 ) returns WIN].

We say that the Gap-CDH assumption [20] holds when, for any PPT
algorithm S, Advgap-cdh
Grp,S (k) is negligible in k.
The Gap-DL Assumption A discrete log (DL) problem instance consists of (q, g, X = g x ), where the exponent x is hidden. A DL problem
solver is a PPT algorithm which, given a random DL problem instance(q, g, X) as input, tries to return x. A DL problem solver S that is allowed to access CDH arbitrary times is called a Gap-DL problem solver.
We consider the following experiment.
kExperimentgap-dl
Grp,S (1 )(q, g) ← Grp(1k ), x ← Zq , X := g x∗

If S CDH (q, g, X) outputs x∗ and g x = X then return WIN else LOSE.
Then we define Gap-DL advantage of S over Grp as;def

gap-dl k
Advgap-dl
Grp,S (k) = Pr[ExperimentGrp,S (1 ) returns WIN].

6

We say that the Gap-DL assumption holds when, for any PPT algorithm
S, Advgap-dl
Grp,S (k) is negligible in k.
Though the Gap-DL assumption is considered fairly strong, it is believed to hold for a certain class of cyclic groups [19].
The Knowledge-of-Exponent Assumption Bellare and Palacio [6]and Canetti and Dakdouk [7, 10] discussed the Knowledge-of-Exponent
Assumption (KEA) [11]. Informally, the KEA says that, given a randomly
chosen h ∈ Gq as input, a PPT algorithm H can extend (g, h) as a DHtuple (g, h, X, D) only when H knows the exponent x of X = g x . The
formal definition is as follows.
Let H and H′ be any PPT algorithms and W be any distribution. H
and H′ take input of the form (g, h, w). Here g is any fixed base and h isa randomly chosen element in Gq . w is a string in {0, 1}∗ output by W
called an auxiliary input [7, 10]. We consider the following experiment.
kExperimentkea-indaux
Grp,H,H′ (1 )(q, g) ← Grp(1k ), w ← W, a ← Zq , h := g a(X, D) ← H(g, h, w), x′ ← H′ (g, h, w)′

If(X a = D and g x ̸= X) then return WIN else LOSE.
Note that w is independent auxiliary input with respect to h in our experiment above. This independency is crucial ([7, 10]).
Then we define KEA advantage of H over Grp and H′ as;def

kea-indaux k
Advkea-indaux
Grp,H,H′ (k) = Pr[ExperimentGrp,H,H′ (1 ) returns WIN].

Here an algorithm H′ is called the KEA extractor. We say that the KEA
holds when, for any PPT algorithm H, there exists a PPT algorithm H′
such that for any distribution W Advkea-indaux
Grp,H,H′ (k) is negligible in k.

3

A Prototype ID Scheme Secure against Two-phase
Concurrent Attacks

In this section we construct and discuss a prototype ID scheme IDproto.
3.1

IDproto and Its Security

IDproto consists of a triple (K, P, V) as shown in the Fig.1. On input
1k , a key generator K runs as follows. A group parameter generator Grp
7

outputs (q, g) on input 1k . Then K chooses x ∈ Zq , puts X = g x and sets
pk = (q, g, X) and sk = (q, g, x). Then K returns (pk, sk).
P and V interact as follows. In the first round, V is given pk as input,
chooses a ∈ Zq randomly and computes h = g a . Then V sends h to P. In
the second round, P is given sk as input and receives h as input message,
computes D = hx . Then P sends D to V. Receiving D as input message, V
verifies whether (g, X, h, D) is a DH-tuple. For this sake, V checks whether
D = X a holds. If so, then V returns 1 and if not, then 0.
Key Generation– K: given 1k as input;• (q, g) ← Grp(1k ), x ← Zq , X := g x• pk := (q, g, X), sk := (q, g, x), return (pk, sk)
Interaction– V: given pk as input;• a ← Zq , h := g a , send h to P
– P: given sk as input and receiving h as input message;• D := hx , send D to V
– V: receiving D as input message;• If D = X a then return 1 else return 0
Fig. 1. A Prototype ID Scheme IDproto

Theorem 1 IDproto is secure against two-phase concurrent attacks
under the Gap-DL assumption and the KEA; for any PPT two-phaseconcurrent adversary A = (A1 , A2 ), there exists a PPT Gap-DL problem
solver S which satisfies the following tight reduction;
gap-dlkea-indaux
Advimp-2pc
IDproto,A (k) 6 AdvGrp,S (k) + AdvGrp,H,H′ (k).

3.2

Proof of Theorem 1

Let A = (A1 , A2 ) be as in Theorem 1. Using A as subroutine, we construct
a Gap-DL problem solver S. The construction is illustrated in Fig.2.
S is given q, g, X = g x as a DL problem instance, where x is random
and hidden. S initializes inner state, sets pk = (q, g, X) and invokes A1
on pk.
In the first phase S replies in answer to A1 ’s queries as follows. In
case that A1 sends hi to the i-th prover clone Pi (sk), S queries its CDH
oracle CDH for the answer of a CDH problem instance (q, g, X, hi ) andgets Di . Then S sends Di to A. In case that A1 outputs its inner statest, S stops A1 and invokes A2 on st.
8

In the second phase S replies in answer to A2 ’s query as follows. In
case that A2 queries V(pk) for the first message by an empty string ϕ, S∗
chooses a∗ ∈ Zq randomly and computes h∗ = g a . Then S sends h∗ to
A2 . In case that A2 sends D∗ to V(pk), S verifies whether (g, X, h∗ , D∗ )∗is a DH-tuple. For this sake, S checks whether D∗ = X a holds. If it does
not hold then S returns a random element z ∈ Zq . If it holds then S
invokes the KEA extractor H′ on (g, h∗ , st). Here H′ is the one associatedwith the H below;
H(g, h∗ , st){D∗ ← A2 (st, h∗ ), return(X, D∗ )}.
Note that (g, h∗ , X, D∗ ) is a DH-tuple because (g, X, h∗ , D∗ ) is a DHtuple. Note also that a distribution W is A1 here. An auxiliary input st
output by A1 satisfies independency with respect to h∗ .
When H′ outputs x∗ S checks whether x∗ is the discrete log of X onbase g. If so, S outputs z = x∗ and if not, a random element z ∈ Zq .
It is obvious that S simulates both concurrent Pi (sk)s and V(pk) per∗fectly. Now we evaluate Gap-DL advantage of S. A wins iﬀ X a = D∗ . If∗∗
X a = D∗ then x∗ is output by H′ . If g x = X then S wins. Therefore;∗

Pr[S wins] > Pr[A wins ∧ g x = X]∗

= Pr[A wins] − Pr[A wins ∧ g x ̸= X].
SoThat is;3.3∗∗

Pr[S wins] > Pr[A wins] − Pr[X a = D∗ ∧ g x ̸= X].
imp-2pc
kea-indaux
Advgap-dl
Grp,S (k) > AdvIDproto,A (k) − AdvGrp,H,H′ (k). (Q.E.D.)

Discussion

Though the Gap-DL and the KEA are fairly strong assumptions, the factthat IDproto is proven secure against two-phase concurrent attacks israther surprising, because it is obvious that IDproto is insecure underman-in-the-middle attacks. To see it just recall the typical man-in-themiddle attack on Diﬃe-Hellman Key-Exchange.
Analogous phenomenon also occurs, for example, for the Schnorr ID
scheme [5]. It seems that the security against two-phase concurrent attacks is somewhat artificial. In Section 4 and Section 5 we modify IDproto
to strengthen its security up to (concurrent) man-in-the-middle level.

4

A Tag-Based ID Scheme Secure against CMIM Attacks

In this section we construct an ID scheme TagIDcmim. Referring to theidea of the tag-based encryption scheme of Kiltz [17], we apply the tag
framework to IDproto to get TagIDcmim.
9Given (q, g, X) as input;
Initial Setting– Initialize inner state, pk := (q, g, X), invoke A1 on pk
The First phase : Answering A1 ’s Queries– In case that A1 sends hi to Pi (sk);• Di ← CDH(g, X, hi ), send Di to A1– In case that A1 outputs its inner state st;• Stop A1 , invoke A2 on st
The Second phase : Answering A2 ’s Query– In case that A2 queries V(pk) for the first message;∗• a∗ ← Zq , h∗ := g a , send h∗ to A2– In case that A2 sends D∗ to V(pk);∗• If X a ̸= D∗ then return random element z ∈ Zq
• else invoke H′ on (g, h∗ , st) and get x∗ from H′∗
If g x = X then return z := x∗else return random element z ∈ Zq
Fig. 2. A Gap-DL Problem Solver S for the Proof of Theorem 1

4.1

TagIDcmim and Its Security

TagIDcmim consists of a triple (K, P, V). The construction is as shown in
the Fig.3. A string tag t is a priori given to P and V by the first round.
In our composition we set t in Zq .
On input 1k , a key generator K runs as follows. A group parameter
generator Grp outputs (q, g) on input 1k . Then K chooses x, y ∈ Zq , puts
X = g x and Y = g y , and sets pk = (q, g, X, Y ) and sk = (q, g, x, y). Then
K returns (pk, sk).
P and V interact as follows. In the first round, V is given pk as input. V
chooses a ∈ Zq randomly and computes h = g a and d = (X t Y )a . Then V
sends (h, d) to P. In the second round, P is given sk as input and receives(h, d) as input message. P verifies whether (g, X t Y, h, d) is a DH-tuple.
For this sake, P checks whether htx+y = d holds. If it does not hold thenP puts D =⊥. Otherwise P computes D = hx . Then P sends D to V.
Receiving D as input message, V verifies whether (g, X, h, D) is a DHtuple. For this sake, V checks whether X a = D holds. If so, then V returns
1 and if not, then 0.
Theorem 2 TagIDcmim is secure against selectiev-tag concurrent manin-the-middle attacks under the Gap-CDH assumption; for any PPT selectievtag concurrent man-in-the-middle adversary A there exists a PPT GapCDH problem solver S which satisfies the following tight reduction;
gap-cdh
Advstag-imp-cmim
TagIDcmim,A (k) 6 AdvGrp,S (k).

10Tag-Receiving– P and V receive a tag t ∈ Zq by the first round
Key Generation– K: given 1k as input;• (q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := g y• pk := (q, g, X, Y ), sk := (q, g, x, y), return (pk, sk)
Interaction– V: given pk as input;• a ← Zq , h := g a , d := (X t Y )a , send (h, d) to P
– P: given sk as input and receiving (h, d) as input message;• If htx+y ̸= d then D :=⊥ else D := hx , send D to V
– V: receiving D as input message;• If X a = D then return 1 else return 0
Fig. 3. A Tag-Based ID Scheme TagIDcmim

4.2

Proof of Theorem 2

Let A be as in Theorem 2. Using A as subroutine, we construct a GapCDH problem solver S. The construction is illustrated in Fig.4.
S is given q, g, X1 = g x1 , X2 = g x2 as a CDH problem instance, wherex1 and x2 are random and hidden. S initializes inner state. S invokes A on
input 1k and gets the target tag t∗ from A. S chooses r ∈ Zq randomly.
∗
S puts Y = X1−t g r , sets pk = (q, g, X1 , Y ) and inputs pk into A. Notethat S knows neither x1 nor y, where y is the discrete log of Y ;y = logg (Y ) = −t∗ x1 + r.
S replies in answer to A’s queries as follows.
In case that A queries V(pk) for the first message by ϕ, S chooses∗∗a ∈ Zq randomly and S puts h∗ = X2 g a and d∗ = (h∗ )r . Then S sends(h∗ , d∗ ) to A (Call this case SIM-V).
In case that A gives a tag ti and sends (hi , di ) to the i-th prover clone
Pi (sk), S verifies whether (g, X1ti Y, hi , di ) is a DH-tuple. For this sake,
S queries its DDH oracle DDH for the answer. If it is not satisfied then∗S puts Di =⊥. Otherwise S puts Di = (di /hri )1/(ti −t ) (Call this case
SIM-P). S sends Di to A. Note that, in the selective-tag framework, A is
prohibited from using t∗ as ti (i.e. t∗ ̸= ti for any i).
In case that A outputs D∗ to V(pk), S verifies whether (g, X1 , h∗ , D∗ )is a DH-tuple. For this sake, S queries DDH for the answer. If so, then∗S returns Z = D∗ /X1a and if not, S returns random element Z ∈ Gq .
In the case SIM-V, S simulates V(pk) perfectly. This is because the
distribution of (h∗ , d∗ ) is equal to that of (h, d). To see it, note that (h∗ , d∗ )11corresponds to (h, d) when x2 + a∗ is substituted for a;
∗

∗

∗

∗

∗

h∗ = g x2 +a , d∗ = (g x2 +a )r = (g r )x2 +a = (X1t Y )x2 +a .
In the case SIM-P, S simulates concurrent Pi (sk)s perfectly. This isbecause Di is equal to hxi 1 by the following equalities;(t −t∗ )x1 +(t∗ x1 +y−r)

di /hri = hiti x1 +y−r = hi i(t −t∗ )x1= hi i.

As a whole S simulates both V(pk) and Pi (sk)s perfectly. Now weevaluate Gap-CDH advantage of S. When A wins (g, X1 , h∗ , D∗ ) is a
DH-tuple and the followings hold;∗∗D∗ = (g x1 )x2 +a = g x1 x2 X1a .
So S wins because its output Z is g x1 x2 . Therefore the probability that
S wins is lower bounded by the probability that A wins;
Pr[S wins] > Pr[A wins].
That is;stag-imp-cmim
Advgap-cdh
Grp,S (k) > AdvTagIDcmim,A (k). (Q.E.D.)

Given (q, g, X1 , X2 ) as input;
Initial Setting– Initialize inner state, invoke A on input 1k , get the target tag t∗ from A∗– r ← Zq , Y := X1−t g r , pk := (q, g, X1 , Y ), input pk into A
Answering A’s Queries– In case that A queries V(pk) for the first message (the case SIM-V);∗• a∗ ← Zq , h∗ := X2 g a , d∗ := (h∗ )r , send (h∗ , d∗ ) to A
– In case that A gives ti and sends (hi , di ) to Pi (sk);• If DDH(g, X1ti Y, hi , di ) ̸= 1 then Di :=⊥∗• else Di := (di /hri )1/(ti −t ) (the case SIM-P)• Send Di to A
– In case that A sends D∗ to V(pk);∗• If DDH(g, X1 , h∗ , D∗ ) = 1 then return Z := D∗ /X1a
• else return random element Z ∈ Gq
Fig. 4. A Gap-CDH Problem Solver S for the Proof of Theorem 2

4.3

Discussion

By virtue of the tag framework, the solver S can simulate concurrent
prover clones (Pi (sk)s) perfectly in the interaction with a selective-tag
adversary A. Moreover, S embeds a portion of CDH problem instance(X2 ) simulating a verifier (V(pk)) perfectly, and succeeds in extracting∗
the answer (X1a times g x1 x2 ).
12

5An ID Scheme Secure against CMIM Attacks

In this section we construct an ID scheme IDcmim. We apply the CHKtransformation [9] to TagIDcmim. That is, to leave the tag framework, we
add a one-time signature OTS to TagIDcmim and replace the tag t by averification key vk.

5.1

IDcmim and Its Security

IDcmim consists of a triple (K, P, V). IDcmim employs a strong one-time
signature OTS = (SGK, Sign, Vrfy) such that the verification key vk is in
Zq . The definition and security of strong one-time signatures is noted inAppendix A.
The construction is as shown in the Fig.5. On input 1k a key generator
K runs as follows. A group parameter generator Grp outputs (q, g) on
input 1k . Then K chooses x, y ∈ Zq , puts X = g x and Y = g y , and sets
pk = (q, g, X, Y ) and sk = (q, g, x, y). Then K returns (pk, sk).
P and V interact as follows. In the first round, V is given pk as input.
V runs signing key generator SGK on input 1k to get (vk, sgk). V choosesa ∈ Zq randomly and computes h = g a and d = (X vk Y )a . V runs Signsgk
on message (h, d) to get a signature σ. Then V sends vk, (h, d), σ to P. In
the second round, P is given sk as input and receives vk, (h, d), σ as input
message. P verifies whether the signature σ for the message (h, d) is valid
under vk and whether (g, X vk Y, h, d) is a DH-tuple. For the latter sake,
P checks whether h(vk)x+y = d holds. If at least one of them does nothold then P puts D =⊥. Otherwise P computes D = hx . Then P sends
D to V. Receiving D as input message, V verifies whether (g, X, h, D) isa DH-tuple. For this sake, V checks whether X a = D holds. If so, then V
returns 1 and if not, then 0.
Theorem 3 IDcmim is secure against concurrent man-in-the-middle attacks under the Gap-CDH assumption and the one-time security in thestrong sence of OTS; for any PPT concurrent man-in-the-middle adversary A there exist a PPT Gap-CDH problem solver S and a PPT forger
F on OTS which satisfies the following tight reduction;
gap-cdhef-cmaAdvimp-cmim
IDcmim,A (k) 6 AdvGrp,S (k) + AdvOTS,F (k).

The detailed proof of Theorem 3 is provided in Appendix B.
13

Key Generation– K: given 1k as input;• (q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := g y• pk := (q, g, X, Y ), sk := (q, g, x, y), return (pk, sk)
Interaction– V: given pk as input;• (vk, sgk) ← SGK(1k ), a ← Zq , h := g a , d := (X vk Y )a , σ ← Signsgk ((h, d))• Send vk, (h, d), σ to P
– P: given sk as input and receiving vk, (h, d), σ as input message;• If Vrfyvk ((h, d), σ) ̸= 1 or h(vk)x+y ̸= d then D :=⊥ else D := hx• Send D to V
– V: receiving D as input message;• If X a = D then return 1 else return 0
Fig. 5. An ID Scheme IDcmim

6

Conclusion

We have presented three ID schemes which are basically proofs of ability
to complete Diﬃe-Hellman tuples. By virtue of the tag framework, simulation went well in the security reduction for Theorem 2. At the sametime, embed-and-extract technique worked for CDH problem instance. As
a result, the second scheme got security against selective-tag concurrent
man-in-the-middle attacks based on tight reduction to the Gap-CDH Assumption. Applying the CHK transformation to the second scheme, We
left the tag-framework to get the third scheme.

Acknowledgement
We appreciate thoughtful comments oﬀered by the anonymous reviewers.

References
1. Arita, S., Kawashima, N.: An Identification Scheme with Tight Reduction. IEICE
Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E90-A, issue 9, pp. 1949-1955 (2007)
2. Boneh, D., Boyen, X.: Short Signatures without Random Oracles. In: EUROCRYPT 2004, LNCS, vol. 3027, pp. 56-73. Springer, Heidelberg (2004)
3. Bellare, M., Fischlin, M., Goldwasser, S., Micali, S.: Identification Protocols Secureagainst Reset Attacks. In: EUROCRYPT 2001, LNCS, vol. 2045, pp. 495-511.
Springer, Heidelberg (2001)
4. Bleichenbacher, D., Maurer U.: On the Eﬃciency of One-time Digital Signatures.
In: ASIACRYPT 1996, LNCS, vol. 1163, pp. 196-209. Springer, Heidelberg (1996)
5. Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security
against Impersonation under Active and Concurrent Attacks. In: CRYPTO 2002,
LNCS, vol. 2442, pp. 162-177. Springer, Heidelberg (2002)

14

6. Bellare, M., Palacio, A.: The Knowledge-of-Exponent Assumptions and 3-Round
Zero-Knowledge Protocols. In: CRYPTO 2004, LNCS, vol. 3152, pp. 273-289.
Springer, Heidelberg (2004)
7. Canetti, R., Dakdouk, R. R.: Extractable Perfectly One-way Functions. In: ICALP
2008, LNCS, vol. 5126, pp. 449-460. Springer, Heidelberg (2008)
8. Crame, R., Damgård, I., Nielsen, J.B.: Multiparty Computation from Threshold
Homomorphic Encryption. In: EUROCRYPT 2001, LNCS, vol. 2045, pp. 280-300.
Springer, Heidelberg (2001)
9. Canetti, R., Halevi, S., Katz, J.: Chosen-Ciphertext Security from Identity-Based
Encryption. In: EUROCRYPT 2004, LNCS, vol. 3027, pp. 207-222. Springer, Heidelberg (2004)
10. Dakdouk, R. R., Theory and Application of Extractable Functions. Doctor of Philosophy Dissertation, Yale University, USA (2009)
11. Damgård, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: CRYPTO 1991, LNCS, vol. 576, pp. 445-456. Springer, Heidelberg(1991)
12. R. Gennaro, Multi-trapdoor Commitments and their Applications to Non-Malleable
Protocols, In: CRYPTO 2004, LNCS, vol. 3152, pp. 220-236. Springer, Heidelberg(2004)
13. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University
Press (2001)
14. Guillou, L., Quisquater, J. J.: A Paradoxical Identity-Based Signature Scheme
Resulting from Zero-Knowledge. In: CRYPTO 1988, LNCS, vol. 403, pp. 216-231.
Springer, Heidelberg (1988)
15. Katz, J.: Eﬃcient Cryptographic Protocols Preventing “Man-in-the-Middle” Attacks. Doctor of Philosophy Dissertation, Columbia University, USA (2002)
16. Katz, J.: Eﬃcient and Non-Malleable Proofs of Plaintext Knowledge and Applications. In: EUROCRYPT 2003, LNCS, vol. 2656, pp. 211-228. Springer, Heidelberg(2003)
17. Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: TCC 2006,
LNCS, vol. 3876, pp. 581-600. Springer, Heidelberg (2006)
18. Kurosawa, K., Desmedt, Y.: A New Paradigm of Hybrid Encryption Scheme. In:
CRYPTO 2004, LNCS, vol. 3152, pp. 426-442. Springer, Heidelberg (2004)
19. Maurer, U., Wolf, S.: Lower Bounds on Generic Algorithms in Groups. In: EUROCRYPT 1998, LNCS, vol. 1403, pp. 72-84. Springer, Heidelberg (1998)
20. Okamoto, T., Pointcheval, D.: The Gap-Problems: A New Class of Problems for the
Security of Cryptographic Schemes. In: PKC 2001, LNCS, vol. 1992, pp. 104-118.
Springer, Heidelberg (2001)
21. Schnorr, C. P.: Eﬃcient Signature Generation by Smart Cards. Journal of Cryptology, vol. 4, Num. 3, pp. 161-174 (1991)
22. Stinson, D. R., Wu, J.: An Eﬃcient and Secure Two-flow Zero-Knowledge Identification Protocol. Journal of Mathematical Cryptology, vol. 1, issue 3, pp. 201-220(2007)
23. Wu, J., Stinson, D. R.: An Eﬃcient Identification Protocol and theKnowl-edge-of-Exponent Assumption. Cryptology ePrint Archive, 2007/479,
http://eprint.iacr.org/
24. Waters, B.: Dual System Encryption: Realizing Fully Secure IBE and HIBE under
Simple Assumptions. In: CRYPTO 2009, LNCS, vol. 5677, pp. 619-636. Springer,
Heidelberg (2009)15

A

One-time Signatures

A one-time signature OTS is a triple of PPT algorithms (SGK, Sign, Vrfy).
SGK is a signing key generater which outputs a pair of a verification key
and a matching signing key (vk, sgk) on input 1k . Sign and Vrfy are asigning algorithm and a verification algorithm, respectively. We say that(m, σ) is valid if Vrfyvk (m, σ) outputs one. We require OTS to satisfy
the standard completeness condition. We also require OTS to be existentially unforgeable against chosen message attack (EUF-CMA) by any
PPT forger F. The following experiment is the strong one.
k
Experimentef-cma
OTS,F (1 )(vk, sgk) ← SGK(1k ), m ← F (vk), σ ← Signsgk (m), (m′ , σ ′ ) ← F(vk, (m, σ))
If Vrfyvk (m′ , σ ′ ) = 1 ∧ (m′ , σ ′ ) ̸= (m, σ) then return WIN else LOSE.
Then we define advantage of existential forgery by chosen message attackof F over OTS as;
def

ef-cma k
Advef-cma
OTS,F (k) = Pr[ExperimentOTS,F (1 ) returns WIN].

We say that a OTS is EUF-CMA (or, has one-time security) in the strong
sence when, for any PPT algorithm F, Advef-cma
OTS,F (k) is negligible in k(and then we say that OTS is a strong one-time signature).

B

Proof of Theorem 3

Let A be as in Theorem 3. Using A as subroutine, we construct a GapCDH problem solver S. The construction is illustrated in Fig.6.
S is given q, g, X1 = g x1 , X2 = g x2 as a CDH problem instance,
where x1 and x2 are random and hidden. S initializes inner state. S
gets (vk∗ , sgk∗ ) from SGK(1k ) and chooses r ∈ Zq randomly. S puts∗
Y = X1−vk g r , sets pk = (q, g, X1 , Y ) and invokes A on input pk. Notethat S knows neither x1 nor y, where y is the discrete log of Y ;y = logg (Y ) = −vk∗ x1 + r.
S replies in answer to A’s queries as follows.
In case that A queries V(pk) for the first message by ϕ, S chooses∗∗a ∈ Zq randomly and S puts h∗ = X2 g a and d∗ = (h∗ )r . S gets asignature σ ∗ from Signsgk∗ ((h∗ , d∗ )). Then S sends vk∗ , (h∗ , d∗ ), σ ∗ to A
(Call this case SIM-V).
16

In case that A sends vki , (hi , di ), σi to the i-th prover clone Pi (sk), S
verifies whether ((hi , di ), σi ) is valid under vki and whether (g, X1vki Y, hi , di )is a DH-tuple. For the latter sake, S queries its DDH oracle DDH for theanswer. If at least one of them is not satisfied then S puts Di =⊥. Oth∗erwise, if vki ̸= vk∗ then S puts Di = (di /hri )1/(vki −vk ) (Call this case
SIM-P). If vki = vk∗ , S aborts (Call this case ABORT). S sends Di to A
except the case ABORT.
In case that A outputs D∗ to V(pk), S verifies whether (g, X1 , h∗ , D∗ )is a DH-tuple. For the latter sake, S queries DDH. If so, then S returns∗
Z = D∗ /X1a and if not, S returns random element Z ∈ Gq .
In the case SIM-V, S simulates V(pk) perfectly. This is because the
distribution of (h∗ , d∗ ) is equal to that of (h, d). To see it, note that (h∗ , d∗ )corresponds to (h, d) when x2 + a∗ is substituted for a;
∗

∗

∗

∗

∗

h∗ = g x2 +a , d∗ = (g x2 +a )r = (g r )x2 +a = (X1vk Y )x2 +a .
In the case SIM-P, S simulates concurrent Pi (sk)s perfectly. This isbecause Di is equal to hxi 1 by the following equalities;(vki −vk∗ )x1 +(vk∗ x1 +y−r)

i x1 +y−r
di /hri = hvk= hii(vki −vk∗ )x1

= hi

.

As a whole S simulates both V(pk) and Pi (sk)s perfectly except thecase ABORT. Now we evaluate Gap-CDH advantage of S. When A wins
(g, X1 , h∗ , D∗ ) is a DH-tuple and the followings hold;∗∗D∗ = (g x1 )x2 +a = g x1 x2 X1a .
So S wins because its output Z is g x1 x2 . Therefore the probability that
S wins is lower bounded by the probability that A wins and the case
ABORT does not happen;
Pr[S wins] > Pr[A wins ∧ ¬ABORT]> Pr[A wins] − Pr[ABORT].
imp-cmimThat is; Advgap-cdh
Grp,S (k) > AdvIDcmim,A (k) − Pr[ABORT].

Claim The probability that the case ABORT occurs is negligible in k.
Proof of the Claim Using A as subroutine, we construct a signatureforger F on OTS as follows. Given vk∗ as input, F initializes inner state,chooses x1 , x2 ∈ Zq randomly and puts X1 = g x1 , X2 = g x2 . Similarly to
S, F generates r, Y, pk and invokes A on pk.
17

In case that A queries V(pk) for the first message, F generates a∗ , h∗ , d∗and sends vk∗ , (h∗ , d∗ ), σ ∗ to A in a similar way to S except querying its
signing oracle SIGN sgk∗ for a signature σ ∗ on (h∗ , d∗ ).
In case that A sends vki , (hi , di ), σi to the i-th prover clone Pi (sk), F
verifies whether the signature is valid and whether (g, X1vki Y, hi , di ) is a
DH-tuple. For the latter sake, F checks whether the following holds;(vki −vk∗ )x1 +r

hi= di .

Then, if vki ̸= vk∗ then F sends Di to A in a similar way to S. If vki = vk∗
then S returns ((hi , di ), σi ) and stops (Call this case FORGE).
Note that the view of A in F is the same as the view of A in S. So;
Pr[FORGE] = Pr[ABORT].
Now in the case FORGE the followings hold;vki = vk∗ , ((hi , di ), σi ) ̸= ((h∗ , d∗ ), σ ∗ ).
This is because if ((hi , di ), σi ) were equal to ((h∗ , d∗ ), σ ∗ ) then the transcript of a whole interaction would be relayed by A. This is ruled out.
So in the case FORGE, F succeeds in making up an existential forgery
and we have Advef-cma
OTS,F (k) = Pr[FORGE](= Pr[ABORT]). But the advantage is negligible in k by the assumption in Theorem 3. (Q.E.D.)
Given (q, g, X1 , X2 ) as input;
Initial Setting– Initialize inner state, (vk∗ , sgk∗ ) ← SGK(1k )∗– r ← Zq , Y := X1−vk g r , pk := (q, g, X1 , Y ), invoke A on pk
Answering A’s Queries– In case that A queries V(pk) for the first message (the case SIM-V);∗• a∗ ← Zq , h∗ := X2 g a , d∗ := (h∗ )r , σ ∗ ← Signsgk∗ ((h∗ , d∗ ))∗∗∗∗• Send vk , (h , d ), σ to A
– In case that A sends vki , (hi , di ), σi to Pi (sk);• If Vrfyvki ((hi , di ), σi ) ̸= 1 or DDH(g, X1vki Y, hi , di ) ̸= 1 then Di :=⊥• else∗If vki ̸= vk∗ then Di := (di /hri )1/(vki −vk ) (the case SIM-P)
else abort (the case ABORT)• Send Di to A
– In case that A sends D∗ to V(pk);∗• If DDH(g, X1 , h∗ , D∗ ) = 1 then return Z := D∗ /X1a
• else return random element Z ∈ Gq
Fig. 6. A Gap-CDH Problem Solver S for the Proof of Theorem 3

18