Self Evaluation of PSEC-KEM
1 Introduction
This document describes the security assessment and performance on PSECKEM, which is a key distribution scheme in the public-key cryptosystem.

2 Design Policy and the Underlying Theory andTechniques
PSEC-KEM is a version (PSEC-KEM in [4]) modi ed to KEM (Key Encapsulation Mechanism) from a public-key encryption, PSEC-2, which is a version [1]with the strongest security converted from the primitive elliptic curve encryptionfunction, elliptic 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 has 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 (NMCCA2)) 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 and elliptic curve (EC)ElGamal. 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(OTP)
Yes
EC-CDH
Truly random**
EC-Cramer-Shoup
Yes
EC-DDH
UOWHF
*
ECIES
Yes
EC-GDH
Truly random**
EC-ElGamal
No (broken)
000EC-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 as1

sumptions, respectively. ** denotes that the eciency is almost optimal, and *denotes that the eciency is less than the almost optimal cases.
2.2 Summary of Eciency

Here we compares the eciency of PSEC-KEM with those of other encryption
schemes, EC-Cramer-Shoup, ECIES, and EC-ElGamal.
To compare the schemes under the equal conditions, we assume that theplaintext size is 128 bits for all schemes, since public-key encryption schemes
are usually employed for key distribution of a symmetric-key encryption (128
key is the most typical key size of symmetric-key encryptions).
The parameter sizes for EL-Cramer-Shoup, ECIES, 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 (43 )ECIES
2
1 (23 )
EC-ElGamal
2
1

3: 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.
Here, we view MGF as a random oracle. This e ectively gives us two independent random oracles,

G : BhLen ! BpLen+128+KeyLen ;H : B32+21qmLen ! BhLen :For simplicity, we denote EC for ECP2OSP(C1 ; qmLen) and EQ for ECP2OSP(Q; qmLen).
Theorem 3.1 Let A be an (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 the success probability, "0 , of providing a list of (qH + qD ) strings which2includes a correct answer of the elliptic curve computational Die-Hellman(CDH) problem regarding K and the running time t0 , such that+ 20128 ) 0 2qD + qG ;"0  2(1 + "20128) 0 (qG + 3qD )(1
p
2hLen
and

t0  t + qH 1 (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].
Hereafter, we will repeatedly use the following simple result:Lemma 3.2 For any probability events E, F and G
E j F ^ G]
Pr[E ^ F j G]  Pr[
Pr[F j 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(i.e., semantic security) in the scenario of the key
encapsulation mechanism such as PSEC-KEM is a bit di erent from the (publickey) encryption. See Section 2.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
greater than ". Let us describe the reduction B.

3.1.1 Top Level Description of the Reduction.
1. B is given public key PK including two point P and W on E and anotherpoint C13 . The aim of B is to obtain a list of data including the DH
solution, Q3 , for (P; W;C13 ) such that logP W = logC13 Q3 (= s).
3

2. B randomly selects a bit b and two random strings, c32 2 BhLen andK 2 BkeyLen . B runs A on the public data, ciphertext c3 = (EC 3 ;c32 )with EC 3 = ECP2OSP(C13 ; 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 b0 . B then outputs the list of queries asked to H
(especially its EQ part), in which EQ3 (i.e., Q3 ) 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 6= EC 3 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.
 For a fresh query 3 = (EC 3 ; EQ) to H , the simulator randomly selects
H (3 ) and the pair (3 ; H (3 )) is concatenated to H-List. It calculates r =c32 8 H (3 ), and looks for a query r in the GList. When it does not exist,
the simulator randomly selects t 2 BpLen+128 as t = [G(r)]pLen+128 , i.e.,the (pLen +128) bit pre x of G(r). Then, it calculates = OS2IP(t) modp, and checks whether C13 = P . If it holds, it calculates Q3 = W , whichis the solution of the DH problem with (P; W;C13 ) (and outputs Q3 ). If
EQ = ECP2OSP(Q3 ; qmLen), it sets [G(r)]keyLen = K if b = 0, and it
randomly selects [G(r)]keyLen if b = 1. In this case, (EC 3 ; c32 ) is a valid
output (or correctly simulated output) of the encryption oracle in the real
scenario of IND-CCA2. If C13 6= 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 ()) 2 H-List such that  = (EC; EQ) (for any
EQ). If no such pair is found in H-List, \Reject" is returned. If such pairexists, it calculates r = c2 8 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. Then, it 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
the both equations hold, DS outputs [G(r)]keyLen , i.e., keyLen bit sux ofG(r), as key k.

4

3.1.4 Remarks.

When we have found Q3 , we could output the expected result Q3 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 b0 (orafter a time limit).
The distribution of in the simulation is a bit di erent from that in thereal situation: in the simulation is distributed uniformly in f0; 1; : : : ;p 0 1g,
but in the real situation it is a bit biased as that = 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 = C10 if and only if EC = EC 0 , and Q = Q0 if and only if
EQ = EQ0.
3.2 Notations

In order to proceed to the analysis of the success probability of the abovementioned reduction, one needs to set up notations. First, we still denote with astar (3 ) all variables related to the challenge ciphertext c3 = (EC 3 ; c32 ), 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 3 ; EQ3 ) has been asked to H , andAskG denotes the event that query r3 has been asked to G.
 GBad is the event that r3 (= c32 8 H (EC 3 ; EQ3 )) is asked to G oracle andEC 3 6= ECP2OSP( P ), or EC 3 = ECP2OSP( P ) but [G(r3 )]keyLen 6= K
if b = 0, where = OS2IP(t3 ) mod p and t3 = [G(r3 )]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 3;{ RBad denotes the event that r = r3;
 AskRE denotes the intersection of both events about the oracle queries,
AskRE = AskR ^ AskE, where{ AskR denotes the event that r (= c2 8 H (EC; EQ)) has been asked
to G;
5

{ 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.

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 c3 = (EC 3; c32 ) has been directly
obtained from the encryption oracle, the decryption oracle simulation DS cancorrectly produce the decryption oracle's answers on qD queries (ciphertext; c =(EC; c2 ), c =6 c3 ) with probability greater than "1 , within time bound t1 , where (q + 3q )(1 + 20128 ) q 
D"1  1 0 G D p;+ 2hLent1  qH 1 (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 c3 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 both queries to the random oracles G and H .

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 = r3 implies that = 3 , C1 = C13 (i.e.,
EC = EC 3 ), Q = Q3 , and H (EC; EQ) = H (EC 3 ; EQ3 ). Hence c2 = c32 , i.e.,c = (EC; c2) is equivalent to c3 = (EC 3 ; c32 ). 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 the6decryption oracle such that c = (EC 3 ;c2 ) with c2 6= c32 (i.e., r 6= r3 ) satis es
OS2IP([G(r)]pLen+128 )  OS2IP([G(r3 )]pLen+128 ) 0128
(mod p). The probability
1+2
to satisfy the equation for each c is at most p . 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,
0128
Pr[Fail ^ EBad]  (qG + qD )(1 + 2 ) :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]:
For the former term, since r is never asked to G and independent from r3 ,the probability that c is valid (i.e., =0128OS2IP([G(r)]pLen+128 ) (mod p) and
EC = ECP2OSP( P )) is at most 1+2p . Since the adversary has a chancefor qD queries to decryption oracle,
0128
Pr[Fail ^ :EBad ^ :AskR]  qD (1 +p2 ) :For the latter term, Pr[Fail ^ :EBad ^ AskR ^ :AskE], r is queried to G,
but (EC;EQ) is never asked to H and independent from (EC 3 ; EQ3 ). So theprobability that r0 = c2 8 H (EC; EQ) is 0equivalent
to r or G(r0 ) happens to be128
1 + 1+2 . Since the adversary has a chance
consistent with C1 is at most 2hLenpfor qD queries to the decryption oracle,
1 + 1 + 20128 ):Pr[Fail ^ :EBad ^ :AskR]  qD ( 2hLenp
As a consequence,
0128+2
Pr[Fail]  (qG + 3qD )(1p) + qD :2hLen
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 1 (T + O(1));
where T is the computational complexity of the operations of P and W .

7

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;C13 ), to obtain a listof qH values including Q3 . 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] 0 Pr[:AskH ^ Bad] Pr[Bad] 0 Pr[:AskH ^ GBad] 0 Pr[:AskH ^ Fail] Pr[Bad] 0 Pr[GBad j :AskH] 0 Pr[Fail] Pr[Bad] 0 Pr[AskG j :AskH] 0 Pr[Fail]+ 20128 ) 0 2qD + qG :
 Pr[Bad] 0 (qG + 3qD )(1p
2hLen) + qD is directly obtained from lemma 3.3,
Here, Pr[Fail]  (qG +3qD )(1+2p
2hLen
and Pr[GBad j :AskH]  Pr[AskG j :AskH] is obtained from the fact that event
GBad implies AskG. When :AskH occurs, H (EC 3 ;EQ3 ) is unpredictable, and+qD .
r3 = c32 8H (EC 3 ; EQ3 ) is also unpredictable. Hence Pr[AskG j :AskH]  q2GhLen
We then evaluate the second term.
Pr[AskH ^ :Bad] = Pr[:Bad] 1 Pr[AskH j :Bad]
 Pr[:Bad] 1 Pr[A = b ^ AskH j :Bad]
 Pr[:Bad] 1 (Pr[A = b j :Bad] 0 Pr[A = b ^ :AskH j :Bad]) :Here, when :AskH occurs, H (EC 3 ;EQ3 ) is unpredictable, thus r3 = c32 8
H (EC 3 ; EQ3 ) is unpredictable, and so is b as well. This fact is independent fromevent :Bad. Hence Pr[A = b ^:AskH j :Bad]  Pr[A = b j :AskH ^:Bad] = 1=2.
Since the distribution of c3 = (EC 3 ; c32 ) in this simulation scenario is a bit different ((1 + 20128 ) times biased) from that of c3 in the real situation,
1"
2(1 + 20128 ) + 2  Pr[A = b]  Pr[A = b j :Bad] 1 Pr[:Bad] + Pr[Bad]:
Therefore, Pr[:Bad] "=(1 + 20128 ) 0 Pr[Bad]"1
Pr[AskH^:Bad]  2(1 + 20128 ) + 2 0 Pr[Bad] 0 2 =:2Combining the evaluation for the rst and second terms, and from the fact that
Pr[Bad]  0, one gets+ 20128 ) 0 qD + qG :Pr[AskH]  2(1 + "20128 ) 0 (qG + 3qD )(1
p
2hLen
0128

8

3.5 Complexity Analysis.

Since the major part of this reduction complexity is for the simulation of thedecryption oracle, the time complexity of the overall reduction ist0 = t + qH 1 (T + O(1));
where T is the computational complexity of the operations of P and W .

4 Evaluation by Implementation
In this section, we show the speed and memory usage when we implement ESIGN
by C language. We use the recommended parameters in our speci cation.
The environment is followings:
CPUIntel Pentium-III 600MHz
Memory 128 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 test.
The speed is following:
Key generation 5.64 ms
Encryption
11.09 ms
Decryption
10.97 ms
The memory usage is following:
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).
[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, N2563, http://shoup.net/papers/, 2001 Sep.
9