IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011

367

PAPER

An Eﬃcient Adaptive-Deniable-Concurrent Non-malleable
Commitment Scheme
Seiko ARITA†a) , Member

advanced properties all at once for commitment
schemes in the Global CRS-KR model.
• We define, as a more-easy-to-prove property, a straightline equivocal-extractability of commitment schemes
and prove that it (with some other auxiliary properties) yields the adaptive-deniable-concurrent nonmalleability in the Global CRS-KR model.
• We construct a straight-line equivocal-extractable commitment scheme in the Global CRS-KR model, under the decisional linear assumption and the knowledge of exponent assumption on bilinear groups. The
scheme is eﬃcient and practical, using a constant number of pairing computations and three-round exchangesof linear-size messages.

SUMMARY
It is known that composable secure commitments, thatis, concurrent non-malleable commitments exist in the plain model, based
only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, thedeniability of them is trivially satisfied, and especially the latter scheme
satisfies also adaptivity, hence it is adaptive-deniable-concurrent nonmalleable. However, those schemes cannot be said to be practically eﬃcient. We show a practically eﬃcient (string) adaptive-deniable-concurrent
commitment scheme is possible under a global setup model, called the
Global CRS-KR model.
key words: commitment schemes, adaptivity, deniability, concurrency,
non-malleability

1.

Introduction

As the advanced security properties, there are emerging concerns on composability, deniability and adaptivity of cryptographic protocols. The composability, culminating in the
Universal Composability (UC) [4], requires secure protocols
remain secure even if they are composed with other protocols. The deniability requires secure protocols leave no evidence of their executions. The adaptivity requires secure
protocols remain secure (to some reasonable extent) even if
some honest parties are corrupted during their executions.
In this paper, we want to construct practically eﬃcientcommitment protocols with those advanced security properties in some global setup model.
It is known that composable secure commitments∗ , thatis, concurrent non-malleable commitments exist in the plain
model, based only on standard assumptions such as the existence of claw-free permutations [8], [22], [24] or even oneway functions [20], [25]. Since being based on the plain
model, the deniability of them is trivially satisfied, and especially the scheme of [22] satisfies also adaptivity, hence
it is already an adaptive-deniable-concurrent non-malleablecommitment scheme. However, those schemes cannot be
said to be practically eﬃcient.
We show a practically eﬃcient (string) adaptivedeniable-concurrent non-malleable commitment scheme ispossible under a global setup model, called the Global CRSKR model.
• We define a notion of adaptive-deniable-concurrent
non-malleable commitments, that captures the three
Manuscript received March 12, 2010.
Manuscript revised June 21, 2010.
†
The author is with Institute of Information Security,
Yokohama-shi, 221-0835 Japan.
a) E-mail: arita@iisec.ac.jp
DOI: 10.1587/transfun.E94.A.367

Related works. In the literature, to our knowledge, there
exist two practically-eﬃcient commitment schemes that establish the adaptive-deniable-concurrent non-malleability.
One is the commitment scheme by Canetti, Dodis, Pass andWalfish [5] and the another is its improvement by Dodis,
Shoup and Walfish [16]. Both schemes rely on a global
setup model, called the Augmented CRS model (a kind of
global CRS model with an augmented functionality) andare proved to be adaptively UC-secure in that model. The
scheme of [5] uses four-round message exchange of squaresize O(k2 ) of security parameter k, and the scheme of [16]uses six-round message exchange of linear size O(k). We
believe that our Global CRS-KR model is comparable to theAugmented CRS model and our scheme, using three-roundmessage exchange of linear size O(k), is more simple andeﬃcient than those schemes.
2.

An Adaptive-Deniable-Concurrent Non-malleable
Commitment

2.1 Commitment Schemes
In this paper, we deal with commitments in a tag-based manner. On input value v and tag t, sender S commits to v
through a transcript c for receiver R using a CRS σ (Commitment phase). Later, using local output d of the commitment phase, S decommits c to the value v using the same
tag t and CRS σ (Decommitment phase). The hiding property requires even adversarial receivers R∗ cannot know thevalue v under the commitment c in the commitment phase.
∗
From now on, the composability always addresses selfcomposition in this paper.

c 2011 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011368

The binding property requires even adversarial senders S∗
cannot decommit the same commitment c to two diﬀerent
values. More precisely,
Definition 1 (Commitment Schemes) A triple Σ = (K, S,
R) of probabilistic polynomial time algorithms is called a(tag-based) commitment scheme if it satisfies the following
three properties:
Fig. 1The Global CRS-KR model.

Fig. 2The Augmented CRS model.

(Correctness) For any value v ∈ {0, 1}k and any tag, theprobabilityPr[ σ ← K(1k ), (d, c) ← Sσ,tag (v), Rσ,tag ,(−, v ) ← Sσ,tag (d), Rσ,tag (c) : v = v ]is negligibly close to 1 (with respect to k).
(Hiding) For any adversary R∗ and any tag, the probabilityPr[ σ ← K(1k ), (v0 , v1 , s) ← R∗ (σ, tag),$b ← {0, 1}, (−, b ) ← Sσ,tag (vb ), R∗ (s): b = b ]is negligibly close to 1/2 (with respect to k). Here, v0 , v1 aresupposed to be in {0, 1}k .
(Binding) For any adversary S∗ and any tag, the probabilityPr[σ← K(1k ),((d1 , d2 ), c) ← S∗ (σ, tag), Rσ,tag ,(−, v1 ) ← S∗ (d1 ), Rσ,tag (c),(−, v2 ) ← S∗ (d2 ), Rσ,tag (c):v1  ⊥, v2  ⊥, v1  v2 ]is negligible (with respect to k).
For our purpose, we need a new type of binding property, the determining property.
Definition 2 (Determining Property) A commitment scheme Σ = (K, S, R) is said to be determining if there exists
a deterministic function det(·) (that depends only on Σ andmay not be eﬃciently computable) and for any feasible adversary S∗ the probabilityPr[ σ ← K(1k ), (−, c) ← S∗ (σ), Rσ,tag  :∃ d, r s.t. (−, v) = S∗ (d), Rσ,tag (c; r)
⇒ v = det(c) ]is negligibly close to 1 (with respect to k). Here, the tag is
being chosen by S∗ . We call the unique value v = det(c) thedetermining value of c.
In the above definition we note that the d and r are
not supposed to be eﬃciently computable. The determining
property means that any commitment c generated by feasible adversaries S ∗ must statistically determine the value v

that can be committed to under c. If Σ is statistically binding
then it is determining, and if Σ is determining then it is computationally binding† . In the rest of paper, we only consider
commitment schemes that are determining.
2.2 Definition of Adaptive-Deniable-Concurrent Nonmalleability
Intuitively, we call a commitment scheme adaptivedeniable-concurrent non-malleable if the scheme permits nofake commitments even by a man-in-the-middle adversarythat is able to invoke any number of left and right parties
concurrently to receive/make commitments and is able toadaptively corrupt any number of left parties that complete
commitment phases, and in addition if the scheme leaves noevidence of protocol execution.
2.2.1 The Global CRS-KR Model
To achieve the property in an eﬃcient way, we rely on a
global setup model, called the Global CRS-KR model, which
is a simple extension of the KR model of [3]. In the Global
CRS-KR model, as in Fig. 1, parties must register their identities to receive their public keys and a global CRS. Secretkeys are sent only to corrupt participants.
For contrast, here we see the Augmented CRS modelof Canetti, Dodis, Pass and Walfish [5], in Fig. 2.
In the Augmented CRS model, the public value is thesame for all parties. However it needs diﬀerent secret keys
for all corrupt parties, and thus needs a master secret. Meanwhile, in the Global CRS-KR model, although the public†
If a commitment scheme is not computationally binding, thenthe d must be eﬃciently computable by commitment-phase S ∗ anddet(c) must be ambiguous, meaning that the scheme is not determining.

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

369

value depends on parties, it does not need any kind of master secret.
Thus, we cannot say any one is better than the another,
unconditionally. The Augmented CRS model is better in theview of eﬃciency of public values, and the Global CRS-KR
model is better in the cost of needed trust for the third party
that implements the functionality, since the model does notneed any master secret.
Note that, in both of the above two models, an adversary is supposed to corrupt some party, to participate a
protocol-session as an active player. This means that an adversary must register its id and get the secret key of corrupt
party that it plays.
2.2.2 The Definition
We define two experiments, for a commitment scheme Σ andan adversary A, as in Fig. 3, in order to define the adaptivedeniable-concurrent non-malleability of Σ.
Definition 3 A commitment scheme Σ = (K, S, R) is
said to be adaptive-deniable-concurrent non-malleable in
the Global CRS-KR model if for any feasible adversary
A, thereexists a feasible
algorithm S and the ensem
is computationally indistinble staΣS (v1 , · · · , vm , z)v1 ,··· ,vm ,z guishable from the ensemble mimΣA (v1 , · · · , vm , z)v1 ,··· ,vm ,zwith any polynomial m = m(k), any values v1 , · · · , vm (∈{0, 1}k ) and any string z.
Note that Definition 3 incorporates the Global CRS-KR
model. An adversary needs to register its id ID∗ to mountan attack.
Basically, Definition 3 is in the similar line to the definition of concurrent non-malleability of [20], [22], [24]. In
the first experiment mimΣA , a man-in-the-middle adversary A
carries over a concurrent man-in-the-middle attack between
m left parties and n right parties. The resulting A’s viewand the determining values v∗j of right commitments must be
simulated by the stand-alone simulator S in the second experiment staΣS . This means that commitments by left parties
are no use for A to make right commitments, i.e., concurrent
non-malleability.
As seen above, in the second experiment, the simulator
S has to simulate left commitments in the simulated viewof A. After completing such simulated left commitments aswell as real right commitments, the simulator S is given thevalues vi . This models the situation of adaptive corruption ofleft honest parties, where left honest parties are corrupt justafter completing commitments and the committed values are
given to the adversary. Definition 3 requires that the simulator S must be able to adapt decommitment of those simulated left commitments to those newly given values, i.e.,
adaptivity.
Moreover, note that the simulator S is not capable tosimulate the CRS σ in the second experiment. The σ ismerely a given string also for S . This brings us deniability.

Fig. 3

Experiments mimΣA and staΣS .

(Recall that it is the key that the simulator is able to program
CRS in the usual local CRS model. But this violated thedeniability.)Thus, Definition 3 concerns the concurrent nonmalleability, adaptivity and deniability of commitment
schemes, all at once. (Note that we are not defining eachof those three property, separately.)
Remark In the above definition, adversary A is restricted
to be a type of “selective-tag,” namely, A is supposed tochoose left tags t1 , . . . , tn before he knows the CRS and A
must use diﬀerent tags t∗j from ti for his challenges. The
restriction is not restrictive. In fact, a tag-based commitment scheme that is secure for selective-tag-type adversaries
is easily transformed into an ordinal commitment schemewithout tags that is secure for fully adaptive adversaries, byusing a method of the CHK transformation [7], just as in the

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011

370

cases of encryption schemes. (Sender generates a key-pairof strong one-time signature. It uses the verification key asa tag and signs a transcript by the corresponding secret key.)

2.3 Definition of Straight-Line Equivocal-Extractability
As a more-easy-to-prove suﬃcient condition for theadaptive-deniable-concurrent non-malleability, we definestraight-line equivocal-extractability of commitment schemes, that involves only a “classical” (instead of concurrent)
man-in-the-middle adversary. The straight-line equivocalextractability requires that a left party can be adaptively simulated by some feasible algorithm EQV that knows an adversary’s secret key and at the same time the property requiresthat the value committed to by the adversary for a right party
can be extracted by some feasible algorithm EXT that knows
the trapdoor of the global CRS. More formally, we define
two experiments, for a commitment scheme Σ and an adversary A, as in Fig. 4.
Definition 4 A commitment scheme Σ = (K, S, R) is
said to be straight-line equivocal-extractable in the Global
CRS-KR model if there exists a feasible algorithm EQVsuch that for any feasible man-in-the-middle adversary A,
there
exists a feasible algorithm EXT and the ensemblefakeComΣEQV,A,EXT (v, z) is computationally indistinguishv,zable from the ensemble realComΣA (v, z) with any value
v (∈ {0, 1}k ) and any string z.

v,zNote that Definition 4 incorporates the Global CRS-KR
model. An adversary needs to register its id ID∗ to mountan attack.
Remark The definition requires that the algorithm EQV is
independent of adversaries A.
Theorem 1 If a commitment scheme Σ = (K, S, R) is determining, public-coin for R and straight-line equivocalextractable in the Global CRS-KR model, then Σ is adaptivedeniable-concurrent non-malleable in the Global CRS-KR
model.
Proof Idea To prove the theorem, we construct a standalone man-in-the-middle adversary Ai j from an assumed
concurrent adversary A against the scheme, which internallysimulates left parties besides the i-th left party and right parties besides the j-th right party for A. We use the straightline equivocal-extractability for Ai j to upper bound advantage of the assumed A, using a hybrid argument. In doing
that, as one subtle point, we need to eﬃciently construct theview of Ai2 , . . . , Aim given the view of Ai1 , that will be possible since the scheme is public-coin for receiver R.
Proof Let Σ = (K, S, R) be a commitment scheme that isFig. 4

Experiments realComΣA and fakeComΣEQV,A,EXT .

determining, public-coin for R and straight-line equivocalextractable. Let EQV be the algorithm that is guaranteed to exist by the definition of straight-line equivocalextractability for Σ. Let A be arbitrary feasible adversary
against Σ. We can assume A is deterministic without loss ofgenerality (by supposing A’s coins are included in its inputz). We want to construct a simulator S that satisfies
staΣS (v1 , · · · , vm , z) ≡c mimΣA (v1 , · · · , vm , z)

(1)

for any values v1 , · · · , vm (∈ {0, 1}k ) and any string z. We
construct such simulator S as follows:
Simulator S on input of a string z:
1. S invokes A on input z. A outputs ID∗ , t1 , . . . , tm . Then,S also outputs ID∗ , t1 , . . . , tm .
2. S receives a CRS σ and a public/private-key pair
pkID∗ , skID∗ . Giving those σ, pkID∗ , skID∗ to A, S plays
each of m left parties for A by invoking EQV on

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

371

ti , skID∗ , w (Here, w is any string such as 0k ) (i =1, . . . , m). S forwards messages of A to each of n rightparties to its own outside right parties Rσ,t∗j and forwards messages from Rσ,t∗j to A as its j-th right party
messages ( j = 1, . . . , n). Let di be the local output of
EQV(ti , skID∗ , w) (i = 1, . . . , m).
3. On halting A, S outputs its view viewA .
4. Receiving left values vi , S invokes the corresponding
second stage of EQV on di and vi to get its output diand outputs di as its own output (i = 1, . . . , m).
Toward showing Eq. (1) with the above S , we first construct a (classical) man-in-the-middle adversary Ai, j using A
as follows (i = 0, . . . , m − 1, j = 1, . . . , n).
A man-in-the-middle adversary Ai, j on input z, vi+2 , . . . ,vm :1. Ai, j internally invokes A on input z. A outputs
ID∗ , t1 , . . . , tm . Then, Ai, j outputs ID∗ , ti+1 .
2. Receiving a CRS σ and a public/private-key pair
pkID∗ , skID∗ , Ai, j carries over a man-in-the-middle attack against its (outside) left party and right party,
using the internally simulated A that is given thoseσ, pkID∗ , skID∗ .
a. In the attack, Ai, j internally simulates m left parties for A as follows.
i. Ai, j simulates each of the first i left parties
by using the α-th copy of EQV on tα , skID∗ , w(α = 1, . . . , i). (w is any dummy string.)
ii. Ai, j forwards messages from its left party to
A as messages of A’s (i + 1)-th left party, andforwards messages from A to its (i + 1)-th leftparty to its left party.
iii. Ai, j simulates the rest of m − i − 1 left parties
honestly to commit to vβ (β = i + 2, . . . , m).
b. At the same time Ai, j internally simulates n rightparties for A as follows.
i. Ai, j honestly simulates each of n right parties
except the j-th right party for A.
ii. Ai, j forwards messages from its right party
to A as messages of A’s j-th right party, andforwards messages from A to A’s j-th rightparty to its right party.
Using the above Ai, j , we define hybrid experiments

hyb-iΣA (v1 , . . . , vm , z) for i = 0, 1, . . . , m as in Fig. 5. In theexperiments, when i = m, all of the left parties are simulatedby EQV and hyb-mΣA is exactly distributed as staΣS :hyb-mΣA (v1 , . . . , vm , z) ≡ staΣS (v1 , · · · , vm , z).

(2)

On the other hand, when i = 0, all of the left parties arehonestly simulated to commit to vi . Moreover the straightline equivocal-extractability of Σ means that det(c∗j ) =EXT(i, j) (τ, viewAi, j ) (with exception of negligible probability). Hence, we have

Fig. 5Hybrid Experiments hyb-iΣA .

hyb-0ΣA (v1 , . . . , vm , z) ≡ s mimΣA (v1 , · · · , vm , z).

(3)

By Eqs. (2) and (3), Eq. (1) follows from the next claim
by a standard hybrid argument.
Claim 1 For i = 0, . . . , m − 1, we have
hyb-iΣA (v1 , . . . , vm , z) ≡c hyb-(i + 1)ΣA (v1 , . . . , vm , z).

Proof We define two auxiliary experiments realΣA andidealΣA . The experiment realΣA (v1 , . . . , vm , z) first constructs
B = Ai,1 . Then, it computes(τ, viewB , v∗1 , di+1 ) ← realComΣB (vi+1 , (z, vi+2 , . . . , vm )),and returns(viewA , v∗1 , . . . , v∗n , d1 , . . . , dn )← Expand(τ, viewB , v∗1 , di+1 , (v1 , . . . , vm )).
The experiment idealΣA is the same as realΣA except that it
uses fakeComΣEQV,B,EXT , instead of realComΣB , to compute(τ, viewB , v∗1 , di+1 ).
In the above, the procedure Expand reconstructs the

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011372

view of Ai, j from the view of B = Ai,1 and extracts valuesv∗j committed to by A in right interactions using EXT withtrapdoor τ. More precisely, Expand proceeds as follows:
Procedure Expand(τ, viewB , v∗1 , di+1 , (v1 , . . . , vm )):1. For j = 2, . . . , n, do:a. Construct Ai, j ’s view viewi, j from viewB . (Recall
B = Ai,1 and Σ is public-coin with respect to receivers.)b. v∗j ← EXT(i, j) (τ, viewi, j ) with the algorithm
EXT(i, j) for Ai, j .
2. For α = 1, . . . , i, i + 2, . . . , m, do:a. Reconstruct from viewB the local output dα of thesimulated α-th left party. (Recall B = Ai,1 internally simulates the α-th left party.)b. dα ← EQV(dα , vα )3. Return (viewA , v∗1 , . . . , v∗n , d1 , . . . , dn )It is easy to see that the view of A (included in viewB ) inrealΣA (v1 , . . . , vm , z) is exactly distributed as viewA in hyb-iΣA .
(In both cases, the first i left parties are simulated by EQV.)
Then, by definition of Expand, we have
hyb-iΣA (v1 , . . . , vm , z) ≡ realΣA (v1 , . . . , vm , z).

(4)

Similarly, we havehyb-(i + 1)ΣA (v1 , . . . , vm , z) ≡ idealΣA (v1 , . . . , vm , z).

(5)

The straight-line equivocal-extractability of Σ against Bmeans that the outputs of realComΣB and fakeComΣEQV,B,EXT
are indistinguishable and then, since Expand is an eﬃcient
procedure, realΣA (v1 , . . . , vm , z) and idealΣA (v1 , . . . , vm , z) areindistinguishable. The claim follows from Eqs. (4) and (5).

Remark We can construct a deniable concurrent zeroknowledge argument if the adaptive-deniable-concurrent
non-malleable commitment scheme once exists, by using
the GMW protocol of graph 3-coloring instantiated with it.
That means• It is diﬃcult (if not impossible) to construct
adaptive-deniable-concurrent non-malleable commitment schemes only using the CRS model, since deniable concurrent zero-knowledge arguments are known
to be diﬃcult in the CRS model [23].
• An eﬃcient construction of adaptive-deniable-concurrent non-malleable commitment scheme in the Global
CRS-KR model, that will be shown in the next section,
gives an eﬃcient deniable concurrent zero-knowledge
argument in the Global CRS-KR model. (We remarkthat the eﬃcient concurrent zero-knowledge scheme of[13] in the auxiliary string is not deniable.)

3.

A Construction of Straight-Line Equivocal-Extractable Commitment

This section constructs a determining, public-coin for receivers, and straight-line equivocal-extractable (and therefore adaptive-deniable-concurrent non-malleable) commitment scheme in the Global CRS-KR model, using bilinear
groups. The scheme is practically eﬃcient, using a constantnumber of pairing computations and three-round exchangesof linear-size messages.
3.1 The Design Principle
The basic design of our commitment scheme follows the oneof Damgård and Nielsen [15]. Generate a one-time commitment key of a base commitment using a coin-flipping protocol and then commit to a value by the base commitment
with the generated one-time key. The CRS is used in thecoin-flipping.
However, in our scheme, the generated coins used toform a one-time commitment key are not opened to a receiver, remaining secret of a sender. To assure the coins arehonestly generated and used to form one-time commitment
key, the sender appends a non-interactive zero-knowledge
argument for proving that honesty. (As seen later, the used
NIZK argument can be constructed without using Cook reduction, depending on the property of the bilinear map.)
More accurately, the argument proves that the sender formed
the one-time commitment key honestly or the sender knows
the receiver’s secret key, which enables only simulator EQV
to form a fake equivocal commitment.
The scheme “duplicates” some items in the sender messages so that extractor EXT can extract the generated coins(used to form a one-time commitment key) and values committed to by adversaries in the course of proving security
with help of some KEA extractors.
3.2 Building Blocks(1)

The Homomorphic Commitment.

As the base commitment, we use the homomorphic commitment of Groth, Ostrovsky, Sahai [19]. The homomorphic
commitment is built on a group G with bilinear map. The
commitment to a value m is computed as Com(m; r, t) =
r
m t
m r+t
(M1 = gm
1 g4 , M2 = g2 g5 , M3 = g3 g6 ) with a tuple(g1 , . . . , g6 ) of six elements in G as a commitment key.
A tuple (g1 , . . . , g6 ) is called linear when there exist α and β that satisfy g1 = gα4 , g2 = gβ5 , g3 = gα+β
6 .
A linear tuple (g1 , . . . , g6 ) defines an equivocal (so perfectly hiding) commitment: Com(m0 ; r0 , t0 ) = Com(m; r0 +α(m0 − m), t0 + β(m0 − m)). Meanwhile, a non-linear tuple (g1 , . . . , g6 ) defines perfectly binding commitment. The
commitment (M1 , M2 , M3 ) with a non-linear tuple (gi =gci ) determines its underlying value m through gm =(M11/c4 M21/c5 M3−1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) .

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

373

(2)

The Perfect Non-interactive Zero-Knowledge Argument.

To prove the above-mentioned honesty of generation of onetime commitment key, we incorporate the non-interactive
zero-knowledge argument of Abe and Fehr [1] into ourscheme in a following way.
Let CRS be a pair of elements g, gc in a group G withbilinear map. A common input to a prover and a verifier isa triple of A, b, g̃ and a statement to be proved is: “Thereexist a and s satisfying that A = ga gcs and g̃ = gab .” Theproof is simply a single element P = g s , which is verified ase(A, gb ) = e(g̃, g)e(P, gbc ). The NIZKA is perfectly simulated
in zero-knowledge, if one knows ec satisfying gc = gec , as
P = (Ag̃−1/b )1/ec . The NIZKA is computationally sound,for example, under the Diﬃe-Hellman inversion assumption
in a following way. Given an opening (a, s) of A = ga gcs ,an opening c of g̃ = gc and a convincing proof P, one caneﬃciently compute g1/ec as g1/ec = (g−s P)b/(ab−c) if ab  c.
Note that we need openings of A and g̃ to use the soundness,
which would require some use of KEA extractors, as in [1].
3.3 The Commitment Scheme
We describe our commitment scheme. Our scheme Σ =(Σ |Σ ) executes two parallel independent copies of subscheme Σ = (K, S , R) in the Global CRS-KR model. Eachof these two executions uses an independent global CRS andan independent public/private key pair. If both executions ofΣ output the same value m, the scheme Σ outputs that valuem. (Otherwise, it outputs ⊥.)Let G be a group of prime order q with bilinear mape(·, ·) : G × G → GT and let H be an injective function
from {0, 1}tagLen to Zq (with length tagLen of tag strings).
The subscheme Σ = (K, S, R) on group G proceeds as inFig. 6. (DH(·, ·, ·, ·) means that a given tuple constitutes a
DH-tuple.) It relies on a global CRS consisting of five elements (g, gc , g x , h x , gy ) in G and requires the knowledge ofreceiver’s public-key gID that is also an element of G.
First, parties run a coin-tossing protocol using (part of)
the CRS to generate random coins c1 , . . . , c6 in Zq ∗ . Then,sender S forms a one-time commitment key (g1 , . . . , g6 ) using the generated coins c1 , . . . , c6 as gi = gci , and computes NIZK arguments P1 , . . . , P6 that yield the one-timekey (g1 , . . . , g6 ) was honestly generated from c1 , . . . , c6 or S
knows the secret key of R. (Construction of the OR proof
follows the standard way of making OR-proof of Σ protocols [9].) In the process, some part of the CRS is used
only after it is ‘twisted’ with the tag tag to prevent adversaries from copying generated coins from/to another sessions. Main body of commitment to input m is generated
with the homomorphic commitment using that one-time key
as M1 = g1 m g4 r , M2 = g2 m g5 t , M3 = g3 m g6 r+t .
In the scheme, several messages are duplicated suchas h1 , . . . , h6 for g1 , . . . , g6 and Q1 , . . . , Q6 for P1 , . . . , P6 .
Those will be used by KEA-extractors to extract the coins
generated by adversaries from its view in the proof of secu-

Fig. 6The Commitment Subscheme Σ = (K, S, R).

rity. A decommitment is done in a canonical way.
As seen, the proposed scheme is practically eﬃcient,using a constant number of pairing computations and threeround exchanges of linear-size messages.
3.4 Security
First, we review two necessary assumptions. Let G denote agroup of k-bit prime order q. The decisional linear assumption holds on G if linear tuples (g4 α , g5 β , g6 α+β , g4 , g5 , g6 )are computationally indistinguishable from random tuples(g4 α , g5 β , g6 γ , g4 , g5 , g6 ) with random elements g4 , g5 , g6 in
G and random α, β, γ in Zq .
The knowledge of exponent assumption [12] meansthat it is possible only if one knows b to generate a pair
(gb , gab ) given a random ga . More formally, for feasible al-

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011374w
gorithms H, H ∗ and any string w, an experiment ExpG,H,H∗
a
is defined as follows. H is given q, g, A = g (with randoma from Zq ) and w, and outputs (B, W). On the same inputs
q, g, A and w, H ∗ is invoked and outputs b. If W = Ba andB  gb , the experiment outputs 1, otherwise outputs 0. The
knowledge of exponent assumption holds on G if for any w
and any feasible adversary H (called KEA-adversary) there
exists a feasible H ∗ (called KEA-extractor) with negligiblew
w
advantage AdvG,H,H∗ (k) := Pr[ExpG,H,H ∗ (k) = 1].

We begin to analyze security of the proposed commitment scheme Σ = (Σ |Σ ). In the analysis, we use ordinal
characters such as a, b, c, . . . for items in one of the two parallel executions of the subscheme Σ on which we have acurrent focus, and use characters with superscript + such asa+ , b+ , c+ , . . . for the corresponding items in the another parallel execution. First we see its computational hiding property.
Proposition 1 Under the decisional linear assumption on
G, the proposed commitment scheme is computationally hiding in the Global CRS-KR model.
Proof Suppose that a feasible adversary R∗ with identityID∗ breaks the hiding property of the proposed scheme Σ using tag tag with non-negligible probability. Using such R∗ ,we construct an eﬃcient distinguisher D that distinguishes
between a pair of linear tuples and a pair of random tuples.
Given a pair of tuples as input, D simulates a sender for R∗
and plugs the input tuple into the second sender-message
as a one-time commitment key, for each of the two parallel executions of the subscheme Σ . In doing that, D uses
the knowledge of simulated secret key of R∗ , and proves it
knows the secret key in the OR proof, instead of proving
honesty of the fake one-time commitment key. More details
follow.
Distinguisher D on input ((g1 , . . . , g6 ), (g+1 , . . . , g+6 )):1. (Simulate a sender for R∗ .) D invokes R∗ and does asfollows, for each of the two parallel executions of thesubscheme.
a. (Emulate CRS and a key-pair.) D selects random eID∗ from Zq ∗ and a random g from G. D
sets gID∗ = geID∗ and gives (gID∗ , eID∗ ) as his
pair of public/private keys to R∗ . In addition, Dchooses random ec , e x , d x , ey from Zq , sets gc =
gec , g x = gex , h x = gdxx , gy = gey , and gives
tag and (g, gc , g x , h x , gy ) to R∗ . D records η =e x · (H(tag) + d x ) for later use. (Note G x = gη .)b. (Emulate the first message.) Receiving a pairof messages (m0 , m1 ) from R∗ , D selects a random bit b (only this process is common for thetwo parallel executions). Then, D selects random
1/b(si ), (ki ), (bi ) from Zq and computes Ai = gi i gcsi
(with gi in the input) and Ui = gki for i = 1, . . . , 6.
D sends (Ai ), (Ui ) to R∗ .

c. (Emulate the second message.) Receiving challenge (b∗i ) from R∗ , to generate the second sendermessage ((gi ), (hi ), . . . , (Mi )), D uses its own input(gi ) (or (g+i )) as the (gi ) in the second message,
computes (hi ) as hi = gηi with η recorded at Step 1aand honestly computes the proofs Pi = g si , Qi =gy si . Then, with bi = b∗i /bi , D computes wi =ki − bi eID∗ using the secret key eID∗ . Finally, D
computes (M1 , M2 , M3 ) as honest homomorphic
commitment to mb with its own input (g1 , . . . , g6 )using as a commitment key. D sends the second message ((gi ), (hi ), (Pi ), (Qi ), (bi ), (wi ), (Mi ))to R∗ .
2. (Output.) If R∗ outputs b̂ which is equal to b, then D
outputs 1, otherwise outputs 0.
We evaluate the probability that D outputs 1. When
given both (g1 , . . . , g6 ) and (g+1 , . . . , g+6 ) are linear, the simulated view of R∗ in D is completely independent of b by theperfect hiding property of homomorphic commitment withlinear tuples. So, the probability that D outputs 1 is 1/2.
Suppose both (g1 , . . . , g6 ) and (g+1 , . . . , g+6 ) are random
tuples. Let ci and ai be values defined by gi = gci and ai =ci /bi . As for transcripts generated by D, we have
1/bi si
gc = gci /bi gcsi = gai gcsiUi = gki = gwi +bi eID∗ = gwi gID∗ bi
gi = gci , hi = gηi = (gci )η = (gη )ci = Gcxi
Pi = g si , Qi = gy si .

Ai = giThus, the simulated transcript is also determined by values (ai ), (si ), (wi ), (bi ), (ci ) just as the real transcripts. Here,by the description of D, we see (ci ), (bi ), (si ), (ki ) among
them are independently uniformly distributed and the rest(ai ), (bi ), (wi ) are determined through the relations ci =ai bi , b∗i = bi bi , wi = ki − bi xID by them. Meanwhile,in the real transcript, (ai ), (bi ), (si ), (wi ) are independently
uniform and the remaining (ci ), (bi ), (ki ) are determined by
the same relations by them. So, we see the distribution of(ai ), (si ), (wi ), (bi ), (ci ) is identical regardless whether it issimulated or real. Hence, the simulated view of R∗ by Dis same as the real view of R∗ , and the probability that D
outputs 1 given random tuples (g1 , . . . , g6 ) and (g+1 , . . . , g+6 )is equal to the success probability of R∗ to guess the committed values in the definition of hiding property. This must be
nonnegligibly larger than 1/2 by the contradictive assumption.
Hence, D has non-negligible advantage to distinguishbetween a pair of linear tuples and a pair of random tuples.
Such D, by standard argument, implies a distinguisher between a linear tuple and a random tuple with non-negligible
advantage, contradicting the decisional linear assumption.
Second, we show the determining property (Definition
2) of the proposed scheme.

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

375

Proposition 2 Under the discrete logarithm assumption
and the knowledge of exponent assumption on G, the proposed commitment scheme is determining in the Global
CRS-KR model.
Proof Since the homomorphic commitment with nonlinear tuples is perfectly binding, it is enough to show thatany feasible adversarial sender S∗ can generate linear onetime commitment keys (g1 , . . . , g6 ) in (both of) the two parallel executions of the subscheme only with negligible probability.
Suppose a feasible adversary S∗ generates a linear tuple (g1 , . . . , g6 ) as its one-time commitment key in either of
the two parallel executions of the subscheme Σ for a honest
receiver with identity ID (using tag tag) with non-negligible
probability. Without loss of generality, we assume S∗ generates a linear tuple in the second execution with nonnegligible probability. Using S∗ , we construct an eﬃcient
invertor I that breaks the discrete-logarithm assumption on
G with help of some KEA-extractors. Given g, gc (= gec ),I sets (g, gc ) in the corresponding part of CRS and simulates a receiver of ID for internally invoked S∗ . In an execution of the subscheme, I would receive the second sendermessage (gi ), (hi ), (Pi ), (Qi ), . . . from S∗ . If the messages
passes the specified test by Σ , there should be some ci andsi that satisfy (gi , hi ) = (gci , G x ci ) and (Pi , Qi ) = (g si , gy si ).
Then, I can use some KEA-extractors Hc∗i and H s∗i to extractsuch ci and si respectively, which provide I with an opening
ai (= ci bi /bi ), si of Ai = gai gcsi in the first sender-message ofS∗ . (For example, KEA-adversary Hci on input (g, g x ) reproduces the exact view of S∗ invoked in I using some auxiliary input w x , and outputs (gi (= gci ), hi1/(H(tag)+dx ) (= gcxi )).)
By rewinding S∗ , I can obtain another opening âi , ŝi ofthe same Ai = gâi gcŝi from another second sender-message(ĝi ), (ĥi ), (P̂i ), (Q̂i ), . . .. By the contradictive assumption we
can suppose both (gi ) and (ĝi ) are linear, and we will see itmeans that ai  âi with some i. Then I can compute thedesired discrete-log ec of gc over g, using such ai , si , âi , ŝi as
ec = (âi − ai )(si − ŝi )−1 . More details follow.
Invertor I on input (g, gc (= gec )):1. (Simulate a receiver for S∗ .) I invokes S∗ and simulates an honest receiver for S∗ as follows, for each of
the two parallel executions of the subscheme.
a. (First execution.) For the first execution, I honestly generates a CRS and a public key for S∗ andsimulates the receiver in a completely honest way.
b. (Second execution.) For the second execution, I
simulates the receiver in a following way, using its
input (g, gc ) as part of CRS.
i. (Emulate a public/private-key pair and a
CRS.) I selects a random δ from Zq ∗ , setsgID = gδc and gives gID as receiver’s publickey (for the second execution) to S∗ . I also
selects random e x , d x , ey from Zq ∗ under constraint that H(tag) + d x  0 and sets g x =gex , gy = gey , h x = gdxx (with g in the input).
I gives (g, gc , g x , h x , gy ) as a CRS (for the second execution) to S∗ , using g, gc in the input.
ii. (Emulate the challenge.) Receiving the first
sender-message (Ai ), (Ui ) from S∗ , I takes
random (bi ) from Zq ∗ and sends them to S∗ .
iii. (Extract values generated by S∗ .) Receiving the second sender-message (gi ), . . . , (bi ),. . . from S∗ , I extracts values (ci ), (ai ), (si ) as
follows, after verifying the equations specified by Σ .
A. (Extract (ci )) I sets
w x = (δ, gc , d x , ey , b1 , . . . , b6 , coins1)(where coins1 denotes the coins used
to honestly simulate the first execution)and for i = 1, . . . , 6, I invokes KEAextractor Hc∗i on input (g, g x ; w x ) andobtains the result ci to compute ai =ci bi /bi . (Note that e x is independent ofw x .)
B. (Extract (si )) I sets
wy = (δ, gc , e x , d x , b1 , . . . , b6 , coins1)
and for i = 1, . . . , 6, I invokes KEAextractor H s∗i on input (g, gy ; wy ) and obtains the result si . (Note that ey is independent of wy .)iv. (Rewind and extract the new values.) I
rewinds S∗ to Step 1(b)ii and repeats the processes with new challenge (b̂i ) to get the new
extracted values (ĉi ), (âi ), ( ŝi ), receiving another second message (ĝi ), . . . , (b̂i ), . . . fromS∗ .
2. (Compute the discrete log.) Finally,a. If there exists some i satisfying bi  b̂i , then I
computes the discrete-log ec using wi , bi , ŵi , b̂i (asshown below).
b. Otherwise if there exists some i satisfying ai 
âi , then I computes the discrete-log ec using
ai , si , âi , ŝi (as shown below).
c. Otherwise I aborts.
It is direct to see I perfectly simulates a real view of S∗
using its input (g, gc ) as part of CRS of the second execution.
Then, I invokes KEA-extractors Hc∗i at Step 1(b)iiiA and H s∗iat Step 1(b)iiiB, respectively twice, by rewinding S∗ . From
now on we condition ourselves on the non-negligible eventin which S∗ generates a linear tuple (g1 , . . . , g6 ) as its onetime commitment key in the second parallel execution, andcompletes the commitment phase. For a while, assume that
Claim 2 The extracted values (ci ) (or (ĉi )) at Step 1(b)iiiAand (si ) (or ( ŝi )) at Step 1(b)iiiB satisfy gi = gci , Pi = g si

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011376

(or ĝi = gĉi , P̂i = g ŝi ) for i = 1, . . . , 6 with overwhelming
probability.
Under the claim, we can change the right-hand side of
the verifier equation as
b /b



e(Ai , gbi /bi ) = e(gi , g) e(Pi , gc i i )bi /bi= e(gci , g) e(g si , gc )= e(g, gci bi /bi gcsi )bi /bithat means Ai = gci bi /bi gcsi = gai gcsi for i = 1, . . . , 6. Similarly, we have Ai = gâi gcŝi for i = 1, . . . , 6.
Suppose there exists some i satisfying bi  b̂i at Step
2a. Then, by the verifier equation on wi , we have Ui =
b

b̂



 −1

gwi gIDi = gŵi gIDi , which means gID = g(ŵi −wi )(bi −b̂i ) . Then,since gID = gδc , I can compute the desired discrete-log ec as
ec = (ŵi − wi )(bi − b̂i )−1 δ−1 .
Else if there exists some i satisfying ai  âi at Step 2b,
since we have Ai = gai gcsi = gâi gcŝi as seen above under Claim−12, it holds that gc = g(âi −ai )(si − ŝi ) . Hence, I can compute thediscrete-log ec by ec = (âi − ai )(si − ŝi )−1 .
Otherwise, we have bi = b̂i and ai = âi for any i, then it
must hold ĉi /ci = b̂i /bi for any i. In this case, the probability that both tuples (gi (= gci )) and (ĝi (= gĉi )) are simultaneously linear is negligible (since the ratio ĉi /ci is uniformly
random) and we see that I reaches Step 2c only with negligible probability.
Thus, to complete the proof, all we need is to prove
Claim 2.
Proof (of Claim 2) KEA-extractors Hc∗i correspond to thefollowing KEA-adversaries Hci .
KEA-Adversary Hci on input (g, g x ; w x = (δ, gc , d x , ey , b1 ,. . . , b6 , coins1)):
1. (Reproduce the view of S∗ .) Hci invokes S∗ and reproduces the view of S∗ using w x as follows, for eachof the two parallel executions.
a. (First execution.) Hci takes coins1 in w x and uses
it to honestly simulate the first execution of thesubscheme.
b. (Second execution.) For the second execution,
Hci simulates the receiver in a following way.
i. (Emulate a public/private-key pair and a
CRS.) Hci takes δ and gc from its auxiliary
input w x to regenerate gID = gδc and gives
it as receiver’s public-key (for the second
execution) to S∗ . Hci takes d x , ey from w x
to regenerate h x = gdxx , gy = gey and gives(g, gc , g x , h x , gy ) as a CRS to S∗ .
ii. (Emulate the challenge.) Receiving the first
sender-message (Ai ), (Ui ) from S∗ , Hci takes(bi ) from w x and sends them to S∗ .

iii. (Generate an output.) Receiving the response (gi ), (hi ), . . . from S∗ , Hci picks up gi
and hi from it and outputs (gi , hi1/(H(tag)+dx ) ).
(Recall I generated d x so that H(tag) + d x 0.)
On input (g, g x ), Hci reproduces the exact view of S∗ invoked in I using the auxiliary input w x , and generates (gi , hi )satisfying DH(g, G x , gi , hi ) with the same probability as S∗
in I does so. When (g, G x , gi , hi ) is a DH-tuple and gi = gci ,we have hi1/(H(tag)+dx ) = Gcxi /(H(tag)+dx ) = gcxi . (Here, recall that
I generated d x so that H(tag) + d x  0.) Thus Hci outputs(gci , gcxi ) on input (g, g x ). As directly verified, the items in w x
are independent of the discrete-log e x of g x over g. Hence,by the knowledge of exponent assumption, we see that thecorresponding KEA-extractor Hc∗i (in I) outputs ci satisfying gi = gci only with negligible exception (whenever S∗
generates valid (gi , hi )).
KEA-adversary H si on input (g, gy ; wy ) proceeds as Hciand outputs (Pi = g si , Qi = gy si ). By a similar argument, we
see H s∗i in I outputs si satisfying Pi = g si only with negligible
exception.

Now we show the straight-line equivocal-extractability(Definition 4) of the proposed scheme.
Proposition 3 Under the decisional linear assumption andthe knowledge of exponent assumption on G, the proposedcommitment scheme is straight-line equivocal-extractable in
the Global CRS-KR model.
Proof Idea To show the proposition, we need to constructa simulator EQV of a left party and an extractor EXT of thevalues committed to by any feasible adversary A for a rightparty, that satisfy Definition 4.
EQV is given A’s secret key eID∗ and proves that it
knows eID∗ in the second sender-message, instead of proving
its honesty to the generation of one-time commitment key.
By doing this, EQV can use a linear tuple as the one-timecommitment key for its commitment. Since linear tuples
define equivocal commitments, EQV is able to adaptively
simulate left parties without knowing values actually beingcommitted to. We show such simulation of left parties by
EQV is indistinguishable from the real left parties for feasible adversaries A under the decisional linear assumption on
G with help of some KEA-extractors. (To show the indistinguishability, we need to extract the values committed to by
A, that is enabled by using some KEA-extractors.)
EXT extracts the value committed to by A from its view
viewA using the trapdoor information of the CRS. For thatsake, EXT needs to extract the coins c∗i , used by A to generate its one-time commitment key. EXT invokes some KEA
extractors on input (g, g x ) using (some part of) the view
viewA as auxiliary information to extract such coins c∗i . Here,
we need to take care to use the knowledge of exponent assumption in the right way for such KEA-extractors, because

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

377

the view viewA itself is dependent on the discrete-log between g and g x which are included in the CRS. (We canuse the knowledge of exponent assumption only for KEAextractors that uses auxiliary information that is independentof its input.) We will carefully examine the distribution of
viewA and pick up some portion from viewA that is independent of that discrete-log, by making use of zero-knowledge
simulators for proofs Pi .
In the course of the proof, one key point is to ensurethat the adversary A cannot use linear tuples as its own onetime commitment key, even if A receives linear tuples as
one-time commitment keys from the simulated left party by
EQV. This impossibility is brought by the use of tag tag
h x , that is inin the scheme for generation of G x = gH(tag)xturn used for the generation of (hi ) in the second sendermessage. This dependency on tag prevents the flipped coins
generated for one-time commitment keys from being copied
from/to other sessions.
The detailed proof of Proposition 3 is in Appendix A.
By Theorem 1, Proposition 2 and Proposition 3, we
have
Theorem 2 Under the decisional linear assumption andthe knowledge of exponent assumption on G, the proposedcommitment scheme is adaptive-deniable-concurrent nonmalleable in the Global CRS-KR model.
4.

Conclusion

We defined a notion of adaptive-deniable-concurrent nonmalleable commitments, which captures the composability,
deniability and adaptivity at once for commitment schemes.
Then we defined a more-easy-to-prove property of straightline equivocal-extractability of commitment schemes andproved that it yields the adaptive-deniable-concurrent nonmalleability in the Global CRS-KR model. We also gavea construction of a straight-line equivocal-extractable (especially, adaptive-deniable-concurrent non-malleable) commitment scheme in the Global CRS-KR model, under thedecisional linear assumption and the knowledge of exponent
assumption on bilinear groups. The scheme is practically efficient, using a constant number of pairing computations andthe three-round exchanges of linear-size messages.

[6] R. Canetti and M. Fischlin, “Universally composable commitments,” CRYPTO 2001, LNCS 2139, pp.19–40, 2001.
[7] R. Canetti, S. Halevi, and J. Katz, “Chosen-ciphertext security
from identity-based encryption,” EUROCRYPT 2004, LNCS 3027,
pp.207–222, 2004.
[8] Z. Cao, I. Visconti, and Z. Zhang, “Constant-round concurrent nonmalleable statistically binding commitments and decommitments,”
PKC 2010, LNCS 6056, pp.193–208, 2010.
[9] R. Cramer, I. Damgård, and B. Schoenmakers, “Proofs of partial knowledge and simplified design of witness hiding protocols,”
CRYPTO 1994, LNCS 839, pp.174–187, 1994.
[10] G.D. Crescenzo, Y. Ishai, and R. Ostrovsky, “Non-interactive andnon-malleable commitment,” pp.141–150, STOC 1998.
[11] G.D. Crescenzo, J. Katz, R. Ostrovsky, and A. Smith, “Eﬃcient andnon-interactive non-malleable commitments,” EUROCRYPT 2001,
LNCS 2045, pp.40–59, 2001.
[12] I. Damgård, “Towards practical public-key cryptosystems provablysecure against chosen-ciphertext attacks,” CRYPTO’91, LNCS 576,
pp.445–456, 1991.
[13] I. Damgård, “Eﬃcient concurrent zero-knowledge in the auxiliary
string model,” EUROCRYPT 2000, LNCS 1807, pp.418–430, 2000.
[14] I. Damgård and J. Groth, “Non-interactive and reusable nonmalleable commitment schemes,” Proc. STOC 2003, pp.426–437,
ACM Press, 2003.
[15] I. Damgård and J.B. Nielsen, “Perfect hiding and perfect binding
universally composable commitment schemes with constant expansion factor,” CRYPTO 2002, LNCS 2442, pp.581–596, 2002.
[16] Y. Dodis, V. Shoup, and S. Walfish, “Eﬃcient constructions of composable commitments and zero-knowledge proofs,” CRYPTO 2008,
LNCS 5157, pp.515–535, 2008.
[17] D. Dolev, C. Dwork, and M. Naor, “Non-malleable cryptography,”
SIAM J. Comput., vol.30, no.2, pp.391–437, 2000.
[18] M. Fischlin and R. Fischlin, “Eﬃcient non-malleable commitment
schemes,” CRYPTO 2000, LNCS 1880, pp.413–431, 2000.
[19] J. Groth, R. Ostrovsky, and A. Sahai, “Perfect non-interactive zeroknowledge for NP,” EUROCRYPT, LNCS 4004, pp.339–358, 2006.
[20] H. Lin, R. Pass, and M. Venkitasubraamaniam, “Concurrent nonmalleable commitments from any one-way function,” TCC 2008,
LNCS 4948, pp.571–588, 2008.
[21] P.D. MacKenzie, M.K. Reiter, and K. Yang, “Alternatives to nonmalleability: Definitions, constructions, and applications,” TCC
2004, pp.171–190, LNCS 2951, 2004.
[22] R. Ostrovsky, G. Persiano, and I. Visconti, “Simulation-based concurrent non-malleable commitments and decommitments,” TCC
2009, LNCS 5444, pp.91–108, 2009.
[23] R. Pass, “On deniabililty in the common reference string and random
oracle model,” CRYPTO 2003, LNCS 2729, pp.316–337, 2003.
[24] R. Pass and A. Rosen, “Concurrent non-malleable commitments,”
pp.563–572, FOCS 2005.
[25] Z. Zhang, Z. Cao, N. Ding, and R. Ma, “Non-malleable statistically hiding commitment from any one-way function,” ASIACRYPT
2009, LNCS 5912, pp.303–318, 2009.

References[1] M. Abe and S. Fehr, “Perfect NIZK with adaptive soundness,” TCC
2007, LNCS 4392, pp.118–136, 2007.
[2] B. Barak, “How to go beyond the black-box simulation barrier,”
Proc. 42nd FOCS, pp.106–115, IEEE, 2001.
[3] B. Barak, R. Canetti, J.B. Nielsen, and R. Pass, “Universally composable protocols with relaxed set-up assumptions,” Proc. 45th
FOCS, pp.186–195, IEEE, 2004.
[4] R. Canetti, “Universally composable security: A new paradigm for
cryptographic protocols,” Proc. FOCS, pp.136–145, 2001.
[5] R. Canetti, Y. Dodis, R. Pass, and S. Walfish, “Universally composable security with global setup,” TCC 2007, LNCS 4392, pp.61–85,
2007.

Appendix A: Proof of Proposition 3
Let Σ = (Σ |Σ ) with Σ = (K, S , R) denote the proposedcommitment scheme on G. We want to show there exists a
feasible algorithm EQV such that for any feasible adversary
A, there exists a feasible algorithm EXT and
fakeComΣEQV,A,EXT (m, z) ≡c realComΣA (m, z)(A· 1)

with any value m (∈ Zq ) and any string z (Definition 4).
For that sake, we define four experiments Exp0 , . . . ,IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011

378

Exp3 in the sequel and proves indistinguishability of their
outputs step by step. Exp0 is nothing but the experiment
realComΣA (m, z) instantiated with our Σ, and the final experiment Exp3 gives EQV and EXT, proving Eq. (A· 1).

any feasible adversary A outputs a linear tuple (g∗1 , . . . , g∗6 )as the one-time commitment key for the right interaction ineither of the two execution of the subscheme only with negligible probability in Exp1 (or Exp2 ).

A.1 Exp0

Proof The proof is similar to the proof of Proposition 2,
where we have shown that any feasible sender S∗ in a standalone setting can generate a linear tuple (g1 , . . . , g6 ) as the
one-time commitment key only with negligible probability,
by exhibiting an invertor I that computes the discrete-log ofgc over g with help of the KEA-extractors Hci and H si using
such S∗ .
To prove this lemma, we again construct an invertor Ithat computes the discrete-log of gc over g using such A. In
addition to the work done by I in the proof of Proposition
2, the new I needs to simulate the honest left party. Sincealso this I, which sets up the public key for the simulated A,
knows A’s secret key eID∗ , there is no diﬃculty for this I to
simulate the left party in Exp1 (or Exp2 ).
One subtle point is in the construction of the new
KEA-adversary Hci . Recall that the work of Hci is
to compute (gi (= gci ), gcxi ) on input (g, g x ) (and w x =(δ, gc , d x , ey , b1 , . . . , b6 , coins1)). In the proof of Proposition 2, the trapdoor d x (in w x ), which is generated to satisfy
H(tag)+d x  0, is used to compute the gcxi by Hci . Hci pickedup hi (= Gcxi ) from the S∗ ’s second message and computed
gcxi = hi1/(H(tag)+dx ) . (Recall G x = g x H(tag)+dx .) However in thecase of this lemma, Hci must deal with the right interaction∗
c∗and need to compute g xi from hi (= G∗x ci ) in the right inter∗H(tag)
h x . Now tag∗ , which also belongs
action with G∗x = g x
to the right interaction, is selected by A after it sees the CRS(which includes g, g x ). So, we have no guarantee of being
H(tag∗ ) + d x  0 and the new Hci cannot mimic the old Hci∗c∗just doing as g xi = hi1/(H(tag )+dx ) .
To remedy this situation, the new I generates g x andh x in CRS in a following manner. First, I selects a rangη .
dom e x , η from Z∗q , and sets g x = gex , h x = g−H(tag)xη(Note G x = g and remember the left tag tag is selectedc∗by A before it sees CRS.) Then, Hci can compute g xi as1 ∗  H(tag∗ )−H(tag)hi, using η that will be newly added in the auxη∗gi
iliary input w x . (Note when (g, G∗x , g∗i , h∗i ) is a DH-tuple and∗∗∗)−H(tag) c∗
g∗i = gci , we have h∗i = (G∗x )ci = (gη gH(tag
)i =
x
1


∗
∗
∗
∗
H(tag
)−H(tag)∗cchg∗i η (g xi )H(tag )−H(tag) . So, g∗iη= g xi .) Becausei
A must choose distinct tag∗ from tag (to gain a nontrivial
advantage), it is guaranteed that H(tag∗ ) − H(tag)  0. 

Given m and z as input, Exp0 invokes an adversary A onz. First, A selects a tag tag for the left interaction, its own
id ID∗ and right-party’s id ID. A receives a CRS σ, itspublic/private-key pair (gID∗ , eID∗ ) and the right-party’s public key gID , for each of the two parallel executions of thesubscheme. Then, Exp0 simulates the left party that commits to m and the right party for A, honestly. Exp0 returns the trapdoor (τ, τ+ ) of the CRSs of both executions,the simulated A’s view viewA , the determining value m∗ of
A’s commitment in viewA and the left-party’s decommitment((m, r, t), (m, r+ , r+ )) which corresponds to the left-party’s
commitment in viewA . A full description of Exp0 is inSect. Appendix B.
A.2 Exp1
Only the behavior of the left party is changed as follows.
The new left party proves the knowledge of A’s secret keyeID∗ , instead of proving the honesty of the generation of the
one-time commitment key. More precisely, for each of thetwo parallel executions of the subscheme, the new left party
computes Ui as Ui = gki with random ki (instead of Ui =gwi gID∗ bi with bi selected in advance). Moreover, the leftparty selects a random one-time commitment key (gi = gci )independently of Ai = gai gcsi in the first message. Although
the proofs Pi = g si , Qi = gy si are honestly computed using
si , the response wi is computed as wi = ki − bi eID∗ using A’s
secret key eID∗ for challenge bi , that is now computed fromA’s challenge b∗i through bi = ci /ai , bi = b∗i /bi .
Claim 3 The output of Exp1 is perfectly indistinguishable
from the output of Exp0 .
Proof The only diﬀerence between Exp0 and Exp1 is in
the order of generation of challenges bi and bi : Generaterandom bi and set bi = b∗ /bi , or generate random bi =ci /ai and set bi = b∗ /bi . This diﬀerence does not aﬀect theresulting distribution of left party’s messages and the output
of Exp1 distributes exactly as the output of Exp0 .
A.3 Exp2
The third experiment Exp2 proceeds just as Exp1 , exceptthat (ci ) is now selected so that (gci ) becomes a linear tuple,
instead of a random tuple.
In order to prove indistinguishability between the outputs of Exp2 and Exp1 , first we prepare a following lemma.
Lemma 1 Under the same assumption as Proposition 3,

Claim 4 Under the same assumption as Proposition 3, theoutput of Exp2 is computationally indistinguishable fromthe output of Exp1 .
The proof is in the same line to the proof of Proposition 1, where in order to show the hiding property a distinguisher between linear and random tuples was constructed
and it simulated an honest sender for adversarial receiver R∗

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

379

to gain his advantage. In the proof of this claim, a new distinguisher does the same simulation for the left interaction
for adversary A, and in addition it simulates an honest rightparty and extracts the value committed to by A for the rightparty in some eﬃcient way, using some KEA-extractors,
which is needed for the assumed distinguisher to distinguishbetween the two experiments.
Proof Suppose that the output of Exp2 is distinguishable
from the output of Exp1 by some eﬃcient distinguisher D12
with some non-negligible advantage (with respect to m andz).
Using such distinguisher D12 , we construct an eﬃcient(non-uniform) distinguisher DLIN between a pair of linear
tuples and a pair of random tuples with non-negligible advantage, that would contradict to the decisional linear assumption on G.
Given a pair of tuples (g1 , . . . , g6 ), (g+1 , . . . , g+6 ) as inputs, DLIN simulates the left party for A in such a way thatthe (g1 , . . . , g6 ), (g+1 , . . . , g+6 ) would occupy one-time commitment keys of the left interactions in the two parallel
executions. Note that, due to the modification introducedin Exp1 , one-time commitment keys included in the second sender-message are being chosen independently fromthe first sender-message (Ai ), (Ui ). So, such simulation isquite easy. After generating the view of A, DLIN invokes
KEA-extractors Hc∗i , that are essentially the same as theones used by I in the proof of Lemma 1, to extract coins∗c∗i satisfying g∗i = gci for the one-time commitment key∗(gi ) in the right interaction. Because, by Lemma 1, thecommitment keys (g∗1 , . . . , g∗6 ) can be supposed to be non∗linear, DLIN is able to compute gm (with the determining∗
value m of A’s commitment in the right interactions) as
∗
∗
∗
∗
∗ ∗
∗ ∗
∗ ∗
gm = (M1∗ 1/c4 M2∗ 1/c5 M3∗ −1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) using those∗mc∗i , and as well as g+ . This means that DLIN can extract m∗ by using another KEA-extractor (that corresponds∗∗
to another KEA-adversary that outputs (gm , g+ m ) on in+put (g, g )) and then can invoke the assumed distinguisher
D12 on m∗ (and other easy-to-collect items) to distinguish
the given tuples. A formal description of DLIN is given in
Fig. A· 1.
As easily seen (from the comments in the description),
DLIN perfectly simulates the view of A in Exp1 if the input(gi ), (g+i ) are random, and perfectly simulates the view of A
in Exp2 if the input (gi ), (g+i ) are linear. Then, DLIN extracts
the value m∗ , which is supposed to be committed to by A
for the right party, by using KEA-extractor H ∗ . Assuming
the extracted m∗ is in fact the one committed to by A, DLIN
is now able to use the assumed distinguisher D12 on m∗ andother items, to distinguish the input tuples are linear or random, contradicting the assumption.
Thus, now all we need to show is that the KEAextractor H ∗ , which corresponds to following KEAadversary H, extracts the right determining value m∗ of A’scommitment in the right interaction only with negligible exceptions.

Fig. A· 1

Distinguisher DLIN .

KEA-Adversary H on input (g, g+ ; z, m, w, w+ ):1. (Reproduce the view of A.) H invokes A on z. Receiving ID∗ , ID, tag from A, H reproduces the view ofA using the coins given in w, w+ , for each of the twoparallel executions of the subscheme.
2. (Extract coins generated by A.) For each of the above
two parallel executions, H extracts the coins (c∗i ) that

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011

380

defines the one-time commitment key (g∗i ) in the rightinteractions. Namely, H sets
w x = (z, eID∗ , gID , gc , η, ey , g1 , . . . , g6 , coinL ,b1 , . . . , b6 , w+ )(where notation is the same as in DLIN besides coinL ,that denotes the coins used to simulate the left party
in this execution) and invokes KEA-extractor Hc∗i on∗
input (g, g x ; w x ) to obtain c∗i satisfying g∗i = gci for i =1, . . . , 6. Then, H computes
∗

∗

∗

∗

∗

∗

∗

∗

∗

u = (M1∗ 1/c4 M2∗ 1/c5 M3∗ −1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) .
∗(Note it should be u = gm with determining value m∗of A’s homomorphic commitment in this execution.)
3. (Generate an output.) Output a pair of extracted values (u, u+ ) of the two executions.
Given (g, g+ ) as input, the KEA-adversary H uses thecoins given in the auxiliary input w, w+ to reproduce the exact view of A in DLIN and then extracts coins c∗i generated∗
by A, which are expected to satisfy g∗i = gci by using KEAextractors Hc∗i on (g, g x ) andw x = (z, eID∗ , gID , gc , η, ey , g1 , . . . , g6 , coinL , b1 , . . . , b6 , w+ ).
For a while, assume the coins c∗i are right. Then, since∗∗(g∗1 = gc1 , . . . , g∗6 = gc6 ) is not linear by Lemma 1 (onlywith negligible exceptions), it defines perfectly binding homomorphic commitment and so H can compute the value
∗
∗
∗
∗ ∗
∗ ∗
∗ ∗
u = (M1∗ 1/c4 M2∗ 1/c5 M3∗ −1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) that must be∗
equal to gm with m∗ = det(M1∗ , M2∗ , M3∗ ). The output of H
is a pair (u, u+ ) of such u for the two∗ executions of the sub∗scheme. Thus, H outputs (gm , g+ m ) on input (g, g+ ), andsince clearly Logg (g+ ) is independent from the auxiliary input (z, m, w, w+ ), we see the corresponding H ∗ extracts theright determining value m∗ of A’s commitment only withnegligible exceptions, by the knowledge of exponent assumption, as desired.
Now, all we have to do is to show the above KEAextractors Hc∗i , which correspond to the following KEAadversaries, extract the right coins c∗i satisfying g∗i =∗gci only with negligible exceptions. As in the proof
of Lemma 1, given (g, g x ) as input, Hci reproduces theexact view of A invoked in H using the auxiliary input w x , and picks up g∗i and h∗i from the view and out1
 ∗  H(tag∗ )−H(tag)
c∗i
hi
∗
c∗i
puts gi (= g ), g∗ η(= g x ) . Namely, Hci outputs
i

c∗i

c∗
, g xi ) on input (g, g x ). In addition, as directly verified, all(gitems in w x are independent of the discrete-log e x of g x overg. Hence, by the knowledge of exponent assumption, Hc∗i in∗
H must output c∗i satisfying g∗i = gci only with negligible
exception. This completes the proof of Claim 4.

A.4 Exp3
In the final experiment Exp3 , the simulated left party ischanged to commit to a dummy value m0 through the hom0 t0
0 r0
momorphic commitment M1 = gm
1 g4 , M2 = g2 g5 , M3 =m0 r0 +t0
g3 g6 , instead of committing to the true value m, foreach of the two executions of subscheme. Since by themodification introduced in Exp2 the one-time commitment
key (gi (= gci )) of the left interaction is linear, its decommitment to the true value m (to be included in the output) exists and is computed by r = r0 + cc14 (m0 − m), t =t0 + cc25 (m0 − m). In addition, in Exp3 , the computation of
the determining value m∗ = det(M1∗ , M2∗ , M3∗ ) of A’s commitment is changed. It is now eﬃciently extracted by using KEA-extractor H ∗ on (g, g+ ; z, m, w, w+ ) with w =(eID∗ , gID , τ, (Ai ), (Ui ), (bi ), (gi ), (bi ), (Mi )).
Claim 5 The output of Exp3 is statistically indistinguishable from the output of Exp2 .
Proof In Exp2 , the homomorphic commitment M1 , M2 , M3
in the left interaction is perfectly hiding and equivocal since
the used one-time commitment key g1 , . . . , g6 is linear. So,
it is trivial to see the viewA in Exp3 is exactly distributed as
the viewA in Exp2 .
Then, all we need to show is that given input(g, g+ ; z, m, w, w+ ), H ∗ in Exp3 correctly outputs the determining value m∗ = det(M1∗ , M2∗ , M3∗ ) of A’s commitment in the right interaction only with negligible exceptions. This H ∗ is similar as H ∗ used by DLIN in the proofof Claim 4. However, there is an important diﬀerence.
As seen below, the new H (that corresponds to the newH ∗ ) also uses extractors Hc∗i of c∗i on input (g, g x ). However, in the current setting, the information given to this Hc∗ithrough auxiliary input w x will contain (part of) A’s view(Ai ), (Ui ), (bi ), (gi ), (bi ), (Mi ), instead of the used coins as
before. So, as to the new Hci , there is no direct guaranteethat the discrete-log e x of the given input (g x , g) is independent of the given auxiliary input w x . (The left party’s second
message, especially (bi = b∗i /bi ), depends on the A’s challenge (b∗i ), which possibly depends on the CRS, which includes g, g x . ) So, before describing the new KEA-adversary
H, we need to give an equivalent code for simulating the leftparty in Exp3 , to avoid such problem.
Fix arbitrary left party’s first message (Ai ), (Ui ) and arbitrary right party’s first message (bi ) in Exp3 . (Note thenA’s challenge (b∗i ) for the left party is also fixed.) Then, in
Exp3 , the second left-party message (gi ), (hi ), . . . , (wi ) (excluding (Mi ) which is clearly independent of g, g x ) is being generated by the following procedure. (Note the fixed(Ui = gki ) implicitly determines ki .)• The original procedure:
1. Take a random tuple (c1 , . . . , c6 ) so that (g1 =
gc1 , . . . , g6 = gc6 ) is linear and a random tuple(s1 , . . . , s6 ) from Z∗q . (Note si implicitly determines ai through the fixed Ai = gai gcsi .)2. For i = 1 to 6, compute gi = gci , hi = Gcxi , Pi =g si , Qi = gysi , bi = ci /ai , bi = b∗i /bi , wi =ki − bi eID∗ .

ARITA: AN EFFICIENT ADAPTIVE-DENIABLE-CONCURRENT NON-MALLEABLE COMMITMENT SCHEME

381

This procedure is re-written as follows, using trapdoor
information τ and the zero-knowledge simulator of proof Pi .
• The second procedure:
1. Take a linear tuple (g1 , . . . , g6 ) from G and a random tuple (b1 , . . . , b6 ) from Zq .
2. For i = 1 to 6, compute hi = gηi , Pi =−1/b

e(Ai gi i )1/ec , Qi = Pi y , bi = b∗i /bi , wi =ki − bi eID∗ , with η = e x · (H(tag) + d x ).
We can select random (bi ), instead of random (bi ),preserving the distribution and the above procedure is rewritten as follows.
• The third procedure:
1. Take a linear tuple (g1 , . . . , g6 ) from G and a random tuple (b1 , . . . , b6 ) from Zq .
2. For i = 1 to 6, compute hi = gηi , bi = b∗i /bi , Pi =−1/bi 1/ec

(Ai gi)e, Qi = Pi y , wi = ki − bi eID∗ .

The third procedure shows that the second left-party
message includes the three independent random components(gi ), (bi ), (Mi ) and the other items (hi ), (Pi ), (Qi ), (wi ) are determined by them. Thus, we see that the discrete-log e x ofg x over g is independent of the part of viewA consisting of(Ai ), (Ui ), (bi ) and (gi ), (bi ), (Mi ).
Now we describe the KEA-adversary H that uses theabove third procedure to simulate the left-party messages.
KEA-Adversary H on input (g, g+ ; z, w = (eID∗ , gID , τ,(Ai ), (Ui ), (bi ), (gi ), (bi ), (Mi )), w+ ):1. (Reproduce the view of A.) H invokes A on z. Receiving ID∗ , ID, tag from A, H reproduces the view of A
using w as follows, for each of the two parallel executions of the subscheme.
a. (Emulate a public/private-key pair and a
CRS.) H takes the trapdoor information τfrom w to regenerate A’s public/private-key pair(gID∗ , eID∗ ), right-party’s public key gID and a
CRS (g, gc , g x , h x , gy ), and gives them to A. H
records η = e x · (H(tag) + d x ) for later use.
b. (Emulate a first left-party message.) Receivinga request for a first left-party message from A, H
takes (Ai ), (Ui ) from w and sends them to A.
c. (Emulate a first right-party message.) Receiving
a first message tag∗ , (A∗i ), (Ui∗ ) to the right-party
from A, H takes (bi ) from w and sends them to A.
d. (Emulate a second left-party message.) Receiving a first message (b∗i ) to the left-party
from A, H takes (gi ), (bi ), (Mi ) from w, com= b∗i /bi , Pi =putes hi = gηi , bi
−1/b

e(Ai gi i )1/ec , Qi = Pi y , wi = ki − bi eID∗ , andsends (gi ), (hi ), (Pi ), (Qi ), (bi ), (wi ), (Mi ) to A.
e. (Extract the coins generated by A.) Receiving the second message (g∗i ), (h∗i ), . . . , (Mi∗ ) to theright-party from A, H extracts the coins (c∗i ) that

A generated. Namely, H sets
w x = (z, eID∗ , gID , ec , η, ey , (Ai ), (Ui ), (bi ),(gi ), (bi ), (Mi ), view+A )(where view+A denotes the view of A in the anotherexecution of the subscheme) and invokes KEAextractor Hc∗i on input (g, g x ; w x ) to obtain c∗i , fori = 1, . . . , 6.
∗
f. (Extract gm generated by A.) H computes u =
∗
∗
∗
∗ ∗
∗ ∗
∗ ∗
(M1∗ 1/c4 M2∗ 1/c5 M3∗ −1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) .
2. (Generate an output.) Return a pair of the extracted
values (u, u+ ) at Step 1f.
Given (g, g+ ) as input, KEA-adversary H reproduces
the exact view of A in Exp3 by using the third procedure on those independent random components given in
the auxiliary input w, and then extracts A’s coins c∗i that∗are expected to satisfy g∗i = gci by KEA-extractor Hc∗i on(g, g x ) and w x = (z, eID∗ , gID , ec , η, ey , (Ai ), (Ui ), (bi ),(gi ), (bi ), (Mi ), view+A ). For a while, assume the expec∗∗
tations are right. Then, since (g∗1 = gc1 , . . . , g∗6 = gc6 ) is
not linear by Lemma 1, it defines a perfectly binding homomorphic commitment and so H can compute the value
∗
∗
∗
∗ ∗
∗ ∗
∗ ∗
u = (M1∗ 1/c4 M2∗ 1/c5 M3∗ −1/c6 )1/(c1 /c4 +c2 /c5 −c3 /c6 ) that must be∗
equal to gm with m∗ = det(M1∗ , M2∗ , M3∗ ). The output ofexecutions of the
H is a pair (u, u+ ) of such u for the two∗∗
subscheme. Thus, H outputs (gm , g+ m ) on (g, g+ ). Since
clearly the discrete-log of g+ over g is independent from theauxiliary input (z, m, w, w+ ), by the knowledge of exponent
assumption, the corresponding KEA-extractor H ∗ extracts
the right determining value m∗ of A’s commitment only withnegligible exceptions, as desired.
Now, all we have to do is to show that the KEAextractor Hc∗i , which corresponds to the following KEA∗
adversary Hci , extracts the coins c∗i satisfying g∗i = gcionly with negligible exceptions. Given (g, g x ) as input, Hci reproduces the exact view of A invoked in H
using the auxiliary input w x by using the third procedure, and picks up g∗i and h∗i from them and outputs∗∗c∗g∗i (= gci ), (h∗i /g∗i η )1/(H(tag )−H(tag)) (= g xi ) . As discussed before, the items in w x (especially the ones that belongs to theview of A) was chosen to be independent of the discrete log
e x of g x with g. Hence, by the knowledge of exponent as∗
sumption, Hc∗i outputs c∗i satisfying g∗i = gci only with negligible exceptions. That completes the proof of Claim 5. 
By Claims 3, 4 and 5, Eq. (A· 1) is satisfied by EQV and
EXT in Fig. A· 2, that are immediate from the descriptionof Exp3 and the third procedure, completing the proof of
Proposition 3.
Appendix B: A Full Description of Exp0
Experiment Exp0 on input m ∈ Zq and z ∈ {0, 1}∗ :1. (Simulate left and right parties for A.) Invoke A onz. Receiving ID∗ , ID and tag from A, simulate the left

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.1 JANUARY 2011382

take two random r, t from Zq and compute M1 =
r
t
r+t
gm
M2 = gm
M3 = gm
Send
1 g4 ,
2 g5 ,
3 g6 .
(gi ), (hi ), (Pi ), (Qi ), (bi ), (wi ), (Mi ) to A.
e. (Complete the commitment phases.) Receivinga second message (g∗i ), (h∗i ), . . . , (Mi∗ ) to the rightparty from A, compute b ∗i = bi /b ∗i and checkDH(g, G∗x , g∗i , h∗i ), DH(g, gc , P∗i , Q∗i ),∗∗Ui∗ = gwi gID b i ,
b∗

∗

e(A∗i , gb i ) = e(g∗i , gc )e(P∗i , gc i )∗)with G∗x = gH(tagh x for i = 1, . . . , 6. If any ofxthem (for any i) is not true, abort with output ⊥.

2. (Generate an output.) Let viewA be the view of
A after completing the above commitment phase. If
the two values of m∗ = det(M1∗ , M2∗ , M3∗ ) determinedin the two parallel executions are the same, return((τ, τ+ ), viewA , m∗ , ((m, r, t), (m, r+, t+ ))), otherwise return ⊥.

Fig. A· 2

EQV and EXT.

and right parties for A as follows, for each of the twoparallel executions of the subscheme.
a. (Emulate a public/private-key pair and a CRS forA.) Select a random eID∗ from Zq and a random element g from G, and set gID∗ = geID∗ . Select a random element gID from G. Give to A (gID∗ , eID∗ ) as
A’s pair of public/private key and gID as the rightparty’s public key. In addition, choose ec , e x , d x , ey
randomly from Zq , set gc = gec , g x = gex , h x =gdxx , gy = gey , and give (g, gc , g x , h x , gy ) as the
CRS to A.
b. (Emulate a first left-party message.) Receivinga request for a first left-party message from A,
choosea1 , . . . , a6 , s1 , . . . , s6 , w1 , . . . , w6 , b1 , . . . , b6
randomly from Z∗q and compute Ai = gai gcsi , Ui =gwi gID∗ bi for i = 1, . . . , 6. Send A1 , . . . , A6 , U1 ,. . . , U6 to A.
c. (Emulate a first right-party message.) Receiving
a first message tag∗ , A∗1 , . . . , A∗6 , U1∗ , . . . , U6∗ to theright-party from A, choose b1 , . . . , b6 randomly
from Zq ∗ and send them to A.
d. (Emulate a second left-party message.) Receiving a first message b∗1 , . . . , b∗6 to the left-party fromA, computebi = b∗i /bi , ci = ai bi , gi = gci ,hi = G x ci , Pi = g si , Qi = gy si
for i = 1, . . . , 6 with G x = g x H(tag) h x . Then,

Seiko Arita
has been interested in prime
numbers, algebraic curves and cryptographic
protocols. He is with Institute of Information
Security, Yokohama, Japan.