Self Evaluation of PSEC: Provably Secure Elliptic
Curve Encryption Scheme

Abstract
This document evaluates the security and performance of a public-key
cryptosystem, PSEC (Provably Secure Elliptic Curve Encryption Scheme),
which has three versions: PSEC-1, PSEC-2 and PSEC-3.

1 Security
1.1 Summary
1. If the elliptic curve decision Die-Hellman (EC-DDH) assumption (see thenext section) is true, PSEC-1 is secure in the strongest sense under the
random oracle model. Here, security in the strongest sense means to besemantically secure or non-malleable against adaptive chosen-ciphertext
attacks (IND-CCA2 or NM-CCA2).
2. If the elliptic curve Die-Hellman (EC-DH) assumption is true, PSEC2 with one-time padding (PSEC-2-OTP) is secure in the strongest sense
under the random oracle model.
3. If the elliptic curve Die-Hellman (EC-DH) assumption is true and theunderlying symmetric-key encryption is secure against passive attacks,
PSEC-2 with the symmetric-key encryption (PSEC-2-SymE) is secure in
the strongest sense under the random oracle model.
The advantage of this scheme is that security in the strongest sense is guaranteed for the total system that integrates the asymmetric and symmetric encryption schemes. Therefore, even if the underlying symmetric-key
encryption is secure only against passive attacks and not against active
attacks, PSEC-2, overall, guarantees security against active attacks.
An additional property of PSEC-2 is authentication without using MAC
function. That is, the recipient can con rm whether the decrypted message is the same as the one the originator sent.
1

4. If the elliptic curve gap Die-Hellman (EC-Gap-DH) assumption is true,
PSEC-3 with one-time padding (PSEC-3-OTP) is secure in the strongest
sense under the random oracle model.
5. If the elliptic curve gap Die-Hellman (EC-Gap-DH) assumption is true
and the underlying symmetric-key encryption is secure against passive
attacks, PSEC-3 with the symmetric-key encryption (PSEC-3-SymE) issecure in the strongest sense under the random oracle model.
PSEC-3 has the same additional merits as those of PSEC-2.

1.2 Comparison with Other Schemes
This section compares the security of PSEC-1/2/3 with other encryption schemes
such as OAEP-RSA, ACE and EC-ElGamal. Table 1 summarizes the comparison of security.
Table 1: Comparison of Security
SchemeProvably Secure? Number-theoretical Functional(IND-CCA2?)
assumption
assumption
PSEC-1Yes
EC-PDDH
Truly random
PSEC-2(OTP)
Yes
EC-DH
Truly random
PSEC-3(OTP)
Yes
EC-GDH
Truly random
EC-Cramer-Shoup
Yes
EC-DDHUOWHFOAEP-RSA
Yes
RSA
Truly random
PKCS#1 Ver.1
No00
DDH denotes the decision Die-Hellman, and EC-DH, EC-PDDH and ECGDH denote the elliptic curve versions of Die-Hellman, partial decision DieHellman and Gap-Die-Hellman assumptions. (OTP) denotes a scheme which
employs the one-time-pad as symmetric encryption.

1.3 Theoretical Results
This section shows our results on the security of PSEC-1, PSEC-2 and PSEC-3.
They are easily obtained from the results presented in [6, 7, 10, 11].
De nition 1.1 (EC-PDDH assumption) Let G be the key generator of PSEC1, and (q; a; b; p; P ) be a part of the public-key. Let s, t and u be uniformly
selected in Z=pZ. Q := sP , R := tP , V := stP , and W := uP . Let b 2 f0; 1g
be uniformly selected, and X := V if b = 0, and X := W if b = 1.
The elliptic curve partial decision Die-Hellman (EC-PDDH) problem is
intractable, if for any (uniform/ non-uniform) probabilistic polynomial time ma-2chine Adv , for any constant c, for suciently large k (= pLen),

Pr[Adv (q; a; b; p; P; Q; R; X ) = b] < 1=2 + 1=k :c

The probability is taken over the coin ips of G and Adv.
The assumption that the elliptic curve partial decision Die-Hellman problem is intractable is called the elliptic curve partial decision Die-Hellman(PDDH) assumption.

De nition 1.2 (EC-DDH Assumption) Let G be the setup algorithm of PSEC{

3, and (q; a; b; p; P ) be a part of the common parameters. Let r, s and t be uniformly selected in Z=pZ, and set R := r 1 P , S := s 1 P , T := t 1 P and U := rs 1 P .
Let b be a random coin. If b = 0, set v xT , otherwise set v xU .
The Elliptic Curve Decision Die-Hellman (EC{DDH) problem is intractable,
if for any probabilistic polynomial time machine A, for any constant c, for sufciently large k (= pLen),

Pr[A(q; a; b; p; P; R; S; v) = b] < 1=2 + 1=k :c

The probability is taken over the coin ips of G and A as well as the random
choice of r, s, t and b.
The assumption that the Elliptic Curve Decision Die-Hellman problem
is intractable is called the Elliptic Curve Decision Die-Hellman (EC-DDH)
assumption.

De nition 1.3 (EC-DH Assumption) Let G be a key generator of PSEC-2,and (q; a; b; p; P ) is a part of the public-key. Let s and t be uniformly selected in
Z=pZ. Q := sP , R := tP , and V := stP .
The elliptic curve Die-Hellman (EC-DH) problem is intractable, if for any(uniform/non-uniform) probabilistic polynomial time machine Adv , for any constant c, for suciently large k (= pLen),

Pr[Adv(q; a; b; p; P; Q; R) = V ] < 1=k :c

The probability is taken over the coin ips of G and Adv.
The assumption that the elliptic curve Die-Hellman problem is intractableis called the elliptic curve Die-Hellman (EC-DH) assumption.

De nition 1.4 (EC-GDH Assumption) The Elliptic Curve Gap Die-Hellman(EC-GDH) problem is intractable, if the EC{DH problem is still intractableeven for an adversary who has access to an oracle that perfectly answers the
EC-DDH problem.
The assumption that the Elliptic Curve Gap Die-Hellman problem is intractable is called the Elliptic Curve Gap Die-Hellman (EC-GDH) assumption.

De nition 1.5 (SPA(SymE)) Let Adv be an adversary that runs in two stages.
In the rst stage, Adv endeavors to come up with a pair of equal-length messages, m0 and m1 , along with some state information s, where jm0 j = jm1 j 

3(gLen) (a: constant). In the second stage, Adv is given a ciphertext y :=SymEnc(key; m ), where key 2 f0; 1g
and b 2 f0; 1g are randomly and
a

b

gLen

uniformly chosen.
SymE is secure against passive attacks (SPA), if for any (uniform/nonuniform) probabilistic polynomial time machine Adv , for any constant c, forsuciently large gLen,

Pr[Adv (gLen; m0 ; m1; s; y ) = b] < 1=2 + 1=(gLen) :The probability is taken over the coin ips of (key; b) and Adv .
c

Theorem 1.6 (PSEC-1) Let rLen  c0 pLen (c0: constant) and hLen =pLen 0 1. PSEC-1 is semantically secure against adaptive chosen-ciphertext attacks (IND-CCA2) or non-malleable against adaptive chosen-ciphertext attacks(NM-CCA2) in the random oracle model, provided that the EC-DDH assumption
is true.

Theorem 1.7 (PSEC-2-OTP) Let SymE for PSEC-2 be the one-time padding.

Let rLen = qLen 0 1, and hLen = pLen 0 1. PSEC-2 is semantically secure against adaptive chosen-ciphertext attacks (IND-CCA2) or non-malleable
against adaptive chosen-ciphertext attacks (NM-CCA2) in the random oracle
model, provided that the EC-DH assumption is true.

Theorem 1.8 (PSEC-2-SymE) Let rLen = qLen 0 1, and hLen = pLen 0
1. PSEC-2 is semantically secure against adaptive chosen-ciphertext attacks(IND-CCA2) or non-malleable against adaptive chosen-ciphertext attacks (NMCCA2) in the random oracle model, provided that the EC-DH assumption is true
and that the underlying SymE is secure against passive attacks (IND-PAS).

Theorem 1.9 (PSEC-3-OTP) Let SymE be the one-time pad, and thus mLen =kLen. Let hLen = pLen=a for some constant a. PSEC-3-OTP is chosen-

ciphertext secure in the random oracle model, provided that the EC-GDH assumption holds.

Theorem 1.10 (PSEC-3-SymE) Let hLen = pLen=a for some constant a.

PSEC-3-SymE is chosen-ciphertext secure in the random oracle model, provided
that the EC-GDH assumption holds and that the underlying SymE is secureagainst passive attacks, for suitable kLen and mLen.

Remark: We can also give the concrete eciency analysis of the reduction forproving the security, and show that our reduction is ecient [6, 7].

2 Performance as Implementated
2.1 Performance in Hardware
 Process:
Cell base.
4 Design environment:

Verilog-XL + DesignCompiler

 Resource:

About 25.6KG(@ 2NAND areal equality) + Memory(13312bit)
Structure: [Random logic+Multiplier22+Adder] + [Memory(13312bit)] Speed:Evaluation speed in 30MHz clock. (Measured by simulator)
PSEC-1

PSEC-2

Encryption 45 ms
Decryption 45 ms

PSEC-3

Encryption 45 ms
Decryption 45 ms

Encryption 45 ms
Decryption 23 ms(Assuming key length = 160 bit.)

2.2 Performance in Software Platform:
CPU: Pentium with MMX 266MHz
OS: Turbo Linux version 4.0
 Language:
C Language (gcc version 2.91.60)
gnu mp (gmp version 3.0.1) for large integer calculation
 Memory size(Code size):
PSEC-1

Encryption 63.34 Kbytes
Decryption 63.18 Kbytes

PSEC-2

Encryption 65.61 Kbytes
Decryption 65.97 Kbytes

PSEC-3

Encryption 65.69 Kbytes
Decryption 65.89 Kbytes

 Memory size(Work size):
PSEC-1

Encryption 1032 Kbytes
Decryption 1028 Kbytes

PSEC-2

Encryption 988 Kbytes
Decryption 1068 Kbytes

PSEC-3

Encryption 1056 Kbytes
Decryption 780 Kbytes

 Process speed:
5

PSEC-1

Encryption 76.4 ms
Decryption 70.6 ms

PSEC-2

Encryption 77.1 ms
Decryption 72.0 ms

PSEC-3

Encryption 77.3 ms
Decryption 35.8 ms(Assuming key length = 160 bit.) Data size:

160 bits
160 bits
160 bits
160 bitsSize of plaintext
128 bitsSize of public key le 176 bytes
Size of secret key le 48 bytes
Size of ciphertext le 89 bytes(PSEC-1) / 105 bytes(PSEC-2) / 125 bytes(PSEC-3)
pLen
qLen
hLen
gLen

 Optimize level:

We use compile option \gcc -O3."
This evaluation is a result of executing sample program in http://www.nttmcl.com/sec.
We can accelerate elliptic curve scalar multiplication by using window
method or some other techniques. In this evaluation, we only used simple
binary method.
Then, we can implement more faster program than the sample code.

3 Comparison of Computational Eciency with
Other Schemes

This section compares the eciency of PSEC with those of other encryption
schemes, EC-ElGamal and EC-Cramer-Shoup.
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).
We then assume the following parameter sizes for PSEC-1/2/3. The eld
size (qLen) and the size of the order of the base point (pLen) are 160 bits.
For PSEC-1, random string length (rLen) is 32 bits, and hashed value length(hLen) is 160 bits. As for PSEC-2-OTP, random string length (rLen) is 160
bits, hashed value lengths (gLen and hLen) are 128 bits and 160 bits. PSEC3-OTP assumes that hashed value lengths (gLen and hLen) are 128 bits.
The parameter sizes for EC-ElGamal and EL-Cramer-Shoup are assumed tobe the same as those of PSEC.
6

In our estimation, we assume standard (extended) binary methods for all
schemes. We ignore the minor terms such as the complexities of hash function
evaluations and exclusive-or operations.
For estimating the lengths of keys and ciphertexts, we ignore the lengthsof the common parameters among users such as elliptic curve parameters, andother minor terms such as parameter size information.
The following table summarizes the comparison of eciency.
Table 2: Comparison of Eciency
SchemeEncryption Decryption Key Length Ciphertext(#M (160)) (#M (160)) (jq j) (bits) Length(bits)
PSEC-1
480
480
160
320
PSEC-2(OTP)
480
480
160
448
PSEC-3(OTP)
480
240
160
576
EC-ElGamal
480
240
160
320
EC-Cramer-Shoup
1000
520
480
608
Here, #A(160) denotes the number of executions of the elliptic curve addition over a nite eld with 160 bit size.

References[1] Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P.: Relations Among
Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto'98,
LNCS 1462, Springer-Verlag, pp. 26{45 (1998).
[2] Bellare, M. and Rogaway, P.: Random Oracles are Practical: A Paradigm
for Designing Ecient Protocols, Proc. of the First ACM Conference on
Computer and Communications Security, pp.62{73 (1993).
[3] Bellare, M. and Rogaway, P. : Optimal Asymmetric Encryption, Proc. ofEurocrypt'94, LNCS 950, Springer-Verlag pp.92-111 (1995).
[4] Bleichenbacher, D.: Chosen Ciphertext Attacks Against Protocols Basedon the RSA Encryption Standard PKCS #1, Proc. of Crypto'98, LNCS
1462, Springer-Verlag, pp. 1{12 (1998).
[5] Canetti, R., Goldreich, O. and Halevi, S.: The Random Oracle Methodology, Revisited, Proc. of STOC, ACM Press, pp.209{218 (1998).
[6] Fujisaki, E. and Okamoto, T.: How to Enhance the Security of Public-Key
Encryption at Minimum Cost, Proc. of PKC'99, Springer-Verlag, LNCS
1560, pp. 53{68 (1999).
7

[7] 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).
[8] IEEE P1363 Draft, http://grouper.ieee.org/groups/1363/P1363/draft.html(1999).
[9] Joye, M., Quisquater, J.J., and Yung, M.: On the Power of Misbehaving
Adversaries and Security Analysis of EPOC, Manuscript (February 2000).
[10] Okamoto, T. and Pointcheval, D.: OCAC: an Optimal Conversion for
Asymmetric Cryptosystems, manuscript (2000).
[11] Okamoto, T. and Pointcheval, D.: PSEC{3: Provably Secure Elliptic Curve
Encryption Scheme { V3, submission to P1363a (2000).
[12] 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).

8

Appendix
OCAC: an Optimal Conversion for Asymmetric
Cryptosystems
Tatsuaki Okamoto

David Pointcheval

Abstract
Five years after the optimal asymmetric encryption padding (OAEP)
which makes chosen-ciphertext secure encryption scheme from any trapdoor one-way permutation (but whose unique application is RSA), thispaper presents OCAC, an optimal conversion which applies to any weakly
secure cryptosystem: the overload is negligible, since it just consists, aswith OAEP, of two hashings for both encryption and decryption. Furthermore, advantages of OCAC beyond OAEP are numerous:
1. it is more general than OAEP, since it can apply to any partially
trapdoor one-way function (RSA and modular square, but also DieHellman, Higher Residues, etc);
2. it is possible to integrate symmetric encryption (block and stream
ciphers) to reach very high speed rates;
3. it also provides a key distribution with session key encryption which
achieves chosen-ciphertext security with an only semantically secure
symmetric scheme.
Therefore, OCAC could become a new alternative to OAEP, and evenreach security relative to factorization.
In addition, in order to clarify the security requirement of the underlying asymmetric encryption, this paper introduces a novel class ofcomputational problems, the, which is considered to be dual
to the class of the. We show the relationship among
inverting problems ( , computational-DH problem), decision problems( , decision-DH problem), and gap problems ( , gap-DH problem).
gap problems

decision problems
e.g.

e.g.

e.g.

1 Introduction

For a long time many conversions from a weakly secure encryption into a chosenciphertext secure cryptosystem have been attempted, with variable success.
Such a goal is of greatest interest since many one-way encryption schemes
are known, with variable eciency and various properties, whereas chosenciphertext secure schemes are very rare.

1.1 Chosen-Ciphertext Secure Cryptosystems
Until few years ago, the description of a cryptosystem, together with someheuristic arguments for security, were enough to convince and to make a scheme
to be widely adopted. Formal semantic security [15] and further non-malleability [11]were just seen as theoretical properties. However, after multiple cryptanalyses
9

of international standards [5, 8, 7], provable security has been realized to beimportant and even became a basic requirement for any new cryptographic
protocol. Therefore, for the last two years, many cryptosystems have been proposed. Some furthermore introduced new problems [17, 21, 18, 23, 26], otherare intricate constructions, over old schemes, to reach chosen-ciphertext security (from El Gamal [33, 32, 9, 1, 20], Okamoto-Uchiyama [22], D-RSA [25] orPaillier [24]), with speci c security proofs.
Indeed, it is easy to describe a one-way cryptosystem from any trapdoor
problem. Furthermore, such trapdoor problems are not so rare (Die-Hellman [10],factorization, RSA [29], elliptic curves, McEliece [16], etc). A very nice result
would be a generic and ecient conversion from any such trapdoor problem
into a chosen-ciphertext secure encryption scheme.

1.2 Related WorkIn 1994, Bellare and Rogaway [3] suggested such a conversion, the so-called
OAEP (Optimal Asymmetric Encryption Padding). However, its application
domain was restricted to trapdoor permutations, which is a very rare object(RSA seems to be the only one application). Nevertheless, it provided themost ecient RSA-variant, the OAEP-RSA scheme, provably chosen-ciphertext
secure, and became the new RSA standard { PKCS #1 [30].
At PKC '99, Fujisaki and Okamoto [13] proposed another conversion withfurther improvements [14, 27]. It therefore seemed that the expected goal wasreached: a generic conversion from any one-way cryptosystem into a chosenciphertext secure encryption scheme. However, the resulting scheme is not optimal, from the computational point of view. Namely, the decryption phase ismore heavy than one could expect, since it requires a re-encryption.
As a consequence, with those conversions, one cannot expect to obtain ascheme with an easy decryption phase (unless both encryption and decryption
are easy, which is very unlikely). However, decryption is usually implemented
on a smart card, hence ecient decryption process is a challenge with a practical
impact.
1.3 Achievement: a New and Optimal Conversion
The present work provides a new conversion which is optimal in both the encryption and decryption phases. Indeed, the encryption needs an evaluation of
the one-way function, and the decryption just makes one call to the inverting
function. Further light computations are to be done, but just an XOR and
two hashings. Moreover, many interesting features appear with integration ofsymmetric encryption schemes.
The aim of the new conversion is very natural: it roughly rst encrypts asession key using the asymmetric scheme, and then encrypts the plaintext withany symmetric encryption scheme, which is semantically-secure under simple
passive attacks (possibly the one-time pad), using the session key as secret10

key. Of course this simple and actually used scheme does not reach chosenciphertext security, but just making the session key more impredictable andadding a checksum, it can be made so:= Epkasym (R)K = G(R)
Epk (m) = C jjE sym(m)jjH (C; R; m);
C

K

(1)
(2)
(3)

where G and H are any hash functions.
Moreover, if one uses a semantically secure symmetric encryption scheme
against basic passive attacks (no known-plaintext attacks), the last part of theciphertext, which is very fast since it only makes calls to a hash function andto a symmetric encryption, can be used more than once, with many messages.
This makes a highly secure use of a session key, with symmetric encryption E sym
which initially just meets a very weak security property:= Epkasym (R)K = G(R)
Epk (m ) = C jjE sym (m )jjH (C; R; m ) for i = 1; : : : :
C
i

K

i

i

1.4 Outline of the Paper
We rst review, in Section 2, the security notions about encryption schemes(both symmetric and asymmetric) required in the rest of the paper, with namely
the semantic security. Then, in the next section (Section 3), we describe a new
attack scenario, we call the Plaintext-Checking Attack. In Section 4, we develop
a novel class of problems, the Gap-Problems. Then in Section 5, we describe
our new Optimal Conversion together with the security proofs, relative to theabove gap-problems. The next section (Section 6) presents some interesting
applications of this conversion. Then comes the conclusion.

2 Security Notions for Encryption Schemes
2.1 Asymmetric Encryption Schemes
In this part, we formally de ne public-key encryption schemes, together withthe security notions.
De nition 2.1 (Asymmetric Encryption Schemes) An asymmetric encryption scheme, on a message space M, consists of 3 algorithms (Kasym ; E asym ; D asym ): the key generation algorithm Kasym(1 ) outputs a random pair of secretk

public keys (sk; pk), relatively to the security parameter k ; the encryption algorithm Epkasym (m; r) outputs a ciphertext c corresponding
to the plaintext m 2 M (using the random coins r 2 );11 the decryption algorithm Dskasym(c) outputs the plaintext m associated to theciphertext c.

Remark:As written above, Epkasym (m; r) denotes the encryption of a message m 2 M
using the random coins r 2 . When the random coins are useless in thediscussion, we simply note Epkasym (m).
The basic security notion required from an encryption scheme is the onewayness, which roughly means that, from the ciphertext, one cannot recover thewhole plaintext.
De nition 2.2 (One-Way) An asymmetric encryption scheme is said to be

one-way if no polynomial-time attacker can recover the whole plaintext from agiven ciphertext with non-negligible probability. More formally, an asymmetricencryption scheme is said (t; ")-INV if for any adversary A with running timebounded by t, its inverting probability is less than ":Succinv = Pr[(sk; pk) Kasym (1 ); m M; r

: A(Epkasym(m; r)) = m] < ":A by now more and more required property is the semantic security [15]also known as indistinguishability of encryptions or polynomial security since itis the computational version of perfect security [31].
RkR

De nition 2.3 (Semantic Security) An asymmetric encryption scheme issaid to be semantically secure if no polynomial-time attacker can learn any
bit of information about the plaintext from the ciphertext, excepted the length.
More formally, an asymmetric encryption scheme is said (t; "; `)-IND if for any
adversary A = (A1 ; A2 ) with running time bounded by t,2

3(sk; pk) Kasym(1 )Advind = 2 1 Pr 4 (m0; m1 ; s) A1(pk); asym
: A2 (c; s) = b5 0 1 < ";bf0; 1g; r ; c Epk (m ; r)
k

R

R

b

where m0 and m1 are both `-bit long.

Both notions are denoted INV and IND respectively in the following.
Another security notion has been de ned, called non-malleability [11]. It
roughly means that it is impossible to derive, from a given ciphertext, a new
ciphertext such that the plaintexts are meaningfully related. But we won't
detail it since this notion has been proven equivalent to semantic security against
parallel attacks [4].
Indeed, the adversary considered above may obtain, in some situations, more
informations that just the public key. With just the public key, we say that sheplays a chosen{plaintext attack since she can encrypt any plaintext of her choice,thanks to the public key. It is denoted CPA. But she may, for some time, accessa decryption oracle. She then plays a chosen{ciphertext attack, which is either
non-adaptive [19] if this access is limited in time, or adaptive [28] if this access12

is unlimited, and the adversary can therefore ask any query of her choice to thedecryption oracle, but of course she is restricted not to use it on the challenge
ciphertext.
It has already been proven [2] that under this latter attack, the adaptive
chosen-ciphertext attacks, denoted CCA, the semantic security and the nonmalleability notions are equivalent, and is the strongest security notion that one
could expect. We therefore call this security level in this scenario the chosen{
ciphertext security.

2.2 Symmetric Encryption Schemes
In this part, we brie y focus on symmetric encryption schemes.
De nition 2.4 (Symmetric Encryption Schemes) A symmetric encryption
scheme, on a message space M, consists of 3 algorithms (Ksym ; E sym ; D sym ): the key generation algorithm Ksym(1 ) outputs a random key k, relativelykto the security parameter k; the encryption algorithm Eksym(m) outputs a ciphertext c corresponding to
the plaintext m 2 M, in a deterministic way;
 the decryption algorithm Dksym (c) gives back the plaintext m associated tothe ciphertext c.

As for asymmetric encryption, impossibility for any adversary to get backthe whole plaintext just given the ciphertext is the basic requirement. However,
we directly consider semantic security.
De nition 2.5 (Semantic Security) A symmetric encryption scheme is said

to be semantically secure if no polynomial-time attacker can learn any bit of information about the plaintext from the ciphertext, excepted the length. Moreformally, a symmetric encryption scheme is said (t; "; `)-IND if for any adversary A = (A1 ; A2 ) with running time bounded by t,2

sk Ksym(1 )Advind = 2 2 Pr 4 (m0 ; m1; s)
b

R

3

k

A1 (k);

f0; 1g; c E ( )
sym
mb
k

where m0 and m1 are both `-bit long.

: A2(c; s) = b5 0 1 < ";In the basic scenario, the adversary just sees some ciphertexts, but nothingelse. However, many stronger scenarios can also be considered. The rst which
seemed natural for public-key cryptosystems are the known/chosen-plaintext
attacks, where the adversary sees some plaintext-ciphertext pairs with the plaintext possibly chosen by herself. These attacks are not trivial in the symmetricencryption setting, since the adversary is unable to encrypt herself.
The stronger scenario considers the adaptive chosen-plaintext/ciphertext attacks, where the adversary has access to both an encryption and a decryption
oracle.
13

However, just the security against the basic no-plaintext/ciphertext attacks(a.k.a. passive attacks) is enough in our application. Therefore, one can remark that it is a very weak requirement. Indeed, if one considers AES candidates, cryptanalysts even fail in breaking eciently semantic security using
adaptive chosen plaintext/ciphertext attacks: with respect to pseudo-random
permutations, semantic security is equivalent to say that the family (Eksym )k is(t; ")-indistinguishable from the uniform distribution on all the permutations
over f0; 1g , after just one query (cf. universal hash functions [6])!
`Remark:One should remark that the one-time pad provides a perfect semanticallysecure symmetric encryption: if Ksym(1 ) outputs k-bit long secret key, then for
any t it is (t; 0; k )-semantically secure.
k

3 The Plaintext-Checking Attacks

We have recalled above all the classical security notions together with the classical scenarios of attacks in the asymmetric setting. A new kind of attacks(parallel attacks) has been recently de ned [4], which have no real practicalmeaning, but the goal was just to deal with non-malleability. In this paper, wede ne a new one, where the adversary can check whether a message-ciphertext
pair (m; c) is valid: the Plaintext-Checking Attack.
De nition 3.1 (Plaintext-Checking Attack) The attacker has access to a

Plaintext-Checking Oracle which takes as input a plaintext m and a ciphertext
c and outputs 1 or 0 whether c encrypts m or not.

It is clear that such an oracle is less powerful than a decryption oracle. This
scenario will be denoted by PCA, and will be always assumed to be fully adaptive: the attacker has always access to this oracle without any restriction: she
can even include the challenge ciphertext in the query. Therefore, it is clearthat semantic security under this attack cannot be reached. But we don't mind,
since we just require a scheme to be one-way in this scenario. It is a very weak
notion.
Remark:One can remark that any deterministic INV-CPA asymmetric encryption
scheme is clearly still INV-PCA. Namely, any trapdoor one-way permutation
provides a INV-PCA-secure encryption scheme (e.g. RSA [29]).

4 Gap Problems

The attacking problem under the above-mentioned Plaintext-Checking Attack
can be characterized by a novel class of computational problems, the gap problems.
14

We rst de ne the gap problems as well as the related inverting and decision
problems. Then we give some examples.

4.1 De nitions
Let f : f0; 1g3 2 f0; 1g3 7! f0; 1g be any binary relation. The two classicalproblems are the following: the inverting problem of f is, given x, to compute any y such as f (x; y ) = 1
if it exists, or to answer Fail.
 the decision problem (type 1) of f is, given a pair (x; y ), to decide whether
f (x; y) = 1 or not.
 the decision problem (type 2) of f is, given x, to decide whether there
exists some y such that f (x; y ) = 1 or not.
In this section, we de ne the gap problems.
De nition 4.1 (Gap Problem) The gap problem (type 1 or 2) of f is to solve

the inverting problem of f with the help of the oracle of f 's decision problem(type 1 or 2, respectively).

Let us also de ne some notations: a problem X is tractable if it can be solved with non-negligible probability
by some probabilistic polynomial time Turing machine.
 a problem X is strongly tractable if it can be solved with overwhelming
probability by some probabilistic polynomial time Turing machine.
Therefore, we have the negation:
 a problem X is intractable if it is not tractable a problem X is weakly intractable if it is not strongly tractable.
Finally, to compare the diculty of problems, we use the notion of polynomial
reductions: a problem X is reducible to problem Y if there exists a probabilistic polynomial time oracle Turing machine A (with oracle of problem Y ) tocompute X with non-negligible probability.
 a problem X is strongly reducible to problem Y if there exists a probabilistic polynomial time oracle Turing machine A (with oracle of problem Y )to compute X with overwhelming probability.
We can easily obtain the following proposition,
Y

Y

Proposition 4.2 Let f be any binary relation.

15

 If the gap problem of f is tractable (resp. strongly tractable), the inverting

problem of f is reducible (resp. strongly reducible) to the decision problemof f .

 Let us assume that all the de ned problems, based on f , are uniformly easy
or dicult. If the decision problem of f is strongly tractable, the inverting
problem of f is reducible to the gap problem of f .

Proof:The rst claim directly comes from the de nition of the gap problem. Let us
consider the second claim, with a probabilistic polynomial time Turing machine
A that solves the decision problem of f , with overwhelming probability. Let us
also assume that we have a probabilistic polynomial time oracle Turing machine
B that solves the inverting problem of f with the help of a decision oracle D.
Since A solves the decision problem with overwhelming probability, it perfectly
simulates the D oracle, after polynomially many queries, with non-negligible
probability. In these cases, the machine B can invert. [QED]{This proposition implies a duality between the gap and decision problems. In
other words, the reasonability (or weakness) of the intractability assumptionsof the gap and decision problems of f are comparable, unless one of them isshown to be tractable.
D

4.2 The Random Self-Reducible Problems
De nition 4.3 A problem is said random self-reducible if any instance can betransformed in an other uniformly distributed instance whose solution helps insolving the initial instance.

Such problems are clearly uniformly easy or dicult Problems. Furthermore,
the weak intractability is equivalent to the classical intractability.
Corollary 4.4 Let f be any random self-reducible binary relation.

 If the gap problem of f is tractable, the inverting problem of f is reducible
to the decision problem of f .

 If the decision problem of f is tractable, the inverting problem of f isreducible to the gap problem of f .

Remark:Almost all the classical problems used in cryptography are random self-

reducible.

164.3 Examples of Gap Problems
Let us review some of these classical problems, with their gap variations.
De nition 4.5 (The Die-Hellman Problems) Let us consider any group

G of order q together with a generator g. We de ne three problems as follows: The Inverting Die-Hellman Problem (a.k.a. the Computational DieHellman problem): given a pair (ga ; g b ), nd the element C = g ab .

 The Decision Die-Hellman Problem: given a triple (g ; g ; g ), decideabcwhether c = ab mod q or not.

 The Gap Die-Hellman Problem: given a pair (g ; g ), nd the element
a

C =g

b

with the help of a Decision Die-Hellman Oracle (which answers
whether a given triple is correct or not).
ab

Note that these decision and gap problems are of type 1, wheredef log C =? log A 2 log B mod q  ;f ((A; B ); C ) =

g

g

g

which is a priori not a polynomially computable function.
De nition 4.6 (The Gap-DH Assumption) For any probabilistic polyno-

mial oracle Turing machine which has access to a Decision-DH oracle, the probability of, given (g a ; g b ), nding C = gab is negligible.

Since no polynomial time reduction (even a probabilistic one) is known fromthe Computational-DH to the Decision-DH problems, the Gap-DH assumption
seems as reasonable as the Decision-DH assumption due to the duality of these
problems (Proposition 4.2). Note that, as for most of the problems in use incryptography, the Inverting Problem is stronger than the Gap Problem (andthe Decision Problem either). Therefore, the tractability of the Gap-DH problem would lead to an equivalence between Computational-DH and Decision-DH(they would be reducible to each other), which is very unlikely.
De nition 4.7 (The Rabin Problems) Let us consider n = pq. We de ne

three problems as follows: The Inverting Rabin Problem (a.k.a. the Factoring Problem): given a pair(n; y ), nd x = y 1 2 mod n if x exists.
 The Decision Rabin Problem (a.k.a the Quadratic Residuosity Problem):given a pair (n; y ), decide whether x exists or not.
 The Gap Rabin Problem: given a pair (n; y ), nd x = y1 2 mod n if x==

exists, with the help of a Decision Rabin Oracle.

17

Note that these decision and gap problems are of type 2, wheredef y =? x2 mod n ;f (y; x) =which is a polynomially computable function.
Since no polynomial time reduction is known from the Factorization to the
Quadratic-Residuosity problem, the Gap-Rabin assumption seems as reasonable
as the Quadratic-Residuosity assumption.
De nition 4.8 (The RSA Problems) Let us consider n = pq and e relatively prime with '(n). We de ne three problems as follows: The Inverting RSA Problem: given a triple (n; e; y), nd x = y1 mod n.
 The Decision RSA Problem: given a quadruple (n; e; y; x), decide whether
x = y 1 mod n.
 The Gap RSA Problem: given a triple (n; e; y ), nd x = y1 mod n with
=e

=e

=e

the help of a Decision RSA Oracle.

Note that these decision and gap problems are of type 1, wheredef y =? x mod n ;f (y; x) =ewhich is a polynomially computable function. Therefore, it is a really di erent
situation from the Die-Hellman problems. They are both type 1 problems,
but in the current RSA situation, the function f is polynomially computable.
Thus the Decision-problem is clearly strongly tractable (and even more thanthat since one can always answer correctly). As a consequence, the Gap andInverting-RSA problems are equivalent.
De nition 4.9 (The Okamoto-Uchiyama Problems) Let us consider n =p2 q, g 2 Z such that g 01 mod p2 is of order p, and h = g mod n. We de ne
?
n

p
p

n

three problems as follows: The Inverting-OU Problem (a.k.a. the Factoring Problem): given a quadruple (n; g; h; y ), nd x 2 Z such that y = g h mod n.
 The Decision-OU Problem (a.k.a. the High-Residuosity Problem): given
?
p

x

r

a tuple (n; g; h; y; x), decide whether y = g x hr mod n for some r , or not.

 The Gap-OU Problem (thus called the Gap-High-Residuosity Problem):given a quadruple (n; g; h; y), nd x 2 Z such that y = g h mod n with?
p

the help of a Decision-OU Oracle.

xr

Note that these decision and gap problems are of type 1, where f is a rst orderfunction:def 
?
f (y; x) = 9r; y = g h mod n ;which is a priori not a polynomially computable function.
x

18

r

De nition 4.10 (The Gap-High-Residuosity Assumption) For any probabilistic polynomial oracle Turing machine, which has access to a High-Residuosity Oracle, the probability of success in factoring is negligible.

Since no polynomial time reduction from Factorization to the High-Residuosity problem, the Gap-High Residuosity assumption seems as reasonable as theHigh-Residuosity assumption.

5 Description of the Conversion
5.1 The Basic Conversion
Let us consider (Kasym; E asym ; Dasym ), any INV-PCA{secure asymmetric encryption scheme, as well as two given hash functions G and H which output k1 -bit
strings and k2-bit strings respectively. Then, the new scheme (K; E ; D ) works
as follows: Key generation algorithm K(1 ): it simply runs Kasym (1 ) to get a pair ofkeys (sk; pk), and outputs it.
 Encryption algorithm Epk (m; R; r): it gets c1 = Epkasym (R; r), then it computes the session key K = G(R), c2 = K 8 m as well as c3 = H (c1 ; R; m).
The ciphertext consists of the triple C = (c1 ; c2 ; c3 ).
 Decryption algorithm Dsk (C ):asymfrom C = (c1; c2; c3), it rst extracts R fromc1 by decrypting it: R = Dsk (c1 ). It can therefore recover the session
key K = G(R) and m = K 8 c2 which is output only if c3 = H (c1 ; R; m).
Otherwise, it outputs \Reject".
The overload is minimal. Indeed, if we consider the encryption phase, itjust adds the computation of two hash values and an XOR. Concerning thedecryption phase, which had been made heavy in previous conversions [13, 14,27] with a re-encryption to check the validity, we also just add the computationof two hash values and an XOR, as in the encryption process.
kk

5.2 The Hybrid Conversion
As it as already been done with some previous conversions [13, 14, 22, 25, 27],
the \one-time pad" encryption can be generalized to any symmetric encryption
scheme which is not perfectly secure, but semantically secure against passive
attacks.
Let us consider two encryption schemes, (Kasym; E asym ; Dasym ) is a INV-PCA{
secure asymmetric scheme and (Ksym ; E sym ; Dsym ) is a IND{secure symmetricscheme which uses k1-bit long keys, as well as two hash functions G and H
which output k1 -bit numbers and k2-bit numbers respectively. Then, the newscheme (Khyb ; E hyb ; Dhyb ) works as follows:19 Key generation algorithm Khyb(1 ): it simply runs Kasym (1 ) to get a pairkkof keys (sk; pk), and outputs it.
 Encryption algorithm Epkhyb(m; R; r ): it gets c1 = Epk (R; r) and a random
session key K = G(R). Then it computes c2 = E sym(m) as well as thechecking part c3 = H (c1; R; m). The ciphertext consists of C = (c1 ; c2 ; c3 ).
 Decryption algorithm Dskhyb(C ): fromC = (c1 ; c2 ; c3 ), it rst extracts R
from c1 by decrypting it: R = Dskasym (c1 ). It can therefore recover thesession key K = G(R) as well as the plaintext m = Dsym(c2 ) which is
output only if c3 = H (c1 ; R; m). Otherwise, it outputs \Reject".
The overload is similar to the previous, but then, the plaintext can be longer.
Such an hybrid transformation cannot be just considered as folklore since the
OAEP conversion (which furthermore requires a trapdoor permutation) does notallow symmetric encryption integration. Furthermore, the required property forthe symmetric encryption is very weak. Indeed, as it will be seen during thesecurity analysis in next section, it is just required that the symmetric encryption scheme is semantic security in the basic scenario (no plaintext/ciphertext
attacks).
KK

5.3 Chosen-Ciphertext Security
Theorem 5.1 Let us assume that the asymmetric encryption scheme (Kasym ; E asym; Dasym ) is INV-PCA{secure1
 and the symmetric encryption scheme (Ksym; E sym ; Dsym) is IND-secure,then the conversion (Khyb ; E hyb ; Dhyb ) is IND-CCA in the random oracle model.
More precisely, one can claim the following exact security result.

Theorem 5.2 Let us consider a CCA{adversary Acca against the \semantic

security" of the conversion (Khyb ; E hyb ; D hyb ), between `-bit messages, withina time bounded by t, with advantage ", after qD , qG and qH queries to thedecryption oracle, and the hash functions G and H respectively. Then for any
0 <  < ", there either exist

 an adversary Bpca against the (t; ')-INV-PCA-security of the asymmetricencryption scheme (Kasym ; E asym ; D asym ), after less than (g + q ) 1 (q +1)
queries to the Plaintext-Checking Oracle, where
"0

G

H

D

q
2 02 2 or an adversary B against the (t; ; `)-IND{security of symmetric encryption scheme (Ksym ; E sym ; D sym ).
'=

D

k

1 In other words, \If the type 1 Gap problem is intractable (where f (y; x) = 1 i

x

)"

20

Dasym ( ) =yProof:More than semantically secure under chosen-ciphertext attacks, this converted scheme can be proven \plaintext{aware" [3, 2], which implies chosenciphertext security. To prove above Theorems, we rst assume that the symmetric encryption scheme (Ksym ; E sym ; Dsym ) is (t; ; `)-IND{secure, for some probability 0 <  < ".
Semantic Security. The semantic security of this scheme intuitively comesfrom the fact that for any adversary, in order to have any information about
the encrypted message m, she at least has to have asked (c1 ; R; ?) to H (whichis called \event 1" and denoted by E1 ) or R to G (which is called \event 2"
and denoted by E2). Therefore, for a given c1 = Epkasym (R; r), R is in the list ofqueries asked to G or H . Then, for any candidate R~, one asks to the Plaintext
Checking Oracle whether c1 encrypts R~ or not. The accepted one is output as
the inversion of Epkasym on the ciphertext c1 , which breaks the INV-PCA.
More precisely, let us consider A = (A1 ; A2 ), an adversary against the semantic security of the converted scheme, using an adaptive chosen-ciphertext
attack. Within a time bound t, she asks q queries to the decryption oracle andq and q queries to the hash functions G and H respectively, and distinguishes
the right plaintext with an advantage greater than ". Actually, in the random
oracle model, because of the randomness of G and H , if neither event 1 nor
event 2 happen, she gets c2 = E sym(m ), for a totally random key K and thencannot gain any advantage greater than  , since the running time is boundedby t and messages are `-bit long. Then,
Pr[A2(Epkhyb (m ; r ); s) = b j :(E1 _ E2)]  21 + 2 :However,
1 "hyb
2 + 2  Pr[A2 (Epk (m ; r); s) = b]
= Pr[A2 = b ^ :(E1 _ E2 )] + Pr[A2 = b ^ (E1 _ E2)]
= Pr[A2 = b j :(E1 _ E2 )] 2 Pr[:(E1 _ E2)] + Pr[A2 = b ^ (E1 _ E2 )] 21 + 2 + Pr[E1 _ E2]:
This leads to Pr[E1 _ E2 ]  (" 0  )=2. If E1 or E2 occurred, an R~ will be accepted
and returned after at most (q + q ) queries to the Plaintext Checking Oracle.
D

G

H

b

K

b

b

b

b

b

b

b

b

b

b

G

H

Plaintext{Extractor. Since we are in an adaptive chosen-ciphertext scenario, we have to simulate the decryption oracle, or to provide a plaintextextractor. When the adversary asks a query (c1; c2; c3), the simulator looks forthe triples (m; R; K ) in the table of the query/answer's previously got from thehash functions G and H , using c1, which one both led to c2 and c3. For any correct one, it asks to the Plaintext-Checking Oracle whether c1 encrypts the given21R (therefore globally at most qH ). In the positive case, it has found a triple(m; R; K ) such that, K = G(R) and for some r0, c1 = Epkasym(R; r0), c2 = EKsym (m)and c3 = H (c1 ; R; m). The corresponding plaintext is therefore m.

Some decryptions may be incorrect, but only refusing a valid ciphertext: aciphertext is refused if the query R has not been directly asked to G by theattacker, or (c1 ; R; m) not asked to H . This may happen in two situations:
 the attacker has guessed the right value for H (c1 ; R; m) without having
asked for it, but only with probability 1=2 2 ; the c3 has been given directly by the encryption oracle, which means that
it is a part of the challenge ciphertext. Because of c1, R and m in the
triple H -input, the decryption oracle query would either be exactly thechallenge ciphertext, which is not allowed to the attacker, or a non-valid
ciphertext.
Using this plaintext-extractor, we obtain,k

Pr[(E1 _ E2 ) ^ no incorrect decryption]  " 02  0 2q 2 ;Dkin which cases one solves the Inverting-problem, simply using the Decisionproblem oracle to check which element, in the list of queries asked to G and H ,is the solution. [QED]{

6 Some Examples

We now apply this conversion to many classical encryption schemes which areclearly INV-PCA under some well de ned assumptions.

6.1 The RSA Encryption Scheme
6.1.1 Description of the Original Scheme.

In 1978, Rivest{Shamir{Adleman [29] de ned the rst asymmetric encryption
based on the RSA{assumption. It works as follows: The user chooses two large primes p and q and publishes the productn = pq together with any exponent e, relatively prime to '(n). He keeps
p and q secret, or the invert exponent d = e01 mod '(n).
 To encrypt a message m 2 Z , one just has to compute c = m mod n.
 The recipient can recover the message thanks to d, m = c mod n.
The one-wayness of this scheme relies on the RSA assumption. Since thisscheme is deterministic, it is still one-way, even against CPA, relative to the
RSA assumption.
?
n

e

d

22

6.1.2 The Converted Scheme: OCAC{RSA.

Let us consider two hash functions G and H which output k1-bit numbers andk2 -bit numbers respectively, and any semantically secure symmetric encryption
scheme (Ksym; E sym; Dsym).
 Key generation algorithm K(1 ): it chooses two large primes p and q
greater than 2 , computes the product n = pq . A key pair is composedby a random exponent e, relatively prime to '(n) and its inverse d =e01 mod '(n).
 Encryption algorithm E (m; R): withsymR 2 Z , it gets c1 = R mod n,then it computes K = G(R) and c2 = E (m) as well as c3 = H (c1 ; R; m).
The ciphertext consists of the triple C = (c1 ; c2 ; c3 ).
 Decryption algorithm D (c1 ; c2; c3),symit rst extracts R = c1 mod n. Thenit recovers K = G(R) and m = D (c2 ) which is output if and only if
c3 = H (c1 ; R; m). Otherwise, it outputs \Reject".
k

k

?
n

e;n

e

K

d

d;n

K

Theorem 6.1 The OCAC{RSA encryption scheme is IND-CCA in the random
oracle model, under the RSA assumption (and the semantic security of the symmetric encryption scheme under the basic passive attack).

This becomes the best alternative to OAEP{RSA [3, 30], since E sym can simply be the \one-time pad" but also any semantically secure encryption scheme
to provide high-speed rates.

6.2 The El Gamal Encryption Scheme
6.2.1 Description of the Original Scheme.

In 1985, El Gamal [12] de ned an asymmetric encryption scheme based on theDie-Hellman key distribution problem [10]. It works as follows: An authority chooses and publishes an Abelian group G of order q, denoted
multiplicatively but it could be an elliptic curve, together with a generator
g . Each user chooses a secret key x in Z and publishes y = g .
 To encrypt a message m, one has to choose a random element k in Z andsends the pair (r = g mod p; s = m 2 y ) as the ciphertext.
 The recipient can recover the message from a pair (r; s) since m = s=r ,where x is his secret key.
To reach semantic security, this scheme requires m to be encoded by an elementin the group G . Whereas the one-wayness of this scheme anyway relies on theComputational Die-Hellman problem.
?
q

x

?
q

k

k

x

Lemma 6.2 The El Gamal encryption scheme is INV-PCA under the Gap-DH
Assumption.

23

Proof:This lemma is clear since a Plaintext-Checking Oracle, for a given public key

y = g x and a ciphertext (r = g k ; s = m 2 y k ), simply checks whether the triple(y = gx ; r = gk ; s=m) is a DH-triple. It is exactly a Decision Die-Hellman{

Oracle. [QED]

6.2.2 The Converted Scheme: OCAC{El Gamal.

Let us consider two hash functions G and H which output k1-bit numbers andk2 -bit numbers respectively, and any semantically secure symmetric encryption
scheme (Ksym; E sym; Dsym).
 Key generation algorithm K(1 ): it chooses a large prime q, greater than
2 , a subgroup G of order q of an Abelian group G 0 and a generator g of
G . A key pair is composed by a random element x in Z and y = g .
 Encryption algorithm E (m; R; r ): with R 2 G 0 and r 2 Z , it gets csym
1=g
and c01 = R 2 y in G 0 , then it computes K = G(R) and c2 = E (m)as well as c3 = H (c1 ; c01 ; R; m). The ciphertext consists of the tuple C =(c1 ; c01 ; c2 ; c3 ).
 Decryption algorithm D (c1 ; c01 ; c2; csym3), it rst extracts R = c01 =c1 . Thenit recovers K = G(R) and m = D (c2 ) which is output if and only if
c3 = H (c1 ; c01 ; R; m). Otherwise, it outputs \Reject".
k

k

?
q

y

x

r

q

r

K

x

x

K

Theorem 6.3 The OCAC{El Gamal encryption scheme is IND-CCA in the random oracle model, under the Gap-DH assumption (and the semantic security ofthe symmetric encryption scheme under the basic passive attack).

6.3 The Okamoto-Uchiyama Encryption Scheme
6.3.1 Description of the Original Scheme.

Last year, Okamoto{Uchiyama [21] de ned an asymmetric encryption based ona trapdoor discrete logarithm. It works as follows: Each user chooses two large primes p and q and computes n = p2 q. He
also chooses an element g 2 Z such that g 01 mod p2 is of order p andcomputes h = g mod n. The modulus n, and the elements g and h are
made public while p and q are kept secret.
 To encrypt a message m, smaller than p, one has to choose a random
element r 2 Z and sends c = g h mod n as the ciphertext.
 The recipient can recover the message m from c since m = L(c )=L(g ) modp, where L(x) = (x 0 1)=p mod p for any x = 1 mod p, and c = c 01 mod
p2 .
n

n

?
n

p
p

m

r

p

p

24

p

p

The semantic security of this scheme relies on the p-subgroup assumption (a.k.a.
p-residuosity or more generally high-residuosity), while the one-wayness relieson the factorization of the modulus n. The relies on the gap problem

INV PCA(Gap-High-Residuosity).
However, since the encryption process is public, the bound p is unknown. A
public bound has to be de ned, for example n1 4 which is clearly smaller thanp, or 2 where 2 < p; q < 2 +1 .
=

k

k

k

Lemma 6.4 The Okamoto-Uchiyama encryption scheme is INV-PCA under the
Gap-High-Residuosity Assumption.

Proof:

This lemma is clear since a Plaintext-Checking Oracle is exactly a highresiduosity oracle. [QED]{
6.3.2 The Converted Scheme: OCAC{Okamoto-Uchiyama

Let us consider two hash functions G and H which output k1-bit numbers andk2 -bit numbers respectively, and any semantically secure symmetric encryption
scheme (Ksym; E sym; Dsym).
 Key generation algorithm K(1 ): it chooses two large primes p and q
greater than 2 , as well as g as described above. It then computes n = p2q
and h = g mod n.
 Encryption algorithm E (m; R; r ): with R < 2 and r sym< 23 , it gets
c1 = g h mod n, then it computes K = G(R) and c2 = E (m) as well
as c3 = H (c1 ; R; m). The ciphertext consists of the triple C = (c1 ; c2 ; c3 ).
 Decryption algorithm D (c1; c2; c3), it symrst extracts R = L(c1 )=L(g ).
Then it recovers K = G(R) and m = D (c2 ) which is output if and only
if R < 2 and c3 = H (c1 ; R; m). Otherwise, it outputs \Reject".
k

k

n

k

n;g;h

R

k

r

K

p

p

p

K

k

Theorem 6.5 The OCAC{Okamoto-Uchiyama encryption scheme is IND-CCA

in the random oracle model, under the Gap-High-Residuosity assumption (andthe semantic security of the symmetric encryption scheme under the basic passive attack).

7 Conclusion

This paper presented OCAC, an optimal conversion which applies to any weakly
secure cryptosystem: the overload is as negligible as OAEP, and advantages of
OCAC beyond OAEP are numerous. Therefore, OCAC provides an optimal
solution to realize a provably secure (in the strongest security sense) asymmetricor hybrid encryption schemes based on any practical asymmetric encryption
primitive such as RSA, El Gamal, or Elliptic-Curve El Gamal. In addition, thispaper introduced a novel class of computational problems, the gap problems,
which is considered to be dual to the class of the decision problems.
25

References[1] M. Abdalla, M. Bellare, and P. Rogaway. DHAES: An Encryption Scheme
Based on the Die-Hellman Problem. Submission to IEEE P1363a.
September 1998.
Available from http://grouper.ieee.org/groups/1363/.
[2] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among
Notions of Security for Public-Key Encryption Schemes. In Crypto '98,
LNCS 1462, pages 26{45. Springer-Verlag, Berlin, 1998.
[3] M. Bellare and P. Rogaway. Optimal Asymmetric Encryption { How to
Encrypt with RSA. In Eurocrypt '94, LNCS 950, pages 92{111. SpringerVerlag, Berlin, 1995.
[4] M. Bellare and A. Sahai. Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization.
In Crypto '99, LNCS 1666, pages 519{536. Springer-Verlag, Berlin, 1999.
[5] D. Bleichenbacher. A Chosen Ciphertext Attack against Protocols basedon the RSA Encryption Standard PKCS #1. In Crypto '98, LNCS 1462,
pages 1{12. Springer-Verlag, Berlin, 1998.
[6] L. Carter and M. Wegman. Universal Hash Functions. Journal of Computerand System Sciences, 18:143{154, 1979.
[7] D. Coppersmith, S. Halevi, and C. S. Jutla. ISO 9796 and the New Forgery
Strategy. Working Draft presented at the Rump Session of Crypto '99,
1999.
[8] J. S. Coron, D. Naccache, and J. P. Stern. On the Security of RSA Padding.
In Crypto '99, LNCS 1666, pages 1{18. Springer-Verlag, Berlin, 1999.
[9] R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably
Secure against Adaptive Chosen Ciphertext Attack. In Crypto '98, LNCS
1462, pages 13{25. Springer-Verlag, Berlin, 1998.
[10] W. Die and M. E. Hellman. New Directions in Cryptography. IEEE
Transactions on Information Theory, IT{22(6):644{654, November 1976.
[11] D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. In Proc.
of the 23rd STOC. ACM Press, New York, 1991.
[12] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Basedon Discrete Logarithms. IEEE Transactions on Information Theory, IT{
31(4):469{472, July 1985.
[13] E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key
Encryption at Minimum Cost. In PKC '99, LNCS 1560, pages 53{68.
Springer-Verlag, Berlin, 1999.
26

[14] E. Fujisaki and T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Crypto '99, LNCS 1666, pages 537{554.
Springer-Verlag, Berlin, 1999.
[15] S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28:270{299, 1984.
[16] R. J. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding
Theory. DSN progress report, 42-44:114{116, 1978. Jet Propulsion Laboratories, CALTECH.
[17] D. Naccache and J. Stern. A New Public-Key Cryptosystem. In Eurocrypt'97, LNCS 1233, pages 27{36. Springer-Verlag, Berlin, 1997.
[18] D. Naccache and J. Stern. A New Cryptosystem based on Higher Residues.
In Proc. of the 5th CCS, pages 59{66. ACM Press, New York, 1998.
[19] M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against
Chosen Ciphertext Attacks. In Proc. of the 22nd STOC, pages 427{437.
ACM Press, New York, 1990.
[20] T. Okamoto, E. Fujisaki, and H. Morita. PSEC: Provably Secure Elliptic
Curve Encryption Scheme. Submission to IEEE P1363a. March 1999.
Available from http://grouper.ieee.org/groups/1363/.
[21] T. Okamoto and S. Uchiyama. A New Public Key Cryptosystem as Secure
as Factoring. In Eurocrypt '98, LNCS 1403, pages 308{318. Springer-Verlag,
Berlin, 1998.
[22] T. Okamoto, S. Uchiyama, and E. Fujisaki. EPOC: Ecient Probabilistic
Public-Key Encryption. Submission to IEEE P1363a. November 1998.
Available from http://grouper.ieee.org/groups/1363/.
[23] P. Paillier. Public-Key Cryptosystems Based on Discrete Logarithms
Residues. In Eurocrypt '99, LNCS 1592, pages 223{238. Springer-Verlag,
Berlin, 1999.
[24] P. Paillier and D. Pointcheval. Ecient Public-Key Cryptosystems Provably Secure against Active Adversaries. In Asiacrypt '99, LNCS 1716, pages
165{179. Springer-Verlag, Berlin, 1999.
[25] D. Pointcheval. HD{RSA: Hybrid Dependent RSA { a New Public-Key
Encryption Scheme. Submission to IEEE P1363a. October 1999.
Available from http://grouper.ieee.org/groups/1363/.
[26] D. Pointcheval. New Public Key Cryptosystems based on the DependentRSA Problems. In Eurocrypt '99, LNCS 1592, pages 239{254. SpringerVerlag, Berlin, 1999.
27

[27] D. Pointcheval. Chosen-Ciphertext Security for any One-Way Cryptosystem. In PKC '2000, LNCS 1751, pages 129{146. Springer-Verlag, Berlin,
2000.
[28] C. Racko and D. R. Simon. Non-Interactive Zero-Knowledge Proof of
Knowledge and Chosen Ciphertext Attack. In Crypto '91, LNCS 576, pages
433{444. Springer-Verlag, Berlin, 1992.
[29] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital
Signatures and Public Key Cryptosystems. Communications of the ACM,
21(2):120{126, February 1978.
[30] RSA Data Security, Inc. Public Key Cryptography Standards { PKCS.
Available from http://www.rsa.com/rsalabs/pubs/PKCS/.
[31] C. E. Shannon. Communication Theory of Secrecy Systems. Bell System
Technical Journal, 28(4):656{715, 1949.
[32] V. Shoup and R. Gennaro. Securing Threshold Cryptosystems against
Chosen Ciphertext Attack. In Eurocrypt '98, LNCS 1403, pages 1{16.
Springer-Verlag, Berlin, 1998.
[33] Y. Tsiounis and M. Yung. On the Security of El Gamal based Encryption.
In PKC '98, LNCS. Springer-Verlag, Berlin, 1998.

28