IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1136

PAPER

Identification Schemes from Key Encapsulation Mechanisms∗
Hiroaki ANADA†a) and Seiko ARITA†b) , Members

SUMMARY
We propose a generic conversion from a key encapsulation mechanism (KEM) to an identification (ID) scheme. The conversion
derives the security for ID schemes against concurrent man-in-the-middle(cMiM) attacks from the security for KEMs against adaptive chosen ciphertext attacks on one-wayness (one-way-CCA2). Then, regarding the derivation as a design principle of ID schemes, we develop a series of concrete
one-way-CCA2 secure KEMs. We start with El Gamal KEM and proveit secure against non-adaptive chosen ciphertext attacks on one-wayness(one-way-CCA1) in the standard model. Then, we apply a tag frameworkwith the algebraic trick of Boneh and Boyen to make it one-way-CCA2
secure based on the Gap-CDH assumption. Next, we apply the CHK transformation or a target collision resistant hash function to exit the tag framework. And finally, as it is better to rely on the CDH assumption rather thanthe Gap-CDH assumption, we apply the Twin DH technique of Cash, Kiltz
and Shoup. The application is not “black box” and we do it by making theTwin DH technique compatible with the algebraic trick. The ID schemes
obtained from our KEMs show the highest performance in both computational amount and message length compared with previously known ID
schemes secure against concurrent man-in-the-middle attacks.
key words: identification scheme, key encapsulation mechanism, one-wayCCA2 security, concurrent man-in-the-middle attack, the computationalDiﬃe-Hellman assumption

1.

Introduction

Password-based identification protocols are broadly used toverify identities of entities. But they are exposed to a critical threat that, when a password happens to be sent without
encryption through a communication channel, an adversary
can eavesdrop the password and impersonate the prover easily. Another threat is that, if an adversary acts a verifier andthe prover interacts with it without knowing that it is a fakeverifier, then the adversary can catch the password even if it
is sent under encryption.
Here the need of public key based ID schemes arises.
In the public key framework, a prover holds a secret key and
Manuscript received November 4, 2011.
Manuscript revised February 25, 2012.
†
The authors are with Institute of Information Security,
Yokohama-shi, 221-0835 Japan.
∗
Preliminary versions of this paper appeared in Proceedings ofthe 4th International Conference on Provable Security — ProvSec
2010, Lecture Notes in Computer Science vol.6402, pp.18–34,
Springer-Verlag [1], under the title of “Identification Schemes ofProofs of Ability Secure against Concurrent Man-in-the-Middle
Attacks”, and in Proceedings of the 4th International Conference
on Cryptology — AfricaCrypt 2011, Lecture Notes in Computer
Science vol.6737, pp.59–76, Springer-Verlag [2], under the same
title as this paper.
a) E-mail: hiroaki.anada@gmail.comb) E-mail: arita@iisec.ac.jp
DOI: 10.1587/transfun.E95.A.1136

a verifier refers to a matching public key. They interact forsome rounds doing necessary computations until the verifier
feels certain that the prover has the secret key. The secret
key is never revealed directly but embedded and hidden inmessages by those computations.
However, even for such ID schemes, there is still astrong threat by the following active attack. Pretending to
be a verifier, an adversary accesses a prover application (ona client PC, for instance), and invokes many clones of the application, which have independent states and random tapes,
but the same secret key. Interacting with those clones, theadversary embeds some cheating trick in messages and collects information of the secret key from the responses of
those clones. Afterwards, it tries to impersonate the prover
against a true verifier (on a server, for instance) using thatcollected information. This situation is modeled as concurrent (two-phase) attack [7] in cryptography.
Another strong threat is man-in-the-middle attack,where an adversary stands between a prover and a verifier
and interacts with both sides simultaneously. The advantageous point is that the adversary can interact with the prover
adaptively according to the message from the verifier.
Now in the Internet environment where everyone is involved, attacks on ID schemes have become fairly strong
and concurrent man-in-the-middle attack (cMiM attack, forshort) [7] has become a real threat. In cMiM setting, anadversary stands between prover clones and a verifier. Interacting in some cheating way, the adversary collects information of the secret key from the prover clones, while theadversary interacts with the verifier simultaneously trying
to impersonate the prover.
Historically, there have been two types of ID schemes.
One is the Σ-protocol type [11] which is a kind of proofs ofknowledge [6], [21] consisting of 3-round interaction, andthe other is challenge-and-response type obtained in a natural way from encryption schemes or signature schemes.
Most of known traditional ID schemes, such as the Schnorr
scheme [37] and the Guillou-Quisquater (GQ) scheme[22], are the Σ-protocol type because they are faster thanchallenge-and-response type.
Unfortunately, the Schnorr scheme and the GQ scheme
are not secure under man-in-the-middle attacks, hence there
have been significant eﬀorts to make ID schemes secureagainst such cMiM attacks based on the Σ-protocol. For example, Katz [25], [26] made an ID scheme of non-malleable
proof of knowledge. But the security model is with timing
constraint, not against full cMiM attacks. Gennaro [20] con-c 2012 The Institute of Electronics, Information and Communication Engineers
Copyright ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1137

structed an ID scheme of (fully) concurrently non-malleable
proof of knowledge by employing a multi-trapdoor commitment. But it is no longer so fast as a challenge-and-response
ID scheme obtained from, for instance, the Cramer-Shoupencryption scheme [14]. Moreover, the security is basedon a strong type of assumption (the Strong Diﬃe-Hellman(SDH) assumption or the Strong RSA assumption).
One of the reasons why it is so diﬃcult to construct
an ID scheme secure against cMiM attacks seems that weare rooted in the category of Σ-protocols. Let us remember that challenge-and-response ID schemes obtained from
IND-CCA2 secure encryption schemes (see [14] for example) and EUF-CMA secure signature schemes (see [4] forexample) have already been secure against cMiM attacks.
1.1 Our Contribution

tion [33], [36], the Twin Diﬃe-Hellman technique† [13] anda modification to shorten message length.
It is true that there have already been a few one-wayCCA2 secure KEMs in discrete logarithm setting. In contrast to those KEMs, the feature of our KEMs is that they
only need the smallest amount of computational cost andmessage length, while its security is based on the (Gap-)
Computational Diﬃe-Hellman (CDH) assumption.
Finally, we point out another feature that provers of ID
schemes obtained by our generic conversion are deterministic, which means our ID schemes are prover-resettable [5].
Moreover, they are also verifier-resettable because they consist of 2-round interaction. This is a remarkable property
because, as is discussed by Yilek [41], resettable security
is crucially helpful for virtual machine service in the Cloud
Computing, for example.
1.2 Related Works

In the notion of encryption scheme, a key encapsulation
mechanism (KEM) is the foundational concept for a hybrid
construction with a data encryption mechanism (DEM). Asa first contribution in this paper, we propose to use a KEM
as an ID scheme analogous to the usage of an encryption
scheme. That is, given a KEM, we derive a challenge-andresponse ID scheme as follows. A verifier of a KEM-based
ID scheme makes a pair of a random string and its encapsulation (that is, a ciphertext of the string) using a public
key, and send the encapsulation as a challenge to the prover
having the matching secret key. The prover decapsulates
the encapsulation and returns the result as a response. The
verifier checks whether or not the response is equal to thestring. Although this is a straightforward conversion, it has
never been mentioned in the literature, to the best of ourknowledge.
As a generic property, KEM-based ID schemes have an
advantage over (non-hybrid) encryption-based ID schemes.
That is, a KEM only has to encapsulate a random string andmay generate it by itself, while an encryption scheme has toencrypt any string given as an input. Consequently, KEMbased ID schemes have a possibility to be simpler and more
eﬃcient than encryption-based ID schemes.
In addition, as we will show in Sect. 3, a KEM only
need to be one-way-CCA2 secure for the obtained ID
scheme to be cMiM secure. In other words, the IND-CCA2
security, which is stronger than the one-way-CCA2 security,
is rather excessive for deriving a cMiM secure ID scheme.
Nonetheless by this time, most known encryption schemes
and KEMs have been designed to possess IND-CCA2 security (because the purpose is not to derive ID schemes, ofcourse).
Hence there arises a need to provide one-way-CCA2
secure KEMs. As a second contribution, we give concrete,
discrete logarithm-based one-way-CCA2 secure KEMs.
Starting with El Gamal KEM, we develop a series of fiveone-way-CCA2 secure KEMs applying techniques such as
the selective tag with the algebraic trick [3], [27], the CHKtransformation [12], the target collision-resistant hash func-

Recently, independently of us, Fujisaki [19] pointed out afact similar to our generic construction above (that is, theconversion from a one-way-CCA2 secure KEM to a cMiM
secure ID scheme). We discuss the conversion more precisely than it.
As for concrete constructions, the IND-CCA2 secure
KEM of Cramer and Shoup (Cramer-Shoup KEM) [15],which is naturally a one-way-CCA2 secure KEM, performs
comparably eﬃciently even now, while its security is basedon the DDH assumption.
Hanaoka-Kurosawa [24] gave a one-way-CCA2 secure
KEM based on the CDH assumption. It is directly comparable with our KEM3 and our KEM3 reduces the computation
by at least 0.25 times a single exponentiation than HanaokaKurosawa KEM.
Our KEM2 and KEM3 may be directly obtained from theKEM of Kiltz [28] and the KEM of Cash, Kiltz and Shoup[13], respectively. Their KEMs are described in the hashedDH setting and intended to be used in the KEM-DEM hybrid construction. Diﬀerent from those, we show our KEM’s
security based on a weaker assumption, that is, the CDH assumption, rather than the hashed DH assumption, and we
obtain a weaker security, that is, the one-way-CCA2 security, rather than the IND-CCA2 security. In addition, an application of the Twin DH technique to KEM2 to get KEM3 is
not a “black box” and we do it by making the Twin DH
technique compatible with the algebraic trick of Boneh andBoyen [3].
1.3 Organization of the Paper
In Sect. 2, we fix some notations and briefly review the notion of an ID scheme, a KEM and computational hardness
assumptions. In Sect. 3, we propose a generic conversion
from a KEM to an ID scheme. In Sect. 4, we discuss El†
Applying the Twin Diﬃe-Hellman technique was suggested
to us by Prof. Kiltz [29].

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1138

Gamal KEM as a starting point. In Sect. 5, we employ
the tag technique with the algebraic trick [3], [27] to gettKEM, which is one-way-CCA2 secure in the selective tag
model based on the Gap-CDH assumption. In Sect. 6, weapply the CHK transformation [12] to leave the selective tag
model and get KEM1. In Sect. 7, we further develop the series by using a target collision resistant hash function to get
KEM2. In Sect. 8, we apply the Twin Diﬃe-Hellman technique [13] to KEM2 and get KEM3, which is secure based on
the CDH assumption. In Sect. 9, we compare eﬃciency of
the ID schemes from our KEMs with previously known ID
schemes and KEMs. In Sect. 10, we conclude our work.
2.

If decision = 1 ∧ π∗  {πi }ni=1 then return Win
else return Lose.
In the above experiment, we denoted a transcript of interaction between Pi (sk) and A(pk) as πi and a transcript between A(pk) and V(pk) as π∗ . Here i runs from 1 to n and n
is polynomial in k.
As a rule, man-in-the-middle adversary A is prohibitedfrom relaying a transcript of a whole interaction with someprover clone to the verifier V(pk), as is described π∗  {πi }ni=1
in the experiment. This is a natural and standard constraint
to keep man-in-the-middle attack meaningful.
We define the imp-cmim advantage of A over ID as:Preliminaries
imp-cmim

The security parameter is denoted k. The bit length ofa string s is denoted |s|. On an input 1k , a probabilistic
polynomial-time (PPT, for short) algorithm Grp runs and returns (q, g), where q is a prime of length k and g is a generator of a multiplicative cyclic group Gq of order q. Grp
specifies elements and group operations of Gq . The ring of
exponent domain of Gq , which consists of integers from 0
to q − 1 with modulo q operation, is denoted Zq .
When an algorithm A on an input a returns z, we denote
it as z ← A(a). When A on an input a and B on an input binteract and B returns z, we denote it as z ← A(a), B(b).
When A accesses an oracle O, we denote it as AO . When A
accesses n oracles O1 , . . . , On concurrently, we denote it as
AO1 |···|On . Here “concurrent” means that A accesses oracles
in an 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 denotedPr[Y1 ; · · · ; Ym : X].
2.1 Identification Scheme
An identification scheme ID is a triple of PPT algorithms (K,P, V). K is a key generator which returns a pair of a public key
and a matching secret key (pk, sk) on an input 1k . P and V
implement a prover and a verifier strategy, respectively. We
require ID to satisfy the completeness condition that boolean
decision by V(pk) after completing interaction with P(sk)is 1 with probability one. We say that V(pk) accepts if its
boolean decision is 1.
2.1.1 Attacks on Identification Scheme
The aim of an adversary A that attacks an ID scheme ID isimpersonation. We say that A wins when A(pk) succeeds
in making V(pk) accept.
An adversary A performs a concurrent man-in-themiddle attack as in the following experiment [5], [7].
imp-cmim

ExprmtA,ID(1k )(pk, sk) ← K(1k )decision ← AP1 (sk)|···|Pn (sk) (pk), V(pk)

AdvA,IDdef

imp-cmim(k) = Pr[ExprmtA,ID(1k ) returns Win].

We say that an ID is secure against concurrent man-in-themiddle attacks (cMiM secure, for short) if, for any PPT alimp-cmim
gorithm A, AdvA,ID (k) is negligible in k.
Suppose that an adversary A consists of two algorithms
A1 and A2 . The following experiment is called a concurrent(two-phase) attack.
imp-caExprmtA,ID (1k )(pk, sk) ← K(1k ), st ← A1P1 (sk)|···|Pn (sk) (pk)decision ← A2 (st), V(pk)
If decision = 1 then return Win else return Lose.
imp-caimp-cmim

AdvA,ID (k) is defined in the same way as AdvA,ID (k).
The concurrent attack is a weaker model than the cMiM
attack because of the constraint that the learning phase of A1
is limited to before the impersonation phase of A2 .
The concurrent attack and the cMiM attack are classified to active attacks. In contrast, there is a passive attack
described below.
imp-paExprmtA,ID (1k )(pk, sk) ← K(1k )If A1 (pk) makes a query, reply πi ← |P(sk), V(pk)|st ← A1 ({πi }ni=1 )decision ← A2 (st), V(pk)
If decision = 1 then return Win else return Lose.
In the above experiment, we denoted a transcript of a wholeinteraction between P(sk) and V(pk) as π = |P(sk), V(pk)|.
imp-paimp-cmim
AdvA,ID (k) is defined in the same way as AdvA,ID (k).
The passive attack is a weaker model than the concurrent attack because of the constraint that A cannot choose
messages in the learning phase.
2.1.2 Tag-Based Identification Scheme
A tag-based ID scheme tagID (see, for example, [1]) is a
triple of PPT algorithms (K, P, V) and works in the same way
as an ordinary ID scheme, except that a string t, called a tag,

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1139

is a priori given to P and V by the first round. An interaction
between P and V depends on a given tag t.
As for attacks on tagID, we only consider here thecMiM attack in the selective tag model which is describedby the following experiment.
stag-imp-cmim

ExprmtA,tagID(1k )(pk, sk) ← K(1k ), t∗ ← A(1k )decision ← AP1 (t1 ,sk)|···|Pn (tn ,sk) (pk), V(t∗ , pk)If decision = 1 ∧ t∗  {ti }ni=1then return Win else return Lose.
In the above experiment, the adversary A firstly designatesa tag t∗ called a target tag and, after that, A is given a public key pk. In addition, before starting each interaction asa verifier, A provides a tag ti ( t∗ ) to each prover clone
Pi (sk).
stag-imp-cmim
imp-cmim(k) is defined in the same way as AdvA,ID
AdvA,tagID(k).
2.2 Key Encapsulation Mechanism
A key encapsulation mechanism (KEM) KEM is a triple of
PPT algorithms (K, Enc, Dec). K is a key generator which
returns a pair of a public key and a matching secret key(pk, sk) on an input 1k . Enc is an encapsulation algorithm
which, on an input pk, returns a pair (K, ψ), where K is a random string and ψ is a ciphertext of K. Dec is a decapsulation
algorithm which, on an input (sk, ψ), returns the decapsula of ψ. We require KEM to satisfy the completenesstion K of a consistently genercondition that the decapsulation K
ated ciphertext ψ by Enc is equal to the original string K
with probability one. For this requirement, we simply force
Dec deterministic.
2.2.1 Attacks on One-Wayness of KEM
An adversary A performs an adaptive chosen ciphertext attack on one-wayness of a KEM (called one-way-CCA2, forshort) as in the following experiment [24], [35].
kExprmtow-cca2
A,KEM (1 )(pk, sk) ← K(1k ), (K ∗ , ψ∗ ) ← Enc(pk)∗ ← ADEC(sk,·) (pk, ψ∗ )K
∗ = K ∗ ∧ ψ∗  {ψi }qdec then return Win
If K
i=1

else return Lose.
In the above experiment, ψi , i = 1, . . . , qdec mean ciphertexts
for which A queries its decapsulation oracle DEC(sk, ·) for
the answers. Here the number qdec of queries is polynomial
in k. Note that the challenge ciphertext ψ∗ itself must notdec
in thebe queried to DEC(sk, ·), as is described ψ∗  {ψi }qi=1experiment.
We define the one-way-CCA2 advantage of A over KEM
as:

def

ow-cca2 k
Advow-cca2
A,KEM (k) = Pr[ExprmtA,KEM (1 ) returns Win].

We say that a KEM is secure against adaptive chosen ciphertext attacks on one-wayness (one-way-CCA2 secure, forshort) if, for any PPT algorithm A, Advow-cca2
A,KEM (k) is negligible in k. Note that if a KEM is IND-CCA2 secure [14],then it is one-way-CCA2 secure. So IND-CCA2 security isa stronger notion than one-way-CCA2 security.
Suppose that an adversary A consists of two algorithms
A1 and A2 . The following experiment is called a nonadaptive chosen ciphertext attack on one-wayness of a KEM(called one-way-CCA1, for short).
kExprmtow-cca1
A,KEM (1 )(pk, sk) ← K(1k ), st ← ADEC(sk,·)(pk)
1∗ ← A2 (st, ψ∗ )(K ∗ , ψ∗ ) ← Enc(pk), K∗ = K ∗ then return Win else return Lose.
If K
ow-cca2
Advow-cca1
A,KEM (k) is defined in the same way as AdvA,KEM (k).
The non-adaptive chosen ciphertext attack is a weakermodel than the adaptive one because of the constraint thatthe learning phase of A1 is limited to before the solving
phase of A2 .
The adaptive and non-adaptive chosen ciphertext attacks are classified to active attacks. In contrast, there isa passive attack on one-wayness of a KEM described below† (which we call one-way-PA, for short).
ow-pa

ExprmtA,KEM (1k )(pk, sk) ← K(1k )If A1 (pk) makes a query, reply (Ki , ψi ) ← Enc(pk)pa), (K ∗ , ψ∗ ) ← Enc(pk)st ← A1 ({(Ki , ψi )}i=1
∗ ← A2 (st, ψ∗ )Kq

∗ = K ∗ then return Win else return Lose.
If K
In the above experiment, the number q pa of queries is polynomial in k.
ow-pa
AdvA,KEM (k) is defined in the same way as Advow-cca2
A,KEM (k).
The passive attack is a weaker model than the nonadaptive chosen ciphertext attack because of the constraintthat A cannot choose ciphertexts in the learning phase.
2.2.2 Tag-Based Key Encapsulation Mechanism
A tag-based key encapsulation mechanism (KEM) tagKEM(see, for example, [27]) is a triple of PPT algorithms (K,Enc, Dec) and works in the same way as an ordinary KEM,
except that a string t, called a tag, is a priori given to Enc
and Dec as an input. A ciphertext ψ depends on a given tagt.
As for attacks on tagKEM, we only consider here theadaptive chosen ciphertext attack on one-wayness of a tagbased KEM in the selective tag model which is described by†
In the experiment, A1 may run Enc(pk) by itself to get(Ki , ψi ).

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1140

If Z = g xy then return Win else return Lose.

the following experiment.

We define the Gap-CDH advantage of S over Grp as:

stag-ow-cca2

ExprmtA,tagKEM (1k )(pk, sk) ← K(1k ), t∗ ← A(1k )∗ ← ADEC(sk,·,·) (pk, ψ∗ )(K ∗ , ψ∗ ) ← Enc(pk, t∗ ), K
∗ = K ∗ ∧ t∗  {ti }qdec
If K
i=1

then return Win else return Lose.
In the above experiment, the adversary A firstly designatesa tag t∗ called a target tag and, after that, A is given a
public key pk. In addition, A queries its decapsulation oracle DEC(sk, ·, ·) for the answer for a pair (ti , ψi ), whereti ( t∗ ) is a tag that A generates.
stag-ow-cca2
AdvA,tagKEM (k) is defined in the same way as Advow-cca2
A,KEM (k).
2.3 Computational Hardness Assumptions
We say a solver S, a PPT algorithm, wins when S succeeds
in solving a computational problem instance.
2.3.1 The CDH and the Gap-CDH Assumptions
A quadruple (g, X, Y, Z) of elements in Gq is called a DiﬃeHellman (DH) tuple if (g, X, Y, Z) is written as (g, g x , gy , g xy )for some elements x and y in Zq . A CDH problem instanceis a triple (g, X = g x , Y = gy ), where the exponents x andy are random and unknown to a solver. The CDH oracle
CDH is an oracle which, queried about a CDH problem instance (g, X, Y), replies the correct answer Z = g xy . A DDH
problem instance is a quadruple (g, X, Y, Z). The DDH oracle DDH is an oracle which, queried about a DDH problem instance (g, X, Y, Z), replies the correct 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 (g, X, Y) as an input, tries to return Z = g xy . We
define the following experiment.
kExprmtcdh
S,Grp (1 )(q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := gy
Z ← S(g, X, Y)
If Z = g xy then return Win else return Lose.
We define the CDH advantage of S over Grp as:
def

cdh
k
AdvcdhS,Grp (k) = Pr[ExprmtS,Grp (1 ) returns Win].

We say that the CDH Assumption [34] holds for Grp if, for
any PPT algorithm S, Advcdh
S,Grp (k) is negligible in k.
A CDH problem solver S that is allowed to access
DDH polynomially many times is called a Gap-CDH problem solver. We define the following experiment.
gap-cdhExprmtS,Grp (1k )defgap-cdh

gap-cdh

AdvS,Grp (k) = Pr[ExprmtS,Grp (1k ) returns Win].
We say that the Gap-CDH Assumption [34] holds for Grp
if, for any PPT algorithm S, Advgap-cdh(k) is negligible in k.
S,Grp
2.3.2 The Twin Diﬃe-Hellman TechniqueA 6-tuple (g, X1 , X2 , Y, Z1 , Z2 ) of elements in Gq is calleda twin Diﬃe-Hellman tuple if the tuple is written as(g, g x1 , g x2 , gy , g x1 y , g x2 y ) for some elements x1 , x2 , y in Zq .
The following lemma of Cash, Kiltz and Shoup is usedin Sect. 8 to decide whether a tuple is a twin DH tuple or notin the security proof.
Lemma 1 (Cash, Kiltz and Shoup [13] Theorem 2,“Trapdoor Test”). Let X1 , r, s be mutually independent
random variables, where X1 takes values in Gq , and eachof r, s is uniformly distributed over Zq . Define the ranY, Z1 , Z2 are random variable X2 := X1−r g s . Suppose that 
dom variables taking values in Gq , each of which is defined independently of r. Then the probability that the truthr
Y s does not agree with the truth value
value of Z1 Z2 = of (g, X1 , X2 , Y, Z1 , Z2 ) being a twin DH tuple is at most 1/q.
Y, Z1 , Z2 ) is a twin DH tuple, thenMoreover, if (g, X1 , X2 , 
r
s



Z1 Z2 = Y certainly holds.
2.3.3 The Gap-DL Assumption
A discrete log (DL) problem instance consists of (g, X = g x ),where the exponent x is random and unknown to a solver. A
DL problem solver is a PPT algorithm which, given a random DL problem instance (g, X) as an input, tries to return x.
A DL problem solver S that is allowed to access CDH polynomially many times is called a Gap-DL problem solver. We
define the following experiment.
gap-dlExprmtS,Grp (1k )(q, g) ← Grp(1k ), x ← Zq , X := g xx∗ ← SCDH (g, X)∗

If g x = X then return Win else return Lose.
We define the Gap-DL advantage of S over Grp as:
gap-dldef

gap-dl

AdvS,Grp (k) = Pr[ExprmtS,Grp (1k ) returns Win].
We say that the Gap-DL Assumption holds for Grp if, forgap-dlany PPT algorithm S, AdvS,Grp (k) is negligible in k.
Although the Gap-DL Assumption is considered fairly
strong, it is believed to hold for a certain class of cyclic
groups [32].

(q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := gy

2.3.4 The Knowledge-of-Exponent Assumption

Z ← SDDH (g, X, Y)

Informally, the Knowledge-of-Exponent Assumption (KEA)ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1141[8], [17] says that, given a randomly chosen h ∈ Gq as an
input, a PPT algorithm H can extend (g, h) to a DH-tuple(g, h, X, Z) only when H knows the exponent x of X = g x .
The formal definition is described as follows.
Let Λ(1k ) be any distribution. Let H and H be any
PPT algorithms which take input of the form (g, h, λ). Hereg is any fixed generator, h is a randomly chosen element in
Gq , and λ is a string in {0, 1}∗ output by Λ(1k ) called auxiliary input [10], [16]. We define the following experiment.
kExprmtkea
H,H ,Grp (1 )(q, g) ← Grp(1k ), λ ← Λ(1k ), a ← Zq , h := ga(g, h, X, Z) ← H(g, h, λ), x ← H (g, h, λ)If X = Z ∧ g  X then return Win
else return Lose.
ax

Note that λ is independent of h in the experiment. This independence is crucial ([10], [16]).
We define the KEA advantage of H over H and Grp
as:
def

kea
k
AdvkeaH,H ,Grp (k) = Pr[ExprmtH,H ,Grp (1 ) returns Win].

An algorithm H is called the KEA extractor. Advkea
H,H ,Grp(k) can be considered the probability that the KEA extractor
H fails to extract the exponent x of X = g x . We say that the
KEA holds for Grp if, for any PPT algorithm H, there exists a PPT algorithm H such that for any distribution Λ(1k )AdvkeaH,H ,Grp (k) is negligible in k.
3.

Identification Scheme from Key Encapsulation
Mechanism

In this section, we propose a generic conversion from a
KEM to an ID scheme. Then we observe a security derivation from a KEM to the obtained ID scheme. The derivation
gives a design principle for getting an ID scheme with desired security. Especially, we confirm that a one-way-CCA2
secure KEM gives rise an ID scheme secure against concurrent man-in-the-middle attacks.

Key Generation– K: the same as that of KEM
Interaction– V: given pk as an input;• Invoke Enc on pk: (K, ψ) ← Enc(pk)• Send ψ to P
– P: given sk as an input and receiving ψ as an input message; ← Dec(sk, ψ)• Invoke Dec on (sk, ψ): K
 to V• Send K
 as an input message;– V: receiving K
 = K then return 1 else return 0• If K
Fig. 1Dec).

An ID Scheme ID=(K,P,V) Obtained from a KEM KEM= (K, Enc,

Given (pk, ψ∗ ) as an input;
Initial Setting– Initialize its inner state– Invoke A on pk
Answering A’s Queries– In the case that A queries V(pk) for the challenge message• Send ψ∗ to A
– In the case that A sends ψ to a prover clone P(sk)• If ψ = ψ∗ , then K :=⊥• else query DEC(sk, ·) for the answer for ψ: K ← DEC(sk, ψ)• Send K to A∗ to V(pk) as the response message– In the case that A sends K∗ as the answer for ψ∗• Return K
Fig. 2 A One-Way-CCA2 Adversary B Employing a cMiM Adversary
A for the Proof of Theorem 1.

as an input. Consequently, KEM-based ID schemes has apossibility to be simpler and more eﬃcient than encryptionbased ID schemes.
The following theorem is a security derivation from a
KEM to the obtained ID scheme.
Theorem 1. If a key encapsulation mechanism KEM is oneway-CCA2 secure, then the obtained identification scheme
ID is cMiM secure. More precisely, for any PPT adversary
A that attacks ID in the cMiM setting, there exists an PPTadversary B that attacks KEM in the one-way-CCA2 setting
satisfying the following inequality.
imp-cmim

3.1 The Conversion
Let KEM = (K, Enc, Dec) be a KEM. Then an ID scheme ID
is obtained in a natural way as shown in Fig. 1. The key generation algorithm is the same as that of KEM. The verifier V,
given a public key pk as an input, invokes the encapsulation
algorithm Enc on pk and gets its return (K, ψ). V sends ψ
to P. The prover P, given a secret key sk as an input andreceiving ψ as an input message, invokes the decapsulation
 P sends Kalgorithm Dec on (sk, ψ) and gets its return K.
to V. Finally the verifier V, receiving K as an input message,
 is equal to K. If so, then V returns
verifies whether or not K
1 and otherwise, 0.
It is noteworthy that, a KEM only has to encapsulate a
random string and may generate it by itself, while a (nonhybrid) encryption scheme has to encrypt any string given

AdvA,ID(k)  Advow-cca2
B,KEM (k).

3.2 Proof of Theorem 1
Let KEM be a one-way-CCA2 secure KEM and ID be the obtained ID scheme by the conversion above. Let A be any
given PPT adversary that attacks ID. Using A as a subroutine, we construct a PPT one-way-CCA2 adversary B that
attacks KEM as shown in Fig. 2.
On an input pk and the challenge ciphertext ψ∗ , B initializes its inner state and invokes A on an input pk.
In the case that A queries V(pk) for the challenge message, B sends ψ∗ to A.
In the case that A sends a message ψ to a prover clone
P(sk), B checks whether or not ψ is equal to ψ∗ . If so, thenB puts K =⊥. Otherwise, B queries its decapsulation oracle

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1142
Table 1

Security Derivation from a KEM to the Obtained ID Scheme.

Security of a
KEM against
one-way-PA
one-way-CCA1
one-way-CCA2

=⇒
=⇒
=⇒
=⇒

Security of the Obtained
ID Scheme against
passive attack
concurrent (two-phase) attack
concurrent man-in-the-middle attack

DEC(sk, ·) for the answer for the ciphertext ψ and gets its
decapsulation K as a reply. B sends K to A as a response
message.
∗ to V(pk) as the response
In the case that A sends K∗ as themessage for the challenge message ψ∗ , B returns K∗
answer for the challenge ciphertext ψ .
The view of A in B is the same as the real view of
A. This is obvious except for the case that ψ is equal to ψ∗ .
When A sent ψ = ψ∗ , a transcript of the interaction between
P(sk) and A(pk) would be wholly equal to a transcript of theinteraction between A(pk) and V(pk), because the prover P
is deterministic. This is ruled out, so B’s response, K =⊥, isappropriate.
If A wins, then B wins. Hence the inequality in Theorem 1 follows. (Q.E.D.)
In an analogous ways, we can show the following facts.
If a KEM is secure against non-adaptive chosen ciphertext attacks on one-wayness (one-way-CCA1), then the obtained
ID scheme ID is secure against concurrent (two-phase) attacks. If a KEM is secure against passive attacks on onewayness (one-way-PA), then the obtained ID scheme ID issecure against passive attacks.
Table 1 shows this security derivation. We can view the
Table 1 as a design principle to construct an ID scheme withdesired security.
We remark that the selective tag model for security
proofs is compatible with the conversion. That is, if a KEM
is secure in the selective tag model, then the obtained ID
scheme is secure in the selective tag model.

Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), x ← Zq , X := g x• pk := (q, g, X), sk := (q, g, x), return (pk, sk)
Encapsulation– Enc: given pk as an input;• a ← Zq , K := X a , h := ga , ψ := h, return (K, ψ)
Decapsulation– Dec: given sk and ψ = h as an input; := h x , return K•K
Fig. 3

El Gamal KEM: EGKEM.

4.1 El Gamal KEM and Its Security
El Gamal KEM EGKEM consists of a triple (K, Enc, Dec). The
construction is shown in Fig. 3.
On an input 1k , the key generator K runs as follows. The
group generator Grp returns (q, g) on an input 1k . Then K
chooses x from Zq , computes X = g x and sets pk = (q, g, X)
and sk = (q, g, x). Then K returns (pk, sk).
On an input 1k , the encapsulation algorithm Enc runs
as follows. Enc chooses a ∈ Zq at random, and computes
K = X a and h = ga , and puts ψ = h. The random string is K
and its encapsulation is ψ. Enc returns the pair (K, ψ).
On an input sk and ψ = h, the decapsulation algorithm=
Dec runs as follows. Dec computes the decapsulation Kh x . Then Dec returns K.
The security of EGKEM is stated as follows.
Theorem 2. The key encapsulation mechanism EGKEM is
one-way-CCA1 secure based on the Gap-DL assumption
and the KEA for Grp. More precisely, for any PPT oneway-CCA1 adversary A = (A1 , A2 ) on EGKEM, there exists
a PPT Gap-DL problem solver S on Grp and a PPT algorithm H for the KEA which satisfy the following tight reduction.
gap-dlkea
Advow-cca1
A,EGKEM (k)  AdvS,Grp (k) + AdvH,H ,Grp (k).

3.3 Discussion
The prover P in Fig. 1 is deterministic. Therefore, the obtained ID scheme ID is prover-resettable [5]. Moreover, ID
is also verifier-resettable because ID consists of 2-round interaction.
4.

El Gamal KEM Revisited

In this section, we discuss El Gamal KEM EGKEM [18] as astarting point. The objective here is to see that EGKEM canbe proven one-way-CCA1 secure. The obtained ID schemefrom EGKEM is similar to the scheme of Stinson and Wu [38],[39]. Unlike their security proof being done in the random
oracle model, we provide a security proof in the standard
model (in Appendix A).

Proof. A detailed proof is described in Appendix A as
EGKEM and Theorem 2 are just our starting point. An outline is stated as follows. The CDH oracle enables the solver
S to simulate the adversary A1 ’s decapsulation oracle perfectly. After that the KEA extractor works to extract theanswer of a DL problem instance from A2 ’s return. (Notethat the Gap-DL assumption and the KEA are compatible.)
4.2 Discussion
It is well-known that El Gamal KEM EGKEM is one-way-PA
secure based on the CDH assumption. In contrast, Theorem
2 says a stronger fact though the assumptions are stronger
ones.
5.

A Tag-Based One-Way-CCA2 Secure KEM

In this section, owing the idea to the tag-based encryption

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1143
Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := gy• pk := (q, g, X, Y), sk := (q, g, x, y), return (pk, sk)
Tag-Receiving– Enc and Dec are given a tag t ∈ Zq
Encapsulation– Enc: given pk as an input;• a ← Zq , K := X a , h := ga , d := (X t Y)a , ψ := (h, d), return (K, ψ)
Decapsulation– Dec: given sk and ψ = (h, d) as an input;
 := h x else K
 :=⊥, return K• If htx+y  d then K
Fig. 4

A Tag-Based One-Way-CCA2 KEM: tKEM.

scheme of Kiltz [27], we apply a tag framework with thealgebraic trick of Boneh and Boyen [3] to El Gamal KEM
EGKEM to make it one-way-CCA2 secure.
5.1 A Tag-Based KEM and Its Security
A tag-based KEM tKEM consists of a triple (K, Enc, Dec).
The construction is shown in Fig. 4.
On an input 1k , the key generator K runs as follows. The
group generator Grp returns (q, g) on an input 1k . Then K
chooses x and y from Zq , computes X = g x and Y = gy , andsets pk = (q, g, X, Y) and sk = (q, g, x, y). Then K returns(pk, sk).
A string tag t is a priori given to Enc and Dec. In ourconstruction, we set the tag t in Zq .
On an input 1k , the encapsulation algorithm Enc runs
as follows. Enc chooses a from Zq at random, and computes
K = X a and h = ga . Additionally, Enc computes d = (X t Y)aand puts ψ = (h, d). The random string is K and its encapsulation is ψ. Enc returns the pair (K, ψ).
On an input sk and ψ = (h, d), the decapsulation algorithm Dec runs as follows. Dec verifies whether(g, X t Y, h, d) is a DH-tuple. For this sake, Dec checks
whether htx+y = d holds. If it does not hold, then Dec puts =⊥. Otherwise, Dec computes the decapsulation K
 = hx .
KThen Dec returns K.
The security of tKEM is stated as follows.
Theorem 3. The key encapsulation mechanism tKEM is
one-way-CCA2 secure in the selective tag model based on
the Gap-CDH assumption. More precisely, for any PPT adversary A there exists a PPT Gap-CDH problem solver S
which satisfies the following tight reduction.
stag-ow-cca2

AdvA,tKEM

gap-cdh(k)  AdvS,Grp (k).

5.2 Proof of Theorem 3
An outline is stated as follows. The algebraic trick of the
tag framework [3], [27] enables the solver S to simulate anadversary A’s decapsulation oracle perfectly. The algebraic
trick also enables S to embed a portion of a given CDH
problem instance in the challenge ciphertext. It is easy toGiven (q, g, V, W) as an input;
Initial Setting– Initialize its inner state– Invoke A on 1k and get a target tag: t∗ ← A(1k )∗– u ← Zq , X := V, Y := X −t gu , pk := (q, g, X, Y)
∗
∗
∗
a
∗
– a ∈ Zq , h = Wg , d = (h∗ )u , ψ∗ = (h∗ , d∗ )– Inputs (pk, ψ∗ ) into A
Answering A’s Queries and Extracting the Answer from Return– Receive a tag: t ← A– In the case that A queries DEC(sk, ·, ·) for the answer for (t, ψ =(h, d));
 :=⊥• If DDH(g, h, X t Y, d)  1 then K := (d/hu )1/(t−t∗ ) (: the case Simdec)• else K
 to A• Reply K∗ ;– In the case that A returns K∗ /X a∗• Return Z := K
Fig. 5

A Gap-CDH Problem Solver S for the Proof of Theorem 3.

extract the answer for the CDH problem instance from A’s
return.
Let us proceed in detail. Let A be as in Theorem 3.
Using A as a subroutine, we construct a Gap-CDH problem
solver S. The construction is illustrated in Fig. 5.
S is given q, g, V = gv , W = gw as a CDH problem
instance, where v and w are random and unknown to S. S
initializes its inner state. S invokes A on an input 1k andgets a target tag t∗ from A. S chooses u from Zq at random∗
and puts X = V and Y = X −t gu , sets pk = (q, g, X, Y). S∗
chooses a∗ from Zq at random and puts h∗ = Wga , d∗ =(h∗ )u and ψ∗ = (h∗ , d∗ ). S inputs pk and ψ∗ into A.
Note that pk is correctly distributed. Note also that S
knows neither x nor y, where x and y denote the discrete logof X and Y on a base g, respectively. Here the following
holds;
y = −t∗ x + u.
S replies A in answer to A’s queries as follows.
In the case that A queries DEC(sk, ·, ·) for the answer
for (t, ψ = (h, d)), S verifies whether (g, h, X t Y, d) is a DHtuple. For this sake, S queries its DDH oracle DDH for theanswer. If it is not satisfied then S puts K =⊥. Otherwise S
 = (d/hu )1/(t−t∗ ) (call this case Simdec). S replies Kputs K
to A. Note that, in the selective tag model, A is prohibitedfrom setting t = t∗ (that is, A must keep that t  t∗ ).
∗ /X a∗ .
∗ , S returns Z = K
In the case that A returns K
S is able to simulate the real view of A perfectly, as wesee below.
Firstly, the challenge ciphertext ψ∗ = (h∗ , d∗ ) is consistent and correctly distributed. This is because the distribution of ψ∗ = (h∗ , d∗ ) is equal to that of the real consistentciphertext ψ = (h, d). To see it, note that w+a∗ is substituted
for a;∗∗h∗ = Wga = gw+a ,
∗

∗

∗

∗

d∗ = (gw+a )u = (gu )w+a = (X t Y)w+a .
Secondly, in the case Simdec, S can simulate the decap-

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1144

 is
sulation oracle DEC(sk, ·, ·) perfectly. This is because Kxequal to h by the following equalities;∗∗∗

d/hu = htx+y−u = h(t−t )x+(t x+y−u) = h(t−t )x .
As a whole, S simulates the real view of A perfectly.
Now we evaluate the Gap-CDH advantage of S. If∗ ) is a DH-tuple and the following
A wins, then (g, h∗ , X, K
holds (note that we have set X = V, so x = v);
∗ = (g x )w+a∗ = gvw X a∗ .
K∗ /X a = gvw , which isHence the return Z is equal to K
the correct answer for the input (g, V, W). That is, S wins.
Therefore, the probability that S wins is lower bounded by
the probability that A wins;∗

Pr[S wins]  Pr[A wins].
That is;gap-cdhstag-ow-cca2

AdvS,Grp (k)  AdvA,tKEM(k). (Q.E.D.)

5.3 Discussion
We note that the selective tag model for security proofs iscompatible with our generic conversion. That is, the obtained ID scheme from tKEM is cMiM secure in the selective
tag model.
6.

A One-Way-CCA2 Secure KEM by the CHK Transformation

Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := gy• pk := (q, g, X, Y), sk := (q, g, x, y), return (pk, sk)
Encapsulation– Enc: given pk as an input;• (vk, sgk) ← SGK(1k )• a ← Zq , K := X a , h := ga , d := (X vk Y)a , σ ← Signsgk ((h, d))• ψ := (vk, (h, d), σ)• Return (K, ψ)– Dec: given sk and ψ = (vk, (h, d), σ) as an input; :=⊥ else K
 := h x• If Vrfyvk ((h, d), σ)  1 or h(vk)x+y  d then K• Return K
Fig. 6

A One-Way-CCA2 KEM by the CHK Transformation: KEM1.

On an input sk and ψ = (vk, (h, d), σ), the decapsulation algorithm Dec runs as follows. Dec verifies whether
the signature σ for the message (h, d) is valid under vk andwhether (g, X vk Y, h, d) is a DH-tuple. For the latter, Dec
checks whether h(vk)x+y = d holds. If at least one of them =⊥. Otherwise, Dec comdoes not hold then Dec puts K = h x . Then Dec returns K.
putes the decapsulation K
The security of KEM1 is stated as follows.
Theorem 4. The key encapsulation mechanism KEM1 is oneway-CCA2 secure based on the Gap-CDH assumption and
one-time security of a strong one-time signature employed.
More precisely, for any PPT adversary A there exist a PPT
Gap-CDH problem solver S and a PPT forger F which satisfy the following tight reduction.
gap-cdhIn this section, we apply a generic method, that is, the CHKtransformation [12], to the tag-based KEM tKEM to exit the
tag framework. Along the technique, we replace the tag t
by a one-time verification key vk of a strong one-time signature OTS. (The definition of strong one-time signatures issummarized in Appendix B.)
6.1 A KEM by the CHK Transformation and Its Security
A KEM KEM1 by the CHK transformation of the tag-based
KEM tKEMconsists of a triple (K, Enc, Dec). The construction is shown in Fig. 6.
On an input 1k , the key generator K runs as follows.
The group generator Grp returns (q, g) on an input 1k . Then
K chooses x and y from Zq , puts X = g x and Y = gy , and sets
pk = (q, g, X, Y) and sk = (q, g, x, y). Then K returns (pk,sk).
On an input 1k , the encapsulation algorithm Enc runs
as follows. Enc runs signing key generator SGK on an input
1k to get (vk, sgk), where vk is a verification key and sgk is
the matching signing key. Enc chooses a from Zq at random,and computes K = X a and h = ga . Enc computes d :=(X vk Y)a (here, if it is needed for OTS, we take a hash valueH(vk) of vk before the exponentiation so that H(vk) ∈ Zq ).
Enc runs Signsgk on message (h, d) to get a signature σ.
Enc puts ψ = (vk, (h, d), σ). The random string is K and its
encapsulation is ψ. Enc returns the pair (K, ψ).

euf-cmaAdvow-cca2
A,KEM1 (k)  AdvS,Grp (k) + AdvF ,OTS (k).

Proof. A detailed proof is described in Appendix C as it is anadaptation of the routine established by [12] to our situation.
An outline is stated as follows. The proof goes almost thesame way as the proof of Theorem 3 except that we haveto treat a case that the verification key vk∗ in the challenge
ciphertext is equal to a verification key vk in a decapsulation
query. The EUF-CMA property in the strong sense of a onetime signature employed assures that the case happens onlywith negligible probability.
6.2 Discussion
When we use a one-time signature such that |vk|  |q| = k,
we have to take a hash value H(vk) by a hash function H :{0, 1}∗ → Zq just before doing a computation in Zq . In thissetting, the security statement in Theorem 4 needs a target
collision resistance for {H} to make a collision case (that is,the case that vk  vk∗ and H(vk) = H(vk∗ )) negligible.
7.

A One-Way-CCA2 Secure KEM with a Target Collision Resistant Hash Function

In this section, depending on the specific structure, we use a
specific tool, that is, a target collision resistant hash function(a TCR hash function, for short) to exit the tag framework oftKEM. Along the technique, we replace the tag t by a TCR

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1145
Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), x, y ← Zq
• X := g x , Y := gy , κ ← Hkey(1k )• pk := (q, g, X, Y, κ), sk := (q, g, x, y, κ), return (pk, sk)
Encapsulation– Enc: given pk as an input;• a ← Zq , K := X a , h := ga , τ ← Hκ (h), d := (X τ Y)a• ψ := (h, d)• Return (K, ψ)
Decapsulation– Dec: given sk and ψ = (h, d) as an input;• τ ← Hκ (h) :=⊥ else K
 := h x• If hτx+y  d then K• Return K
Fig. 7

A One-Way-CCA2 KEM with a TCR Hash Function: KEM2.

hash function value. (The definition of a TCR hash function
family Hfam(1k ) = {Hκ }κ∈Hkey(1k ) is summarized in Appendix
D.)
7.1 A KEM with a TCR Hash Function and Its Security
A KEM KEM2 with TCR hash function consists of a triple(K, Enc, Dec). The construction is shown in Fig. 7.
On an input 1k , the key generator K runs as follows.
The group generator Grp returns (q, g) on an input 1k . Then
K chooses x and y from Zq and computes X = g x andY = gy . In addition, K chooses a hash key κ from a hash
key space Hkey(1k ). The hash key κ indicates a specifichash function Hκ with values in Zq in a hash function family Hfam(1k ) = {Hκ }κ∈Hkey(1k ) . K sets pk = (q, g, X, Y, κ) andsk = (q, g, x, y, κ). Then K returns (pk, sk).
On an input 1k , the encapsulation algorithm Enc runs
as follows. Enc chooses a from Zq at random and computes
h = ga . Enc computes the hash value τ ← Hκ (h) and computes d = (X τ Y)a . Enc puts ψ = (h, d). The random string
is K and its encapsulation is ψ. Then Enc returns the pair(K, ψ).
On an input sk and ψ = (h, d), the decapsulation algorithm Dec runs as follows. Dec computes the hash valueτ ← Hκ (h). Dec verifies whether the quadruple (g, X τ Y, h, d)
is a DH-tuple. For this sake, P checks whether hτx+y = d =⊥. Otherwise,holds. If it does not hold, then Dec puts Kx
Dec computes the decapsulation K = h . Then Dec returns
K.
The security of KEM2 is stated as follows.
Theorem 5. The key encapsulation mechanism KEM2 isone-way-CCA2 secure based on the Gap-CDH assumption
and the target collision resistance of a hash function family Hfam(1k ) = {Hκ }κ∈Hkey(1k ) . More precisely, for any PPTadversary A there exist a PPT Gap-CDH problem solver S
and a PPT collision-finder CF on Hfam which satisfy thefollowing tight reduction.
gap-cdhtcr
Advow-cca2
A,KEM2 (k)  AdvS,Grp (k) + AdvCF ,Hfam (k).

Given (q, g, V, W) as an input;
Initial Setting– Initialize its inner state∗– a∗ ← Zq , h∗ := Wga– κ ← Hkey(1k ), τ∗ ← Hκ (h∗ )∗– u ← Zq , X := V, Y := X −τ gu , d∗ = (h∗ )u∗– pk := (q, g, X, Y, κ), ψ := (h∗ , d∗ )– Invoke A on pk and ψ∗
Answering A’s Queries and Extracting the Answer from Return– In the case that A queries DEC(sk, ·) for the answer for ψ = (h, d);• τ ← Hκ (h) :=⊥• If DDH(g, X τ Y, h, d)  1 then K• else := (d/hu )1/(τ−τ∗ ) (: the case Simdec)
If τ  τ∗ then K
else abort (: the case Abort) to A• Reply K∗ ;– In the case that A returns K∗ /X a∗• Return Z := K
Fig. 8A Gap-CDH Problem Solver S for the Proof of Theorem 5.

7.2 Proof of Theorem 5
An outline is stated as follows. The proof goes almost thesame way as the proof of Theorem 3 except that we haveto treat a case that the hash value τ∗ of h∗ in the challenge
ciphertext is equal to a hash value τ of h in a decapsulation
query. The TCR property of a TCR hash function family
employed assures that the case happens only with negligible
probability.
Let us proceed in detail. Let A be as in Theorem 5.
Using A as a subroutine, we construct a Gap-CDH problem
solver S. The construction is illustrated in Fig. 8.
S is given q, g, V = gv , W = gw as an input, wherev and w are random and unknown to S. S initializes its
inner state. S chooses a∗ from Zq at random and computes∗h∗ = Wga . Then S chooses κ from Hkey(1k ) and computesτ∗ ← Hκ (h∗ ). S chooses u from Zq at random, puts X = V∗
and computes Y = X −τ gu and d∗ = (h∗ )u . S sets pk =(q, g, X, Y) and puts ψ∗ = (h∗ , d∗ ).
Note that pk is correctly distributed. Note also that S
knows neither x nor y, where x and y denote the discrete logof X and Y on a base g, respectively. Here the following
holds;
y = −τ∗ x + u.
S invokes A on an input (pk, ψ∗ ). S replies to A’s
queries as follows.
In the case that A queries its decapsulation oracle
DEC(sk, ·) for the answer for φ = (h, d), S computesτ ← Hκ (h). S verifies whether (g, X τ Y, h, d) is a DH-tuple.
For this sake, S queries its decision oracle DDH. If the =⊥. Otherwise, if τ  τ∗ ,answer is “False”, then S puts K
u 1/(τ−τ∗ )then S computes K = (d/h )(call this case Simdec).
If τ = τ∗ , then S aborts (call this case Abort). Then S
 to A except for the case Abort.
replies K∗ as the answer for ψ∗ , S
In the case that A returns K∗a∗
returns Z = K /X .

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 20121146

S is able to simulate the real view of A perfectly until
the case Abort happens, as we see below.
Firstly, the challenge ciphertext ψ∗ = (h∗ , d∗ ) is consistent and correctly distributed. This is because the distribution of ψ∗ = (h∗ , d∗ ) is equal to that of the real consistentciphertext ψ = (h, d). To see it, note that w+a∗ is substituted
for a;∗

 = hx =⊥. Otherwise, if τ  τ∗ , then CF replies K
CF sets K∗
to A. If τ = τ , then CF returns h and stops (call this caseCollision).
Note that the view of A in CF is the same as the realview until the case Collision happens. Especially, the viewof A in CF is the same as the view of A in S until the case
Abort or the case Collision happens. So we have:∗h∗ = Wga = gw+a ,∗w+a∗ ud = (gPr[Abort] = Pr[Collision].

u w+a∗) = (g )τ∗

w+a∗= (X Y).

Secondly, in the case Simdec, S can simulate the de
capsulation oracle DEC(sk, ·) perfectly. This is because K
is equal to h x by the following equalities;∗∗∗

d/hu = hτx+y−u = h(τ−τ )x+(τ x+y−u) = h(τ−τ )x .
As a whole, S simulates the real view of A perfectly
until the case Abort happens.
Now we evaluate the CDH advantage of S. When∗ ) is a DH-tuple, so the following holdA wins, (g, X, h∗ , K(note that we have set X = V, so x = v);
∗ = (g x )w+a = gvw X a .
K∗

Notice that the case Collision implies that the following
conditions hold;⎧⎪(g, X τ Y, h, d) is a DH-tuple
⎪
⎪
⎪
∗
⎨
and (g, X τ Y, h∗ , d∗ ) is a DH-tuple⎪⎪⎪⎪⎩and τ = τ∗ .
If in addition to the above conditions h were equal to h∗ , thend would be equal to d∗ , which would mean that A queried
the challenge ciphertext ψ∗ to its decapsulation oracle. Thisis ruled out. Hence it must hold thath  h∗ .

∗∗ /X a = gvw , which isHence the return Z is equal to K
the correct answer for the input (g, V, W). That is, S wins.
Therefore the probability that S wins is lower bounded by
the probability that A wins and Abort does not happen.
∗

Pr[S wins]  Pr[A wins ∧ ¬Abort] Pr[A wins] − Pr[Abort].
Hence we get the following inequality.
(k)  Advow-cca2
Advgap-cdh
A,KEM2 (k) − Pr[Abort].
S,Grp
So our task being left is to show that Pr[Abort] is negligible
in k.
Claim 7.1. The probability that Abort occurs is negligible
in k.

Namely, in the case Collision, CF succeeds in obtaining atarget collision. So we have:
Pr[Collision] = Advtcr
CF ,Hfam (k).
Combining the two equalities, we get
Pr[Abort] = Advtcr
CF ,Hfam (k).
The right hand side is negligible in k by the assumption in
Theorem 5. (Q.E.D.)
7.3 Discussion
As we will see in Sect. 9, the obtained ID scheme from
KEM2 shows the highest performance in both computationalamount and message length compared with previous ID
schemes secure against cMiM attacks.
8.

Proof of Claim 7.1. Using A as a subroutine, we constructa target collision finder CF on Hfam as follows. Given 1k
as an input, CF initializes its inner state. CF gets (q, g)from Grp(1k ). CF chooses a∗ from Zq at random, computes∗h∗ = ga and returns h∗ . CF receives a random hash key κand computes τ∗ ← Hκ (h∗ ). Then CF chooses x, y ∈ Zq
at random and computes X = g x , Y = gy . CF computes∗∗d∗ = (X τ Y)a and puts ψ∗ = (h∗ , d∗ ). Finally CF sets
pk = (q, g, X, Y, κ), sk = (q, g, x, y, κ) and invokes A on pk
and ψ∗ .
In the case that A queries its decapsulation oracle
DEC(sk, ·) for the answer for ψ = (h, d), CF computesτ ← Hκ (h) and verifies whether (g, X τ Y, h, d) is a DH-tuple.
CF does the same as an honest decapsulation algorithm does
because CF has the secret key sk. If it is not a DH-tuple,

A One-Way-CCA2 Secure KEM by the Twin DiﬃeHellman TechniqueIn this section, as it is better to rely on the CDH assumption
rather than the Gap-CDH assumption, we apply the Twin
DH technique of Cash, Kiltz and Shoup [13], [29] to KEM2.
An application of the Twin DH technique to KEM2 to get
KEM3 is not a “black box” and we do it by making the Twin
DH technique compatible with the algebraic trick of Bonehand Boyen [3] introducing necessary random variables.
8.1 A KEM by the Twin Diﬃe-Hellman Technique and Its
Security
A KEM KEM3 by the Twin Diﬃe-Hellman technique consists of a triple (K, Enc, Dec). The construction is shown inANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1147
Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), κ ← Hkey(1k )• x1 , x2 , y1 , y2 ← Zq , X1 := g x1 , X2 := g x2 , Y1 := gy1 , Y2 := gy2• pk := (q, g, X1 , X2 , Y1 , Y2 , κ), sk := (q, g, x1 , x2 , y1 , y2 , κ)
• Return (pk, sk)
Encapsulation– Enc: given pk as an input;• a ← Zq , h := ga , τ ← Hκ (h)• d1 := (X1τ Y1 )a , d2 := (X2τ Y2 )a , K := X1a , ψ = (h, d1 , d2 )• Return (K, ψ)
Decapsulation– Dec: given sk, ψ = (h, d1 , d2 ) as an input;• τ ← Hκ (h) :=⊥ else K
 := h x1• If hτx1 +y1  d1 or hτx2 +y2  d2 then K• Return K
Fig. 9A One-Way-CCA2 KEM by the Twin DH Technique: KEM3.

Fig. 9.
On an input 1k , the key generator K runs as follows. The
group generator Grp returns (q, g) on an input 1k . Then K
chooses x1 , x2 , y1 , y2 from Zq and computes X1 = g x1 , X2 =g x2 , Y1 = gy1 , Y2 = gy2 . In addition, K chooses a hash key κfrom a hash key space Hkey(1k ). The hash key κ indicates a
specific hash function Hκ with values in Zq in a hash function family Hfam(1k ). K sets pk = (q, g, X1 , X2 , Y1 , Y2 , κ) andsk = (q, g, x1 , x2 , y1 , y2 , κ). Then K returns (pk, sk).
On an input pk, the encapsulation algorithm Enc runs
as follows. Enc chooses a from Zq at random and computes
h = ga and the hash value τ ← Hκ (h). Then Enc computes
d1 = (X1τ Y1 )a , d2 = (X2τ Y2 )a and K = X1a . The random string
is K and its encapsulation is ψ = (h, d1 , d2 ). Note here that(g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple. Enc returns thepair (K, ψ).
On an input sk and ψ = (h, d1 , d2 ), the decapsulation algorithm Dec runs as follows. Dec computes
the hash value τ ← Hκ (h). Then Dec verifies whetherψ = (h, d1 , d2 ) is a consistent ciphertext, that is, whether(g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple or not. For thissake, Dec checks whether hτx1 +y1 = d1 and hτx2 +y2 = d2 hold.
 =⊥.
If at least one of them does not hold, then Dec puts Kx
 = h 1 . Then
Otherwise, Dec computes the decapsulation KDec returns K.
The security of KEM3 is stated as follows.
Theorem 6. The key encapsulation mechanism KEM3 isone-way-CCA2 secure based on the CDH assumption andthe target collision resistance of a hash function family employed. More precisely, for any PPT one-way-CCA2 adversary A on KEM3 that queries decapsulation oracle at mostqdec times, there exist a PPT CDH problem solver S on Grp
and a PPT collision-finder CF on Hfam which satisfy thefollowing tight reduction.
qdec
tcr+ Advcdh
Advow-cca2
A,KEM1 (k) S,Grp (k) + AdvCF ,Hfam (k).
q
8.2 Proof of Theorem 6
An outline is stated as follows. The proof goes almost theGiven (q, g, V, W) as an input;
Initial Setting– Initialize its inner state∗– a∗ ← Zq , h∗ := Wga– κ ← Hkey(1k ), τ∗ ← Hκ (h∗ )– r, s ← Zq , X1 := V, X2 := X1−r g s∗∗– u1 , u2 ← Zq , Y1 := X1−τ gu1 , Y2 := X2−τ gu2
∗
∗
u
∗
∗
u
1
2
– d1 := (h ) , d2 := (h )– pk := (q, g, X1 , X2 , Y1 , Y2 , κ), ψ∗ := (h∗ , d1∗ , d2∗ )– Invoke A on pk and ψ∗
Answering A’s Queries and Extracting the Answer from Return– In the case that A queries DEC(sk, ·) for the answer for ψ = (h, d1 , d2 ) :=⊥• If ψ = ψ∗ , then put K• else (: the case Consistency-Check)∗
Y := hτ−τ , Z1 := d1 /hu1 , Z2 := d2 /hu2τ ← Hκ (h), 
r
s




If Z1 Z2  Y , then K :=⊥else∗
 := Z1 1/(τ−τ ) (: the case Simdec)
If τ  τ∗ , then K
else abort (: the case Abort) to A• Reply K∗ as the answer for ψ∗– In the case that A returns K∗a∗• Return Z := K /X1
Fig. 10

A CDH Problem Solver S for the Proof of Theorem 6.

same way as the proof of Theorem 5 except that we have totreat an argument for the Trapdoor Test (Lemma 1) which
decides whether a given tuple is a twin DH tuple or not.
Let us proceed in detail. Let A be any given adversarythat attacks KEM3 in one-way-CCA2 setting. Using A as a
subroutine, we construct a PPT CDH problem solver S asshown in Fig. 10, where the algebraic trick [3] and the TwinDiﬃe-Hellman technique [13] are essentially used.
S is given q, g, V = gv , W = gw as an input, where v
and w are random and unknown to S. S initializes its innerstate. S chooses a∗ from Zq at random and computes h∗ =∗Wga . Then S chooses κ from Hkey(1k ) and computes τ∗ ←Hκ (h∗ ). S chooses r and s from Zq at random, and puts X1 =V, X2 = X1−r g s . S chooses u1 and u2 from Zq at random, and∗∗computes Y1 = X1−τ gu1 , Y2 = X2−τ gu2 . S computes d1∗ =(h∗ )u1 , d2∗ = (h∗ )u2 . S sets pk = (q, g, X1 , X2 , Y1 , Y2 , κ), ψ∗ =(h∗ , d1∗ , d2∗ ) and invokes A on an input (pk, ψ∗ ).
Note that pk is correctly distributed. Note also that S
does not know x1 , x2 , y1 , y2 at all, where x1 , x2 , y1 , y2 denotethe discrete log of X1 , X2 , Y1 , Y2 on a base g, respectively.
Here the following holds.
yi = −τ∗ xi + ui , i = 1, 2.

(1)

S replies to A’s queries as follows.
In the case that A queries its decapsulation oracle
DEC(sk, ·) for the answer for ψ = (h, d1 , d2 ), S checks =⊥.
whether ψ is equal to ψ∗ or not. If ψ = ψ∗ , then S puts K
Otherwise, S computes τ ← Hκ (h) and verifies whether ψ =(h, d1 , d2 ) is consistent or not (call this case ConsistencyCheck). That is, S verifies whether (g, X1τ Y1 , X2τ Y2 , h, d1 , d2 )∗is a twin DH tuple as follows. Put 
Y = hτ−τ , Z1 = d1 /hu1r
and Z2 = d2 /hu2 . If Z1 Z2  
Y s , then it is not a twin DH tu =⊥. Otherwise, S decides that it is a twinple and S puts K∗
 = Z1 1/(τ−τ ) (callDH tuple. Then, if τ  τ∗ , S computes K

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1148

this case Simdec). Otherwise (τ = τ∗ ), S aborts (call this to A except for the case Abort.
case Abort). S replies K
∗ /X a∗ .
∗ , S returns Z = K
In the case that A returns K
S is able to simulate the real view of A perfectly until
the case Abort happens, except for a negligible case, as wesee below.
Firstly, the challenge ciphertext ψ∗ = (h∗ , d1∗ , d2∗ ) is consistent and correctly distributed. This is because the distribution of ψ∗ = (h∗ , d1∗ , d2∗ ) is equal to that of the real consistent ciphertext ψ = (h, d1 , d2 ). To see it, note that w + a∗ issubstituted for a;∗∗h∗ = Wga = gw+a ,
∗

∗

∗

∗

di∗ = (gw+a )ui = (gui )w+a = (Xiτ Yi )w+a , i = 1, 2.
Secondly, S can simulate the decapsulation oracle
DEC(sk, ·) perfectly except for a negligible case. To see it,note that the consistency check really works though it may
involve a negligible error case, which is explained by thefollowing two claims.
Claim 8.1. (g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple if
and only if (g, X1 , X2 , 
Y, Z1 , Z2 ) is a twin DH tuple forτ−τ∗ 
u1
Y = h , Z1 = d1 /h and Z2 = d2 /hu2 .
Proof of Claim 8.1. This claim is proven by direct calculations. See Appendix E.
r∗
Y s holds for 
Y = hτ−τ , Z1 = d1 /hu1
Claim 8.2. If Z1 Z2 = and Z2 = d2 /hu2 , then (g, X1 , X2 , 
Y, Z1 , Z2 ) is a twin DH tuple except for an error case that occurs at most 1/q probaY, Z1 , Z2 ) is a twin DH tuple,
bility. Conversely, if (g, X1 , X2 , 
r
s



then Z1 Z2 = Y certainly holds.
∗
Proof of Claim 8.2. We observe that each of 
Y = hτ−τ , Z1 =u1
u2
d1 /h and Z2 = d2 /h is given independently of r. So we
can apply Lemma 1 in Sect. 2. (Q.E.D.)

negligible case Overlook), so d1 = hτx1 +y1 holds. If, in addition, S is in the case
Simdec (that is, τ  τ∗ ), then the1/(τ−τ∗ ) = Z1of S to A is correct. This is because
answer K
 = (d1 /hu1 )1/(τ−τ∗ ) is equal to h x1 by the following equaliK
ties.
∗

∗

∗

d1 /hu1 = hτx1 +y1 −u1 = h(τ−τ )x1 +(τ x1 +y1 −u1 ) = h(τ−τ )x1 ,where we use the equality (1).
As a whole, S simulates the real view of A perfectly
until the case Abort happens except for the negligible case
Overlook.
Now we evaluate the CDH advantage of S. When A∗ ) is a DH tuple, so the following holds
wins, (g, X1 , h∗ , K(note that we have set X1 = V, so x1 = v);
∗ = g x1 (w+a∗ ) = gvw X1a∗ .
K∗ /X a = gvw , which isHence the return Z is equal to K1
the correct answer for the input (g, V, W). That is, S wins.
Therefore, the probability that S wins is lower bounded by
the probability that A wins, Overlooki never occurs for
i = 1, . . . , qdec and Abort does not happen:∗

Pr[S wins]⎡⎞⎛ qdec
⎤
⎢⎢⎢
⎟⎟⎟
⎜⎜⎜
⎥⎥
 Pr ⎢⎢⎣A wins ∧ ⎜⎜⎝ (¬Overlooki )⎟⎟⎠ ∧ (¬Abort)⎥⎥⎥⎦
i=1⎞⎤⎡⎛ qdec⎟⎟⎟⎥⎥⎢⎢⎢⎜⎜⎜⎟⎢⎜
 Pr[A wins] − Pr ⎢⎣⎜⎝ Overlooki ⎟⎠ ∨ Abort⎥⎥⎥⎦i=1= Pr[A wins]⎤⎞⎡⎛ qdec⎤⎞⎛ ⎡ qdec⎥⎥⎥⎟⎟⎟⎢⎢⎢⎜⎜⎜⎥⎥⎟⎟⎜⎜⎜ ⎢⎢⎢⎥⎟⎢⎜⎜⎢− ⎜⎝Pr ⎢⎣ Overlooki ⎥⎦ + Pr ⎢⎣⎜⎝ (¬Overlooki )⎟⎠ ∧ Abort⎥⎥⎥⎦⎟⎟⎟⎠ .
i=1

i=1

Using the inequality (2), we get:Let us define the event Overlook as:⎧r⎪
Y s holds
Z1 Z2 = 
⎪
⎪
⎪
def ⎨
Overlook = ⎪and (g, X1 , X2 , 
Y, Z1 , Z2 ) is not⎪⎪⎪⎩a twin DH tuple.

qdec
ow-cca2
AdvcdhS,Grp (k) AdvA,KEM3 (k) −q⎡⎛ qdec⎞⎤⎢⎢⎢⎜⎜⎜
⎟⎟⎟
⎥⎥
⎢
⎟
⎜
− Pr ⎢⎣⎜⎝ (¬Overlooki )⎟⎠ ∧ Abort⎥⎥⎥⎦ .

Then, by Claim 8.2, the probability that Overlook occurs is
at most 1/q for each consistency check. So for at most qdec
consistency checks, Consistency-Checki , i = 1, . . . , qdec , theprobability that at least one corresponding Overlooki occurs
is at most qdec /q. That is;⎤⎡ qdec⎥⎥ qdec⎢⎢⎢⎢.
(2)
Pr ⎢⎣ Overlooki ⎥⎥⎥⎦ qi=1

So our task being left is to show that the last term probability is negligible in k.
qdec(¬Overlooki )) ∧Claim 8.3. The probability that ( i=1
Abort occurs is negligible in k.

qdec is polynomial and q is exponential in k, so the right handside is negligible in k.
Suppose S has confirmed that a decapsulation queryψ = (h, d1 , d2 ) passed the consistency check. In that case,(g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple (except for ai=1

Proof of Claim 8.3. Using A as a subroutine, we construct a PPT target collision finder CF on Hfam as follows. Given 1k as an input, CF initializes its inner state.
CF gets (q, g) from Grp(1k ). CF chooses a∗ ∈ Zq at ran∗dom, computes h∗ = ga and outputs h∗ . CF receives arandom hash key κ and computes τ∗ ← Hκ (h∗ ). Then
CF makes a secret key and public key honestly by itself:
sk = (q, g, x1 , x2 , y1 , y2 , κ), pk = (q, g, X1 , X2 , Y1 , Y2 , κ). Fi∗∗∗∗
nally, CF computes d1∗ = (X1τ Y1 )a , d2∗ = (X2τ Y2 )a and puts

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1149

ψ∗ = (h∗ , d1∗ , d2∗ ). CF invokes A on pk and ψ∗ .
In the case that A queries its decapsulation oracle
DEC(sk, ·) for the answer for ψ = (h, d1 , d2 ), CF checks
whether ψ is equal to ψ∗ or not. If ψ = ψ∗ , then CF replies
K =⊥ to A. Otherwise (ψ  ψ∗ ), CF computes τ ← Hκ (h)and verifies whether ψ = (h, d1 , d2 ) is consistent. CF can doit in the same way as Dec does because CF has the secretkey sk. If it is not consistent, CF replies K =⊥ to A. Otherwise, if τ  τ∗ , then CF replies K = h x1 to A. Else if τ = τ∗ ,then CF returns h and stops (call this case Collision).
The view of A in CF is the same as the real view until
the case Collision happens.
Observe here the following. If Overlook never occurs
in S, then only consistent queries (ψs) have the chance tocause a collision (τ = τ∗ ) as is the case in CF . Hence wehave:⎡⎛ qdec⎞⎤⎢⎢⎢⎜⎜⎜
⎟⎟⎟
⎥⎥
⎢
⎟
⎜
Pr ⎢⎣⎜⎝ (¬Overlooki )⎟⎠ ∧ Abort⎥⎥⎥⎦  Pr[Collision]. (3)i=1

On the other hand, notice that Collision implies thefollowing.
⎧∗∗⎪(g, X1τ Y1 , X2τ Y2 , h∗ , d1∗ , d2∗ ): a twin DH tuple⎪⎪⎪⎨and ∃(g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ): a twin DH tuple⎪⎪⎪⎪⎩and τ = τ∗ .
If in addition to the above conditions h were equal to h∗ , then(d1 , d2 ) would be equal to (d1∗ , d2∗ ), which would mean that
A queried the challenge ciphertext ψ∗ to its decapsulation
oracle. This is ruled out. Hence it must hold that:h  h∗ .
Namely, in the case Collision, CF succeeds in obtaining atarget collision. So we have:
Pr[Collision] = Advtcr
CF ,Hfam (k).

(4)

Combining (3) and (4), we get⎞⎡⎛ qdec⎤⎟⎟⎟⎢⎢⎢⎜⎜⎜⎥⎥Pr ⎢⎢⎣⎜⎜⎝ (¬Overlooki )⎟⎟⎠ ∧ Abort⎥⎥⎥⎦  Advtcr

CF ,Hfam (k).

i=1

The right hand side is negligible in k by the assumption in
Theorem 6. (Q.E.D.)
8.3 Discussion
To reduce the length of ciphertext ψ = (h, d1 , d2 ), we can replace the term d2 with its hash value v2 := Hκ (d2 ). Let us callthis KEM KEM3̃. The security statement and the obtained ID
scheme is described in Appendix F.
9.

Eﬃciency Comparison

In this section, we evaluate the eﬃciency of the ID schemes

from our KEMs comparing with other ID schemes, especially, which are secure against concurrent man-in-themiddle attacks in the standard model. Among ID schemes
secure against concurrent man-in-the-middle attacks, theID scheme from KEM2 shows the highest performance inboth computational amount and message length. Among ID
schemes whose security is based on the CDH assumption,
the ID scheme from KEM3̃ shows the highest performance inboth.
Comparable ID schemes are divided into four categories. The first category is Σ-protocols, the second category is challenge-and-response ID schemes obtained from
EUF-CMA secure signature schemes, the third category is
the ones obtained from IND-CCA2 secure (non-hybrid) encryption schemes and the fourth category is the ones obtained from KEMs.
In the first category, to the best of our knowledge, theGennaro scheme [20] is the most eﬃcient. Here we consider
one of the schemes in [20], that is, the Schnorr ID scheme
plus a multi-trapdoor commitment scheme in the RSA setting. But it is no more eﬃcient than the ID scheme obtained
from the Cramer-Shoup encryption [14] (Cramer-Shoup ID,
for short).
In the second category, all the known signatureschemes in the standard model, including the Short Signature [4] and the Waters Signature [40], are costly as ID
schemes than Cramer-Shoup ID.
In the third category, Cramer-Shoup ID is the most efficient.
In the fourth category, Cramer-Shoup KEM (CS3b in[15]) (which we denote as CSKEM), which is IND-CCA2 secure based on the DDH assumption, is the most eﬃcient. We
remark that the KEM part of Kurosawa-Desmedt hybrid encryption scheme [30] is not comparable because the KEM
is not one-way-CCA2 secure [23]. Among ID schemes
whose security is based on the CDH assumption, an ID
scheme from the one-way-CCA2 secure KEM of HanaokaKurosawa [24] (which we denote as HKKEM) is the mostcomparable.
Table 2 shows a comparison of these ID schemes, plus
the Schnorr ID scheme and an ID scheme from El Gamal
KEM, with the ID schemes from our KEMs.
In Table 2, we compare computational amount by
counting the number of exponentiations in a prover P anda verifier V. We also compare the maximum message length.
In Computational Amount column, notation (s, t) or(s, t, u) means that the prover P or the verifier V includes
s single exponentiations, t double exponentiations and u
triple exponentiations of the form ga , ga hb and ga hb ic , respectively.
A simple estimation, which is denoted by index 1, isdone by evaluating the amount of a double and a triple exponentiation as two times and three times as large as theamount of a single exponentiation, respectively. That is, thetotal amount T 1 (P) for a prover P and T 1 (V) for a verifier V

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1150
Table 2 Eﬃciency Comparison of the ID Schemes from Our KEMs with Previous ID Schemes andKEMs.
OMDL, GDL, SDH, GCDH and SRSA mean assumptions of the One-More DL, the Gap-DL, the Strong
DH, the Gap-CDH and the Strong RSA, respectively.
OW-CCA* means the one-way-CCA* security and ca means concurrent (two-phase) attack.
(s, t) (or (s, t, u)) means s single exponentiations, t double exponentiations (and u triple exponentiations).
kg and vf mean a key generation and a verification of a one-time signature, respectively.
T 1 (P) := s + 2t and T 1 (V) := s + 2t + 3u (plus 0.1 or 0.05 for kg or vf, respectively) andT 2 (P) := s + 1.75t and T 2 (V) := s + 1.75t + 1.875u (plus 0.1 or 0.05 for kg or vf, respectively).
T 1 := T 1 (P) + T 1 (V) and T 2 := T 2 (P) + T 2 (V).
G and h mean an element in Gq and a hash value in Zq , respectively.
vk and σ mean a verification key and a signature of a one-time signature, respectively.
ID Sch.
or KEM
SchID
GenID
EGKEM
CSKEM
HKKEM
Our tKEM
Our KEM1
Our KEM2
Our KEM3
Our KEM3̃

Security
Security
Security
Assump.
as KEM
as ID Sch.
OMDL
ca
DL&SRSAcMiM
GDL&KEA OW-CCA1
ca
DDH
IND-CCA2cMiM
CDH
OW-CCA2
cMiM
GCDH(stag) OW-CCA2
cMiM
GCDH
OW-CCA2cMiM
GCDH
OW-CCA2
cMiM
CDH
OW-CCA2
cMiM
CDH
OW-CCA2
cMiM

P
(1,0)
(3,1)+kg
(1,0)
(3,0)
(3,0)
(2,0)
(2,0)+vf
(2,0)
(3,0)
(3,0)

are evaluated as s + 2t and s + 2t + 3u times as large as asignal exponentiation, respectively.
When some techniques for exponentiations are applicable, better estimations can be achieved. Here we only consider a basic technique for modular exponentiations by El
Gamal and Shamir [18], [42]. By that technique, a double
exponentiation is 1.75 times as large as a single exponentiation and a triple exponentiation is 1.875 times as large as asingle exponentiation. As a result, T 1 (P) and T 1 (V) are evaluated as s + 1.75t and s + 1.75t + 1.875u times as large as asingle exponentiation, respectively.
We note that a one-time signature does not cost somuch. In Table 2, the Lamport signature [31] in mind, we
estimate that a key generation and a verification amount to
at most 0.10 times and 0.05 times as large as a single exponentiation, respectively (see [9], for example).
T 1 and T 2 in Computational Amount column of Table 2
show total computational amount for each ID scheme. That
is, T 1 = T 1 (P) + T 1 (V) and T 2 = T 2 (P) + T 2 (V).
As shown in the column, the ID scheme from our KEM2
achieves T 1 = 6.00, T 2 = 5.75 with the maximum message length 2G, which is the highest performance among
ID schemes secure against cMiM attacks.
Also, the ID scheme from our KEM3̃ shows the highest performance in both computational amount (T 1 =9.00, T 2 = 8.50) and message length (2G + h) among ID
schemes secure against cMiM attacks based on the CDH assumption. Our KEM3̃ reduces T 1 by 2.00 exponentiations andT 2 by 0.25 exponentiations from those of HKKEM.
10.

Conclusions

We proposed a generic conversion from a KEM to an ID
scheme. Then, starting with El Gamal KEM, we develop aseries of five one-way-CCA2 secure KEMs applying tech-Computational AmountT 1 (P) T 2 (P)V
T 1 (V) T 2 (V)1.00 1.00(0,1,0)2.00 1.75
5.10 4.85 ( 12 ,2,0)+vf 4.55 4.05
1.00 1.00(2,0,0)2.00 2.00
3.00 3.00(3,1,0)5.00 4.75
3.00 3.00(2,0,2)8.00 5.75
2.00 2.00(2,1,0)4.00 3.75
2.05 2.05 (2,1,0)+kg 4.10 3.85
2.00 2.00(2,1,0)4.00 3.75
3.00 3.00(2,2,0)6.00 5.50
3.00 3.00(2,2,0)6.00 5.50

T1
3.00
9.65
3.00
8.00
11.00
6.00
6.15
6.00
9.00
9.00

T2
2.75
8.90
3.00
7.75
8.75
5.75
5.90
5.75
8.50
8.50

Max.Msg.
LengthG
G + vkG
3G
3G
2G
2G + vk + σ
2G
3G
2G + hniques such as the selective tag with the algebraic trick[3], [27], the CHK transformation [12], the target collisionresistant hash functions, the Twin Diﬃe-Hellman technique[13] and a modification for shortening message length. The
ID schemes from our KEMs show the highest performancein both computational amount and message length compared with previous ID schemes secure against cMiM attacks.
Acknowledgements
We appreciate sincere suggestions oﬀered by Prof. Kiltz[29] and we would like to thank Prof. Kurosawa for inspiring words, both at ProvSec 2010. We also thank anonymous
reviewers of AfricaCrypt 2011 for careful reading and valuable comments.
References[1] H. Anada and S. Arita, “Identification schemes of proofs of ability
secure against concurrent man-in-the-middle attacks,” Proc. ProvSec
2010, Malacca, Malaysia, Oct. 2010, Lect. Notes Comput. Sci.,
vol.6402, pp.18–34, Springer-Verlag, Heidelberg, Germany.
[2] H. Anada and S. Arita, “Identification schemes from key encapsulation mechanisms,” Proc. AFRICACRYPT 2011, Dakar, Senegal,
July 2011, Lect. Notes Comput. Sci., vol.6737, pp.59–76, SpringerVerlag, Heidelberg, Germany.
[3] D. Boneh and X. Boyen, “Eﬃcient selective-ID secure identitybased encryption without random oracles,” Proc. EUROCRYPT
2004, Interlaken, Switzerland, May 2004, Lect. Notes Comput. Sci.,
vol.3027, pp.223–238, Springer-Verlag, Heidelberg, Germany.
[4] D. Boneh and X. Boyen, “Short signatures without random oracles,”Proc. EUROCRYPT 2004, Interlaken, Switzerland, May 2004, Lect.
Notes Comput. Sci., vol.3027, pp.56–73, Springer-Verlag, Heidelberg, Germany.
[5] M. Bellare, M. Fischlin, S. Goldwasser, and S. Micali, “Identification protocols secure against reset attacks,” Proc. EUROCRYPT
2001, Innsbruck, Austria, May 2001, Lect. Notes Comput. Sci.,

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1151

vol.2045, pp.495–511, Springer-Verlag, Heidelberg, Germany.
[6] M. Bellare and O. Goldreich, “On defining proofs of knowledge,”
Proc. CRYPTO’92, Santa Barbara, CA, USA, Aug. 1992, Lect.
Notes Comput. Sci., vol.740, pp.390–420, Springer-Verlag, Heidelberg, Germany.
[7] M. Bellare and A. Palacio, “GQ and Schnorr identification schemes:
Proofs of security against impersonation under active and concurrent
attacks,” Proc. CRYPTO 2002, Santa Barbara, CA, USA, Aug. 2002,
Lect. Notes Comput. Sci., vol.2442, pp.162–177, Springer-Verlag,
Heidelberg, Germany.
[8] M. Bellare and A. Palacio, “The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols,” Proc. CRYPTO 2004,
Santa Barbara, CA, USA, Aug. 2004, Lect. Notes Comput. Sci.,
vol.3152, pp.273–289, Springer-Verlag, Heidelberg, Germany.
[9] M. Bellare and S. Shoup, “Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles,” Proc.
PKC 2007, Beijing, China, April 2007, Lect. Notes Comput. Sci.,
vol.4450, pp.201–216, Springer-Verlag, Heidelberg, Germany.
[10] R. Canetti and R.R. Dakdouk, “Extractable perfectly one-way functions,” Proc. ICALP 2008, Reykjavik, Iceland, July 2008, Lect.
Notes Comput. Sci., vol.5126, pp.449–460, Springer-Verlag, Heidelberg, Germany.
[11] R. Cramer, I. Damgård, and J.B. Nielsen, “Multiparty computation from threshold homomorphic encryption,” Proc. EUROCRYPT
2001, Innsbruck, Austria, May 2001, Lect. Notes Comput. Sci.,
vol.2045, pp.280–300, Springer-Verlag, Heidelberg, Germany.
[12] R. Canetti, S. Halevi, and J. Katz, “Chosen-ciphertext security
from identity-based encryption,” Proc. EUROCRYPT 2004, Interlaken, Switzerland, May 2004, Lect. Notes Comput. Sci., vol.3027,
pp.207–222, Springer-Verlag, Heidelberg, Germany.
[13] D. Cash, E. Kiltz, and V. Shoup, “The twin Diﬃe-Hellman problem
and applications,” Proc. EUROCRYPT 2008, Istanbul, Turkey, April
2008, Lect. Notes Comput. Sci., vol.4965, pp.127–145, SpringerVerlag, Heidelberg, Germany. Full version available at Cryptology
ePrint Archive, 2008/067, http://eprint.iacr.org/[14] R. Cramer and V. Shoup, “A practical public key cryptosystemprovably secure against adaptive chosen ciphertext attack,” Proc.
CRYPTO’98, Santa Barbara, CA, USA, Aug. 1998, Lect. Notes
Comput. Sci., vol.1462, pp.13–25, Springer-Verlag, Heidelberg,
Germany.
[15] R. Cramer and V. Shoup, “Design and analysis of practical publickey encryption schemes secure against adaptive chosen ciphertext
attack,” SIAM J. Comput., vol.33, no.1, pp.167–226, Aug. 2003.
[16] R.R. Dakdouk, Theory and Application of Extractable Functions,
Doctor of Philosophy Dissertation, Yale University, New Haven, CT,
USA, 2009.
[17] I. Damgård, “Towards practical public key systems secure against
chosen ciphertext attacks,” Proc. CRYPTO’91, Santa Barbara, CA,
USA, Aug. 1991, Lect. Notes Comput. Sci., vol.576, pp.445–456,
Springer-Verlag, Heidelberg, Germany.
[18] T. El Gamal, “A public key cryptosystem and a signature scheme
based on discrete logarithms,” Proc. CRYPTO’84, Santa Barbara,
California, USA, Aug. 1984, Lect. Notes Comput. Sci., vol.196,
pp.10–18, Springer-Verlag, Heidelberg, Germany.
[19] E. Fujisaki, “New constructions of eﬃcient simulation-sound commitments using encryption,” Proc. 2011 Symposium on Cryptography and Information Security, SCIS 2011, Kokura, Japan, Jan. 2011,
1A2-3, The Institute of Electronics, Information and Communication Engineers, Tokyo, Japan.
[20] R. Gennaro, “Multi-trapdoor commitments and their applications to
non-malleable protocols,” Proc. CRYPTO 2004, Santa Barbara, CA,
USA, Aug. 2004, Lect. Notes Comput. Sci., vol.3152, pp.220–236,
Springer-Verlag, Heidelberg, Germany.
[21] S. Goldwasser, S. Micali, and C. Rackoﬀ, “The knowledge complexity of interactive proof systems,” SIAM J. Comput., vol.18, no.1,
pp.186–208, Feb. 1989.
[22] L. Guillou and J.J. Quisquater, “A paradoxical identity-based sig-

nature scheme resulting from zero-knowledge,” Proc. CRYPTO’88,
Santa Barbara, CA, USA, Aug. 1988, Lect. Notes Comput. Sci.,
vol.403, pp.216–231, Springer-Verlag, Heidelberg, Germany.
[23] J. Herranz, D. Hofheinz, and E. Kiltz, “The Kurosawa-Desmedt key
encapsulation is not chosen-ciphertext secure,” Cryptology ePrint
Archive, 2006/207, http://eprint.iacr.org/[24] G. Hanaoka and K. Kurosawa, “Eﬃcient chosen ciphertext securepublic key encryption under the computational Diﬃe-Hellman assumption,” Proc. ASIACRYPT 2008, Melbourne, Australia, Dec.
2008, Lect. Notes Comput. Sci., vol.5350, pp.308–325, SpringerVerlag, Heidelberg, Germany. Full version available at Cryptology
ePrint Archive, 2008/211, http://eprint.iacr.org/[25] J. Katz, Eﬃcient Cryptographic Protocols Preventing “Man-in-theMiddle” Attacks, Doctor of Philosophy Dissertation, Columbia University, New York, NY, USA, 2002.
[26] J. Katz, “Eﬃcient and non-malleable proofs of plaintext knowledge
and applications,” Proc. EUROCRYPT 2003, Warsaw, Poland, May
2003, Lect. Notes Comput. Sci., vol.2656, pp.211–228, SpringerVerlag, Heidelberg, Germany.
[27] E. Kiltz, “Chosen-ciphertext security from tag-based encryption,”
Proc. TCC 2006, New York, NY, USA, March 2006, Lect. Notes
Comput. Sci., vol.3876, pp.581–600, Springer-Verlag, Heidelberg,
Germany.
[28] E. Kiltz, “Chosen-ciphertext security from hashed gap DiﬃeHellman,” Proc. PKC 2007, New York, NY, USA, March 2006,
Lect. Notes Comput. Sci., vol.3876, pp.581–600, Springer-Verlag,
Heidelberg, Germany.
[29] E. Kiltz, Personal communication at ProvSec 2010, Malacca, 2010.
[30] K. Kurosawa and Y. Desmedt, “A new paradigm of hybrid encryption scheme,” Proc. CRYPTO 2004, Santa Barbara, CA, USA, Aug.
2004, Lect. Notes Comput. Sci., vol.3152, pp.426–442, SpringerVerlag, Heidelberg, Germany.
[31] L. Lamport, “Constructing digital signatures from a one-way function,” Technical Report SRI-CSL-98, SRI International Computer
Science Laboratory, Oct. 1979.
[32] U. Maurer and S. Wolf, “Lower bounds on generic algorithms ingroups,” Proc. EUROCRYPT’98, Espoo, Finland, May-June 1998,
Lect. Notes Comput. Sci., vol.1403, pp.72–84, Springer-Verlag,
Heidelberg, Germany.
[33] M. Naor and M. Yung, “Universal one-way hash functions and theircryptographic applications,” Proc. 21st Symposium on Theory ofComputing, Seattle, Washington, USA, May 1989, pp.33–43, Association for Computing Machinery, New York, USA.
[34] T. Okamoto and D. Pointcheval, “The gap-problems: A new classof problems for the security of cryptographic schemes,” Proc. PKC
2001, Cheju Island, Korea, Feb. 2001, Lect. Notes Comput. Sci.,
vol.1992, pp.104–118, Springer-Verlag, Heidelberg, Germany.
[35] D. Pointcheval, “Chosen-ciphertext security for any one-way cryptosystem,” Proc. PKC 2000, Melbourne, Victoria, Australia, Jan.
2000, Lect. Notes Comput. Sci., vol.1751, pp.129–146, SpringerVerlag, Heidelberg, Germany.
[36] J. Rompel, “One-way functions are necessary and suﬃcient for secure signatures,” Proc. 22nd Annual Symposium on Theory of Computing, Baltimore, MD, USA, May 1990, pp.387–384, Association
for Computing Machinery, New York, USA.
[37] C.P. Schnorr, “Eﬃcient identification and signatures for smart
cards,” Proc. CRYPTO’89, Santa Barbara, CA, USA, Aug. 1989,
Lect. Notes Comput. Sci., vol.435, pp.239–252, Springer-Verlag,
Heidelberg, Germany.
[38] D.R. Stinson and J. Wu, “An eﬃcient and secure two-flow zeroknowledge identification protocol,” J. Mathematical Cryptology,
vol.1, no.3, pp.201–220, Aug. 2007.
[39] J. Wu and D.R. Stinson, “An eﬃcient identification protocol and theknowledge-of-exponent assumption,” Cryptology ePrint Archive,
2007/479, http://eprint.iacr.org/[40] B. Waters, “Eﬃcient identity-based encryption without random oracles,” Proc. EUROCRYPT 2005, Aarhus, Denmark, May 2005,

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 2012

1152

Lect. Notes Comput. Sci., vol.3494, pp.114–127, Springer-Verlag,
Heidelberg, Germany.
[41] S. Yilek, “Resettable public-key encryption: How to encrypt on
a virtual machine,” Proc. the Cryptographers’ Track at the RSA
Conference 2010, San Francisco, CA, USA, March 2010, Lect.
Notes Comput. Sci., vol.5985, pp.41–56, Springer-Verlag, Heidelberg, Germany.
[42] S.M. Yen, C.S. Laih, and A.K. Lenstra, “Multi-exponentiation,” IEE
Proc. Computers and Digital Techniques, vol.141, no.6, pp.325–326,
Nov. 1994.

Appendix A: Proof of Theorem 2
Let A = (A1 , A2 ) be as in Theorem 2. Using A as a subroutine, we construct a Gap-DL problem solver S. The construction is illustrated in Fig. A· 1.
S is given q, g, X = g x as a DL problem instance, where
x is random and unknown to S. S initializes its inner state,sets pk = (q, g, X) and invokes A1 on an input pk.
In the first phase, in the case that A1 queries its decapsulation oracle DEC(sk, ·) for the answer for ψ = h, S
queries its CDH oracle CDH for the answer for a CDH
problem instance (g, h, X) and gets Z as a reply. Then S
 = Z to A. In the case that A1 returns the inner
replies K
state st, S ends the first phase and proceeds to the second
phase.
In the second phase, S chooses a∗ from Zq at random∗
and computes ψ∗ = h∗ = ga . Then S invokes A2 on an input∗ , S invokes the KEA(st, ψ∗ ). In the case that A2 returns K∗
extractor H on (g, h , st). Here H is the KEA extractor
associated with the algorithm H below.
H(g, h∗ , st) :∗ , return(g, h∗ , X, Z).
∗ ← A2 (st, h∗ ), Z := K
K
Note that the auxiliary input st is independent of h∗ .
If H returns x∗ , then S returns x∗ .
It is obvious that S simulates A’s decapsulation oracle
DEC(sk, ·) perfectly with the aid of CDH oracle CDH.
Now we evaluate the Gap-DL advantage of S. Let Ext∗
denote the event that g x = X holds (that is, H succeeds in∗extracting the exponent of g x = X). If Ext occurs, then thesolver S wins. So we have:
Pr[S wins] Pr[Ext].
Then we do the following deformation;
Pr[S wins]
 Pr[A wins ∧ Ext] + Pr[¬(A wins) ∧ Ext] Pr[A wins ∧ Ext]
= Pr[A wins] − Pr[A wins ∧ ¬Ext].
∗ = Z = X a holds. Therefore;
Here A wins if and only if K∗∗∗

Pr[S wins]  Pr[A wins] − Pr[X a = Z ∧ g x  X].
That means what we want.
gap-dlkea
AdvS,Grp (k)  Advow-cca1
A,EGKEM (k) − AdvH,H ,Grp (k).

(Q.E.D.)
Appendix B: One-Time Signatures
A one-time signature OTS is a triple of PPT algorithms(SGK, Sign, Vrfy). SGK is a signing key generator which
returns a pair (vk, sgk) of a verification key and a matching signing key on an input 1k . Sign and Vrfy are a signing algorithm and a verification algorithm, respectively. We
require OTS to be existentially unforgeable against chosenmessage attack by any PPT forger F (the EUF-CMA property). The following experiment represents the strong version.
kExprmteuf-cma
F ,OTS (1 )(vk, sgk) ← SGK(1k ), m ← F (vk), σ ← Signsgk (m),(m , σ ) ← F (vk, (m, σ))
If Vrfyvk (m , σ ) = 1 ∧ (m , σ )  (m, σ)then return Win else return Lose.
We define the EUF-CMA advantage of F over OTS in thestrong sense as follows.
def

Given (q, g, X) as an input;
Initial Setting– Initialize its inner state– pk := (q, g, X), invoke A1 on pk
The First Phase : Answering A1 ’s Queries– In the case that A1 queries DEC(sk, ·) for the answer for ψ = h;
 := Z to A1• Z ← CDH(g, h, X), reply K– In the case that A1 returns the inner state st;• Proceed to the Second Phase
The Second Phase : Extracting the Answer from A2 ’s Return∗• a∗ ← Zq , ψ∗ := h∗ := ga∗• Invoke A2 on (st, ψ )∗ ;– In the case that A2 returns K∗• Invoke H on (g, h , st) : x∗ ← H (g, h∗ , st)• Return x∗
Fig. A· 1

A Gap-DL Problem Solver S for the Proof of Theorem 2.

euf-cma k
Adveuf-cma
F ,OTS (k) = Pr[ExprmtF ,OTS (1 ) returns Win].

We say that OTS has the one-time security in the strong sense
if, for any PPT algorithm F , Adveuf-cma
F ,OTS (k) is negligible in k.
We also say that OTS is a strong one-time signature, or, OTS
has the EUF-CMA property in the strong sense.
One-time signatures can be constructed based on theexistence of a one-way function (for example, [31]).
Appendix C: Proof of Theorem 4
Let A be as in Theorem 4. Using A as a subroutine, weconstruct a Gap-CDH problem solver S. The construction
is illustrated in Fig. A· 2.
S is given q, g, V = gv , W = gw as a CDH problem

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1153
Given (q, g, V, W) as an input;
Initial Setting– Initialize inner state– (vk∗ , sgk∗ ) ← SGK(1k )∗– u ← Zq , X := V, Y := X −vk gu , pk := (q, g, X, Y)
∗
∗
∗
a
∗
– a ← Zq , h := Wg , d := (h∗ )u , σ∗ ← Signsgk∗ ((h∗ , d∗ ))– ψ∗ := (vk∗ , (h∗ , d∗ ), σ∗ ), invoke A on pk and ψ∗
Answering A’s Queries and Extracting the Answer from Return– In the case that A queries DEC(sk, ·) for the answer for ψ =(vk, (h, d), σ); :=⊥• If Vrfyvk ((h, d), σ)  1 or DDH(g, X vk Y, h, d)  1 then K• else := (d/hu )1/(vk−vk∗ ) (: the case Simdec)
If vk  vk∗ then K
else abort (: the case Abort) to A• Reply K∗ ;– In the case that A returns K∗ /X a∗• Return Z := K
Fig. A· 2

A Gap-CDH Problem Solver S for the Proof of Theorem 4.

instance, where v and w are random and unknown to S.
S initializes its inner state. Invoking SGK on an input
1k , S gets (vk∗ , sgk∗ ). S chooses u from Zq at random and∗puts X = V and Y = X −vk gu and sets pk = (q, g, X, Y).
Note that pk is correctly distributed. Note also that S
knows neither x nor y, where x and y denote the discrete logof X and Y on a base g, respectively. Here the following
holds;
y = −vk∗ x + u.
S chooses a∗ from Zq at random and S puts h∗ =∗Wga and d∗ = (h∗ )u . S gets a signature σ∗ from
Signsgk∗ ((h∗ , d∗ )). Then S puts ψ∗ = (vk∗ , (h∗ , d∗ ), σ∗ ). S
invokes A on an input pk.
S replies A in answer to A’s decapsulation queries asfollows. In the case that A queries its decapsulation oracle DEC(sk, ·) for the answer for ψ = (vk, (h, d), σ), S
verifies whether ((h, d), σ) is valid under vk and whether(g, X vk Y, h, d) is a DH-tuple. S checks the latter by querying
its DDH oracle DDH for the answer. If at least one of them =⊥.
is not satisfied, then S puts K∗ = (d/hu )1/(vk−vk∗ )Otherwise, if vk  vk then S puts K(call this case Simdec). If vk = vk∗ , S aborts (call this case to A except for the case Abort.
Abort). S replies K∗ as the answer for ψ∗ , S
In the case that A returns K∗a∗
returns Z = K /X .
S is able to simulate the real view of A perfectly until
the case Abort happens, as we see below.
Firstly, the challenge ciphertext ψ∗ = (vk∗ , (h∗ , d∗ ), σ∗ )is consistent and correctly distributed. This is because the
distribution of (h∗ , d∗ ) is equal to that of the real consistentone (h, d). To see it, note that w + a∗ is substituted for a;∗∗h∗ = Wga = gw+a ,∗∗∗Secondly, in the case Simdec, S can simulate the de
capsulation oracle DEC(sk, ·) perfectly. This is because K
is equal to h x by the following equalities;∗∗ = (g x )w+a∗ = gvw X a∗ .
K
So S wins because its return Z is gvw . 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].
That is;(k)  Advow-cca2
Advgap-cdh
A,KEM1 (k) − Pr[Abort].
S,Grp
So our task being left is to show that Pr[Abort] is negligible in k.
Claim C.1. The probability that the case Abort occurs is
negligible in k.
Proof of Claim C.1. Using A as a subroutine, we construct
a signature forger F on OTS as follows. Given vk∗ as an
input, F initializes its inner state. F chooses x and y from
Zq at random and computes X = g x and Y = gy . F chooses∗a∗ from Zq at random and computes h∗ = ga and d∗ =∗∗(X vk Y)a . Then F queries its signing oracle SIGN sgk∗ fora signature on a message (h∗ , d∗ ) and gets a signature σ∗ .
Putting ψ∗ = (vk∗ , (h∗ , d∗ ), σ∗ ), F invokes A on an input(pk, ψ∗ ).
In the case that A queries its decapsulation oracle
DEC(sk, ·) for the answer for ψ = (vk, (h, d), σ), F verifies
whether the signature is valid and whether (g, X vk Y, h, d) isa DH-tuple. For the latter, F does the same as an honest decapsulation algorithm does because F has the secret key sk.
If the signature is not valid or the tuple is not a DH-tuple, F = hx =⊥. Otherwise, if vk  vk∗ , then F replies K
sets K∗
to A. If vk = vk , then F returns ((h, d), σ) and stops (callthis case Forge).
Note that the view of A in F is the same as the realview until the case Forge happens. Especially, the view of
A in F is the same as the view of A in S until the case
Abort or the case Forge happens. So we have:
Pr[Abort] = Pr[Forge].
Notice that the case Forge implies that the following equalities hold;vk = vk∗ , ((h, d), σ)  ((h∗ , d∗ ), σ∗ ).

∗d∗ = (gw+a )u = (gu )w+a = (X vk Y)w+a .

∗As a whole, S simulates the real view of A perfectly
until the case Abort happens.
Now we evaluate the Gap-CDH advantage of S. When∗ ) is a DH-tuple, so the following holds
A wins, (g, X, h∗ , K(note that we have set X = V, so x = v);∗

d/hu = h(vk)x+y−u = h(vk−vk )x+(vk x+y−u) = h(vk−vk )x .

This is because that, if ((h, d), σ) were equal to ((h∗ , d∗ ), σ∗ ),then A would have queried the challenge ciphertext ψ∗ to its
decapsulation oracle. This is ruled out.
Hence in the case Forge, F succeeds in making an existential forgery in the strong sense. That is;

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.7 JULY 20121154

di = gαi β , i = 1, 2 and starting with the assumption that∗
i = di /hui = X β(τ−τ ) , i = 1, 2. (Q.E.D.)
Z

Pr[Forge] = Adveuf-cma
F ,OTS (k).

i

Combining the two equalities, we get

Appendix F: KEM3̃ and the Obtained ID Scheme

Pr[Abort] = Adveuf-cma
F ,OTS (k).
The right hand side is negligible in k by the assumption in
Theorem 4. (Q.E.D.)
Appendix D: Target Collision Resistant Hash Functions
Target collision resistant (TCR) hash functions [33], [36]are treated as a family. Let us denote a function familyas Hfam(1k ) = {Hκ }κ∈Hkey(1k ) . Here Hkey(1k ) is a hash key
space, κ ∈ Hkey(1k ) is a hash key and Hκ is a function from{0, 1}∗ to {0, 1}k . We may assume that Hκ is from {0, 1}∗ to
Zq , where q is a prime of length k.
Given a PPT algorithm CF , a collision finder, we consider the following experiment.
kExprmttcr
CF ,Hfam (1 )m ← CF (1k ), κ ← Hkey(1k ), m ← CF (κ)
If Hκ (m) = Hκ (m ) and m  m then return Win
else return Lose.
We define the TCR advantage of CF over Hfam as follows.
def

tcr
k
Advtcr
CF ,Hfam (k) = Pr[ExprmtCF ,Hfam (1 ) returns Win].

We say that Hfam is a TCR function family, or, Hfam has the
TCR property if, for any PPT algorithm CF , Advtcr
CF ,Hfam (k)is negligible in k.
In theory, TCR hash function families can be constructed based on the existence of a one-way function [33],[36].
Appendix E: Proof of Claim 8.1
Assume that (g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple andput
Xiτ Yi =: gαi , h =: gβ , di =: gαi β , i = 1, 2.
∗∗

Then hτ−τ = gβ(τ−τ ) . Note that we have set∗

Yi := Xi−τ gui , i = 1, 2.
∗∗

So Xiτ Yi = Xiτ Xi−τ gui = Xiτ−τ gui and we have∗gαi −ui = Xiτ−τ , i = 1, 2.
Hence∗

di /hui = gαi β /gβui = g(αi −ui )β = Xiβ(τ−τ ) , i = 1, 2.
This means (g, X1 , X2 , 
Y, Z1 , Z2 ) is a twin DH tuple for Y =τ−τ∗ 
u1
h , Z1 = d1 /h and Z2 = d2 /hu2 .
The converse is also verified by setting the goal to be

In KEM3̃, the ciphertext turns into ψ = (h, d1 , v2 ), v2 :=Hκ (d2 ). So the consistency check for the index 2 becomes:
whether Hκ (hτx2 +y2 ) = v2 or not.
The Trapdoor Test in the security proof is deformed as follows.
r
Z1 Z2 = 
Y s ⇐⇒⇐⇒∗(d1 /hu1 )r (d2 /hu2 ) = (hτ−τ ) s∗

d1−r hru1 +u2 +s(τ−τ ) = d2∗=⇒ Hκ (d1−r hru1 +u2 +s(τ−τ ) ) = v2 .
The last equality may cause a collision, so the security statement for KEM3̃ needs the collision resistance assumption ofa hash function family Hfam employed (the name of game“cr” in Advcr
CF ,Hfam (k) below means collision resistance).
Corollary of Theorem 6. The key encapsulation mechanism KEM3̃ is one-way-CCA2 secure based on the CDH assumption, the target collision resistance and the collisionresistance of a hash function family employed. More precisely, for any PPT one-way-CCA2 adversary A on KEM3̃
that queries its decapsulation oracle at most qdec times,
there exist a PPT CDH problem solver S on Grp, a PPT
collision-finder CF and CF on Hfam which satisfy the following tight reduction.
(k) Advow-cca2
A,KEM3̃qdec
tcr+ Advcdh
S,Grp (k) + AdvCF ,Hfam (k)q+ Advcr
CF ,Hfam (k).

The ID scheme obtained from KEM3̃ is shown in
Fig. A· 3. By the above tuning, the maximum message
length reduces to two elements 2G of Grp plus one hashvalue h by Hκ .
Key Generation– K: given 1k as an input;• (q, g) ← Grp(1k ), κ ← Hkey(1k )• x1 , x2 , y1 , y2 ← Zq , X1 := g x1 , X2 := g x2 , Y1 := gy1 , Y2 := gy2• pk := (q, g, X1 , X2 , Y1 , Y2 , κ), sk := (q, g, x1 , x2 , y1 , y2 , κ)
• Return (pk, sk)
Interaction– V: given pk as an input;• a ← Zq , h := ga , τ ← Hκ (h)• d1 := (X1τ Y1 )a , v2 := Hκ ((X2τ Y2 )a ), K := X1a , ψ = (h, d1 , v2 )• Send ψ to P
– P: given sk as an input and receiving ψ = (h, d1 , v2 ) as an input message;• τ ← Hκ (h) :=⊥ else K
 := h x1• If hτx1 +y1  d1 or Hκ (hτx2 +y2 )  v2 then K to V• Send K
 as an input message;– V: receiving K
 = K then return 1 else return 0• If K
Fig. A· 3

An ID Scheme Obtained from KEM3̃.

ANADA and ARITA: IDENTIFICATION SCHEMES FROM KEY ENCAPSULATION MECHANISMS

1155

Hiroaki Anada
received his B.E. and M.E.
in mathematics from Waseda University. He isinterested in interactive proofs and has recently
received Ph.D. from Institute of Information Security, Yokohama, Japan.

Seiko Arita
received his B.E. and M.E. from
Kyoto University, and Ph.D. from Chuo University. He has been interested in prime numbers, algebraic curves and cryptographic protocols. He is with Institute of Information Security, Yokohama, Japan.