PSEC-KEM の 安 全 性 評 価2002 年 11 月

株式会社 日立製作所

PSEC-KEM 

2002  11  


1



2



1


2.1 KEM  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 KEM  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 DEM  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 DEM  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 DEM  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7

2
2
2
4
5
5
6
6
8

3

ISO 

4

PSEC-KEM
4.1  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9
9
9
11

5

PSEC-KEM 5.1  DL, CDH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 PSEC-KEM 

12
12
13

6

6.1 !" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 #$!" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
18

7



19



 

a | b : %& a(= 0), b '() a * b +,-.
a mod n : %& a, n '() a + n /,0123 (45* {0, 1, . . . , n − 1} 6789 )a : :& a ;<=%&Fqm : qm >?78@ ABC (q *D&, m *EF&)x||y : GHI x, y JK (concatenation)x ⊕ y : GHI x, y (LM*NO9) GHPQRSTU

1


VWXY*, Z[\]^Z_`a PSEC-KEM bc)deKf+g9h1i/j. de'k9(1 PSEC-KEM lm*;ni/j .

1. PSEC-KEM opY
2. PSEC-KEM EqdeY
1r(, st8* NTT uvw_xyz{|`}~-Mt1 (2002  9
Z[\]^Z_`a (key encapsulation mechanism: KEM) *, \yVC*4-(, +/, ) i/j .

~ (^~) 

+(, (1i/, Np()4+(1/jyZ[\]^Z_`a (data encapsulation mechanism: DEM) 9 ¡ s9/¢9b£'¤~9@

i

/j

.
s~, %¥* ISO/IEC JTC1/SC27  D¦§¨@©/@Mt)c
/ª(c«9()¬­Mt)c .

([32], [10]) is®@¯6/, PSEC-KEM *, CRYPTREC2000 °±/j

PSEC-2([24], [25]) Z[\]^Z_`a²9() CRYPTREC2001 °±Mt1. PSEC-KEM */ ElGamal ~([13], [20]) +i9()³´Mt1~/,  Diﬃe-Hellman µ¶·¸¹º+»¼, ½|¾a¿½À]Á]/ ”” (Z[\]^Z_`a9()Â°SÃÄlÅÆ'()ÇÈÉ) /js9Ê Mt)c .
VWXY/*, 2 Ë/,  · yZ[\]^Z_`aÌ, M8t8+ ¡)Í8

ISO @© ¯Ñ+WX
. 4 Ë/*, PSEC-KEM ~Ò+ÓÔ, 5 Ë/, PSEC-KEM ÊÕÖ9
 Diﬃe-Hellman µ¶·¸Ì×Ø'&·¸ÙÚ, M8 PSEC-KEM  ÛÜKf@©
bc)WX. 6 Ë/*R ElGamal ÝyÞ KEM ~9, #$!"+ßc, <à 7 Ë/VWXKT+ÓÔ .
t~@©ÎÏS+Ð(, 3 Ë/, st8

1

2





*ÎÏ4!ÔáâÊãä, åæçy*èÑ/j. Î, 4*éêë/yÌ-ì-+ß®í, î87ï/+A(@tð@8@c. st
8ñêLòó+®gäô(1£'¤~Ê ~/j . ~/*, (1cyVC*4/(, y+, +õc)
. 
l*yVC+(1i9, y+(1i'9@ .
45+ö÷õc)~+³´.
@ ø, 4(y) 9()ù&+ú´(, t+ûl9()üý,  tðc. (7(, -þS, /ÒMt (1~+õc Êp@/#$S/j .
st/
Mt1ÊZ[\]^Z_`a/j . +Z[\]^Z_`a(KEM : key encapsulation mechanism) 9cc, 4+yZ[\]^Z_`a (DEM : data
encapsulation mechanism) 9c®.
;n KEM, DEM bc)- (ä Ð

2.1

s9Ê/

.

KEM 

Z[\]^Z_`a*  3 b]`a78@ .
!"#$%&

KEM.KeyGen() : üý*@ä, /È (PK , pk ) +ý.

KEM.Encrypt(PK , option) :  PK +üý9( (M8¿[z{| option+üý9()0)ic), y/l  (K, C0 ) +ý
.
'(

$%&

)(

KEM.Decrypt(pk, C0 ) : È pk 9, l C0 +üý9(, y K +. ]`a*j 9 fail ()ic.

ý

$%&

Z[\]^Z_`a*, KEM.Encrypt, KEM.Decrypt /ýyLM KEM.KeyLen. g1, 459Np, j  PK /Mt1l (K, C0 ) *, '°iÈ pk - K Mtð@8@c. 1r(, ú´]`ac), stÊ´-1@c
 (PK , pk ) Êú´Mt $Ê/ ©=Mtðc9
78 7.

®, Z[\]^Z_`a*VSüýÊ/, ûlüý+1@c. stÊ45È­S9 c/j- (! 1), Fs9@Ê8 Z[\]^Z_`aöC/*È"­S*õc s9Ê/@c. jäg/iàÓyZ[\]^Z_`a9
 ¡,

2.2

#

s9/$h)9()

i/j .

KEM 

Z[\]^Z_`a*, 459*%@bc)Ð

/i&'%@ . ss/*.

®@(ya (Â°SÃÄlÅÆ) + ) :Stage 1 : ú´]`a+*8¡, /È+ú´
9.

. ÅÆê*++) i

Stage 2 : ÅÆê*)( *+,,-./0· (query) +. 10·*l/j-, ¿½À]
-MtÅÆê+)8t . i(Ê fail @8ð2WiÅÆê+)8t . ÅÆê*¿½À],0· (l) +©®()§´()i³ @c.
2

! 1: 9Z[\]^Z_`a: Stage 3 : ÅÆê*'( *+,+34 . ¿½À]* +:ß
.
1. ]`a+*8¡, (K ∗ , C0∗ ) +ú´.
2. LM KEM.KeyLen  bit I K̃ +½|¾aú´
3. ½|¾a b ∈ {0, 1} +Ã5.
4. b = 0 @8ð (K ∗ , C0∗ ) +ý(, ®/@tð (K̃, C0∗ ) +ý.

.

Stage 4 : ÅÆê*¿½À],0·+6 . 1r(0·* C0∗ 9*%@ i9Stage 5 : ÅÆê* b̂ ∈ {0, 1} +ý()78j.

.

Z[\]^Z_`a KEM '(, ÅÆÅÆê A  advantage +AdvKEM (A) = |Pr[b̂ = b] − 1/2|
. KEM '(, A Ê9ë t, ¿½À],0·Ê: q //¯ä]`a/j 9,A + KEM [t, q]-adversary 935.
9Z[\]^Z_`aÊ/j 9*, -.ÅÆê ($S;<~9ë]`a) '() advan(A) = |Pr[b̂ = 1 | b = 0] − Pr[b̂ = 1 | b = 1]|
tage Ê/ ©=Mcs9+c®. advantage +, AdvKEM9s9ij . æ= 7 ®, AdvKEM (A) = 2 · AdvKEM (A) Ê´-b.
<$ÓÔ1®, 45.>~ PKE Ê+)8t19, ?/ù&+ú´(, t+ûl9() PKE -
9Yäs9

s9/ KEM ~+Í(! 2). s®()§8t

KEM + PKE KEM.

PKE Ê9() (IND-CCA2† ) /j @8ð, æ= 7 ®, PKE KEM * KEM 9(† , 


: ([32]).

Stage 1 : !"#$%&'()*+,-!/./!0"#1. 234,-!56 71.
Stage 2 : 23489:;<= (query) 1. ><=?
@, ABCDE%@A234
6 *. 7FA fail *GHIJ72346 *. 234ABCDE%8<= (?) KFLM#
FL7NOP.
Stage 3 : 234 (QRS) T? M0 , M1  6 . BCDE%UV1.
1. DWX b ∈ {0, 1} YZ, 2. B$%&'(@ Mb BF, ? Cb M#, 3. Cb [\1.
Stage 4 : 234ABCDE%8<=]^. _`FH<= Cb a71.
Stage 5 : 234 b̂ ∈ {0, 1} [\FLbc1.
 AC F, de23f^234 A  advantage  AdvAC (A) = |Pr[b̂ = b] − 1/2| 1. (ghiYj?23FLk.l: IND-CCA2)
, 9:234 (mniopqrs$%&'() FL
advantage tu vwKxPP. ykz (non-malleability) {|7  , ghiYj?237 de}~{| LP ([2]).

3! 2:  Z[\]^Z_`a: ).>//j . PKE KEM ,ÅÆê AKEM Ê@A(19(), st+õc);n® (! 3iBC) PKE , IND-CCA2 ÅÆê APKE +³´ tðc.

APKE *ûl M0 , M1 +-.Ã4, ¿½À]cDt7+()i8®. l Cb(b = 0, 1) Ê©ø8l@0)c 7+)@tð@8@c. s9, (M0 , Cb ) + AKEM  KEM
~9()·¸9()üý tð, AKEM *E-, /@c$/F(cûl (KEM /*y) 9l/j 7G7+) s9Ê/ /, ý+ggõc'°s9/ APKE i/@c$/ (NO$/) F
s9Ê/ . 1r(, AKEM 78¿½À],0·'(), APKE *EHÊIõ/ ¿½À],gg0· tðc (½|¾a¿½À]Á]/j íiNp/j ).

2.3

DEM 

Z[\]^Z_`a+õc)+³J

*, yZ[\]^Z_`a (DEM :data encapsulation mechanism) ÊKÒ/j . yZ[\]^Z_`a DEM *, , .
]`a78@ . g1L DEM.KeyLen +
DEM.Encrypt(K, L, M) : y K, ½Ý] L, 4ûl M +üý9(. ss/, M, L *-.L, K *LM DEM.KeyLen 9.
(M, L Ê:L9BML+N))c 9 fail ()ic)
l C1 +ý
(ûl M +ý

DEM.Decrypt(K, L, C1 ) : y K, ½Ý] L, 4l C1 +üý9
. ]`a*j 9 fail ()ic.

, ]`a*O]`a/@tð@8@c.
g1, -. K, L, M '(, (DEM.Encrypt Ê fail (@c@8ð)

DEM.Decrypt(K, L, DEM.Encrypt(K, L, M)) = MÊ´-1@tð@8@c.

4

! 3: KEM ÅÆê+õc1 PKE ÅÆê³´

2.4

DEM 

yZ[\]^Z_`a'ÅÆzP¿* 9-.

yZ[\]^Z_`a DEM '(, ÅÆê*NOLMûl M0 , M1 , 4, ½Ý] L∗ +ú´(, ¿½À]QR. ¿½À]*½|¾ay K +ú´(, g1, ½|¾ab ∈ {0, 1} +ÃÄ,  K, ½Ý] L∗ / Mb +(1l C1∗ +ÅÆêS . ÅÆê*¿½À
]0·s9Ê/ . 0·*½Ý]/l (L, C1 ) /, (L∗ , C1∗ ) 9%@ i@8-./c. ¿½À]* K  Kf+ÅÆêS . <àÅÆê* b̂ +ý.
KEM 9Np, DEM 'ÅÆê A  advantage + AdvDEM (A) = |Pr[b̂ = b] − 1/2| 9h .
M8, ÅÆê A Ê9ë t, ¿½À],0·Ê: q //, ¿½À],üý9, ¿½
À]78ýLMÊ: l, ½Ý]LMÊ: l /¯ä9, A + DEM [t, q, l, l]-adversary 935.
yZ[\]^Z_`aÊ/j 9*, -.ÅÆê ($S;<~9ë]`a) '()advantage Ê/ ©=Mcs9+c®.

2.5

DEM ISO ½TH ([32]) *, 49 MAC ]`a+õc) DEM +³´ïÊ 3 b (DEM1 ,DEM2 , DEM3 ) UMt)c (1r( DEM3 * MAC ). cDti, 4Ì MAC ]`a
Ê””/jtð, ³´Mt1 DEM Ê (DEM 9()) /j s9iVMt)c (F@ * [10]).
49()*WÀ+ ($XYZ)CBC Áy/õci9, one-time-pad ~ÊUMt)c(àÓ,  4' (y) *, ½|¾a@i/[c\)/j s978, $XYZ CBC Áy/j0)iÒÊ]/ ). CBC Áys9/*, WÀÊ”pseudo-random permutation”/j 9E(1í, h +^´†Ê Mt)-, @ DEM ³´1h, _@+b9 ) .
† KEM  ,  , !"# $%&'()*+,./0123. ,45671 PRP 893:;8!"# $% (AES, . . . ) <=*>. DEM ?@ABC23.

5

2.6



ss/* KEM , DEM + ¡) 1 b H-AC +³´

KEM.KeyLen = DEM.KeyLen /j 9.

H-AC ú´* KEM 9NO/, t+ (PK , pk) 9

.

.

H-AC.Encrypt(PK , L, M, option) :  PK , ½Ý] L, ûl M, 4¿[z{| option +üý9(,

1. (K, C0 ) = KEM.Encrypt(PK , option),
2. C1 = DEM.Encrypt(K, L, M),
3. C = C0 ||C1 ,+µ¶(, C +ý.
 H-AC.Decrypt(pk , L, C) : È pk , ½Ý] L, l C +üý9(,†`/j ® C = C0 ||C1 9,. s®@,Ê/@c9
1. C0 Ê KEM lÂ
* fail.
2. K = KEM.Decrypt(pk , C0 ),3. M = DEM.Decrypt(K, L, C1 ),+µ¶(, M +ý.

2.7

H-AC *9()i/j-, it®. @ øÂ°SÃÄlÅs9Êh8t . 1r(, ûlLÊ-., ½Ý]@A 2 a/459*bc%@0)c . ;n H-AC 'ÅÆÁ]+döÐ(3 eyf¬BC. g* [32], [10]+BCs9).
Æ'()ÇÈÉ/jÅÆê*¿½À]ýhB-îâ/i, ½Ý]/l+0·(, Kf+Í

s∗9ÊhMt)c . ÅÆê* ûl M0 , M1 9, ½Ý] L +¿½À]QR, ¿½À
]*½|¾aÃÄ(1 b ∈ {0, 1} 0) Mb +½Ý] L∗ /, l C ∗ +ÅÆêS. Å

Æê*y(H (L∗ , C ∗ ) ;?½Ý]/l+¿½À]0·(6, <à b̂ ∈ {0, 1} +ý.

ÅÆê A  advantage + AdvH-AC (A) = |Pr[b̂ = b] − 1/2|
KEM , DEM 9Np, H-AC '
9h . M8, ÅÆê A Ê9ë t, ¿½À],0·Ê: q //, ¿½À],üý9, ¿½À]78ýLMÊ: l, ½Ý]LMÊ: l /¯ä]`a9, A +H-AC [t, q, l, l ]-adversary 935.
ÊÊ/

/j

9*, -.ÅÆê ($S;<~9ë]`a) '() advantage©=Mcs9+c®.

 H-AC '(, KEM , DEM Êtjt.>
2.6 i/³´(1 KEM , DEM í, H-AC i/j s9ÊVMt . -F, Ê´-b://j-. H-AC [t, q, l, l]-adversary A '(, KEM [t1 , q]-adversary A1 (t1 ≈ t) 9, DEM [t2 , q, l, l]-adversary

A2 (t2 ≈ t) Ê@A() Ê´-b.
AdvH-AC (A) ≤ 2 · AdvKEM (A1 ) + AdvDEM (A2 )†  KEM 

prefix-freeness

(1), .   [32] !".

6 (1) 
ss/*dö1h½Ý]@cí+ ) .

g* [10].

G0 +  , i9i9(ya9(, H-AC ,ÅÆ ¿½À]k/ú´Mt ”hidden bit” + b, yõ (DEM õ) + k∗ , M8¿½À]ý (y(Hl) + C ∗ = C0∗ ||C1∗ 9. b̂ +ÅÆê A ý9(, T0 + H-AC ÅÆê A ÊF (b̂ = b) +
 lk9.
G0 +m(n`(1(ya G1 + ®. G1 /*, ¿½À]Ê3ðt19, KEM ∗+Ê7 01à, k +ä½|¾a@ k op)) DEM +ß®. g1, ý C + = C0∗ ||C1++ÅÆê+)1à, C = C0 ||C1 Ê¿½À]üýMt19, C0 = C0∗ @8ð KEM ¿½À]+õcD, ö ¿½À]k/§8t1 k+ +õc ®. T1 + A Ê(ya G1 /F
lk9.
s9, A  G0 /ýÙÚ9, G1 /ÙÚ+) KEM ,ÅÆ+ß®ÅÆê+ A1 99
|Pr[T1 ] − Pr[T0 ]| = AdvKEM(A1 )/j . <à, DEM ,ÅÆê A2 /j0),|Pr[T1 ] − 1/2| = AdvDEM (A2 ). :q, A *(ya G1 c)*ö DEM ,ÅÆ+()c s9@ /, A2* A 9g+rc)NO9)c. st8éb~-, h è"~+Í † .
@

iÊ@A

† , A #$% G &'( DEM )*+,-.
1

7, G0 / G1 0&'( KEM )*+,-..

3ISO 







ISO/IEC JTC1/SC27 /*, 1999 -~D¦ (18033) +ß0)c . 18033 *, Part 1 (General),Part 2 (), Part 3 (WÀ), Part 4 (ÞHya)  4 bsyH78³´Mt)c .
Part 2 (tu: V.Shoup) /*, 45~v), -.Lûl+#$S/i¬­(, /, 4+.-1/j
Z[\]^Z_`a+¼ , D¦+wh)c .
xA Part 2  WD(working draft [32]) /*, +Z[\]

^Z_`a (KEM), 4+yZ[\]^Z_`a (DEM) 9yz, tjt, ~Ì, M8*, t8+ÏSÐiUMt)c¡)@+³´ï", st8Î.

PSEC-KEM *Z[\]^Z_`a (KEM) 9() part 2 ¼ Mt)c . Part2 *, PSEC-KEM
R, ;n{ 3 V KEM ~Ê¼ Mt)c (RSA-KEM bc)* [19] iBCMt1c† ).
{ 1: ISO ¼Mt)c

KEM ~

ÝyÞ9@

~PSEC-KEM

ElGamal

ACE-KEMElGamalECIES-KEM

ElGamal

RSA-KEM

RSA

Part 2 *, 2002  10 ß t1|]z}|/ SC27 ~qc), WD 78 CD(committee
draft) ws9ÊMt)c Ê, T*¯S/, {VMt)c )~Ê IS Mt 7©®7*x9a/*è /j .
yZ[\]^Z_`a DEM bc)*, Part 2  WD c)4 (½ÀÀÞS)³´ïÒ*ÓMt)c

Ê, CS@ DEM ~bc)*UMt)c@c. (7(, xA9s

D¦*@Ê8,  SC27 ) DEM D¦Êß-, à, DEM D¦*áß tt s9Ê|]z}|/OMt)

9Mt .

† B. Kaliski 123, RSA-KEM &4 RSA 5678, 9/
H,.

8:;<=>?

56=@A

B

(CDE

FG

4

PSEC-KEM
ss/*Z[\]^Z_`a PSEC-KEM ]`a+Ða9GHI, ¿ÀHInp@©*j


.

4.1



ï+ÃÄ, Z()c. ABC?Ì, -@äNÎi9(, g*opY+BCMt1c.



E 9* 9 bY (q, m, f(β), a, b, P, p, pLen, qmLen) s9+c®. 1r(,

q : &, m : F%&, f(β) : ABC Fq  m Á_À;<~† , a, b : Fq m Ò, P = (x, y) :a, 1r( x, y : Fqm Ò/, y2 = x3 + ax + b (q > 3), y2 + xy = x3 + ax2 + b (q = 2)
+1 . M8, p : &, P &, pLen : log2 p Y, qmLen : log2 qm  Y/j .
9*, 4 b (E, W, KDF, hLen) s9+c®. 1r(, E : s½^y, W : PSEC (E) a, KDF : &ÃÄ, hLen : £%& /j .
PSEC  9*, £%& s s9+c®

PSEC , PSEC Èc)*, 0 ≤ s < p, W = sP ( E a9()ÞZ½y) Êj-, st8, È*ú´[vu (KGP-PSEC) -ú´Mt .
'°

4.2



 (ES-PSEC-KEM-Encrypt) *üý PSEC  P K '(, (c0 , k) (¿ÀHI) +ý. *;n/ß t :1.  (EME-PSEC-KEM-A (! 4)).
option  keyLen ÊMt)c 9
bit L hLen ù& r +ú´(, r 78& KDF -, bit L pLen + 128 + keyLen  bit I H+ú´, H + {pLen + 128}-bit t 9, n keyLen-bit k (A)  . t +%&9@() modp
/Y+ α (¶õÞZ½y) 9.

2.  (EP-PSEC)
/j  E a P , W +, tjt α .

C1 = αP.

Q = αW,

3.  (EME-PSEC-KEM-B (! 5))a C1 , Q 78, & KDF - bit L hLen  bit I+ú´, t9 r QRST.
U+ c2 9
4. 
C1 9 c2 JK c0 = C1 ||c2 , 4 1 /h1 k +ý† 

, 

.

. ,  F q m , Fq  .

9

! 4: EME-PSEC-KEM-A! 5: EME-PSEC-KEM-B

10

4.3



 (ES-PSEC-KEM-Decrypt) *üý PSEC  P K, PSEC È s, 4 l c0 '(, k (¿ÀHI) +ý(t½y9, ”invalid” +S s9ij ). *;n/ßt :1.  (EME-PSEC-KEM-C)
c0  {qmLen + 8}-bit 78  E a C1 +ú´(, n hLen-bit + c2 9ä.
2.

 (DP-PSEC)

1 /h1 E a C1 + È s (1 Q +µ¶.

Q = sC1 .
3.  (EME-PSEC-KEM-D (! 6))a C1 , Q 78, & KDF - bit L hLen  bit I+ú´, t9 c2 QRST. r 78& KDF -, bit L pLen + 128 + keyLen  bit I h +ú´, h +U+ r 9
 {pLen + 128}-bit t 9, n keyLen-bit k (A)  . t +%&9@() modp /Y+ α 9.

! 6: EME-PSEC-KEM-D

4.

,  (DP-PSEC)
a9() C1 = α P Ê´-)ð k (A) +ý

11. ®/@tð ”invalid” +S .

5

PSEC-KEM 5.1

 DL, CDH

ss/* PSEC-KEM ÊÕÖ9,  Diﬃe-Hellman µ¶·¸ (CDH) bc) .
Deﬁnition 5.1. ( : ECDL) E = (q, m, f(β), a, b, P, p, pLen, qmLen) +
. x ∈ {0, 1, . . . , p − 1} +½|¾aÃr9, E 9, xP 78 x +µ¶s½^y (cf. 4.1 i) 9·¸+ (E ) ×Ø'&·¸ (DL : discrete logarithm problem) 9c®.
Deﬁnition 5.2. ( Diﬃe-Hellman   : ECCDH) E +s½^y9.
·¸+ (E )Diﬃex, y ∈ {0, 1, . . . , p − 1} +½|¾aÃr9, E 9, xP , yP 78 xyP +µ¶
Hellman µ¶·¸ (CDH : computational Diﬃe-Hellman problem) 9c®.
87 CDH * DL ;<~9ë ¡Mt .
·¸i äs9Ê/ÎÏ*@ ø×Ø'&·¸Ê  @8ð Diﬃe-Hellman µ¶. (7(¢, bg-×Ø'&·¸9 Diﬃe-Hellman µ¶·¸µ¶çS"e*Mt)c@c(7(@Ê8, SKf*WXMt)-, £)ðs½^y E c), p − 1, g1* p + 1
Ê B-smooth (1r(, j& c '( B = O((lnp)c ) ) @8ð E  DL 9 CDH *µ¶çS"e/j([21]).
)  DL Ê L 12 (q)† ¦&9ë/
@c@8ð,  CDH i L 12 (q) 9ë/ @cs9iVMt)c ([6]). ECDL *¦&9
ë/* @c9¤O8t)-, ECCDH Ê ECDL 9N"¹º+]
/j ®s9Aý@ÕÖ
9@ 9¥ t .
g1, C (D& q Ê smoothness condition +1;s9-, VWXY/*, ECCDH ¹º-¦cE/j+”@”9@




s99

ECDL ¹ºÊ]Mt s9.

!"#×Ø'&·¸+ ä]`a/¦&9ëi*§8t)8D, &9ëi(7√πq/2 /Þ[+KÒ9. xAµ¶ý/ (x:9ëk/)ECDL + äs9Ê *s½^y p : &¨
&Ê,  100 & bit ©âig//j . [12] /*C 109-bit  DL Ê (Pollardï/) 549 ª7) 7t1s9ÊWXMt)c †† .
s:«+ ) 9, 160-bit í, ö÷µ¶/ 225 ≈ 33, 550, 000 µ¶çÊKÒ/, xA
µ¶ý/* 5 ¬­;77 s9@ . 0) 160-bit ;+õctð Pollard ï'()*_/j 9 ) s9Ê/ .
@c. xA§8t)c

$%



<i#$S@i* Pollard ρ-ï ([28]) /,!"#Î/, ®@'·¸¹º+EÅÆicäb7Mt)-, st8+r7@tð, ×Ø'&s9Ê/@c.

Weil/Tate-paring +õc) ECDL +¯ï¨ DL ø°ÅÆÊ, MOV ÅÆ ([22]), FR ÅÆ ([15])@©, cäb7§8t)c ([33] @©). st8'()*, Aa¨+¯ï¨±h°s9Ê¹º, j c*±h°/i¯ï¨×Ø'&·¸Ê¹º/j ®+Ã5KÒÊj ( p | (qn − 1)
@ n Ê_åtð (n > 20 @©) c).
g1, anomalous i×Ø'&·¸Ê=(ä, ÃÄ/@c ([29]).
† L (q) = exp(loga q log log1−a q)a†† 108-bit  2 

 ([8]).

12M8*, (²) ³åC'(, Weil descent +Iõ(1ÅÆ ([16]) i§8t)-, F2m , m: ´& @©*´ Ô/j .
(st8®,ÅÆbc) g* [11] +BCMt1c.)
PSEC-KEM /*, ¨µ` (p) * 160-bit +¶·()-, s½^yÃÄ"*
SECG([34]) +BC
s9@0)c .
+_ ¸()-st8s½^y+õ
SECG U*ÅÆ'c B-, ECDL ¹º* (:õ) ]Mt 9 ))c.

5.2

PSEC-KEM 

ss/* PSEC-KEM EqdeYUbc)Û.

EqdeY/*,  Diﬃe-Hellman µ¶·¸µ¶çS¹º+E(, M8,  (4.2)

KDF , 4 (4.3)  3 c) 2 ¹­õc8t KDF +½|¾a¿½À] G
9@(,  3  KDF , 4 3 c)<$õc8t KDF + G 9*º@½|¾a¿½À] H 9@(1/, PSEC-KEM Ê KEM 9() (cf. 2.2 i) /j s9+ß0)c (½|¾a¿½À]Á]/ ).
 1 -g,ÊVMt)c :Theorem 5.3. (PSEC-KEM )† A +, ¿½À], ½|¾a¿½À] G, H tjt qD /,qG /, qH /0·+(, »|yÊ ε / :ß9ëÊ t /j ®@ PSEC-KEM (K, E, D) '
IND-CCA2(Â°SÃÄlÅÆ'()ÇÈÉ)  ÅÆê9. s9´¼$Ê ε /:ß9ëÊ t  (K Êýs½^y
)  Diﬃe-Hellman(µ¶) ·¸/½+¾ (qH + qD ) >YÞH+ý®@]`aÊ@A(),ε ≥ss/ T * K 

(qG + 3qD )(1 + 2−128 ) 2qD + qG
ε
−
−
,
−128
2(1 + 2)p
2hLent ≤ t + qH · (T + O(1)).

¯¶ 2 /+ß®µ¶9ë/j .

6 K * PSEC-KEM (½|¾a¿½À]Á]/) ú´]`a, E, D *tjt]`a, ]`a/j .
*, PSEC-KEM [t, qD , qH , qG ]-adversary A /j0), AdvPSEC-KEM (A) = ε @ iÊ@A@8ð, +1´¼$ ε , ECCDH [t ]-adversary Ê@As9+¿À()c.

í, ÎÏ KEM '()Ò
PSEC-KEM 9j DEM ~9 ¡, +³´
2.2 i.>Ê1Mt)ctð, Í8tÊ£'¤9()<ÇÁÝ]+bs9@ /, PSEC-KEM '(, Ê´-)ð_/j .
Mt)cPSEC-KEM *®½|¾a¿½À]Á]/ Mt)-, Â*, x:/+V()c
/*@c. :q, j ®@ÙÚ+ ) s9/, ½|¾a¿½À]Á]/*/j0)i, c7@ :ÃÄ/i9*@8@c®@~iVMt)c ([7]). (7(, PSEC-KEM  78, :ÃÄc)*, PSEC-KEM Ê/@c@8ð, ECCDH Ê  7, i(ä* KDFbc) (j Å) ÅÆÊÆ9c®s9@-, àêÅÆÊ:q*¹º (T ECCDH Ê¹º/j
s9iE()) /j B-, PSEC-KEM */j 9 ) s9Ê/ .
†   3.1(7page)13

s®@
VÇ

78, VWX/*, ½|¾a¿½À]Á]/

TÖ9@(, ´+i0)/j

9KT+, :ÃÄ/+Çýi9.

;s9+ ¸üt, PSEC-KEM EqdeYU,  Û+ß01. Kf, ·¸*@ä, ¿ÀÊF(äVMt)cs9+(1. 0), PSEC-KEM *, KEM 9()/js9ÊMt1.
@, security reduction i tight (i.e. ε ≈ ε ) /j-, ¶·s½^yL (160 bit ;), hLen(128B-, @ KEM /j 9È) † . 0)@yZ[\]^Z_`a9
bit ;) +[õ ¡ s9-, @ +Í s9Ê/ .
B

g/, ;n (´¼$de) +U

.



A + PSEC-KEM (K, E, D) ,ÅÆê (cf. 2.2 i) 9`a B +;n®³´:. st+õc) ECCDH + ä ¡]! 7: ]`a BB
B * E  3 a P , W , C1∗ (W, C1∗ ∈ {P Êú´¨ }) ÊüýMt, B *a Q∗ /logC1∗ Q∗ = logP W @ i+¾j ÞH+ý.
∗
B *gD½|¾a bit b, 4½|¾a@ bit I c2 (LM* H ýL9"(c), k (LM* keyLen "(c) +ú´.  A +¯7(, A 78 H-query, G-query, 4¿½À], query ½)@
Ê8 (½)*àÓ), A 78¿½À],ÒÊ18 A ·¸9() ((C1∗ , c∗2 ), k) +S . É4
query /½+, ßc, A Ê78 (j bit +ý) (18 B * H , query 6/ C1 -part Ê C1∗ 9Î††.
Ê()c iÞH+ý()78
A 78 query '(, B *;n¯§+:†  q = 260 , q = 240   2   ε ≈ ε/2 !", tight !
GD
#.
†† CDH$%&'()*+", , -./012 ECCDH 3456789:;<'=>0? ([31], [32]).

14

H, G-

H, G-query '(, $h)Ë7t10·'()* (F(cLM) ½|¾a@Y+S . query 9½|¾a@/½+ÞHÌ. ÍÎË7t10·'()*, '°/½+S¡ðc.
∗
1r(, H-query δ = (C1 , Q) c), C1 = C1 /j 9* (c H(δ) +S(1à, ) r = c∗2 ⊕H(δ)Ê query 9() G-ÞHj 7G7+ÏÐÀ. j í*t/cÊ, @cí, r + G-ÞHv), G(r) +;n®h :.
G(r)  t-part +½|¾ah, α = t mod p, αP +µ¶∗∗i( C1 = αP /jtð Q = αW (st* CDH  ½/j ) +µ¶(, Q = Q∗ @8ð G(r) n
k-part +, b = 0 9<$Ãr k, b = 1 9½|¾a@Y\H. s9, ((C1∗ , c∗2 ), k) *'°H, G ¿½À]ý9ÑÒ@c, F(c”·¸”9@0)c s9¬..
∗C1 = αP 9 (9©*sí9@ ) * G(r)  k-part +½|¾ah .
<à r, G(r) + G-ÞHv) .


¿½À], query(C1 , c2 ) '()*, C1 -part ÊÎÊ(, j

H-ÞHk'+Ó(, @tð reject
7G7+ÏÐÀ)r '(, G(r) +½|¾aÃ4, st8+ G-Þ

@8ð, ®@')'() r = c2 ⊕ H(δ) +µ¶, r Ê G-query j. @cí, (H-ÞH®@' 1 b'Hv) .
G(r)  t-part 78 (modp ()) α +h, C = αP , 4 Q = αW Ê´-b@8ð, G(r) n k-part +Kf9() A S(, cDt7Ê´-1@tð reject.
¿½À]zvwÁyz{|/*, A Ê'°

H, G-query +l»ß0)c í*, 5F(czvwÁyz{|Ê/)c s9¬.
. 0), zvwÁyz{|ÊÔÕ* A
Ê H, G-query +s9@ä, F(cl+§´/1í/j .


qD /¿½À], query '(, zvwÁyz{|Ê 1 /;ÔÕ (ë 01Kf+()(g®)
lk+ Fail 99, Pr[Fail] +;n®de.
A 78¿½À] query(C1 , c2 ) ÔÕ(19. C1 = C1∗ /j 9, (ya]y]78,
c2 = c∗2 /j . B *st+ reject ()c rÊ, ÔÕ()c 9c®s9* (C1∗ , c2 ) *F(cl/j-, Q-part *"(c: Q = Q∗ . Ö) (c2 = c2 -) r = r∗ /j Ê, α-part (logP C1∗ = logW Q∗ ) *"(ä@tð@8@c. α-part * G(r), G(r∗ )  (t-part) + modp (1i/j-, stÊ"(ä@ $* (»Þ+ ¸9) (1 + 2−128 )/p 9@ . ×¿½À], query *: qD //j-, g1 G¿½À]: qG // /, sí (C1 = C1∗ í), ÔÕ$*:
(qG + qD )(1 + 2−128 )p
9@ .
 C1 = C1∗ í, '°H, G-query cDt7+ß0)c@crÊ, gD, G-query +ß0)c. (7( A *F(cl+Ëc))c r78, G(r)  (t-part) + modp (1iÊ logP C1 9ÎÊ()c), $*9Np():(1 + 2−128 )/p, 0)síÔÕ$*:
@c9

qD (1 + 2−128 )p
9@ .
<à G-query *ß®Ê, H-query +ß @cí, query ÊF(cl/jÊ r 9ÎÊ

* r := c2 ⊕ H(C1 , Q)

7 (s$* 1/2hLen ), g1* G(r )  t-part modp Ê logP C1 9ÎÊ

15

7 (s$*9Np (1 + 2−128 )/p) /j . 0)síÔÕ$*:


qD

1

+
2hLen

1 + 2−128p

/j . ;s9-Pr[Fail] ≤qD(qG + 3qD )(1 + 2−128 )+ hLen
p
2

(2)

+Í .
, B ­S/j , (C1∗ , Q∗ ) Ê A 78 H-query ¾gt)c $+de. slk+ AskH

9.
g1, r∗ Ê G 0·Mt, /½78Í8t α-part Ê C1∗ = αP 9@0)(g®7, i(ä* k-partÊ (b = 0 9) ¸ k 9%@0)c lk+ GBad 9.
;n/, ε = Pr[Fail] Ê¿Àè"~+1 s9+V . lk GBad ∨ Fail ()) .

Pr[AskH ∧ (GBad ∨ Fail)] = Pr[GBad ∨ Fail] − Pr[¬AskH ∧ (GBad ∨ Fail)]≥ Pr[GBad ∨ Fail] − Pr[¬AskH ∧ GBad] − Pr[¬AskH ∧ Fail]≥ Pr[GBad ∨ Fail] − Pr[GBad|¬AskH] − Pr[Fail]/j-, ¬AskH 9, Y H(C1∗ , Q∗ ) *ØèÆ/, 0) r∗ iØèÆ, 0), r∗ Ê G Ë7t
$* 1/2hLen . Ö)

Pr[GBad|¬AskH] ≤ (qD + qG )/2hLen
9@ . 0)~ (2) 9j ¡)Pr[AskH ∧ (GBad ∨ Fail)] ≥ Pr[GBad ∨ Fail] −(qG + 3qD )(1 + 2−128 ) 2qD + qG
−
p
2hLen

(3)

+Í .
Î, G*Pr[AskH ∧ ¬(GBad ∨ Fail)]= Pr[¬(GBad ∨ Fail)] · Pr[AskH|¬(GBad ∨ Fail)]≥ Pr[¬(GBad ∨ Fail)] · Pr[(A = b) ∧ AskH|¬(GBad ∨ Fail)]≥ Pr[¬(GBad ∨ Fail)] · (Pr[A = b|¬(GBad ∨ Fail)] − Pr[(A = b) ∧ ¬AskH|¬(GBad ∨ Fail)].
ss/i ¬AskH 9, Y H(C1∗ , Q∗ ) *ØèÆ/, 0) r∗ iØèÆ, Ö) A ÊF
$* 1/2 9@

/ (ss9*lk ¬(GBad ∨ Fail) 9*º/jPr[(A = b) ∧ ¬AskH|¬(GBad ∨ Fail)] ≤9@ . g1E78 (»Þi ¸

s9i¬.),

1
2

9)

1
ε
+ ≤ Pr[A = b] ≤ Pr[A = b|¬(GBad ∨ Fail)] · Pr[¬(GBad ∨ Fail)] + Pr[GBad ∨ Fail].
2(1 + 2−128 ) 2;-,Pr[AskH ∧ ¬(GBad ∨ Fail)] ≥ε/(1 + 2−128 ) − Pr[GBad ∨ Fail]2

9@ . ~ (3), (4), 4 Pr[GBad ∨ Fail] ≥ 0 78h16de~+Í .

(4)

6
ss/*, PSEC-KEM 9, R ElGamal ÝyÞ KEM ~9!" (, #$") +ß®. !

"'k*, Ù{S~/j-, ISO i¼ Mt1 (cf. 3 Ë) ACE-KEM, ECIES-KEM 9.

ACE-KEM * Cramer-Shoup  ([9])  KEM ²/j-, ECICS-KEM * ECIES  ([1],[34])  KEM ²/j . tjt gop* [32] ÚUMt)c . ss/*!"{+U(, !"Kf+döÓÔ 9©h .

6.1



cDt~i KEM 9() (2.2 i.>/) * Mt)c Ê, )c1hEÊ%@0({ 6.1 BC).
{ 2: 

1hE&TE&E

PSEC-KEM

EC CDHrandom

ACE-KEM

EC DDHUOWH

EC-GapCDH

randomECIES-KEM

ss/, ECDDH * ()Dillie-Hellman O·¸+{(, EC-GapCDH * ()Gap-

Diﬃe-Hellman(µ¶) ·¸+{ .
g*ÛÊ, ECDDH *a 4 b (P, W, C, Q) Ê+)8t19, Q Ê (P, W, C) 'Diﬃe-Hellman µ¶·¸ /j 7G7+Ü·¸/j-, EC-GapCDH *, ECDDH ½)+
S ¿½À]+õc), ECCDH +µ¶·¸/j ([32], [27]).
g1&E UOWH * universal one-way hash & ([23]) +.>. UOWH *ÎÑ&
Ê@A tð³´/, &TEi9/ÎÑ&Ê³´/ /, UOWH *x:SEi9/ (#$+· @tð) ³´Æ/j .
{ 6.1 /*, 1&T·¸Ê¹º/j´-bs9+Es9, 41~

tð, KEM 9()Ê Æ/j

zw&c)1&EÊ
s9+{()c .

security reduction *, PSEC-KEM, ECIES-KEM 9iÝ<Â/j . t!Ô, ACE-KEM /*ÌÌÞ i, ·¸@c.
ACE-KEM *, &Ec), (S) ½|¾a&op) ½|¾a¿½À]T*èÒ/j-,/ (Þ|¾yÁ]/ Æ) ~/, x:S+s9Ê/ . 1r(, :q* UOW Êî87.>/ Mt1 zw&+õc/*@ä, R
~Np, SHA-1([14]) ":õ zw&78³´(1i+õc . 0), ACE-KEM ¿À*, R~!Ô, zw&,à@âÊ-ács9/j 9 )8t .
:ÃÄßcEc)

Î, ACE-KEM &TE* ECDDH Ê¹º/j

s9/j-, st* ECCDH -ÇcE/j.
stÊ´-b*, ECCDH í;ÃÄc)¬.+Ò. :q, ¨µ¶Æ@ (£E @) â`ãäÊ@A(M) tð DDH ·¸+ äs9Ê/ (Yå/ DDH Ì DL Êµ¶Æ/j KÒ*@c. g1â`ãääÎÊµ¶/ r/ic), s®@â`ãä* MOV ÅÆÌ FR ÅÆ'k-æçèc), Weil/Tate-paring +õc)³´Æ/j([18], [5]). à, ECDDH éê¯Ñ¬­KÒÊj .

17

ECIES-KEM &TE/j EC-GapCDH([27]) *, ®@ ECDDH ¦c ([18], [5])+(1·¸/, 87 ECCDH -ÇcE/j † . xA9s , EC-GapCDH ,ÅÆ/ëÔi*@cÊ, ¼Mt)ëi@c·¸/j s978, àî87w«Êj s9iG/@c.

6.2



{ 6.2 *1~#$+g9h1i/j . 1c), ÞZ½y¶Êå+ìh, R* ©â/j s978, {/*ÞZ½y¶/&+V()c .
{ 3: ÞZ½y¶/&R~!Ô,PSEC-KEM

22

ACE-KEM

53

ECIES-KEM

2

1

87 ACE-KEM *#$Êíc. PSEC-KEM *Ê ECIES-KEM ÌÌÞ i, ÝN"#$+b9)c.
;!"+î

9, PSEC-KEM &TE*R!Ô)¤ï:c ECCDH /j-, #$

i_ä, ½|¾a¿½À]Á]
~/j9c®s9Ê/+híc)*, PSEC-KEM Ê<iðt1

.

† ECCDH , ECDDH  EC-GapCDH .

18

7


VWXY/*, Z[\]^Z_`aÒ+WX(, Z[\]^Z_`a/j

PSEC-KEM de+ß01.
gD,  · yZ[\]^Z_`aÌ, M8t8+~@©+Ð(, st8Ê·¸@ä[õÆ/j~Ê ISO /áD¦Mtbbj

¡)Í8t



s9+(1. g1st8

s9+WX(1.

, Z[\]^Z_`a/j

PSEC-KEM Ò+ÓÔ, PSEC-KEM ÊÕÖ9, Diﬃe-Hellman µ¶·¸Ì×Ø'&·¸ÙÚ, M8 PSEC-KEM  ÛÜ@©+ß01. Kf, PSEC-KEM *¶·Mt)c s½^yL (µ`, zw&ýY@©) +õc B-, KEM 9()/j s9+(1. 0) ”” @ DEM 9 ¡ s
9/ (£'¤) 9()<ÇÁÝ] IND-CCA2 (=NM-CCA2 [2]) +^´(1 Ê³´/ s9@ .
M8, R ElGamal ÝyÞ/j Z[\]^Z_`a9!"+ßc, PSEC-KEM *, R~'(ðt1 (¤ï), #$+bs9+ÓÔ1.
;78 PSEC-KEM *Z[\]^Z_`a9()ðt1~/j9()*, jäg/Z[\]+ß®~/j-öC/*õc

s9ÊKTz8tÊ, s9Ê/@c. [õÆ*. s®@Z[\]^Z_`a*+A#õc 1hñh)òÒ9 )8t, ~kóôõö@©/iK÷/j 9 ) . Z[\]^Z_`aD¦, j c*¶·~ÃÄ@©, ø'°KÒÊj 9 ) .
yZ[\]^Z_`aÊKÒ/j<ª¯ÑùÍ, úõ@ä()* IT û¨üý*j-)D, þ, ?~* st8¯+¬(, '°Mig

s9/ IT 

M<+g ¯S/, ªÌÇý@ÅÆïÊý¼

ú¯*st8ñh)

Í,



Ôä +

0)c .

Mt6)-, ISO @©, ~qSD¦/, '°iøc.

Î, Ê~de+ß®V[WÐÀHc)*, °±Mt1+de!"SLXë, opF · +Î.h@cgg9ë+7)de§¨+ß®9c®õ/*, M¯áMbc)c@ctÊj. ( , M¯Ñ+cøøäì-üt, -ðt1+A#úõ

1h, V0SeY+ð(1Ã, de¦ÛÜÌ, t01Éde, v ·7bá@'°+Æ9M8*M¯Nro%¥@©,C§-Êg(c.
/@ä, M+¯7(yÀHÊs®@éê · +(, M8@´ÊòÒ/j-, V[WÐ~+ c1+919s9Êg(c9¥t .

[1] M. Abdalla, M. Bellare and P. Rogaway, The oracle Diﬃe-Hellman assumption and an analysis
of DHIES, Topics in Cryptology — CT-RSA 2001, LNCS 2020 (2001), Springer-Verlag, 143-158.
[2] M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, Relations Among Notions of Security
for Public-Key Encryption Schemes, Advances in Cryptology — CRYPTO ’98, LNCS 1462 (1998),
Springer-Verlag, 26-45.
[3] M. Bellare and P. Rogaway, Random Oracles are Practical: A Paradigm for Designing Eﬃcient
Protocols, Proceedings of the 1st ACM Conference on Computer and Communications Security, ACM
Press (1993), 62-73. Available at http://www.cs.ucdavis.edu/ rogaway/papers/index.html[4] M. Bellare and P. Rogaway, Optimal Asymmetric Encryption - How to encrypt with RSA, Advances in Cryptology — Eurocrypt ’94, LNCS 950 (1995), Springer-Verlag, 92-111.
[5] D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, Advances in Cryptology— CRYPTO 2001, LNCS 2139 (2001), Springer-Verlag, 213-229.
[6] D. Boneh and R. Lipton, Algorithms for black-box ﬁelds and their application to cryptography,
Advances in Cryptology — Eurocrypt ’96, LNCS 1109 (1996), Springer-Verlag, 283-297.
[7] R. Canetti, O. Goldreich and S. Halevi, The random oracle methodology, revisited, Proceedingsof the 30th Annual ACM Symposium on the Theory of Computing, 1998, 209-218.
[8] Certicom ECC Challenge, 2002. Available at http://www.certicom.com/research/news/ecc2k108.html.
[9] R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive
chosen ciphertext attack, Advances in Cryptology — Crypto’98, LNCS 1462 (1998), Springer-Verlag,
13-25.
[10] R. Cramer and V. Shoup, Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, 2001. Available at http://shoup.net/papers/ or
http://eprint.iacr.org/[11] CRYPTREC Report, Evaluation of security level of cryptography: The elliptic curve discrete logarithm
problem, Dec. 14, 2001.
[12] The ECCp-109 challenge, 2002. Available at http://www.nd.edu/ cmonico/eccp109/[13] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE
Transactions on Information Theory, 31 (1985), 469-472.
[14] FIPS PUB 180-1, Secure Hash Standard (SHS), U.S. Department of Commerce / National Instituteof Standards and Technology, April 17, 1995.
[15] G. Frey and H. G. Rück, A remark concerning m-divisibility and the discrete logarithm in thedivisor class group of curves, Math. Comp. 62 (1991), 965-874.
[16] S. Galbraith and N. Smart, A Cryptographic Application of Weil Descent, HP Labs Tech. Report,
HPL-1999-70.
[17] P. Gaudry, F. Hess and N. Smart, Constructive and destructive facts of Weil descent on elliptic
curves, HP Labs Tech. Report, HPL-2000-10.
20[18] A. Joux and K. Nguyen, Separating decision Diﬃe-Hellman from Diﬃe-Hellman in cryptographic
groups, 2001. Available at http://eprint.iacr.org[19] B. Kaliski, Key Encapsulation: An Emerging Paradigm for Public-Key Cryptography, RSA Conference 2002, Japan, May 2002, Conference Note.
[20] N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.
[21] U. Maurer, Towards the equivalence of breaking the Diﬃe-Hellman protocol and computing discrete
logarithms, Advances in Cryptology — CRYPTO ’94, LNCS 839 (1994), Springer-Verlag, 271-281.
[22] A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms ina ﬁnite ﬁeld, Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1991,
80-89.
[23] M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications,
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989.
[24] NTT Labs, Speciﬁcation of PSEC: Provably Secure Elliptic Curve Encryption Scheme, 2000. Available
at http://info.isl.ntt.co.jp/psec/CRYPTREC/index-e.html[25] NTT Labs, Self Evaluation of PSEC: Provably Secure Elliptic Curve Encryption Scheme, 2000. Available at http://info.isl.ntt.co.jp/psec/CRYPTREC/index-e.html[26] S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p)and its cryptographic signiﬁcance, IEEE Transactions on Information Theory, IT-24 (1978), 106-110.
[27] D. Pointcheval and T. Okamoto, The GAP problems: A new class of problems for the securityof cryptographic schemes, Proceedings of the 2001 International Workshop on Practice and Theory in
Public Key Cryptography (PKC 2001), LNCS 1992 (2001), 104-118.
[28] J. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.
[29] T. Satoh and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commetarii Math. Univ. St. Pauli., Vol. 47 (1998), 81-92.
[30] I. A. Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve incharacteristic p, Math. Comp., 67 (1998), 353-356.
[31] V.Shoup, Lower Bounds for Discrete Logarithms and Related Problems, Advances in Cryptology —Eurocrypt ’97, LNCS 1233 (1997), Springer-Verlag, 256-266.
[32] V.Shoup, A Proposal for an ISO Standard for Public Key Encryption (v. 2.1), ISO/IEC JTC1/SC27,
N2563, 2001. Available at http://shoup.net/papers/ or http://eprint.iacr.org/[33] N. P. Smart, The discrete logarithm problem on elliptic curves of trace one, J. of Cryptology, Vol.
12 (1999), No. 3, 193-196.
[34] Standard for Eﬃcient Cryptography Group, SEC 1: Elliptic Curve Cryptography, ver.1.0, 2000. Available at http://www.secg.org[35] Standard for Eﬃcient Cryptography Group, SEC 2: Recommended Elliptic Curve Domain Parameters,
2000. Available at http://www.secg.org.

21