PSEC 2564738@;<=
AUg¬ÄØïGÛ z06! ½[¤! G?¢\¥¦PSEC ! §lóoóÉzZý°.lc¦PSEC ! §¦PSEC-1 !
§¦PSEC-2 ! §¦PSEC-3 ! § lmT¢F`fVq|}
l°.«6moådtâ°.ol\q°./nÆÙS¢Q;<8JWP;<
8\q_¾$uxl)Û°.½¾k!AÛ(Q¤ÆÙD:Hy'-jê/Q(Q¥ò"ê°.Yz
19:
2.1 
1. [PSEC-1 ¤§¬] y' Die-Hellman ³¶2Ù (EC-PDDH) ,Ù¤Ù(lXiPè¥qöxtafL\>a@c^Oc* PSEC-1 Ü)Ûk! ·21{x,¬Ä¤,%B l¥k
2. [­³±º£¡ÏÛÍÓº¥ PSEC-2 ¤§¬] y' Die-Hellman(EC-DH) ,ÙqöxtafL\>a@c^Oc* PSEC-2 ¤T¢R\! Nl~¥Ü)Ûk! ·21{x,¬Äk
3. [Ü¤­³±º¥ PSEC-2 ¤§¬] y' Die-Hellman (EC-DH) ,ÙqöxsONz*Ø6! q`ÂÛ21* lafL\>a@c^Oc* PSEC-2 ¤*Ø6! Nl~¥Ü)Ûk! ·21{x,¬Äk
PSEC-2 ¤*Ø6! Nl~¥06! *Ø6! m {~
S:XbNQ! ½[kqu½[J#ó|S:XbNQ! ½[{x,%B lóq»évlàkinuuNl*Ø
6! q`ÂÛ%B lÉÂÛ%B llì  PSEC2 ¤*Ø6! Nl~¥ xÁ Û4ôv ÉÂÛ%B l! ½[m& PSEC-2 Æ×ßrO¢K{zÈé$Ék2

1`ï]q! ·´ zO¢Kö¿ó5éz~!
·qáÔwv~¹3v~ì |u 5bzu q0É 
4. [­³±º£¡ÏÛÍÓº¥ PSEC-3 ¤§¬] y'-jê GapDie-Hellman (EC-GDH) ,Ù afL\>a@c^Oc* PSEC-3 ¤*Ø
6! xT¢R\! Nl~¥Ü)Ûk! ·21{x,¬Äk²Úy'-jê Gap-Die-Hellman (EC-GDH) ,Ùð~Ù(v~,Ùkqx EC-GDH ,ÙqÊ EC-DH sH Çó EC-DDH
sH ÇóqÀ. umu }¹'uÇlu ïyo EC-GDH ,Ùx¿,Ù 5n~¡ EC-GDH m Gap- ,Ù EC-DDH ,Ù2Ù,Ù n{/ku Yxl [10]¡ EC-GDH ,Ù EC-DDH ,ÙÃÀdZc,v,Ùk 5nl
5. [Ü¤­³±º¥ PSEC-3 ¤§¬] y'-jê Gap-Die-Hellman(EC-GDH) ,ÙqöxsONz*Ø6! q`ÂÛ21* laf
L\>a@c^Oc* PSEC-3 ¤&Î*Ø6! Nl~¥Ü)Û
k! ·21{x,¬Äk
PSEC-3 ¤*Ø6! Nl~¥ PSEC-2 ¤*Ø6! Nl~¥ÃM06! *Ø6! m {~S:XbNQ! ½[k|S:XbNQ! ½[{x,%B lóq»évl~
PSEC-2 ÃMßrO¢K{zÈé$É»Kxl`ï]
q! ·´ zO¢Kö¿ó5éz~! ·qáÔwv
~¹3v~ì |u 5bzu q0É 
PSEC-2 l PSEC-3 ÆÖS:XbNQ! ½[ xINE`fÛON½¾¤INE`fhWol06! ½[Nl~6Ërq6
"7INE`fhÔæËrv~6Nlµò*Ø6! O¢K! +q6¥q0Éu k¤¦PSEC ! RMç§ 6.4
iPè¥ PSEC-2 6Ër O¢K! qÃ#xS
{x PSEC-3 6Ërx~þ­Ã#-*Ø6! ! +6mu q0Ékv|m! Øïlz x,%B2

ló¤Ü)Ûk! ·21{x,¬Ä£4¥q»évlu éEr
6. [§¬¤Ý]\NÛp,%B lóéEl~v06! x CramerShoup !  RSA ! !s OAEP qÒly'-jê CramerShoup ! afL\ò{z,Ùqù\ÛÍN&½1óSNE_òkàJlqõòjÛ,Ù¤PSEC-2 ,Ùx~ EC-DH ,Ù,l,Ùk¥y' Die-Hellman 2Ù (EC-DDH) ,Ù!ll
&½ PSEC-2 doÛafL\ò!llõòjÛ,Ù!AÛy'-jê Die-Hellman (EC-DH) ,Ù!llày'Cramer-Shoup ! Jl~ PSEC-3 õòjÛ,Ùqy'-jê Gap-EC-Die-Hellman (EC-GDH) ,Ù EC-DH ,Ù,l,Ùk¤PSEC-3  ló,Ù PSEC-2 «,l,Ù!llq´ ådtâINE`fÛON½¾óÉ£$ÉF PSEC-2 
Jl¥½[
PSEC-1
PSEC-2(OTP)
PSEC-3(OTP)
EC-Cramer-Shoup
OAEP-RSA
PKCS#1 Ver.1
Ïä RSA¯ 1: ló«lóõòjÛ afL\ò¤,%B¥ ,Ù,ÙlóéEr EC-PDDH ñafL\
lóéEr EC-DH ñafL\
lóéEr EC-GDH ñafL\
lóéEr EC-DDH UOWHF
lóéErRSAñafL\
210
0
0
210
0
0

¤Õ OTP *Ø6! xT¢R\! ON UOWHF ÍN&½1
óSNE_ò%Bz¥3àâµ°
Ai PSEC-1, PSEC-2, PSEC-3  lóz31Yz [6, 7, 10]´ 2.1 G  PSEC-1 6÷ô(Q x (q; a; b; p; P; mLen) |06 z s,t q Z=pZ p&MafL\k x Q := sP , R := tP , V := stP z
x  V  x- ® x [x ]
 x ê# mLen bits z~ b 2 f0; 1g
&MafL\k x b = 0  w := x x b = 1  w  mLen
bits afL\Ñ zmeÛw8[W8cCbH\ Adv {xlÙò c, a¶}rÑ k {x
2.2

V

V

mLen

V

V

Pr[Adv (q; a; b; p; P; Q; R; x) = b] < 1=2 + 1=k :cqôfz ry' Die-Hellman ³¶2Ù (EC-PDDH) HqÇxl lmuue G Adv e.ê^ly' Die-Hellman ³¶2ÙHqÇxl lm,Ùy' Die-Hellman ³¶2Ù,Ù úm
´ 2.2 G  PSEC-3 6÷ô(Q x (q; a; b; p; P ) |06 z s, t, u q
Z=pZ p&MafL\k x Q := sP , R := tP , V := stP , p W :=uP z~ b 2 f0; 1g &MafL\k x b = 0  w := xx b = 1  w := x Ù(zêafL\Ñ zmeÛw8[W8cCbH\ Adv {xlÙò c, a¶}rÑ k {xV

W

Pr[Adv (q; a; b; p; P; Q; R; x) = b] < 1=2 + 1=k :cqôfz ry' Die-Hellman 2Ù (EC-DDH) HqÇxl lmuue G Adv e.ê^ly' Die-Hellman 2ÙHqÇxl lm,Ùy' Die-Hellman 2Ù,Ù úm´ 2.3 G  PSEC-2 6÷ô(Q x (q; a; b; p; P ) |06 z s, t q
Z=pZ p&MafL\k x Q := sP , R := tP , p V := stP zmeÛw8[W8cCbH\ Adv {xlÙò c, a¶}rÑ k {x
Pr[Adv(q; a; b; p; P; Q; R) = V ] < 1=k :c

4

qôfz ry' Die-Hellman (EC-DH) HqÇxl lmuue G
Adv e.ê^ly' Die-Hellman HqÇxl lm,Ùy' Die-Hellman ,Ù úm´ 2.4 G  PSEC-3 6÷ô(Q x (q; a; b; p; P ) |06 z s, t q
Z=pZ p&MafL\k x Q := sP , R := tP , p V := stP z
EC-DDH Hz>a@cONrmeÛw8[W8cCbH\
Adv {xlÙò c, a¶}rÑ k {x
Pr[Adv(q; a; b; p; P; Q; R) = V ] < 1=k :cqôfz ry' Gap Die-Hellman (EC-GDH) HqÇxl lmuue G Adv e.ê^ly' Gap Die-Hellman HqÇxl lm,Ùy' Die-Hellman ,Ù úm´ 2.5 Adv Ð21] zæÐ Adv ¸·{,
X0
X1 , oî|í¼ s ÷ôzuu jX0 j = jX1 j  (gLen) (a: Ùò)z~Ð Adv ! · Y := SymEnc(K; X ) Lnuu
K 2 f0; 1go b 2 f0; 1g afL\p&MÙ
meÛw8[W8cCbH\ Adv {xlÙò c, a¶}rÑ gLen {x
a

b

gLen

Pr[Adv (gLen; X0 ; X1; s; Y ) = b] < 1=2 + 1=(gLen)cqôfz r SymE q`ÂÛ21{x lk lmuue (k; b)
Adv e.ê^l´à 2.6 rLen  c0 pLen (c0 : Ùò) p hLen = pLen 0 1 zu ry'Die-Hellman ³¶2Ù (EC-PDDH) ,ÙqöxtafL\>a@c^Oc* PSEC-1 Ü)Ûk! ·21{x,¬Äk´à 2.7 PSEC-2 Nl SymE T¢R\! z rLen = qLen 0 1 phLen = pLen 0 1 zu ry' Die-Hellman (EC-DH) ,ÙqöxtafL\>a@c^Oc* PSEC-2 Ü)Ûk! ·21{x,¬Äk5

´à 2.8 rLen = qLen 0 1 p hLen = pLen 0 1 zu ry' DieHellman (EC-DH) ,ÙqöxsONz*Ø6! q`ÂÛ21* lafL\>a@c^Oc* PSEC-2 Ü)Ûk! ·21{x,¬Äk´à 2.9 PSEC-3 Nl SymE T¢R\! z rLen = qLen 0 1 phLen = pLen 0 1 zu ry' Gap Die-Hellman (EC-GDH) ,ÙqöxtafL\>a@c^Oc* PSEC-3 Ü)Ûk! ·21{x,¬Äk
´à 2.10 rLen = qLen 0 1 p hLen = pLen 0 1 zu ry' Gap
Die-Hellman (EC-GDH) ,ÙqöxsONz*Ø6! q`ÂÛ21* lafL\>a@c^Oc* PSEC-3 Ü)Ûk! ·21{x,¬Äkß©: ê& ló¤%Ó¥31zøC°.qÅl [6, 7, 10]å :
3.1 ÎÛÌ¾¿¼¢¤ç¨Þ æ ÑØÆÄ:IcZ¢G ¦¯®:
Verilog-XL ¨ DesignCompiler
 ×ÇÛÄæá:
I 25.6KG(ª2NAND FgQ) ¨]^b (13312bit) 4ô [afL\eFN@¨ëQ ©¨/Q ] ¨ []^b (13312bit)] ª·Þ:@eN@ 30MHz (Qtâ (E[_d¢E`fsÙ)

3

PSEC-1

!
´

45 ms
45 ms

PSEC-2

!
´

45 ms
45 ms

~x6D:H 160 bit z
6

PSEC-3

!
´

45 ms
23 ms

3.2

ÇÐË¾¿¼¢¤ç¨Þ ÞÑÖÉËÒÛÓ:CPU: Pentium with MMX 266MHz
OS: Trubo Linux version 4.0

 è¸¹:úÿ (gcc version 2.91.60)
wÌ×õò(Qa:Xab x gnu mp (gmp version 3.0.1) SN ÔÕ×æá (ÂÛÌá):PSEC-1

PSEC-2

PSEC-1

PSEC-2! 63.341 Kbytes !
´ 63.175 Kbytes ´ ÔÕ×æá (ÙÛÁÀ×¼):!
´ «àª·:

1032 Kbytes
1028 Kbytes!
´

PSEC-176.4 ms
70.6 ms!
´

65.608 Kbytes
65.974 Kbytes

!
´

!
´

PSEC-365.688 Kbytes
65.890 Kbytes

PSEC-3988 Kbytes
1068 Kbytes!
´

PSEC-2

PSEC-377.1 ms
72.0 ms~x6D:H 160 bit z7!
´

1056 Kbytes
780 Kbytes

77.3 ms
35.8 ms ÊÛÈÃ½Å:
pLen
qLen
hLen
gLen

160 bits
160 bits
160 bits
160 bits
128 bits
176 bytes
48 bytes
89 bytes(PSEC-1) / 105 bytes(PSEC-2) / 125 bytes(PSEC-3)¸·×06W7:cD:H¬C6W7:cD:H! ·W7:cD:H »¶¤:
BfU:cWÜ+ gcc -O3 Nl~
A°.DfYcYeAa\ (call-6) xÞ±x~\6x~31ky'-j(Q9t+z½¾ x;9fQ;¾½¾qkqA°.
EfYc½¾Nllx~qM_¢f6nA°.9t\qq0Éké?ë:>ìä>?ê
PSEC ! óÉ!ã D:Hy'-jê/Q(QòQx°.
zõòjÛ(Q!s06! ì um½¾°.q½[üKóÉ°.z)Û½¾ 5nmS¢Q;=8
JWP;=8Nl\qxuuÅ~½[p{ÛóÉ«²ºk 5n
06! ONzÝ0Û+¤06!  128 VNPÚâ6ËrNl¥ol PSEC-1, PSEC-2 o PSEC-3 Ý0ÛUa]¢KhÙ"* PSEC-1 ì  mLen = 128, rLen = 32, hLen = 160 PSEC-2 ¤T¢R\!
ON¥ì  rLen = 160, gLen = 128, hLen = 160~ PSEC-3 ¤T¢R\!
ON¥ì  qLen = 160, gLen = 128, pLen = 160, hLen = 128 zv
PSEC-1, PSEC-2, PSEC-3 ol p o q D:H 160 bits x«~
 EC-ElGamal, EC-Cramer-Shoup ì Ua]¢KÃy z
~½[ SNE_ådhÀådhy'-jê/Q(Qådh«DTr~uuy'/Q(Qò«6m
4

8

u r PSEC-1, PSEC-2, PSEC-3  EC-ElGamal, EC-Cramer-Shoup ådhO¢KD:H"*Yzo"* #A(160)  160 bits Kûzêy'-j/Q(Qò%Bz
½[
PSEC-1
PSEC-2(OTP)
PSEC-3(OTP)
EC-ElGamal
EC-Cramer-Shoup¯ 2: ådhÀ«! +´ + 6× (jW j) ! ·×¤jC j¥¤#A(160)¥ ¤#A(160)¥ ¤bits¥¤bits¥
480
480
480
480
1000

480
480
240
240
520

160
160
160
160
480

320
448
576
320
608

ãíî
[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 Computerand Communications Security, pp.62{73 (1993).
[3] Bellare, M. and Rogaway, P. : Optimal Asymmetric Encryption, Proc. of Eurocrypt'94, LNCS 950, Springer-Verlag pp.92-111 (1995).
[4] Bleichenbacher, D.: Chosen Ciphertext Attacks Against Protocols Based on the
RSA Encryption Standard PKCS #1, Proc. of Crypto'98, LNCS 1462, SpringerVerlag, 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).

9

[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] 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.472485 (1998).

10Appendix
OCAC: an Optimal Conversion for Asymmetric
Cryptosystems

Tatsuaki Okamoto

David PointchevalïðFive years after the optimal asymmetric encryption padding (OAEP) whichmakes chosen-ciphertext secure encryption scheme from any trapdoor one-way
permutation (but whose unique application is RSA), this paper presents OCAC,
an optimal conversion which applies to any weakly secure cryptosystem: theoverload is negligible, since it just consists, as with OAEP, of two hashings forboth 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e-Hellman,
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 achieveschosen-ciphertext security with an only semantically secure symmetric scheme.
Therefore, OCAC could become a new alternative to OAEP, and even reachsecurity relative to factorization.
In addition, in order to clarify the security requirement of the underlying
asymmetric encryption, this paper introduces a novel class of computational
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), andgap 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 a11

goal is of greatest interest since many one-way encryption schemes are known, withvariable eciency and various properties, whereas chosen-ciphertext secure schemes
are very rare.
1.1 Chosen-Ciphertext Secure Cryptosystems

Until few years ago, the description of a cryptosystem, together with some heuristic 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 of international standards [5, 8, 7], provable security has been realized to be important andeven became a basic requirement for any new cryptographic protocol. Therefore, forthe last two years, many cryptosystems have been proposed. Some furthermore introduced new problems [17, 21, 18, 23, 26], other are intricate constructions, over
old schemes, to reach chosen-ciphertext security (from El Gamal [33, 32, 9, 1, 20],
Okamoto-Uchiyama [22], D-RSA [25] or Paillier [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 genericand 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 wasrestricted to trapdoor permutations, which is a very rare object (RSA seems to be
the only one application). Nevertheless, it provided the most 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 with further
improvements [14, 27]. It therefore seemed that the expected goal was reached: ageneric conversion from any one-way cryptosystem into a chosen-ciphertext secure
encryption scheme. However, the resulting scheme is not optimal, from the compu12tational point of view. Namely, the decryption phase is more heavy than one could
expect, since it requires a re-encryption.
As a consequence, with those conversions, one cannot expect to obtain a schemewith an easy decryption phase (unless both encryption and decryption are easy, which
is very unlikely). However, decryption is usually implemented on a smart card, hencee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 of symmetric encryption schemes.
The aim of the new conversion is very natural: it roughly rst encrypts a session
key using the asymmetric scheme, and then encrypts the plaintext with any symmetricencryption scheme, which is semantically-secure under simple passive attacks (possibly
the one-time pad), using the session key as secret key. Of course this simple andactually used scheme does not reach chosen-ciphertext security, but just making thesession key more impredictable and adding 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 the ciphertext,
which is very fast since it only makes calls to a hash function and to a symmetricencryption, 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 meetsa very weak security property:
CK= Epkasym (R)= G(R)
13

Epk (m ) = C jjE sym (m )jjH (C; R; m ) for i = 1; : : : :
i

K

i

i

1.4 Outline of the Paper

We rst review, in Section 2, the security notions about encryption schemes (bothsymmetric 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 the above gap-problems. The next section(Section 6) presents some interesting applications of this conversion. Then comes theconclusion.
2

Security Notions for Encryption Schemes

2.1 Asymmetric Encryption Schemes

In this part, we formally de ne public-key encryption schemes, together with thesecurity notions.
De nition 2.1 (Asymmetric Encryption Schemes) An asymmetric encryption
scheme, on a message space M, consists of 3 algorithms (Kasym ; E asym ; Dasym ): the key generation algorithm Kasym (1 ) outputs a random pair of secret-publickkeys (sk; pk), relatively to the security parameter k ; the encryption algorithm Epkasym(m; r) outputs a ciphertext c corresponding to theplaintext m 2 M (using the random coins r 2 );
 the decryption algorithm Dskasym (c) outputs the plaintext m associated to the ciphertext c.

Remark:As written above, Epkasym(m; r) denotes the encryption of a message m 2 M using therandom coins r 2 . When the random coins are useless in the discussion, we simply
note Epkasym (m).
14

The basic security notion required from an encryption scheme is the one-wayness,
which roughly means that, from the ciphertext, one cannot recover the whole 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 a given ciphertext
with non-negligible probability. More formally, an asymmetric encryption scheme issaid (t; ")-INV if for any adversary A with running time bounded by t, its inverting
probability is less than ":Succinv = Pr[(sk; pk) Kasym (1 ); m M; rRk

: A(Epkasym(m; r)) = m] < ":R

A by now more and more required property is the semantic security [15] also known
as indistinguishability of encryptions or polynomial security since it is the computational version of perfect security [31].
De nition 2.3 (Semantic Security) An asymmetric encryption scheme is said tobe 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 ) withrunning time bounded by t,2(sk; pk) Kasym(1 )6Advind = 2 1 Pr 64 (m0; m1 ; s) A1(pk);kbRf0; 1g; rR;cEpkasym(m ; r)3
7
: A2 (c; s) = b75 0 1 < ";bwhere 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 roughlymeans that it is impossible to derive, from a given ciphertext, a new ciphertext suchthat 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 she plays achosen{plaintext attack since she can encrypt any plaintext of her choice, thanks tothe public key. It is denoted CPA. But she may, for some time, access a decryption
oracle. She then plays a chosen{ciphertext attack, which is either non-adaptive [19]15

if this access is limited in time, or adaptive [28] if this access is unlimited, and theadversary can therefore ask any query of her choice to the decryption oracle, but ofcourse she is restricted not to use it on the challenge ciphertext.
It has already been proven [2] that under this latter attack, the adaptive chosenciphertext attacks, denoted CCA, the semantic security and the non-malleability 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, relatively to theksecurity parameter k ; the encryption algorithm Eksym(m) outputs a ciphertext c corresponding to theplaintext m 2 M, in a deterministic way;
 the decryption algorithm Dksym (c) gives back the plaintext m associated to theciphertext c.

As for asymmetric encryption, impossibility for any adversary to get back the wholeplaintext 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 besemantically secure if no polynomial-time attacker can learn any bit of information
about the plaintext from the ciphertext, excepted the length. More formally, a symmetric encryption scheme is said (t; "; `)-IND if for any adversary A = (A1 ; A2 ) withrunning time bounded by t,2
sk Ksym(1 )6Advind = 2 2 Pr 64 (m0 ; m1; s) A1 (k);kbRf0; 1g; c Eksym (m )bwhere m0 and m1 are both `-bit long.

16

3
7: A2(c; s) = b75 0 1 < ";

In the basic scenario, the adversary just sees some ciphertexts, but nothing else. However, many stronger scenarios can also be considered. The rst which seemed naturalfor 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 symmetric encryption setting, since the adversaryis 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.
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 avery 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 hashfunctions [6])!
`Remark:One should remark that the one-time pad provides a perfect semantically secure
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 classicalscenarios of attacks in the asymmetric setting. A new kind of attacks (parallel attacks)
has been recently de ned [4], which have no real practical meaning, but the goal wasjust to deal with non-malleability. In this paper, we de ne a new one, where theadversary can check whether a message-ciphertext pair (m; c) is valid: the PlaintextChecking 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.

17

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 thechallenge ciphertext in the query. Therefore, it is clear that 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 isclearly still INV-PCA. Namely, any trapdoor one-way permutation provides a INVPCA-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.
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 2f0; 1g3 7! f0; 1g be any binary relation. The two classical problems
are the following: the inverting problem of f is, given x, to compute any y such as f (x; y ) = 1 if itexists, 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 theinverting problem of f with the help of the oracle of f 's decision problem (type 1 or 2,
respectively).

18

Let us also de ne some notations: a problem X is tractable if it can be solved with non-negligible probability bysome 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 ) to compute X with
non-negligible probability.
Y 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.
Y

We can easily obtain the following proposition,
Proposition 4.2 Let f be any binary relation.

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

 Let us assume that all the de ned problems, based on f , are uniformly easy ordicult. If the decision problem of f is strongly tractable, the inverting problemof 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 that19

we have a probabilistic polynomial time oracle Turing machine B that solves theinverting problem of f with the help of a decision oracle D . Since A solves thedecision problem with overwhelming probability, it perfectly simulates the D oracle,
after polynomially many queries, with non-negligible probability. In these cases, themachine B can invert. [QED]{DThis proposition implies a duality between the gap and decision problems. In otherwords, the reasonability (or weakness) of the intractability assumptions of the gap anddecision problems of f are comparable, unless one of them is shown to be tractable.
4.2 The Random Self-Reducible Problems
De nition 4.3 A problem is said random self-reducible if any instance can be transformed in an other uniformly distributed instance whose solution helps in solving theinitial 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 thedecision problem of f .

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

Remark:Almost all the classical problems used in cryptography are random self-reducible.
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 oforder q together with a generator g . We de ne three problems as follows:20 The Inverting Die-Hellman Problem (a.k.a. the Computational Die-Hellman
problem): given a pair (g a ; g b ), nd the element C = g ab .

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

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

b

ab

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

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 polynomial oracle Turing machine which has access to a Decision-DH oracle, the probability of, given(g a ; gb ), nding C = gab is negligible.

Since no polynomial time reduction (even a probabilistic one) is known from theComputational-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 in cryptography, the Inverting
Problem is stronger than the Gap Problem (and the 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 threeproblems 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): givena pair (n; y), decide whether x exists or not.

21 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.

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 QuadraticResiduosity problem, the Gap-Rabin assumption seems as reasonable as the QuadraticResiduosity 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.
=e The Decision RSA Problem: given a quadruple (n; e; y; x), decide whether x =y 1=e mod n.

 The Gap RSA Problem: given a triple (n; e; y ), nd x = y1 mod n with the=ehelp 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 thecurrent RSA situation, the function f is polynomially computable. Thus the Decisionproblem is clearly strongly tractable (and even more than that since one can always
answer correctly). As a consequence, the Gap and Inverting-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 three
?
n

p
p

n

problems as follows:22 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.
?
p

x

r

 The Decision-OU Problem (a.k.a. the High-Residuosity Problem): given a tuple(n; g; h; y; x), decide whether y = g h mod n for some r, or not.
xr

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

x

r

Decision-OU Oracle.

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 ;xrwhich is a priori not a polynomially computable function.
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 the HighResiduosity 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 andk2 -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 of keyskk(sk; pk), and outputs it.

 Encryption algorithm Epk (m; R; r ): it gets c1 = Epkasym(R; r ), then it computes thesession 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).

23

 Decryption algorithm Dsk (C ): from C = (c1 ; c2 ; c3), it rst extracts R from c1 bydecrypting it: R = Dskasym(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, it just adds
the computation of two hash values and an XOR. Concerning the decryption 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 computation of two hash values and an
XOR, as in the encryption process.
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 symmetric scheme whichuses k1-bit long keys, as well as two hash functions G and H which output k1 -bitnumbers and k2 -bit numbers respectively. Then, the new scheme (Khyb ; E hyb ; Dhyb )works as follows: Key generation algorithm Khyb(1 ): it simply runs Kasym (1 ) to get a pair ofkkkeys (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 the checking partK

c3 = H (c1 ; R; m). The ciphertext consists of C = (c1 ; c2 ; c3 ).

 Decryption algorithm Dskhyb(C ): from C = (c1 ; c2; c3), it rst extracts R fromasym
c1 by decrypting it: R = Dsk(c1 ). It can therefore recover the session key
K = G(R) as well as the plaintext m = D sym (c2 ) which is output only if c3 =K

Reject".

H (c1 ; R; m). Otherwise, it outputs \The overload is similar to the previous, but then, the plaintext can be longer. Suchan hybrid transformation cannot be just considered as folklore since the OAEP conversion (which furthermore requires a trapdoor permutation) does not allow symmetric24encryption integration. Furthermore, the required property for the symmetric encryption is very weak. Indeed, as it will be seen during the security analysis in next section,
it is just required that the symmetric encryption scheme is semantic security in thebasic scenario (no plaintext/ciphertext attacks).
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 ; Dhyb ), between `-bit messages, within a time bounded byt, with advantage ", after qD , qG and qH queries to the decryption oracle, and the hashfunctions G and H respectively. Then for any 0 <  < ", there either exist

 an adversary Bpca against the (t; ')-INV-PCA-security of the asymmetric encryption scheme (Kasym ; E asym ; D asym ), after less than (g + q ) 1 (q + 1) queries toGHD

the Plaintext-Checking Oracle, where
'=

"0

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

More than semantically secure under chosen-ciphertext attacks, this converted scheme
can be proven \plaintext{aware" [3, 2], which implies chosen-ciphertext 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 <  < ".
1 In other words, \If the type 1 Gap problem is intractable (where f (y; x) = 1 i

25Dasym ( ) = )"yxSemantic Security. The semantic security of this scheme intuitively comes fromthe 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 (which is called \event 1" anddenoted 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 of queries asked to G or H . Then, for
any candidate R~ , one asks to the Plaintext Checking Oracle whether c1 encrypts R~ ornot. 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. Withina time bound t, she asks q queries to the decryption oracle and q and q queries
to the hash functions G and H respectively, and distinguishes the right plaintext withan advantage greater than ". Actually, in the random oracle model, because of therandomness 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 then cannot gain any advantage greater than  , since
the running time is bounded by t and messages are `-bit long. Then,
Pr[A2(Epkhyb (m ; r ); s) = b j :(E1 _ E2)]  21 + 2 :However,
1 + "  Pr[A (E hyb (m ; r); s) = b]
2 pk
2 2
= 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 andreturned 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 plaintext-extractor. When theadversary asks a query (c1 ; c2 ; c3 ), the simulator looks for the triples (m; R; K ) in thetable of the query/answer's previously got from the hash functions G and H , using
c1 , which one both led to c2 and c3 . For any correct one, it asks to the PlaintextChecking Oracle whether c1 encrypts the given R (therefore globally at most q ). In
H

26

the positive case, it has found a triple (m; R; K ) such that, K = G(R) and for some r0 ,asym
c1 = Epk(R; r0), c2 = E sym(m) and c3 = H (c1 ; R; m). The corresponding plaintext istherefore m.
Some decryptions may be incorrect, but only refusing a valid ciphertext: a ciphertext
is refused if the query R has not been directly asked to G by the attacker, or (c1; R; m)
not asked to H . This may happen in two situations:K the attacker has guessed the right value for H (c1 ; R; m) without having asked
for it, but only with probability 1=2 2 ;k the c3 has been given directly by the encryption oracle, which means that it is apart of the challenge ciphertext. Because of c1 , R and m in the triple H -input,
the decryption oracle query would either be exactly the challenge ciphertext,
which is not allowed to the attacker, or a non-valid ciphertext.

Using this plaintext-extractor, we obtain,

Pr[(E1 _ E2 ) ^ no incorrect decryption]  " 02  0 2q 2 ;Dkin which cases one solves the Inverting-problem, simply using the Decision-problem
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 are clearly
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 basedon the RSA{assumption. It works as follows: The user chooses two large primes p and q and publishes the product n = pq

together with any exponent e, relatively prime to '(n). He keeps p and q secret,or the invert exponent d = e01 mod '(n).
27 To encrypt a message m 2 Z , one just has to compute c = m mod n.
?
ne The recipient can recover the message thanks to d, m = c mod n.
dThe one-wayness of this scheme relies on the RSA assumption. Since this scheme isdeterministic, it is still one-way, even against CPA, relative to the RSA assumption.
6.1.2 The Converted Scheme: OCAC{RSA.

Let us consider two hash functions G and H which output k1-bit numbers and k2 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 greaterkthan 2 , computes the product n = pq. A key pair is composed by a random
exponent e, relatively prime to '(n) and its inverse d = e01 mod '(n).
k Encryption algorithm E (m; R): with R 2 Z , it gets c1 = R mod n, thenit computes K = G(R) and c2 = E sym (m) as well as c3 = H (c1 ; R; m). The
?
n

e;n

e

K

ciphertext consists of the triple C = (c1; c2 ; c3 ).

 Decryption algorithm D (c1; c2; c3), it rst extracts R = c1 mod n. Then it
recovers K = G(R) and m = Dsym (c2 ) which is output if and only if c3 =
d

d;n

K

Reject".

H (c1 ; R; m). Otherwise, it outputs \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 symmetricencryption 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:28 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 .
?
qx

 To encrypt a message m, one has to choose a random element k in Z and sends
the pair (r = g mod p; s = m 2 y ) as the ciphertext.
?
q

k

k

 The recipient can recover the message from a pair (r; s) since m = s=r , wherex

x is his secret key.

To reach semantic security, this scheme requires m to be encoded by an element in thegroup G . Whereas the one-wayness of this scheme anyway relies on the ComputationalDie-Hellman problem.
Lemma 6.2 The El Gamal encryption scheme is INV-PCA under the Gap-DH Assumption.

Proof:

This lemma is clear since a Plaintext-Checking Oracle, for a given public key y = g
and a ciphertext (r = g ; s = m 2 y ), simply checks whether the triple (y = g ; r =g ; s=m) is a DH-triple. It is exactly a Decision Die-Hellman Oracle. [QED]
{
x

k

k

x

k

6.2.2 The Converted Scheme: OCAC{El Gamal.

Let us consider two hash functions G and H which output k1-bit numbers and k2 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 pairkkis composed by a random element x in Z and y = g .
?
qx Encryption algorithm E (m; R; r): with R 2 G 0 and r 2 Z , it gets c1 = g andc01 = R 2 y in G 0 , then it computes K = G(R) and c2 = E sym (m) as well as
y

r

q

r

K

c3 = H (c1 ; c01 ; R; m). The ciphertext consists of the tuple C = (c1 ; c01 ; c2 ; c3 ).

29 Decryption algorithm D (c1 ; c01 ; c2 ; c3 ), it rst extracts R = c01 =c1 . Then it recovers K = G(R) and m = Dsym (c2) which is output if and only if c3 = H (c1; c01; R; m).
xxK

Otherwise, it outputs \Reject".

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 of the 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 on a
trapdoor discrete logarithm. It works as follows: Each user chooses two large primes p and q and computes n = p2 q. He alsochooses an element g 2 Z such that g 01 mod p2 is of order p and computes
?
n

p
p

h = g n 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 elementr 2 Z and sends c = g h mod n as the ciphertext.
mnr

 The recipient can recover the message m from c since m = L(c )=L(g ) mod p,
where L(x) = (x 0 1)=p mod p for any x = 1 mod p, and c = c 01 mod p2 .
p

p

p

p

The semantic security of this scheme relies on the p-subgroup assumption (a.k.a. presiduosity or more generally high-residuosity), while the one-wayness relies on thefactorization of the modulus n. The INV-PCA relies on the gap problem (Gap-HighResiduosity).
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 than p, or 2 where2 < p; q < 2 +1 .
=

k

k

k

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

30

Proof:This lemma is clear since a Plaintext-Checking Oracle is exactly a high-residuosity
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 and k2 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 thank

2 , as well as g as described above. It then computes n = p2q and h = g mod n.
kn(m; R; r): with R < 2 and r < 23 , it gets c1 =g h mod n, then it computes K = G(R) and c2 = E sym (m) as well as c3 =H (c1 ; R; m). The ciphertext consists of the triple C = (c1 ; c2 ; c3 ).

 Encryption algorithm E
R

k

n;g;h

k

r

K

 Decryption algorithm D (c1 ; c2 ; c3 ), it rst extracts R = L(c1 )=L(g ). Then it
recovers K = G(R) and m = Dsym (c2 ) which is output if and only if R < 2 and
p

p

p

k

K

Reject".

c3 = H (c1 ; R; m). Otherwise, it outputs \Theorem 6.5 The OCAC{Okamoto-Uchiyama encryption scheme is IND-CCA in the
random oracle model, under the Gap-High-Residuosity assumption (and the 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) asymmetric or hybrid encryption schemes based on any practical asymmetric encryption primitive such as RSA,El Gamal, or Elliptic-Curve El Gamal. In addition, this paper introduced a novel classof computational problems, the gap problems, which is considered to be dual to theclass of the decision problems.
31

ãíî
[1] M. Abdalla, M. Bellare, and P. Rogaway. DHAES: An Encryption Scheme Basedon 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 Notionsof 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 Encryptwith RSA. In Eurocrypt '94, LNCS 950, pages 92{111. Springer-Verlag, 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 based on 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 Computer and
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 Secureagainst 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.
32

[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 Based on
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.
[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.
33

[22] T. Okamoto, S. Uchiyama, and E. Fujisaki. EPOC: Ecient Probabilistic PublicKey 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 Dependent-RSA
Problems. In Eurocrypt '99, LNCS 1592, pages 239{254. Springer-Verlag, Berlin,
1999.
[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.
34

[33] Y. Tsiounis and M. Yung. On the Security of El Gamal based Encryption. In
PKC '98, LNCS. Springer-Verlag, Berlin, 1998.

35