Identification Schemes fromKey Encapsulation Mechanisms
Hiroaki Anada and Seiko Arita
Institute of Information Security, Yokohama, Japanhiroaki.anada@gmail.com, arita@iisec.ac.jp

Abstract. We propose a generic way for deriving an identification (ID) scheme secure against concurrent man-in-the-middle attacks from a key encapsulation mechanism(KEM) secure against chosen ciphertext attacks on one-wayness (one-way-CCA). Then we
give a concrete one-way-CCA secure KEM based on the Computational Diﬃe-Hellman(CDH) assumption. In that construction, the Twin Diﬃe-Hellman technique of Cash,
Kiltz and Shoup is essentially employed. We compare eﬃciency of the ID scheme derived
from our KEM with previously known ID schemes and KEMs. It turns out that our KEMbased ID scheme reduces the computation by one exponentiation than the currently mosteﬃcient one derived from the Hanaoka-Kurosawa one-way-CCA secure KEM, whose security is based on the same (CDH) assumption.
Keywords: identification scheme, key encapsulation mechanism, one-way-CCA security,
concurrent man-in-the-middle attack, the computational Diﬃe-Hellman assumption.

1

Introduction

An identification (ID) scheme enables a prover to convince a verifier that the proveris indeed itself by proving that it knows some secret information. In the public key
framework, a prover holds a secret key and a verifier refers to a matching public key.
They interact for some rounds doing necessary computations until the verifier feels
certain that the prover has the secret key. The secret key is never revealed directly but
hidden in messages through those computations.
Historically, there have been two types of ID schemes. One is challenge-and-responsetype obtained in a natural way from encryption schemes or signature schemes, and theother is the Σ-protocol type [7] which is a kind of proofs of knowledge [12, 4] consisting of
3-round interaction. Most of known traditional ID schemes, such as the Schnorr scheme[24] and the Guillou-Quisquater (GQ) scheme [13], are the Σ-protocol type because
they are faster than challenge-and-response type.
Now in the Internet environment where everyone is involved, attacks on ID schemes
have become fairly strong. One of the strongest is concurrent man-in-the-middle attacks.
In concurrent man-in-the-middle setting, an adversary stands between a verifier and aprover, and the adversary invokes many instances of the prover application (proverclones), which have independent states and random tapes. Interacting in some cheatingway, the adversary collects information of the secret key from the prover clones, while theadversary interacts with the verifier simultaneously trying to impersonate the prover.
Unfortunately, the Schnorr scheme and the GQ scheme are not secure against concurrent man-in-the-middle attacks, hence there have been significant eﬀorts to make

ID schemes have tolerance against such concurrent man-in-the-middle attacks based onthe Σ-protocol. For example, Katz [16] made an ID scheme of non-malleable proof ofknowledge. But the security model is with timing constraint, not against full concurrent man-in-the-middle attacks. Moreover, the protocol utilizes the so-called OR-Proof
technique, so it is a little bit costly. Gennaro [11] constructed an ID scheme of (fully)
concurrently non-malleable proof of knowledge employing a multi-trapdoor commitment. But it is no longer so fast as a challenge-and-response ID scheme obtained, forinstance, from the Cramer-Shoup encryption scheme [8]. Moreover, the security is basedon a strong type of assumption (the Strong Diﬃe-Hellman (SDH) assumption or theStrong RSA assumption).
One of the reason why it is so diﬃcult to construct an ID scheme secure against
concurrent man-in-the-middle attacks seems that we are rooted in the category of Σprotocols. Let us remember that challenge-and-response ID schemes obtained from INDCCA secure encryption schemes (see [8] for example) and EUF-CMA secure signatureschemes (see [2] for example) are already secure against concurrent man-in-the-middle
attacks.
1.1

Our Contribution

In the notion of encryption scheme, key encapsulation mechanism (KEM) is the foundational concept for hybrid construction with data encryption mechanism. As a firstcontribution in this paper, we propose to use KEM as ID scheme analogous to the usage of encryption scheme. That is, given a KEM, we derive a challenge-and-response
ID scheme as follows. A verifier of a KEM-based ID scheme makes a pair of random
string and its ciphertext using a public key, and send the ciphertext as a challenge tothe prover having the matching secret key. The prover decapsulates the ciphertext andreturns the result as a response. The verifier checks whether or not the response is equal
to the random string. Although this is a straightforward conversion, it has never been
mentioned in the literature, to the best of our knowledge.
As a generic property, KEM-based ID scheme has an advantage over (non-hybrid)
encryption-based ID scheme. That is, KEM only has to encapsulate random strings andmay generate them by itself, while encryption scheme has to encrypt any strings given
as input. Consequently, KEM-based ID scheme has a possibility to have simpler andmore eﬃcient protocol than encryption-based ID scheme.
In addition, as we will show in Section 3, KEM only need to be one-way-CCA securefor derived ID scheme to have security against concurrent man-in-the-middle attacks(cMiM security). In other words, IND-CCA security, which is stronger than one-wayCCA security, is rather excessive for deriving cMiM secure ID scheme. Nonetheless by
this time, most known encryption schemes and KEMs have been designed to possess
IND-CCA security (because the purpose is not to make up ID schemes, of course).
Hence there arises a need to provide one-way-CCA secure KEMs. As a second contribution, we give a concrete, discrete-logarithm-based one-way-CCA secure KEM. It istrue that there have already been a few one-way-CCA secure KEMs in discrete-logarithm
setting. In contrast to those KEMs, the feature of our KEM is that it needs the smallest
2amount of computational cost while its security is based on the Computational DiﬃeHellman (CDH) assumption which is weaker than the Decisional Diﬃe-Hellman (DDH)
assumption or the Gap-CDH assumption (see [21] for these assumptions). That feature
is achieved by applying the Twin Diﬃe-Hellman technique [6] to Anada-Arita’s scheme[1] to relax the Gap-CDH assumption on which their scheme is based1 .
Finally, we point out a feature that the prover in our generic construction of ID
scheme is deterministic, and hence the derived ID scheme is prover-resettable [3]. Moreover, they are also verifier-resettable because they consists of 2-round interaction. Thisis a remarkable property because, as is discussed by Yilek [27], resettable security is
crucially helpful for virtual machine service in the Cloud Computing, for example.
1.2

Related Works

Recently, independently of us, Fujisaki [10] pointed out a fact similar to our genericconstruction above (that is, the conversion from one-way-CCA secure KEM to cMiM
secure ID scheme). We discuss the conversion more precisely than it.
As for concrete constructions, the IND-CCA secure KEM of Shoup [25], which isnaturally a one-way-CCA secure KEM, performs comparably eﬃciently even now, while
its security is based on the DDH assumption. Hanaoka-Kurosawa [15] gave a one-wayCCA secure KEM whose assumption is the CDH assumption, which is weaker thanthe DDH assumption. It is directly comparable with our KEM and our KEM reduces
the computation by one exponentiation for encapsulation than the Hanaoka-Kurosawa
KEM. While both the Shoup KEM and the Hanaoka-Kurosawa KEM are intended forthe hybrid encryption construction, the one-way-CCA secure KEM of Anada-Arita [1] isintended directly for ID scheme. It performs better than Shoup’s KEM and its security
is based on the Gap-CDH assumption. The Twin Diﬃe-Hellman technique enables us
to relax that gap assumption to lead our one-way-CCA secure KEM.
1.3

Organization of the Paper

In Section 2, we fix some notations and briefly review the notion of ID scheme, KEM
and computational hardness assumption. In Section 3, we propose a generic way forderiving a cMiM secure ID scheme from a one-way-CCA secure KEM. In Section 4,
we construct a one-way-CCA secure KEM by the Twin Diﬃe-Hellman technique. In
Section 5, we compare our KEM or ID scheme with previously known KEMs or ID
schemes. In Section 6, we conclude our work.

2

Preliminaries

The security parameter is denoted k. On input 1k , a PPT algorithm Grp runs andoutputs (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
1

The strategy to apply the Twin Diﬃe-Hellman technique was suggested to us by Prof. Kiltz [18].

3

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 input a outputs z, we denote it as z ← A(a). When A on
input a and B on input b interact and B outputs z, we denote it as z ← ⟨A(a), B(b)⟩.
When A has oracle-access to O, we denote it as AO . When A has concurrent oracleaccess to n oracles O1 , . . . , On , we denote it as AO1 |···|On . Here “concurrent” means that
A accesses to oracles in arbitrarily interleaved order of messages.
A probability of an event X is denoted Pr[X]. A probability of an event X on conditions Y1 , . . . , Ym is denoted Pr[Y1 ; · · · ; Ym : X].
2.1

Identification Scheme

An identification scheme ID is a triple of PPT algorithms (K, P, V). K is a key generator
which outputs a pair of a public key and a matching secret key (pk, sk) on input 1k . P
and V implement a prover and a verifier strategy, respectively. We require ID to satisfy
the completeness condition that boolean decision by V(pk) after interaction with P(sk)is True with probability one. We say that V(pk) accepts if its boolean decision is True.
Concurrent Man-in-the-Middle Attack on Identification Scheme [3, 5] The
aim of an adversary A that attacks an ID scheme ID is impersonation. We say that A
wins when A(pk) succeeds in making V(pk) accept.
An adversary A performs concurrent man-in-the-middle (cMiM, for short) attack in
the following way.
Experimentimp-cmim
(1k )
A,ID
(pk, sk) ← K(1k ), decision ← ⟨AP1 (sk)|···|Pn (sk) (pk), V(pk)⟩
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) andA(pk) as πi and a transcript between A(pk) and V(pk) as π ∗ . As a rule, man-in-themiddle adversary A is prohibited from relaying a transcript of a whole interaction withsome prover clone to the verifier V(pk), as is described π ∗ ̸∈ {πi }ni=1 in the experiment.
This is a standard and natural constraint to keep man-in-the-middle attack meaningful.
We define A’s imp-cMiM advantage over ID as:
def

Advimp-cmim(k) = Pr[Experimentimp-cmim(1k ) returns Win].
A,ID
A,ID
We say that an ID is secure against concurrent man-in-the-middle attacks (cMiM secure,for short) if, for any PPT algorithm A, Advimp-cmim(k) is negligible in k.
A,IDSuppose that an adversary A consists of two algorithms A1 and A2 . The following
experiment is called a 2-phase concurrent attack.
Experimentimp-2pc
(1k )
A,ID
P (sk)|···|Pn (sk)(pk, sk) ← K(1k ), st ← A11(pk), decision ← ⟨A2 (st), V(pk)⟩

If decision = 1 then return Win else return Lose.
42-phase concurrent attack is a weaker model than cMiM attack because of the constraintthat the learning phase of A1 is limited to before the impersonation phase of A2 .
2-phase concurrent attack and cMiM attack are classified to active attacks. On thecontrary, there is a passive attack described below. Let us denote a transcript of a wholeinteraction between P(sk) and V(pk) as π = |⟨P(sk), V(pk)⟩|.
kExperimentimp-pa
A,ID (1 )(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.
Passive attack is a weaker model than 2-phase concurrent attack because of the constraint that A cannot choose messages in the learning phase.
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 outputs a pair of a public key and a matching secret key(pk, sk) on input 1k . Enc is an encapsulation algorithm which, on input pk, outputs a pair(K, ψ), where K is a random string and ψ is a ciphertext of K. Dec is a decapsulationb of ψ. We require KEM toalgorithm which, on input (sk, ψ), outputs the decapsulation K
b of a consistently generated
satisfy the completeness condition that the decapsulation K
ciphertext ψ by Enc is equal to the original random string K with probability one.
Adaptive Chosen Ciphertext Attack on One-Wayness of KEM [22, 15] An
adversary A on a KEM performs adaptive chosen ciphertext attack on one-wayness ofa KEM (one-way-CCA, for short) in the following way.
k
Experimentow-cca
A,KEM (1 )c∗ ← ADEC(sk,·) (pk, ψ ∗ )(pk, sk) ← K(1k ), (K ∗ , ψ ∗ ) ← Enc(pk), Kc∗ = K ∗ ∧ ψ ∗ ̸∈ {ψi }qdec then return Win else return Lose.
If K
i=1

In the above experiment, ψi , i = 1, . . . , qdec mean ciphertexts for which A queries its
decapsulation oracle DEC(sk, ·) for the answer. Here the number qdec of queries is polynomially many in k. The challenge ciphertext ψ ∗ itself must not be queried to DEC(sk, ·),dec
as is described ψ ∗ ̸∈ {ψi }qi=1
in the experiment.
We define A’s one-way-CCA advantage over KEM as:def

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

We say that a KEM is secure against adaptive chosen ciphertext attacks against onewayness (one-way-CCA secure, for short) if, for any PPT algorithm A, Advow-cca
A,KEM (k)5is negligible in k. Note that if a KEM is IND-CCA secure [8], then it is one-way-CCA
secure. So IND-CCA security is a stronger notion than one-way-CCA security.
Suppose that an adversary A consists of two algorithms A1 and A2 . The following
experiment is called a non-adaptive chosen ciphertext attack on one-wayness of a KEM.
kExperimentow-cca1
A,KEM (1 )DEC(sk,·)c∗ ← A2 (st, ψ ∗ )(pk, sk) ← K(1k ), st ← A1(pk), (K ∗ , ψ ∗ ) ← Enc(pk), Kc∗ = K ∗ then return Win else return Lose.
If K

Non-adaptive chosen ciphertext attack is a weaker model than adaptive one because of
the constraint that the learning phase of A1 is limited to before the solving phase of
A2 .
Adaptive and non-adaptive chosen ciphertext attacks are classified to active attacks.
On the contrary, there is a passive attack on one-wayness of a KEM described below.
kExperimentow-pa
A,KEM (1 )(pk, sk) ← K(1k )If A1 (pk) makes a query, reply (Ki , ψi ) ← Enc(pk)c∗ ← A2 (st, ψ ∗ )st ← A1 ({(Ki , ψi )}ni=1 ), (K ∗ , ψ ∗ ) ← Enc(pk), Kc∗ = K ∗ then return Win else return Lose.
If K
Passive attack is a weaker model than non-adaptive chosen ciphertext attack becauseof the constraint that A cannot choose ciphertexts in the learning phase.
2.3

The Computational Diﬃe-Hellman Assumption and the TwinDiﬃe-Hellman Technique

We say a solver S, a PPT algorithm, wins when S succeeds in solving a computational
problem instance.
A quadruple (g, X, Y, Z) of elements in Gq is called a Diﬃe-Hellman tuple (DHtuple, for short) if the quadruple is written as (g, g x , g y , g xy ) for some elements x, y in
Zq . A CDH problem instance is a triple (g, X = g x , Y = g y ), where the exponents x, y
are uniformly random in Zq . A CDH problem solver is a PPT algorithm which, given a
CDH problem instance (g, X, Y ) as input, tries to return Z = g xy , whose experiment is
the following.
k
Experimentcdh
S,Grp (1 )(q, g) ← Grp(1k ), x, y ← Zq , X := g x , Y := g y , Z ← S(g, X, Y )If Z = g xy then return Win else return Lose.
We define S’s CDH advantage over Grp as:
def

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

6

We say that the CDH assumption [21] holds for Grp if, for any PPT algorithm S,
AdvcdhS,Grp (k) is negligible in k.
A 6-tuple (g, X1 , X2 , Y, Z1 , Z2 ) of elements in Gq is called a twin Diﬃe-Hellman
tuple if the tuple is written as (g, g x1 , g x2 , g y , g x1 y , g x2 y ) for some elements x1 , x2 , y in
Zq .
The following lemma of Cash, Kiltz and Shoup is used in Section 4 to decide whether
or not a tuple is a twin DH tuple in the security proof for our concrete KEM.
Lemma (Cash, Kiltz and Shoup [6] Theorem 2, “Trap Door Test”) Let
X1 , r, s be mutually independent random variables, where X1 takes values in Gq , andeach of r, s is uniformly distributed over Zq . Define the random variable X2 := X1−r g s .
c1 , Zc2 are random variables taking values in Gq , each of which is definedSuppose that Yb , Z
c1 r Zc2 = Yb s does notindependently of r. Then the probability that the truth value of Z
c1 , Zc2 ) being a twin DH tuple is at most 1/q.
agree with the truth value of (g, X1 , X2 , Yb , Z
c1 , Zc2 ) is a twin DH tuple, then Z
c1 r Zc2 = Yb s certainly holds.
Moreover, if (g, X1 , X2 , Yb , Z

3

Identification Scheme from Key Encapsulation Mechanism

In this section, we show a generic way for deriving an ID scheme secure against concurrent man-in-the-middle attacks from a one-way-CCA secure KEM.

3.1

Construction

Let KEM = (K, Enc, Dec) be a KEM. Then an ID scheme ID is derived in a natural way as
shown in the Fig.1. The key generation algorithm is the same as that of KEM. The verifierV, given a public key pk as input, invokes the encapsulation algorithm Enc on pk andgets its output (K, ψ). V sends ψ to P. The prover P, given a secret key sk as input andreceiving ψ as input message, invokes the decapsulation algorithm Dec on (sk, ψ) andb P sends K
b to V. Finally the verifier V, receiving K
b as input message,
gets its output K.
b is equal to K. If so, then V returns 1 and otherwise, 0.
verifies whether or not K
It is notable that, if we use an encryption scheme, which is not a KEM, as an ID
scheme in a similar way, then we need to input a random string into the encryption
algorithm. In contrast, in a KEM, an encapsulation algorithm does not need such an
input but only has to output a random string.
Theorem 1 If a key encapsulation mechanism KEM is one-way-CCA secure, then thederived identification scheme ID is cMiM secure. More precisely, for any PPT adversary
A that attacks ID in cMiM setting, there exists an PPT adversary B that attacks KEM
in one-way-CCA setting satisfying the following inequality.
Advimp-cmim(k) 6 Advow-cca
B,KEM (k).
A,ID
7

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

3.2

Proof of Theorem 1

Let KEM be a one-way-CCA secure KEM and ID be the derived ID scheme by theconstruction above. Let A be any given cMiM adversary on ID. Using A as subroutine,
we construct a PPT one-way-CCA adversary B that attacks KEM as shown in the Fig.2.
On input pk and the challenge ciphertext ψ ∗ , B initializes its inner state and invokes
A on input pk.
In case that A queries V(pk) for the challenge message, B sends ψ ∗ to A as thechallenge message.
In case that A sends a challenge message ψ to a prover clone P(sk), B checks whether
or not ψ is equal to ψ ∗ . If so, then B puts K =⊥. Otherwise, B queries its decapsulation
oracle DEC(sk, ·) for the answer for the ciphertext ψ and gets K. B sends K to A as the
response message.
c∗ to V(pk), B returns Kc∗ as the answer
In case that A sends the response message K
for the challenge ciphertext ψ ∗ .
Given pk as input;
Initial Setting– Initialize the inner state– Invoke A on pk
Answering A’s Queries– In case that A queries V(pk) for the challenge message• Send ψ ∗ to A
– In case that A sends ψ to a prover clone P(sk)• If ψ = ψ ∗ , then put K :=⊥• else Query DEC for the answer for ψ: K ← DEC(sk, ψ)• Send K to Ac∗ to V(pk)– In case that A sends K∗
c• Return K as the answer for ψ ∗Fig. 2. A one-way-CCA adversary B employing a cMiM adversary A for the proof of Theorem 1.

The view of A in B is the same as the real view of A. This is obvious except the casethat ψ is equal to ψ ∗ . When A sent ψ = ψ ∗ , the transcript of the interaction between8

P(sk) and A(pk) would be wholly equal to that between A(pk) and V(pk), because theprover P is deterministic. This is ruled out, so B’s response, K =⊥, is appropriate.
If A wins, then B wins. Hence the inequality in Theorem 1 follows. (Q.E.D.)
Remark 1. In analogous ways, we can show the following facts. If a KEM is secure against
non-adaptive chosen ciphertext attacks on one-wayness, then the derived ID scheme ID
is secure against 2-phase concurrent attacks. If a KEM is secure against passive attacks
on one-wayness, then the derived ID scheme ID is secure against passive attacks.
Remark 2. The prover P in the Fig.1 is deterministic. Therefore, the derived ID scheme
ID is prover-resettable [3]. Moreover, ID is also verifier-resettable because ID consists of
2-round interaction.

4

A One-Way-CCA Secure KEM Based on the CDH Assumption

In this section, we propose a one-way-CCA secure KEM based on the CDH assumption.
The challenge-and-response ID scheme of Anada-Arita [1] can be viewed as a one-wayCCA secure KEM based on the Gap-CDH assumption. Our strategy is to relax the gap
assumption by applying the Twin Diﬃe-Hellman technique of Cash, Kiltz and Shoup[6, 18].
In the construction, we employ a target collision resistant (TCR) hash function
family. The definition of a TCR hash function family Hfam(1k ) = {Hµ }µ∈Hkey(1k ) andadvantage Advtcr
CF ,Hfam (k) of a PPT collision finder CF over Hfam are in Appendix A.
4.1

Construction

The construction of a KEM KEM1 is shown in the Fig.3.
On input 1k , the key generator K runs as follows. A group generator Grp outputs (q, g) on input 1k . 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 ina hash function family Hfam(1k ). Then K chooses x1 , x2 , y1 , y2 ∈ Zq and computes
X1 = g x1 , X2 = g x2 , Y1 = g y1 , Y2 = g y2 . K sets pk = (q, g, X1 , X2 , Y1 , Y2 , µ) andsk = (q, g, x1 , x2 , y1 , y2 , µ). Then K returns (pk, sk).
On input pk, the encapsulation algorithm Enc runs as follows. Enc chooses a ∈ Zq
at random and computes h = g a 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 the ciphertext isψ = (h, d1 , d2 ). Note here that (g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple. Enc returns
the pair (K, ψ).
On 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 ) isa consistent ciphertext, that is, whether (g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ) is a twin DH tuple
or not. For this sake, Dec checks whether hτ x1 +y1 = d1 and hτ x2 +y2 = d2 hold. If atleast one of them does not hold, then Dec puts K =⊥. Otherwise Dec computes thedecapsulation K = hx1 . Note that (g, X1 , h, K) is a DH tuple. Finally, Dec returns K.
9Key Generation– K: given 1k as input;• (q, g) ← Grp(1k ), µ ← Hkey(1k )• x1 , x2 , y1 , y2 ← Zq , X1 := g x1 , X2 := g x2 , Y1 := g y1 , Y2 := g y2
• pk := (q, g, X1 , X2 , Y1 , Y2 , µ), sk := (q, g, x1 , x2 , y1 , y2 , µ)
• Return (pk, sk)
Encapsulation– Enc: given pk as input;• a ← Zq , h := g a , τ ← 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 input;• τ ← Hµ (h)• If hτ x1 +y1 ̸= d1 or hτ x2 +y2 ̸= d2 then K :=⊥ else K := hx1• Return K
Fig. 3. A one-way-CCA secure KEM KEM1.

Theorem 2 The key encapsulation mechanism KEM1 is one-way-CCA secure based on
the CDH assumption and the target collision resistance of employed hash function. Moreprecisely, for any PPT one-way-CCA adversary A on KEM1 that queries decapsulation
oracle at most qdec times, there exist a PPT CDH problem solver S on Grp and a PPT
collision-finder CF on Hfam which satisfy the following tight reduction.
Advow-cca
A,KEM1 (k) 6
4.2

qdec
tcr
+ Advcdh
S,Grp (k) + AdvCF,Hfam (k).
q

Proof of Theorem 2

Let A be any given adversary that attacks KEM1 in one-way-CCA setting. Using A as
subroutine, we construct a PPT CDH problem solver S as shown in the Fig.4, wherean algebraic trick [17] and the Twin Diﬃe-Hellman technique [6] are essentially used.
S is given (q, g), X = g x and Y = g y as input, where x and y are random. S∗
initializes its inner state. S chooses a∗ ∈ Zq at random and computes h∗ = Y g a .
Then S chooses µ from Hkey(1k ) and computes τ ∗ ← Hµ (h∗ ). S chooses r, s ∈ Zq
at random, and puts X1 = X, X2 = X1−r g s . S chooses u1 , u2 ∈ Zq at random, and∗∗computes W1 = X1−τ g u1 , W2 = X2−τ g u2 . S computes d∗1 = (h∗ )u1 , d∗2 = (h∗ )u2 . S sets
pk = (q, g, X1 , X2 , W1 , W2 , µ), ψ ∗ = (h∗ , d∗1 , d∗2 ) and invokes A on input pk and ψ ∗ . Notethat pk is correctly distributed. Note also that S does not know x1 , x2 , w1 , w2 at all,where x1 , x2 , w1 , w2 are the discrete log of X1 , X2 , W1 , W2 , respectively. Especially thefollowings hold.
wi = logg (Wi ) = −τ ∗ xi + ui , i = 1, 2.
S replies to A’s queries as follows.
10(1)

In 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 Consistency-Check). That is, S verifies whether (g, X1τ W1 , X2τ W2 , h, d1 , d2 )∗c1 = d1 /hu1 and Z
c2 = d2 /hu2 . If
is a twin DH tuple as follows. Put Yb = hτ −τ , Zr
c1 Z
c2 ̸= Yb s , then it is not a twin DH tuple and S puts K =⊥. Otherwise, S decidesZ∗
c1 1/(τ −τ ) (call this casethat it is a twin DH tuple. Then, if τ ̸= τ ∗ , S computes K = Z
Simdec). Otherwise (τ = τ ∗ ), S aborts (call this case Abort). S replies K to A except
the case Abort.
c∗ , S computes Z = K
c∗ /X a∗ and returns Z.
In case that A replies K
Given q, g, X = g x , Y = g y as input;
Initial Setting– Initialize the inner state∗– a∗ ← Zq , h∗ := Y g ak∗– µ ← Hkey(1 ), τ ← Hµ (h∗ )– r, s ← Zq , X1 := X, X2 := X1−r g s∗∗– u1 , u2 ← Zq , W1 := X1−τ g u1 , W2 := X2−τ g u2
∗
∗ u2
∗
∗ u1
– d1 := (h ) , d2 := (h )– pk := (q, g, X1 , X2 , W1 , W2 , µ), ψ ∗ := (h∗ , d∗1 , d∗2 )– Invoke A on pk and ψ ∗Answering A’s Queries– In case that A queries DEC(sk, ·) for the answer for ψ = (h, d1 , d2 )• If ψ = ψ ∗ , then put K :=⊥• else (: the case Consistency-Check)∗c1 := d1 /hu1 , Z
c2 := d2 /hu2τ ← Hµ (h), Yb := hτ −τ , Zr
s
c1 Z
c2 ̸= Yb , then K :=⊥
If Z
else
∗
c1 1/(τ −τ ) (: the case Simdec)
If τ ̸= τ ∗ , then K := Zelse abort (: the case Abort)• Reply K to Ac∗ as the answer for ψ ∗– In case that A replies K
c∗ /X a∗• Z := K• Return Z
Fig. 4. A CDH problem solver S employing a one-way-CCA adversary A for the proof of Theorem 2.

S is able to simulate the real view of A perfectly until the case Abort happens
except a negligible case, as we see below.
Firstly, the challenge ciphertext ψ ∗ = (h∗ , d∗1 , d∗2 ) is consistent and correctly distributed. This is because the distribution of (h∗ , d∗1 , d∗2 ) is equal to that of the realconsistent ciphertext ψ = (h, d1 , d2 ). To see it, note that y + a∗ is substituted for a:
∗

∗

∗

∗

∗

h∗ = g y+a , d∗i = (g y+a )ui = (g ui )y+a = (Xiτ Wi )y+a , i = 1, 2.
Secondly, S simulates the decapsulation oracle DEC(sk, ·) perfectly except a negligible case. To see it, note that the consistency check really works though it may involvea negligible error case, which is explained by the following two claims.
11Claim 1 (g, X1τ W1 , X2τ W2 , h, d1 , d2 ) is a twin DH tuple if and only if
c1 , Zc2 ) is a twin DH tuple for Yb = hτ −τ ∗ , Z
c1 = d1 /hu1 and Z
c2 = d2 /hu2 .
(g, X1 , X2 , Yb , Z
Claim 1 is proven by direct calculations and the proof is noted in Appendix B.
c1 r Zc2 = Yb s holds for Yb = hτ −τ ∗ , Z
c1 = d1 /hu1 and Z
c2 = d2 /hu2 , thenClaim 2 If Z
c1 , Zc2 ) is a twin DH tuple except an error case that occurs at most 1/q(g, X1 , X2 , Yb , Z
c2 = Yb s
c1 , Zc2 ) is a twin DH tuple, then Z
c1 r Z
probability. Conversely, if (g, X1 , X2 , Yb , Z
certainly holds.
∗
c1 = d1 /hu1 and Z
c2 = d2 /hu2 is
Proof of Claim 2. We observe that each of Yb = hτ −τ , Z
given independently of r. So we can apply the Lemma in Section 2. (Q.E.D.)
Let us define the event Overlook as:{
c1 r Zc2 = Yb s holds
Z
defOverlook =c1 , Zc2 ) is not a twin DH tuple.
and (g, X1 , X2 , Yb , Z
Then, by the Claim 2, the probability that Overlook occurs is at most 1/q for eachconsistency check. So for at most qdec consistency checks, Consistency-Checki , i =1, . . . , qdec , the probability that at least one corresponding Overlooki occurs is at mostqdec /q. That is;
q∨
dec

Pr[

Overlooki ] 6

i=1

qdec
.
q

(2)

qdec is polynomial and q is exponential in k, so the right hand side is negligible in k.
Suppose S has confirmed that a decapsulation query ψ = (h, d1 , d2 ) passed theconsistency check. In that case, (g, X1τ W1 , X2τ W2 , h, d1 , d2 ) is a twin DH tuple (except
a negligible case Overlook), so d1 = hτ x1 +w1 holds. If, in addition, S is in the case∗c1 1/(τ −τ ) of S to A is correct. This is
Simdec (that is, τ ̸= τ ∗ ), then the answer K = Z∗
because K = (d1 /hu1 )1/(τ −τ ) is equal to hx1 by the following equality.
∗∗∗

d1 /hu1 = hτ x1 +w1 −u1 = h(τ −τ )x1 +(τ x1 +w1 −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 the negligible case Overlook.
c∗ ) is a DH tuple, so
Now we evaluate the advantage of S. When A wins, (g, X, h∗ , K
the following holds.
c∗ = X y+a∗ = g x(y+a∗ ) = g xy+xa∗ .
Kc∗ /X a = g xy , which is the correct answer for the input
Hence the output Z is equal to K
(g, X, Y ). That is, S wins. Therefore, the probability that S wins is lower bounded by∗

12the probability that A wins, Overlooki never occurs for i = 1, . . . , qdec and Abort
does not happen:q∧
dec

Pr[S wins] > Pr[A wins ∧ ((¬Overlooki )) ∧ (¬Abort)]

i=1
q∨
dec

> Pr[A wins] − Pr[(

i=1
q∨
dec

= Pr[A wins] − (Pr[Overlooki ) ∨ Abort]
Overlooki ] + Pr[(

i=1

q∧
dec

(¬Overlooki )) ∧ Abort]).

i=1

Using the inequality (2), we get:
dec
∧
qdec
− Pr[( (¬Overlooki )) ∧ Abort].
qq

ow-ccaAdvcdhS,Grp (k) > AdvA,KEM1 (k) −i=1

So our task being left is to show the following inequality.
q∧dec
Claim 3 Pr[( (¬Overlooki )) ∧ Abort] 6 Advtcr
CF,Hfam (k).
i=1Proof of Claim 3. Using A as subroutine, we construct a PPT target collision finder CF
on Hfam as follows. Given 1k as input, CF initializes its inner state. CF gets (q, g) from∗
Grp(1k ). CF chooses a∗ ∈ Zq at random, computes h∗ = g a and outputs h∗ . CF receives
a random hash key µ and computes τ ∗ ← Hµ (h∗ ). Then CF makes a secret key andpublic key honestly by itself : sk = (q, g, x1 , x2 , y1 , y2 , µ), pk = (q, g, X1 , X2 , Y1 , Y2 , µ).
∗∗∗∗Finally, CF computes d∗1 = (X1τ Y1 )a , d∗2 = (X2τ Y2 )a and puts ψ ∗ = (h∗ , d∗1 , d∗2 ). CF
invokes A on pk and ψ ∗ .
In case that A queries the 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 do it in the same way as the Dec does because CF has the secret key
sk. If it is not consistent, CF replies K =⊥ to A. Otherwise, if τ ̸= τ ∗ , then CF replies
K = hx1 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 consistentqueries (ψ’s) have the chance to make a collision τ = τ ∗ , which is unconditionally holds
in CF. Hence we have:q∧decPr[( (¬Overlooki )) ∧ Abort] 6 Pr[Collision].
(3)
i=1

On the other hand, notice that Collision implies the following.
∗∗(g, X1τ Y1 , X2τ Y2 , h∗ , d∗1 , d∗2 ): a twin DH tupleand ∃(g, X1τ Y1 , X2τ Y2 , h, d1 , d2 ): a twin DH tupleandτ = τ ∗.
13

If, in addition to the above conditions, h were equal to h∗ , then (d1 , d2 ) would be equalto (d∗1 , d∗2 ). This means that ψ is equal to ψ ∗ , a contradiction. So it must hold thath ̸= h∗ .
Namely, in the case Collision, CF succeeds in making a target collision:
Pr[Collision] = Advtcr
CF,Hfam (k).
Combining (3) and (4), we get the inequality as claimed.
4.3

(4)

(Q.E.D.)A Tuning for Eﬃciency and the Corresponding Identification Scheme

To reduce the length of ciphertext ψ = (h, d1 , d2 ), we can replace the term d2 with its
hash value v2 := Hµ (d2 ). Let us call this KEM KEM2. In KEM2, the ciphertext turns to ψ =?

(h, d1 , v2 ), so the consistency check for index 2 in Dec(sk, ψ) becomes Hµ (hτ x2 +y2 ) = v2 .
? bs
c1 r Zc2 =In addition, the trapdoor test in the security proof, Z
Y , is deformed as follows.
c2 = Yb s ⇐⇒c1 r ZZ⇐⇒∗(d1 /hu1 )r (d2 /hu2 ) = (hτ −τ )s∗ru1 +u2 +s(τ −τ )
d−r
= d2
1 h
∗

ru1 +u2 +s(τ −τ )=⇒ Hµ (d−r) = v2 .
1 h

The last equality may cause collision, so the security statement for KEM2 needs thecollision resistance assumption of employed hash function Hµ (the name of game “cr”
in Advcr
CF ′ ,Hfam (k) below means collision resistance).
Corollary of Theorem 2 The key encapsulation mechanism KEM2 is one-way-CCA
secure based on the CDH assumption, the target collision resistance and the collisionresistance of employed hash function. More precisely, for any PPT one-way-CCA adversary A on KEM2 that queries 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.
Advow-cca
A,KEM2 (k) 6

qdec
tcr
cr
+ Advcdh
S,Grp (k) + AdvCF ,Hfam (k) + AdvCF ′ ,Hfam (k).
q

The ID scheme derived from KEM2 is shown in the Fig.5. The maximum message
length of the ID scheme derived from KEM1 (that is, the length of challenge messageof V) amounts to three elements in Grp. By the tuning above, the maximum message
length reduces to two elements in Grp plus one hash value of Hµ .

5

Eﬃciency Comparison

In this section, we evaluate the eﬃciency of our ID schemes comparing with other ID
schemes secure against concurrent man-in-the-middle attacks in the standard model.
14

Key Generation– K: given 1k as input;• (q, g) ← Grp(1k ), µ ← Hkey(1k )• x1 , x2 , y1 , y2 ← Zq , X1 := g x1 , X2 := g x2 , Y1 := g y1 , Y2 := g y2
• pk := (q, g, X1 , X2 , Y1 , Y2 , µ), sk := (q, g, x1 , x2 , y1 , y2 , µ)
• Return (pk, sk)
Interaction– V: given pk as input;• a ← Zq , h := g a , τ ← Hµ (h)• d1 := (X1τ Y1 )a , v2 := Hµ ((X2τ Y2 )a ), K := X1a , ψ = (h, d1 , v2 )• Send ψ to P
– P: given sk as input and receiving ψ = (h, d1 , v2 ) as input message;• τ ← Hµ (h)b :=⊥ else K
b := hx1• If hτ x1 +y1 ̸= d1 or Hµ (hτ x2 +y2 ) ̸= v2 then Kb• Send K to Vb as input message;– V: receiving K
b = K then return 1 else return 0• If K
Fig. 5. An ID scheme derived from KEM2.

Under the condition that security is based on the CDH assumption, our ID schemes
reduce the computation by one exponentiation than the currently most eﬃcient one.
Comparable 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-CCA secure
encryption schemes and the fourth category is the ones obtained from one-way-CCA
secure KEMs.
In the first category, to the best of our knowledge, the Gennaro scheme is the mosteﬃcient but is no more eﬃcient than the ID scheme derived from Cramer-Shoup encryption [8, 25, 9] (the Cramer-Shoup ID scheme, for short). As for the second category,
all the known signature schemes in the standard model, including the Short Signature[2] and the Waters Signature [26], are costly than the Cramer-Shoup ID scheme.
In the third category, the Cramer-Shoup ID scheme is the most eﬃcient. Note that
the Cramer-Shoup KEM [25, 9] (Sh00KEM) is also usable as an ID scheme, because theKEM is IND-CCA secure and hence one-way-CCA secure. On the contrary, we remarkthat the KEM part of Kurosawa-Desmedt encryption scheme [19] is not comparable
because the KEM is not one-way-CCA secure [14].
In the fourth category the one-way-CCA secure KEM of Hanaoka-Kurosawa [15](HK08KEM) is vary comparable, as its security is reduced to the CDH assumption. A recently proposed ID scheme of Anada-Arita [1] is also comparable as it can be consideredan ID scheme derived from one-way-CCA secure KEM (AA10KEM)2 .
Table 1 shows comparison of these KEMs with our KEMs KEM1 and KEM2. In thetable, we are comparing computational amount by counting the number of exponentiation. We also compares the maximum message length. (For the DDH assumption and
the Gap-CDH assumption, see [21].)2

We note that one-time signature in the ID scheme of [1] can be replaced by TCR hash function.

15

Table 1. Eﬃciency comparison of KEM1 and KEM2 with previous KEMs. G and h mean an element in
Gq and a hash value in Zq , respectively. OW-CCA means one-way-CCA security.
KEM
Sh00KEM
HK08KEM
AA10KEM
Our KEM1
Our KEM2

Security
Assump.
DDH
CDH
Gap-CDH
CDH
CDH

Securityas KEM
IND-CCAOW-CCAOW-CCAOW-CCAOW-CCA

Security Exponentiation Max. Msg. Length
as ID scm. V(Enc) P(Dec) (Challenge Msg.)
cMiM
5
3
3G
cMiM
7
3
3G
cMiM
4
2
2G
cMiM
6
3
3G
cMiM
6
3
2G + 1h

As shown in Table 1, the ID schemes derived from KEM1 and KEM2 reduce the computation by one exponentiation for verifier than the currently most eﬃcient one derived
from the Hanaoka-Kurosawa one-way-CCA secure KEM [15], whose security is based on
the same (CDH) assumption, which is the weakest in the three assumptions in the table.
We can also look at the table as a trade oﬀ between strength of security assumptions
and computational amounts to execute protocols.

6

Conclusion

We showed a generic way for deriving a cMiM secure ID scheme from a one-way-CCA
secure KEM. Then we gave a concrete one-way-CCA secure KEM utilizing the TwinDiﬃe-Hellman technique. The obtained ID scheme performs better than the currently
most eﬃcient one whose security is based on the (same) CDH assumption.

Acknowledgements
We appreciate sincere suggestions oﬀered by Prof. Kiltz [18] and we would like to thankProf. Kurosawa for inspiring words, both at ProvSec 2010. We also thank anonymous
reviewers for careful reading and valuable comments.

References
1. Anada, H., Arita, S.: Identification Schemes of Proofs of Ability Secure against Concurrent Manin-the-Middle Attacks. In: Heng, S.-H., Kurosawa, K. (eds.) ProvSec 2010. LNCS, vol. 6402, pp.
18-34. Springer, Berlin (2010)
2. Boneh, D., Boyen, X.: Short Signatures without Random Oracles. In: Cachin, C., Camenisch, J.
(eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56-73. Springer, Berlin (2004)
3. Bellare, M., Fischlin, M., Goldwasser, S., Micali, S.: Identification Protocols Secure against Reset
Attacks. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 495-511. Springer, Berlin(2001)
4. Bellare, M., Goldreich, O.: On Defining Proofs of Knowledge. In: Brickell, E.F. (ed.) CRYPTO ’92.
LNCS, vol. 740, pp. 390-420. Springer, Berlin (1992)
5. Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.
2442, pp. 162-177. Springer, Berlin (2002)
6. Cash, D., Kiltz, E., Shoup, V.: The Twin Diﬃe-Hellman Problem and Applications. In: Smart,
N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 127-145. Springer, Berlin (2008). Full version
available at Cryptology ePrint Archive, 2008/067, http://eprint.iacr.org/

167. Cramer, R., Damgård, I., Nielsen, J. B.: Multiparty Computation from Threshold Homomorphic
Encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280-300. Springer,
Berlin (2001)
8. Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure against Adaptive
Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO ’98. LNCS, vol. 1462, pp. 13-25.
Springer, Berlin (1998)
9. Cramer, R., Shoup, V.: Design and Analysis of Practical Public-Key Encryption Schemes Secureagainst Adaptive Chosen Ciphertext Attack. SIAM Journal on Computing, vol. 33, num. 1, pp.
167-226 (2003)
10. Fujisaki, E.: New Constructions of Eﬃcient Simulation-Sound Commitments Using Encryption. In:
The 2011 Symposium on Cryptography and Information Security, 1A2-3. The Institute of Electronics, Information and Communication Engineers, Tokyo (2011)
11. Gennaro, R.: Multi-trapdoor Commitments and their Applications to Non-Malleable Protocols. In:
Franklin, M.K. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 220-236. Springer, Berlin (2004)
12. Goldwasser, S., Micali, S., Rackoﬀ, C.: The Knowledge Complexity of Interactive Proof Systems.
SIAM Journal on Computing, vol. 18, num. 1, pp. 186-208 (1989)
13. Guillou, L., Quisquater, J. J.: A Paradoxical Identity-Based Signature Scheme Resulting from ZeroKnowledge. In: Goldwasser, S. (ed.) CRYPTO ’88. LNCS, vol. 403, pp. 216-231. Springer, Berlin(1988)
14. Herranz, J., Hofheinz, D., Kiltz, E.: The Kurosawa-Desmedt Key Encapsulation is not ChosenCiphertext Secure. Cryptology ePrint Archive, 2006/207, http://eprint.iacr.org/
15. Hanaoka, G., Kurosawa, K.: Eﬃcient Chosen Ciphertext Secure Public Key Encryption under theComputational Diﬃe-Hellman Assumption. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol.
5350, pp. 308-325. Springer, Berlin (2008). Full version available at Cryptology ePrint Archive,
2008/211, http://eprint.iacr.org/
16. Katz, J.: Eﬃcient Cryptographic Protocols Preventing “Man-in-the-Middle” Attacks. Doctor ofPhilosophy Dissertation, Columbia University, New York (2002)
17. Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S., Rabin, T. (eds.)
TCC 2006. LNCS, vol. 3876, pp. 581-600. Springer, Berlin (2006)
18. Kiltz, E.: Personal communication at ProvSec 2010, Malacca (2010)
19. Kurosawa, K., Desmedt, Y.: A New Paradigm of Hybrid Encryption Scheme. In: Franklin, M.K.
(ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 426-442. Springer, Berlin (2004)
20. Naor, M., Yung, M.: Universal One-Way Hash Functions and their Cryptographic Applications. In:
The 21st Symposium on Theory of Computing, pp. 33-43. Association for Computing Machinery,
New York (1989)
21. Okamoto, T., Pointcheval, D.: The Gap-Problems: A New Class of Problems for the Security of
Cryptographic Schemes. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 104-118. Springer, Berlin(2001)
22. Pointcheval, D.: Chosen-Ciphertext Security for Any One-Way Cryptosystem. In: Imai, H., Zheng,
Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 129-146. Springer, Berlin (2000)
23. Rompel, J.: One-Way Functions are Necessary and Suﬃcient for Secure Signatures. In: The 22nd
Annual Symposium on Theory of Computing, pp. 387-384. Association for Computing Machinery,
New York (1990)
24. Schnorr, C. P.: Eﬃcient Identification and Signatures for Smart Cards. In: Brassard, G. (ed.)
CRYPTO ’89. LNCS, vol. 435, pp. 239-252. Springer, Berlin (1989)
25. Shoup, V.: Using Hash Functions as a Hedge against Chosen Ciphertext Attack. In: Preneel, B.
(ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 275-288. Springer, Berlin (2000)
26. Waters, B.: Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619-636. Springer, Berlin (2009)
27. Yilek, S.: Resettable Public-Key Encryption: How to Encrypt on a Virtual Machine. In: Pieprzyk,
J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 41-56. Springer, Berlin (2010)17

Appendix
A

Target Collision Resistant Hash Functions

Target collision resistant (TCR) hash functions [20, 23] are treated as a family. Let us
denote a function family as 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.
kExperimenttcr
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 CF’s advantage over Hfam in the game of target collision resistance as follows.
def

tcr
k
AdvtcrCF,Hfam (k) = Pr[ExperimentCF,Hfam (1 ) returns Win].

We say that Hfam is a TCR function family 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 ofa one-way function [20, 23].

B

Proof of Claim 1

Assume that (g, X1τ W1 , X2τ W2 , h, d1 , d2 ) is a twin DH tuple and put
Xiτ Wi =: g αi , h =: g β , di =: g αi β , i = 1, 2.
∗∗

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

Wi := Xi−τ g ui , i = 1, 2.
∗∗

So Xiτ Wi = Xiτ Xi−τ g ui = Xiτ −τ g ui and we have∗g αi −ui = Xiτ −τ , i = 1, 2.
Henceβ(τ −τ ∗ )di /hui = g αi β /g βui = g (αi −ui )β = Xi

, i = 1, 2.

c1 , Zc2 ) is a twin DH tuple for Yb = hτ −τ ∗ , Z
c1 = d1 /hu1 andThis means (g, X1 , X2 , Yb , Z
c2 = d2 /hu2 .
Z
The converse is also verified by setting the goal to be di = g αi β , i = 1, 2 and startingβ(τ −τ ∗ )from the assumption that Zbi = di /hui = Xi
, i = 1, 2. (Q.E.D.)18