Self Evaluation of PSEC-KEM
1Introduction

This document describes the security assessment and performance of PSECKEM, a key distribution scheme in public-key cryptosystems.

2

Design Policy and the Underlying Theory andTechniques

PSEC-KEM is a version [4] modiﬁed to KEM (Key Encapsulation Mechanism)
from a public-key encryption with the strongest security, PSEC-2, which isconverted (by [1]) from the primitive elliptic curve encryption function, theelliptic curve ElGamal encryption function.
PSEC-KEM inherits the various practical merits of the elliptic curve encryption function (elliptic curve ElGamal encryption function), and is provento oﬀer the strongest level of security (semantic security against adaptive chosenciphertext attacks: IND-CCA2) under some assumptions.
We will show its security and performance results below.

2.1

Summary of Security

PSEC-KEM is semantically secure against adaptive chosen-ciphertext attacks(IND-CCA2) (or non-malleable against adaptive chosen-ciphertext attacks (NM-1

CCA2)) in the random oracle model, under the elliptic curve computationalDiﬃe-Hellman (CDH) assumption.
We will compare the security of PSEC-KEM with other encryption schemes
such as the elliptic curve (EC-)Cramer-Shoup, ECIES-KEM (see [4]) and elliptic curve (EC-)ElGamal. Here, we assume that EC-Cramer-Shoup and ECElGamal are used for key distribution (i.e., KEM).
The following table summarizes the comparison of security.
Table 1: Comparison of Security

SchemeProvably Secure?

Number-theoretical

Functional

Reduction(IND-CCA2?)

assumption

assumption

eﬃciency

PSEC-KEM

Yes

EC-CDH

Truly random**

EC-Cramer-Shoup

Yes

EC-DDHUOWHF*ECIES-KEM

Yes

EC-GDH

Truly random**

EC-ElGamal

No (broken)

−

−

−

EC-CDH, EC-DDH and EC-GDH denote the elliptic curve versions of computational Diﬃe-Hellman, decisional Diﬃe-Hellman and gap Diﬃe-Hellman assumptions, respectively. ** denotes that the eﬃciency is almost optimal, and *denotes that the eﬃciency is less than the almost optimal cases. The deﬁnitionof semantic security against adaptive chosen-ciphertext attacks (IND-CCA2) inthe scenario of KEM (key encapsulation mechanism) is slightly diﬀerent from2

that of the (public-key) encryption. See Section 3.2 in [4] for the deﬁnition.

2.2

Summary of Eﬃciency

Here we compare the eﬃciency of PSEC-KEM to that of other schemes (ECCramer-Shoup, ECIES-KEM, and EC-ElGamal).
The parameter sizes for EL-Cramer-Shoup, ECIES-KEM, EC-ElGamal are
assumed to be the same as those of PSEC-KEM. In this table, we show therequired number of elliptic curve multiplications for each operation.
Table 2: Comparison of Eﬃciency
SchemeEncryption

Decryption

PSEC-KEM

2

2

EC-Cramer-Shoup5

3 (4∗ )ECIES-KEM

2

1 (2∗ )

EC-ElGamal

2

1∗: The case when an additional multiplication is required to check whether
a ciphertext is in the subgroup generated by the base point.

3

Security Proof of PSEC-KEM

In this section, we will prove that PSEC-KEM is semantically secure against
adaptively chosen-ciphertext attacks, under the the elliptic curve computationalDiﬃe-Hellman assumption and in the random oracle model.

3Here, we view MGF as a random oracle. This eﬀectively gives us two independent random oracles,
G : BhLen → BpLen+128+KeyLen ,H : B32+2·qmLen → BhLen .
For simplicity, we use EC for ECP2OSP(C1, qmLen) and EQ for ECP2OSP(Q, qmLen).
Theorem 3.1 Let A be a (adaptively chosen-ciphertext attack) CCA2–adversary
against the “semantic security” (IND) of PSEC-KEM (K, E, D), with advantage
ε and running time t, making qD , qG and qH queries to the decryption oracle,
and the random oracles G and H respectively. Then, there exists an algorithmwith success probability, ε , can provide a list of (qH +qD ) strings which includes
a correct answer of the elliptic curve computational Diﬃe-Hellman (CDH) problem regarding K and the running time t , such thatε ≥(qG + 3qD )(1 + 2−128 ) 2qD + qG
ε−−,2(1 + 2−128 )
p
2hLen

and
t ≤ t + qH · (T + O(1)) ,where T denotes the time complexity of computing two elliptic curve multiplication operations regarding K.
Note: If there exists an algorithm which outputs a list of (qH + qD ) strings
including a correct answer of the computational Diﬃe-Hellman (CDH) problem,
then we can eﬃciently obtain the correct answer of the computational DiﬃeHellman (CDH) problem, using the algorithm (by the random self-reducible
property of the CDH problem) [3, 4].
4Advantage ε is deﬁned as 2 × Pr[A outputs correct answer b ∈ {0, 1}] − 1, inthe underlying scenario.
Hereafter, we will repeatedly use the following simple result:Lemma 3.2 For any probability events E, F and G Pr[E | F ∧ G]
Pr[E ∧ F | G] ≤ Pr[F | G].
We prove theorem 3.1 in three stages. The ﬁrst presents the reduction of algorithm B for breaking the Computational Diﬃe-Hellman (CDH) problem to the
IND-CCA2 adversary A for PSEC-KEM. The second shows that the decryption
oracle simulation employed in this reduction works correctly with overwhelming
probability. Finally, we analyze the success probability of our reduction in total, through the incorporation of the above-mentioned analysis of the decryption
oracle simulation.
Note: The deﬁnition of IND-CCA2in the scenario of the key encapsulation
mechanism such as PSEC-KEM is slightly diﬀerent from that of the (publickey) encryption. See Section 3.2 in [4] for the deﬁnition.

3.1

Description of the Reduction

In this ﬁrst part, we recall how reduction operates. Let A be an adversary
against the semantic security of PSEC-KEM with (K, E, D), under chosenciphertext attacks. Within time bound t, A asks qD , qG and qH queries tothe decryption oracle and the random oracles G and H respectively, and distinguishes key K (either the correct key or just a random string) with an advantage
5

greater than ε. Let us describe the reduction B.

3.1.1

Top Level Description of the Reduction.

1. B is given public key P K including two points, P and W , on E andanother point C1∗ . The aim of B is to obtain a list of data including the
DH solution, Q∗ , for (P, W, C1∗ ) such that logP W = logC1∗ Q∗ (= s).
2. B randomly selects a bit b and two random strings, c∗2 ∈ BhLen andK ∈ BkeyLen . B runs A on the public data, ciphertext c∗ = (EC ∗ , c∗2 )with EC ∗ = ECP2OSP(C1∗, qmLen) and K. B simulates the answers to
the queries of A to the decryption oracle and random oracles G and H,
respectively. See the description of these simulations below.
3. A ﬁnally outputs answer b . B then outputs the list of queries asked to H
(especially its EQ part), in which EQ∗ (i.e., Q∗ ) may be included.

3.1.2

Simulation of Random Oracles G and H.

The random oracle simulation has to simulate the random oracle answers, managing query/answer lists G-List and H-List for the oracles G and H, respectively;
both are initially set to empty lists:• For a fresh query δ = (EC, EQ) with EC = EC ∗ to H, the simulator
outputs a random value H(δ), and the pair (δ, H(δ)) is concatenated to
the H-List. For a fresh query r to G, it outputs a random value G(r), andthe pair (r, G(r)) is concatenated to the G-List.

6• For a fresh query δ ∗ = (EC ∗ , EQ) to H, the simulator randomly selectsH(δ ∗ ) and the pair (δ ∗ , H(δ ∗ )) is concatenated to H-List. It calculates r =c∗2 ⊕ H(δ ∗ ), and looks for a query r in the GList. When it does not exist,
the simulator randomly selects t ∈ BpLen+128 as t = [G(r)]pLen+128 , i.e.,the (pLen+128) bit preﬁx of G(r). It then calculates α = OS2IP(t) mod p,
and checks whether C1∗ = αP . If it holds, it calculates Q∗ = αW , whichis the solution of the DH problem with (P, W, C1∗ ) (and outputs Q∗ ). If
EQ = ECP2OSP(Q∗, qmLen), it sets [G(r)]keyLen = K if b = 0, and it
randomly selects [G(r)]keyLen if b = 1. In this case, (EC ∗ , c∗2 ) is a valid
output (or correctly simulated output) of the encryption oracle in the real
scenario of IND-CCA2. If C1∗ = αP , it randomly selects [G(r)]keyLen .

3.1.3

Simulation of the Decryption Oracle.

On query c = (EC, c2 ) to the decryption oracle, decryption oracle simulation
DS looks at query-answer (δ, H(δ)) ∈ H-List such that δ = (EC, EQ) (for any
EQ). If no such pair is found in H-List, “Reject” is returned. If such a pairexists, it calculates r = c2 ⊕ H(δ), and it looks for a query r in the GList.
If it does not exist, it randomly selects G’s answer to r, G(r), and the pair(r, G(r)) is concatenated to the G-List. It then calculates α = OS2IP(t) mod p,
where t = [G(r)]pLen+128 . It checks whether EC = ECP2OSP(αP ) and EQ =ECP2OSP(αW ). If either one of them does not hold, “Reject” is returned. If
both equations hold, DS outputs [G(r)]keyLen , i.e., keyLen bit suﬃx of G(r),as key k.

7

3.1.4

Remarks.

When we ﬁnd Q∗ , we could output the expected result Q∗ and stop the reduction. But for this analysis, we assume the reduction goes on and that B only
outputs it, or the list of queries asked to H, once A has answered b (or after atime limit).
The distribution of α in the simulation is a bit diﬀerent from that in the realsituation. In the simulation, α is distributed uniformly in {0, 1, . . . , p − 1}, but
in the real situation it is a bit biased as α = OS2IP(t) mod p and t is uniform
in BpLen+128 .
Since our coding method of an elliptic curve point is a one-to-one and onto
mapping, C1 = C1 if and only if EC = EC  , and Q = Q if and only if
EQ = EQ .

3.2

Notations

In order to proceed to the analysis of the success probability of the abovementioned reduction, we ﬁrst provide some notations. First, we denote with astar (∗ ) all variables related to the challenge ciphertext c∗ = (EC ∗ , c∗2 ), obtained
from the encryption oracle. All other variables refer to the decryption query c,asked by the adversary to the decryption oracle, and thus to be decrypted bythis simulation. We consider several events about queries to the random oracles
and the decryption oracle:• AskH denotes the event that query (EC ∗ , EQ∗ ) has been asked to H, andAskG denotes the event that query r∗ has been asked to G.
8• GBad is the event that r∗ (= c∗2 ⊕ H(EC ∗ , EQ∗ )) is asked to G oracle andEC ∗ = ECP2OSP(αP ), or EC ∗ = ECP2OSP(αP ) but [G(r∗ )]keyLen = K
if b = 0, where α = OS2IP(t∗ ) mod p and t∗ = [G(r∗ )]pLen+128 (bit b is
ﬁxed in the reduction scenario). Note that the event GBad implies AskG.
As seen above, GBad is the only event that makes the simulation imperfect,in the chosen-plaintext attack scenario.
• Fail denotes the event that the above decryption oracle simulator outputs
at least one wrong decryption answer among qD answers.
• Bad = GBad ∨ Fail.
• CBad denotes the union of the bad events, CBad = RBad ∨ EBad, where– EBad denotes the event that EC = EC ∗ ;– RBad denotes the event that r = r∗ ;• AskRE denotes the intersection of both events about the oracle queries,
AskRE = AskR ∧ AskE, where– AskR denotes the event that r (= c2 ⊕ H(EC, EQ)) has been asked
to G;– AskE denotes the event that (EC, EQ) has been asked to H;
Note that the Fail event is limited to the situation in which DS rejects a
ciphertext whereas it would be accepted by the actual decryption oracle. Indeed,
when DS accepts, we see that the ciphertext is actually valid and corresponds
to the output plaintext.
93.3

Analysis of the Decryption Oracle Simulation

We analyze the success probability of decryption oracle simulator DS.

3.3.1

Security Claim.

Lemma 3.3 When at most one ciphertext c∗ = (EC ∗ , c∗2 ) has been directly
obtained from the encryption oracle, the decryption oracle simulation DS cancorrectly produce the decryption oracle’s answers to qD queries (ciphertext; c =(EC, c2 ), c = c∗ ) with probability greater than ε1 , within time bound t1 , where
ε1 ≥ 1 −(qG + 3qD )(1 + 2−128 )qD+ hLenp2,t1 ≤ qH · (T + O(1)),
and T is the computational complexity of the operations of αP and αW .
Before we start the analysis, we recall that the decryption oracle simulator
is given the ciphertext c to be decrypted, as well as the ciphertext c∗ obtained
from the encryption oracle and both the G-List and H-List resulting from theinteractions with the simulator of the random oracles G and H. If the ciphertext
has been correctly built by the adversary (r has been asked to G and (EC, EQ)to H), the simulation will output the correct answer. However, it will output“Reject” in any other situation, whereas the adversary may have built a valid
ciphertext without asking either query to the random oracles G and H.

10

3.3.2

Success Probability.

Since our goal is to show the probability of the event Fail. Granted ¬CBad ∧AskRE, the simulation is perfect, and cannot fail. Thus, we have to consider thecomplementary events:
Pr[Fail] = Pr[Fail ∧ CBad] + Pr[Fail ∧ ¬CBad ∧ ¬AskRE].
First we focus on the former term, Pr[Fail ∧ CBad]. CBad = RBad ∨ EBad, but
RBad never occurs. This is because: r = r∗ implies that α = α∗ , C1 = C1∗ (i.e.,
EC = EC ∗ ), Q = Q∗ , and H(EC, EQ) = H(EC ∗ , EQ∗ ). Hence c2 = c∗2 , i.e.,c = (EC, c2 ) is equivalent to c∗ = (EC ∗ , c∗2 ). Such c is not allowed as a queryto the decryption oracle. Thus, CBad = EBad. We will evaluate Pr[Fail ∧ EBad],
which is the probability that there exists at least one c among qD queries to thedecryption oracle such that c = (EC ∗ , c2 ) with c2 = c∗2 (i.e., r = r∗ ) satisﬁes
OS2IP([G(r)]pLen+128 ) ≡ OS2IP([G(r∗ )]pLen+128 ) (mod p). The probability−128

of satisfying this equation for each c is at most 1+2p

. The adversary has a(potential) chance to ask qG queries to check whether the equation holds, andan additional chance for qD queries to decryption oracle. So in total,
Pr[Fail ∧ EBad] ≤(qG + qD )(1 + 2−128 ).
p

We now evaluate the latter term, Pr[Fail ∧ ¬CBad ∧ ¬AskRE]. Since CBad =EBad and AskRE = AskR ∧ AskE, it is
Pr[Fail ∧ ¬EBad ∧ (¬AskR ∨ ¬AskE)]≤ Pr[Fail ∧ ¬EBad ∧ ¬AskR] + Pr[Fail ∧ ¬EBad ∧ AskR ∧ ¬AskE].
11

For the former term, since r is never asked to G and is independent of r∗ ,the probability that c is valid (i.e., α = OS2IP([G(r)]pLen+128 ) (mod p) and−128

EC = ECP2OSP(αP )) is at most 1+2p

. Since the adversary has a chance toissue qD queries to the decryption oracle,
Pr[Fail ∧ ¬EBad ∧ ¬AskR] ≤qD (1 + 2−128 ).
p

For the latter term, Pr[Fail ∧ ¬EBad ∧ AskR ∧ ¬AskE], r is queried to G,
but (EC, EQ) is never asked to H and is independent of (EC ∗ , EQ∗ ). So theprobability that r = c2 ⊕ H(EC, EQ) is equivalent to r or G(r ) happens to be−128

1+ 1+2pconsistent with C1 is at most 2hLen. Since the adversary has a chance

to issue qD queries to the decryption oracle,1
1 + 2−128
Pr[Fail ∧ ¬EBad ∧ ¬AskR] ≤ qD ( hLen +).
2p
As a consequence,
Pr[Fail] ≤(qG + 3qD )(1 + 2−128 )qD+ hLen .
p2

The running time of this simulator includes just the computation time ofαP and αW for all α values obtained from ciphertext c = (EC, c2 ), the corresponding queries, (EC, EQ), in H-List, and the corresponding r values of G-Listand is thus at mostqH · (T + O(1)),
where T is the computational complexity of the operations of αP and αW .

12

3.4

Success Probability of the Reduction

This subsection analyzes the success probability of our reduction with respect
to the advantage of the IND-CCA2 adversary of PSEC-KEM. The goal of the
reduction is, given the elliptic curve parameters and (P, W, C1∗ ), to obtain a listof qH values including Q∗ . Therefore, the success probability is obtained by theprobability that event AskH occurs during the reduction.
We thus evaluate Pr[AskH] by splitting event AskH according to event Bad.
Pr[AskH] = Pr[AskH ∧ Bad] + Pr[AskH ∧ ¬Bad].
First let us evaluate the ﬁrst term.
Pr[AskH ∧ Bad] =Pr[Bad] − Pr[¬AskH ∧ Bad]≥

Pr[Bad] − Pr[¬AskH ∧ GBad] − Pr[¬AskH ∧ Fail]≥

Pr[Bad] − Pr[GBad | ¬AskH] − Pr[Fail]≥

Pr[Bad] − Pr[AskG | ¬AskH] − Pr[Fail]≥

Pr[Bad] −−128

Here, Pr[Fail] ≤ (qG +3qD )(1+2
p)(qG + 3qD )(1 + 2−128 ) 2qD + qG
−
.
p
2hLen

qD
+ 2hLenis directly obtained from lemma 3.3,

and Pr[GBad | ¬AskH] ≤ Pr[AskG | ¬AskH] is obtained from the fact that event
GBad implies AskG. When ¬AskH occurs, H(EC ∗ , EQ∗ ) is unpredictable, and+qDr∗ = c∗2 ⊕H(EC ∗ , EQ∗ ) is also unpredictable. Hence Pr[AskG | ¬AskH] ≤ q2GhLen.

We then evaluate the second term.
Pr[AskH ∧ ¬Bad] =≥Pr[¬Bad] · Pr[AskH | ¬Bad]
Pr[¬Bad] · Pr[A = b ∧ AskH | ¬Bad]
13

≥Pr[¬Bad] · (Pr[A = b | ¬Bad] − Pr[A = b ∧ ¬AskH | ¬Bad]) .

Here, when ¬AskH occurs, H(EC ∗ , EQ∗ ) is unpredictable, thus r∗ = c∗2 ⊕H(EC ∗ , EQ∗ ) is unpredictable, and so is b as well. This fact is independent fromevent ¬Bad. Hence Pr[A = b∧¬AskH | ¬Bad] ≤ Pr[A = b | ¬AskH∧¬Bad] = 1/2.
Since the distribution of c∗ = (EC ∗ , c∗2 ) in this simulation scenario is a bit different ((1 + 2−128 ) times biased) from that of c∗ in the real situation,1ε+ ≤ Pr[A = b] ≤ Pr[A = b | ¬Bad] · Pr[¬Bad] + Pr[Bad].
−128
2(1 + 2
) 2
Therefore,Pr[AskH∧¬Bad] ≥ε1Pr[¬Bad]ε/(1 + 2−128 ) − Pr[Bad]+−
Pr[Bad]=.
−2(1 + 2−128 ) 2
2
2

Combining the evaluation for the ﬁrst and second terms, and from the fact that
Pr[Bad] ≥ 0, one gets
Pr[AskH] ≥3.5

ε(qG + 3qD )(1 + 2−128 ) qD + qG−
− hLen .
2(1 + 2−128 )p2

Complexity Analysis.

Since the major part of this reduction complexity lies in the simulation of thedecryption oracle, the time complexity of the overall reduction ist = t + qH · (T + O(1)),
where T is the computational complexity of the operations of αP and αW .

14

4Evaluation by Implementation

In this section, we show the speed and memory usage when we implement ESIGN
in the C language. We use the recommended parameters in our speciﬁcation.
The environment is as follows:CPUIntel Pentium-III 600MHz

Memory128 Mbytes

OS

Microsoft Windows2000 SP2

Compiler

Microsoft Visual Studio 6.0 Enterprise Edition

We measure the speed by counting the CPU clock. We show the average
speed of 1000 random data tests.
The speed is as follows:
Key generation

5.64 ms

Encryption

11.09 ms

Decryption

10.97 ms

The memory usage is as follows:
Key generation

7.30 Kbytes

Encryption

2.64 Kbytes

Decryption

2.39 Kbytes

References[1] Fujisaki, E. and Okamoto, T.: Secure Integration of Asymmetric and Symmetric Encryption Schemes, Proc. of Crypto’99, Springer-Verlag, LNCS
1666, pp. 535–554 (1999).
15

[2] Bailey, D. V. and Paar, C.: Optimal Extension Fields for Fast Arithmetic in
Public-Key Algorithms, Proc. of Crypto’98, LNCS 1462, Springer-Verlag,
pp.472-485 (1998).
[3] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems.
In Eurocrypt’97, LNCS, Springer-Verlag, Berlin, 1997.
[4] V. Shoup. A Proposal for an ISO Standard for Public Key Encryption(v.2.0). ISO/IEC JTC1/SC27, N2918, http://shoup.net/papers/, 2001 Sep.

16