Speci cation of PSEC: Provably Secure Elliptic Curve
Encryption Scheme

1 Introduction
We describe an elliptic curve encryption scheme, PSEC (provably secure elliptic curve encryption
scheme), which has three versions: PSEC-1, PSEC-2 and PSEC-3. PSEC-1 is a public-key
encryption system that uses the elliptic curve ElGamal trapdoor function and a random function(hash function). PSEC-2 and PSEC-3 are public-key encryption systems that use the elliptic
curve ElGamal trapdoor function, two random functions (hash functions) and a symmetric-key
encryption (e.g., one-time padding and block-ciphers).
The encryption scheme described in this contribution is obtained by using three results on
conversion techniques using random functions [10, 11, 17, 18].

2 Design Policy
One of the most important properties of public-key encryption is provable security. The strongest
security notion in public-key encryption is that of non-malleability or semantical security against
adaptive chosen-ciphertext attacks. Bellare, Desai, Pointcheval and Rogaway [3] show thatsemantical security against adaptive chosen-ciphertext attacks (IND-CCA2) is equivalent to (orsucient for) the strongest security notion (NM-CCA2).
A promising way to construct a practical public-key encryption scheme semantically secureagainst adaptive chosen-ciphertext attacks (IND-CCA2) is to convert a primitive trap-door oneway function (such as RSA or ElGamal) by using random functions. Here, an ideally randomfunction, the \random oracle", is assumed when proving the security, and the random function
is replaced by a practical random-like function such as a one-way hash function (e.g., SHA-1 andMD5, etc.) when realizing it in practice. This approach was initiated by Bellare and Rogaway,
and is called the random oracle model [4, 5].
Although security in the random oracle model cannot be guaranteed formally when a practical random-like function is used in place of the random oracle, this paradigm often yields
much more ecient schemes than those in the standard model and gives an informal security
guarantee.
Two typical primitives of the trap-door one-way function are deterministic one-way permutation (e.g. RSA function) and probabilistic one-way function (e.g., ElGamal and OkamotoUchiyama functions).
1

Bellare and Rogaway presented a generic and ecient way to convert a trap-door one-way
permutation to an IND-CCA2 secure scheme in the random oracle model. (The scheme createdin this way from the RSA function is often called OAEP.) However, their method cannot beapplied to probabilistic trap-door one-way functions such as ElGamal.
Recently the authors, Fujisaki and Okamoto [10, 11], and Okamoto and Pointcheval [17,18] realized three generic and ecient measures to convert a probabilistic trap-door one-way
function to an IND-CCA2 secure scheme in the random oracle model. One is conversion froma semantically secure (IND-CPA) trap-door one-way function to an IND-CCA2 secure scheme[10]. Another is from a trap-door one-way (OW-CPA) function and a symmetric-key encryption(including one-time padding) to an IND-CCA2 secure scheme [11]. The other is from a gaptrap-door one-way (OW-CPA) function and a symmetric-key encryption (including one-time
padding) to an IND-CCA2 secure scheme [17, 18]. The latter two conversions can guarantee
the total security of the public-key encryption system in combination with a symmetric-key
encryption scheme.
PSEC has several outstanding properties as follows:
1. PSEC-1 is semantically secure or non-malleable against chosen ciphertext attacks (INDCCA2 or NM-CCA2) in the random oracle model under the elliptic curve decision DieHellman (EC-DDH) assumption.
2. PSEC-2 with one-time padding (PSEC-2-OTP) is semantically secure or non-malleable
against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model
under the elliptic curve Die-Hellman (EC-DH) assumption.
3. PSEC-2 with symmetric encryption (PSEC-2-SymE) is semantically secure or non-malleable
against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model
under the elliptic curve Die-Hellman (EC-DH) assumption, if the underlying symmetricencryption is secure against passive attacks.
4. PSEC-3 with one-time padding (PSEC-3-OTP) is semantically secure or non-malleable
against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model
under the elliptic curve gap Die-Hellman (EC-Gap-DH) assumption.
5. PSEC-3 with symmetric encryption (PSEC-3-SymE) is semantically secure or non-malleable
against chosen ciphertext attacks (IND-CCA2 or NM-CCA2) in the random oracle model
under the elliptic curve gap Die-Hellman (EC-gap-DH) assumption, if the underlying
symmetric encryption is secure against passive attacks.
6. If practical hash functions (e.g., SHA and MD5) are used as the underlying random functions, PSEC is almost as ecient as the elliptic curve ElGamal scheme. (Note that theelliptic curve ElGamal scheme is not secure against a chosen ciphertext attack.)

3 Notations
PSEC is speci ed by triplet (G ; E ; D), where G is the key generation operation, E the encryption
operation, and D the decryption operation.
2

We have three versions of PSEC: PSEC-1, PSEC-2 and PSEC-3. PSEC-1 is designed for
key-distribution and PSEC-2 and PSEC-3 are designed for both usages: the combination of keydistribution and encrypted data transfer, as well as distribution of a longer key under limited
public-key size.
In this speci cation, we use following notations.

 a := b: the value of b is substituted to a, or a is de ned as b.
 Z: the set of integers.
 Z=nZ := f0; 1; : : : ; n 0 1g.
 Let A, B be sets. AnB := fx j x 2 A ^ x 62 B g.
 (Z=nZ)3 := f1; 2; : : : ; n 0 1gnfx j gcd(x; n) =6 1g.
 Let Fq be a nite eld with q elements, where q = q0 n (q0: prime). When a minimal
polynomial over Z=pZ, f (x) = f0 + f1 x + 1fn xn , and basis (normal basis or polynomial
basis) are xed, en element of Fq is expressed by a = (an01 ; an02 ; : : : ; a0 ) (ai 2 Z=pZ).
 f0; 1g3 is the set of nite strings. f0; 1g3 is also denoted by B.
 f0; 1gi is the set of i bit length bit strings. f0; 1gi is also denoted by Bi.
 Let a 2 Z. Bi [a] denotes a bit string (ai01 ; ai02; : : : ; a0 ) 2 Bi such thata = a0 + 2a1 + 22 a2 + 1 1 1 2i01 ai01.

 When a 2 Fq and q = q0n (q0: prime), let a be represented by a = (an01; an02; : : : ; a0)(ai 2 Z=pZ), where 2k01  p  2k 01. Then Bn1k [a] denotes a bit string, (Bk [an01 ]jjBk [an02 ]1 1 1 Bk [a0]) 2 Bn1k , where jFq j := n 1 k.
 Let P be a point on an elliptic curve over Fq . B8+21qLen[P ] denotes a bit string (00000UCY jj
BqLen [xP ] jjBqLen [yP ]) 2 B8+21qLen (qLen := jFq j). Here, xP and yP denotes the xcoordinate and y-coordinate of P , and (UCY ) follows the de nition of IEEE P1363 E.2.3.2[13].

 Let a := (ai01 ; ai02; : : : ; a0) 2 Bi. I[a] denotes an integer b 2 Z such thatb = a0 + 2a1 + 22 a2 + 1 1 1 2i01 ai01.

 If a 2 Bi, jaj := i.
 a  b (mod n) means a 0 b is divided by n. a := b mod n denotes a 2 Z=nZ and a  b(mod n).

3

 Let a 2 B and b 2 B. ajjb denotes the concatenation of a and b. For example,(0; 1; 0; 0)jj(1; 1; 0) = (0; 1; 0; 0; 1; 1; 0).
 Let X 2 B. [X ]k denotes the most k signi cant bits of X .
 Let X 2 B. [X ]k denotes the least k signi cant bits of X .
 Let a 2 Bi and b 2 Bi. a 8 b means the bit-wise exclusive-or operation. (i.e., a 8 b 2 Bi.) Let a 2 Bi and b 2 Bj (i < j ). When a 8 b is calculated, `0' bits are padded to the upperof a and the resulting string is j bit long, then the 8 operation is executed. For example,(101) 8 (10100) := (00101) 8 (10100) = (10001).
 Let Q be a point on an elliptic curve, xQ denotes the x-coordinate of Q.

4 Primitive Encryption Function
PSEC employs the elliptic curve ElGamal encryption function as a primitive encryption function.
4.1

Key Generation:G

The input and output of G are as follows:[Input ] Security parameter k

2 Z.

[Output ] A pair of public-key, (Fq ; a; b; p; P; W; pLen; qLen)s Z.

2

2 Zn+4 2 Z7 , and secret-key

The operation of G , on input k, is as follows: Choose elliptic curve (EC) domain parameters, q for a nite eld Fq ; two elliptic curvecoecients a and b, elements of Fq , that de nes an elliptic curve E ; a positive prime
integer p dividing the number of points on E ; and a curve point P with order p. (SeeIEEE P1363 A.12.4 { 12.7, [13]). Here the parameter (a; b) is based on the Weierstrassstandard form, 2k01  p  2k 0 1, and P is represented by the ane coordinates (i.e.,
P 2 (Fq )2 ).
When q = q0 n (q0 : prime), Fq is represented by ((q0 ; n); (fn ; 1 1 1 ; f1 ; f0 ); b) 2 Zn+4 , where(fn ; 1 1 1 ; f1 ; f0 ) denoted the minimum polynomial over Z=q0 Z f (x) = f0 + f1 x + 1fn xn , andb denotes the type of basis (b = 1: normal basis; b = 2: polynomial basis).

 Choose s 2 (Z=pZ)3 randomly, and calculates a point W on E , where W = sP .
 Set pLen := k, and qLen := jqj.
Note: The EC domain parameters are used in every EC primitive and scheme and an implicit
component of every EC key. h can be xed by the system and shared by many users.

4

4.2

Encryption:

E

The input and output of E are as follows:[Input ] Plaintext m
Zn+4 Z9 .

2

2 f0; 1gmLen along with public-key (Fq ; a; b; p; P; W; pLen; qLen) 2[Output ] Ciphertext c = (C1 ; c2 )2 Z2 2 f0; 1gqLen.

The operation of E , on input m and (Fq ; a; b; p; P; W; hID; pLen; mLen; hLen, rLen; qLen)
is as follows: Select r 2 f0; 1grLen uniformly.
 Compute Q and C1 , such that

Q := rW; Compute c2:
4.3

C1 := yP:c2 := m 8 BqLen [xQ ]:Decryption:

D

The input and output of D are as follows:[Input ] Ciphertext c = (C1 ; c2 ) Z2
0; 1 qLen along with public-key (Fq ; a; b; p; P; W; pLen;n+49qLen) Z
Z and secret-key s Z.

22

[Output ] Plaintext m

2 2f g2

2 f0; 1gqLen.

The operation of D, on input c along with (q; a; b; p; P; W; pLen; qLen) and s, is as follows: Compute Q0 := sC1, a point on E , and m0 := c2 8 BqLen[xQ ].
 Output m0 as decrypted plaintext.
0

5 Auxiliary Functions
In this section, we show auxiliary functions we use in this speci cation.

 (k bit) pseudo-random number generator.
 (k bit) prime number generator.
 Hash function.
 Symmetric encryption algorithm SymE .
 Elliptic curve cryptosystem generating algorithm.
 Elliptic curve group arithmetic algorithm.
 Primitive integer arithmetic algorithm.
5

6 Speci cation of PSEC-1
6.1 Key Generation: G

The input and output of G are as follows:[Input ] Security parameter k 2 Z.
[Output ] A pair of public-key, (Fq ; a; b; p; P; W; hID; pLen; mLen; hLen; rLen; qLen)
Z13 , and secret-key s Z.

2

2 Zn+42

The operation of G , on input k, is as follows: Choose elliptic curve (EC) domain parameters, q for a nite eld Fq ; two elliptic curvecoecients a and b, elements of Fq , that de nes an elliptic curve E ; a positive prime
integer p dividing the number of points on E ; and a curve point P with order p. (SeeIEEE P1363 A.12.4 { 12.7, [13]). Here the parameter (a; b) is based on the Weierstrassstandard form, 2k01  p  2k 0 1, and P is represented by the ane coordinates (i.e.,
P 2 (Fq )2 ).
When q = q0 n (q0 : prime), Fq is represented by ((q0 ; n); (fn ; 1 1 1 ; f1 ; f0 ); b) 2 Zn+4 , where(fn ; 1 1 1 ; f1 ; f0 ) denoted the minimum polynomial over Z=q0 Z f (x) = f0 + f1 x + 1fn xn , andb denotes the type of basis (b = 1: normal basis; b = 2: polynomial basis).

 Choose s 2 (Z=pZ)3 randomly, and calculates a point W on E , where W = sP .
 Set pLen := k, and qLen := jqj. Set mLen and rLen such that mLen + rLen  qLen.
Set hLen  pLen.
 Select a (hash) function h: f0; 1gmLen+rLen 0! f0; 1ghLen, and its identi er is hID.

Note: The EC domain parameters are used in every EC primitive and scheme and an implicit
component of every EC key. h can be xed by the system and shared by many users.
6.2

Encryption:

E

The input and output of E are as follows:[Input ] Plaintext m 2 f0; 1gmLen along with public-key (Fq ; a; b; p; P; W; hID; pLen; mLen;
hLen, rLen; qLen) 2 Zn+4 2 Z13 .
[Output ] Ciphertext c = (C1 ; c2 )2 Z2 2 f0; 1gqLen.

The operation of E , on input m and (Fq ; a; b; p; P; W; hID; pLen; mLen; hLen, rLen; qLen)
is as follows: Select r 2 f0; 1grLen uniformly, and compute t := h(mjjr).

 Set:= I[t], and compute Q and R, points on C1 , such that

Q := W;

 Compute c2:

C1 := P:c2 := (mjjr) 8 BqLen [xQ ]:66.3

Decryption:

D

The input and output of D are as follows:

2 Z22f0; 1gqLen along with public-key (Fq ; a; b; p; P; W; hID; pLen;
mLen; hLen; rLen; qLen) 2 Zn+4 2 Z13 and secret-key s 2 Z.
[Output ] Plaintext m 2 f0; 1gqLen or null string.
The operation of D, on input c along with (Fq ; a; b; p; P; W; hID; pLen; mLen; hLen; rLen,[Input ] Ciphertext c = (C1 ; c2 )qLen) and s, is as follows: Compute Q0 := sC1, a point on E , and u := c2 8 BqLen[xQ ]. Set u0 = [u]mLen+rLen.
 Check whether the following equation holds or not:0

C1 = 0 P;
where 0 := I[h(u0 )].

 If it holds, output [u0]mLen as decrypted plaintext. Otherwise, output null string.

7 Speci cation of PSEC-2
7.1 Key Generation: G

The input and output of G are as follows:[Input ] Security parameter k

2 Z.

[Output ] A pair of public-key, (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen; rLen; qLen)
Zn+4 Z15 , and secret-key s Z.

22

The operation of G , on input k, is as follows: Choose elliptic curve (EC) domain parameters, q for a nite eld Fq ; two elliptic curvecoecients a and b, elements of Fq , that de nes an elliptic curve E ; a positive prime
integer p dividing the number of points on E ; and a curve point P with order p. (SeeIEEE P1363 A.12.4 { 12.7, [13]). Here the parameter (a; b) is based on the Weierstrassstandard form, 2k01  p  2k 0 1, and P is represented by the ane coordinates (i.e.,
P 2 (Fq )2 ).
When q = q0 n (q0 : prime), Fq is represented by ((q0 ; n); (fn ; 1 1 1 ; f1 ; f0 ); b) 2 Zn+4 , where(fn ; 1 1 1 ; f1 ; f0 ) denoted the minimum polynomial over Z=q0 Z f (x) = f0 + f1 x + 1fn xn , andb denotes the type of basis (b = 1: normal basis; b = 2: polynomial basis).

 Choose s 2 (Z=pZ)3 randomly, and calculates a point W on E , where W = sP .
 Set pLen := k, and qLen := jqj. Set rLen such that rLen  qLen.
72 Select two (hash) functions, h: f0; 1gmLen+rLen 0! f0; 1ghLen, g: f0; 1grLen 0! f0; 1ggLen,
and their identi ers are hID and gID respectively.

 Let SymE = (SymEnc; SymDec) be a pair of symmetric-key encryption and decryption

algorithms with symmetric-key K , where the length of K is gLen. The identi er of SymE
is SEID. Let SEID = 1 denotes that SymE is the one-time-pad.
Encryption algorithm SymEnc takes key K and plaintext X , and returns ciphertext
SymEnc(K; X ). Decryption algorithm SymDec takes key K and ciphertext Y , and returns plaintext SymDec(K; Y ). Here we assume that for any key K , function SymEnc(K; 1)
is one-to-one and onto.

Note: The EC domain parameters are used in every EC primitive and scheme and an implicit
component of every EC key. h can be xed by the system and shared by many users.
7.2

Encryption:

E

The input and output of E are as follows:

2 f0; 1gmLen along with public-key (Fq ; a; b; p; P; W; hID; gID; SEID; pLen;
hLen; gLen; rLen; qLen) 2 Zn+4 2 Z15.
[Output ] Ciphertext c = (C1 ; c2 ; c3 ) 2 Z2 2 f0; 1gqLen+mLen .
The operation of E , on input m, (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen; rLen; qLen)[Input ] Plaintext m

is as follows: Select r 2 f0; 1grLen uniformly, and compute g(r) and t := h(mjjr).
 Set := I[t], and compute Q and C1, points on E , such that
Q := W;

C1 := P: Compute c2 and c3 as follows:c2 := r 8 BqLen [xQ ];c3 := SymEnc(g(r); m):Remark: A typical way to realize SymE is one-time padding.

That is, SymEnc(key; ptext) := key 8 ptext, and SymDec(key; ctext) := key 8 ctext, where 8
denotes the bit-wise exclusive-or operation.
When mLen is longer than gLen, we use an appropriate symmetric encryption (block cipher
or stream cipher) rather than one-time padding.

8

7.3

Decryption:

D

The input and output of D are as follows:[Input ] Ciphertext c = (C1 ; c2 ; c3 ) along with public-key (Fq ; a; b; p; P; W; hID; gID; SEID; pLen;
hLen; gLen; rLen; qLen) Zn+4 Z15 secret-key s Z.

222
[Output ] Plaintext m 2 f0; 1gmLen or null string.
The operation of D, on input c along with (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen;

rLen; qLen) and s, is as follows: Compute Q0 := sC1, a point on E , and u := c2 8 BqLen[xQ ]. Set r0 := [u]rLen.
 Compute m0 := SymDec(g(r0); c3 ).
 Check whether the following equation holds or not:0

C1 = 0 P;
where 0 := I[h(m0 jjr0 )].

 If it holds, output m0 as the decrypted plaintext. Otherwise, output null string.

8 Speci cation of PSEC-3
8.1 Key Generation: G

The input and output of G are as follows:[Input ] Security parameter k

2 Z.

[Output ] A pair of public-key, (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen; rLen; qLen)
Zn+4 Z15 , and secret-key s Z.

22

The operation of G , on input k, is as follows: Choose elliptic curve (EC) domain parameters, q for a nite eld Fq ; two elliptic curvecoecients a and b, elements of Fq , that de nes an elliptic curve E ; a positive prime
integer p dividing the number of points on E ; and a curve point P with order p. (SeeIEEE P1363 A.12.4 { 12.7, [13]). Here the parameter (a; b) is based on the Weierstrassstandard form, 2k01  p  2k 0 1, and P is represented by the ane coordinates (i.e.,
P 2 (Fq )2 ).
When q = q0 n (q0 : prime), Fq is represented by ((q0 ; n); (fn ; 1 1 1 ; f1 ; f0 ); b) 2 Zn+4 , where(fn ; 1 1 1 ; f1 ; f0 ) denoted the minimum polynomial over Z=q0 Z f (x) = f0 + f1 x + 1fn xn , andb denotes the type of basis (b = 1: normal basis; b = 2: polynomial basis).

 Choose s 2 (Z=pZ)3 randomly, and calculates a point W on E , where W = sP .
92 Set pLen := k, and qLen := jqj. Set rLen such that rLen  qLen.
 Select two (hash) functions, h: f0; 1g8+41qLen+21mLen 0! f0; 1ghLen , g: f0; 1gqLen 0!
f0; 1ggLen and their identi ers are hID and gID respectively.
 Let SymE = (SymEnc; SymDec) be a pair of symmetric-key encryption and decryption

algorithms with symmetric-key K , where the length of K is gLen. The identi er of SymE
is SEID. Let SEID = 1 denotes that SymE is the one-time-pad.
Encryption algorithm SymEnc takes key K and plaintext X , and returns ciphertext
SymEnc(K; X ). Decryption algorithm SymDec takes key K and ciphertext Y , and returns plaintext SymDec(K; Y ). Here we assume that for any key K , function SymEnc(K; 1)
is one-to-one and onto.

Note: The EC domain parameters are used in every EC primitive and scheme and an implicit
component of every EC key. h can be xed by the system and shared by many users.
8.2

Encryption:

E

The input and output of E are as follows:

2 f0; 1gmLen along with public-key (Fq ; a; b; p; P; W; hID; gID; SEID; pLen;
hLen; gLen; rLen; qLen) 2 Zn+4 2 Z15.
[Output ] Ciphertext c = (C1 ; c2 ; c3 ; c4 ) 2 Z2 2 f0; 1gqLen+mLen+hLen .
The operation of E , on input m, (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen; rLen; qLen)[Input ] Plaintext m

is as follows: Select u 2 f0; 1gqLen and r 2 (Z=pZ)3 uniformly.
 Compute C1 and T , points on E , such that
C1 := rP;

 Compute

T := rW:c2 := u 8 BqLen [xT ]and g(u).

 Compute c3 and c4 as follows:c3 := SymEnc(g(u); m);c4 := h(B8+21qLen [C1 ]jjc2 jjc3 jjujjm):
Remark: A typical way to realize SymE is one-time padding.

That is, SymEnc(key; ptext) := key 8 ptext, and SymDec(key; ctext) := key 8 ctext, where 8
denotes the bit-wise exclusive-or operation.
When mLen is longer than gLen, we use an appropriate symmetric encryption (block cipher
or stream cipher) rather than one-time padding.
10

8.3

Decryption:

D

The input and output of D are as follows:[Input ] Ciphertext c = (C1 ; c2 ; c3 ; c4 )Z2
0; 1 qLen+mLen+hLen along with public-key(Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen; gLen; rLen; qLen) Zn+4 Z15 secretkey s Z.

2

[Output ] Plaintext m

2

2f g

2

2

2 f0; 1gmLen or null string.

The operation of D, on input c along with (Fq ; a; b; p; P; W; hID; gID; SEID; pLen; hLen;
gLen; rLen; qLen) and s, is as follows: Compute T 0 := sC1, a point on E , and u0 := c2 8 BqLen[xT ].
 Compute m0 := SymDec(g(u0 ); c3).
 Check whether the following equation holds or not:c4 = h(B8+21qLen [C1 ]jjc2 jjc3 jju0 jjm0 ):0 If it holds, output m0 as the decrypted plaintext. Otherwise, output null string.
8.4

Session Like Method for PSEC-3 Encryption

We can use PSEC-3 as following session like method.

 Sender chooses uniform randomly u 2 f0; 1gqLen and r 2 (Z=pZ)3
 Sender computes C1 := rP , T := rW , c2 := u 8 BqLen[xT ] and K := g(u), and sends(C1 ; c2 )

 Receiver decrypts u from (C1 ; c2 ), and computes K := g(u). [key sending phase nished] For each plaintext mi （i = 1; 2; : : : ;), Sender computes c3;i := SymEnc(K; mi) andc4;i := H (B8+21qLen [C1 ]jjc2 jjc3;i jjujjmi ), and sends (c3;i ; c4;i ).
 Sender decrypts mi by using K , and checks c4;i = H (B8+21qLen [C1]jjc2 jjc3;ijjujjmi) [cipher
communication phase nished]

9 Recommended Parameters
For PSEC-1/2/3, the security parameter, k, should be at least 160, and hLen should be at least
128.
Here we will show a typical case of parameters employed in our self-evaluation document.
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 andhLen) are 128 bits and 160 bits. PSEC-3-OTP assumes that hashed value lengths (gLen andhLen) are 128 bits.
11

10 Hash Function
We can use any random-like one-way functions H and G for PSEC. PSEC can be proven to be
secure if H and G are ideal random functions, while no formal security is guaranteed if they arepractical random-like one-way functions.) In this subsection we will show a typical constructionof function H with hLen > 160 out of SHA (NIST Secure Hash Algorithm), which was suggested
by Bellare and Rogaway [5].
We denote by SHA (x) the 160-bit result of SHA applied to x, except that the 160-bit\starting value" in the algorithm description is taken to be ABCDE = . Let SHAl (x) denote
the rst l-bits of SHA (x). Fix the notation < i > for i encoded as a binary 32-bit word. We
de ne the function H as:

80
L
H (x) := SHA80
 (< 0 > jjx)jjSHA (< 1 > jjx)jj 1 1 1 jjSHA (< l > jjx);lwhere l = b 380k c, and Ll = hLen 0 80l.

References[1] Abdalla, M., Bellare, M. and Rogaway, P.: DHES: An Encryption Scheme Based on theDie-Hellman Problem, Submission to IEEE P1363a (1998, August)[2] Ajtai, M. and Dwork, C.: A Public-Key Cryptosystem with Worst-Case/Average-Case
Equivalence, Proc. of STOC'97, pp. 284-293 (1997).
[3] Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P.: Relations Among Notions ofSecurity for Public-Key Encryption Schemes, Proc. of Crypto'98, LNCS 1462, SpringerVerlag, pp. 26{45 (1998).
[4] Bellare, M. and Rogaway, P.: Random Oracles are Practical: A Paradigm for DesigningEcient Protocols, Proc. of the First ACM Conference on Computer and Communications
Security, pp.62{73 (1993).
[5] Bellare, M. and Rogaway, P. : Optimal Asymmetric Encryption, Proc. of Eurocrypt'94,
LNCS 950, Springer-Verlag pp.92-111 (1995).
[6] Canetti, R., Goldreich, O. and Halevi, S.: The Random Oracle Methodology, Revisited,
Proc. of STOC, ACM Press, pp.209{218 (1998).
[7] Dolev, D., Dwork, C. and Naor, M.: Non-Malleable Cryptography, Proc. of STOC, pp.542{552 (1991).
[8] Die, W. and Hellman, M.: New Directions in Cryptography, IEEE Trans. on Information
Theory, IT-22, 6, pp.644{654 (1976).
[9] ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete
Logarithms, IEEE Trans. on Information Theory, IT-31, 4, pp.469{472 (1985).
12[10] Fujisaki, E. and Okamoto, T.: How to Enhance the Security of Public-Key Encryption at
Minimum Cost, Proc. of PKC'99, LNCS 1560, Springer-Verlag, pp.53{68 (1999).
[11] Fujisaki, E. and Okamoto, T.: Secure Integration of Asymmetric and Symmetric Encryption
Schemes, Proc. of Crypto'99, LNCS 1666, Springer-Verlag, pp.535{554 (1999).
[12] Goldwasser, S. and Micali, S.: Probabilistic Encryption, JCSS, 28, 2, pp.270-299 (1984).
[13] IEEE P1363 Draft (D9), http://grouper.ieee.org/groups/1363/P1363/draft.html (1999).
[14] Koblitz, N.: Elliptic Curve Cryptosystems, Math. Comp., 48, 177, pp.203{209 (1987).
[15] Merkle, R.C. and Hellman, M.E.: Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. on Inform. Theory, 24, pp.525-530 (1978).
[16] Miller, V.S.: Use of Elliptic Curves in Cryptography, Proc. of Crypto'85, LNCS 218,
Springer-Verlag, pp.417-426 (1985).
[17] Okamoto, T. and Pointcheval, D.: BEST: A Generic Coversion to Achieve ChosenCiphertext Security, manuscript (2000).
[18] Okamoto, T. and Pointcheval, D.: The Gap Problems: A New Class of Problems for the
Security of Cryptographic Schemes, manuscript (2000).
[19] Rivest, R., Shamir, A. and Adleman,L.: A Method for Obtaining Digital Signatures andPublic-Key Cryptosystems, Communications of the ACM, Vol.21, No.2, pp.120-126 (1978).

13

Appendix
A De nition of Optimal Extension Field(OEF)
binomial : a polynomial of the form tm

0 !.

pseudo-Mersenne prime: a positive rational integer of the form 2n

6 c; log2  bn=2c.

nite eld Fp with p a pseudo-Mersenne prime and an
irreducible binomial as the eld polynomial.

Optimal Extension Field(OEF): am

B Finite Field Arithmetic
An odd characteristic extension eld is a nite eld whose number of elements is a power ofan odd prime. If m  1, then there is a unique eld Fp with pm elements. For purposes of
conversion, the elements of Fp shall be represented in polynomial basis.
This representation is determined by choosing an irreducible polynomial p(t) over Fp . Then
Fp is isomorphic to Fp [t]=p(t). This interpretation shall be the bit string formed by concatenating the values of the coecients represented as integers. Thus the polynomialmmm

am01 tm01 + : : : + a2 t2 + a1 t + a0
is represented by the bit string(am01 ; : : : ; a2 ; a1 ; a0 )where each of the ai are positive integers less than p, padded with leading 0 bits so that eachai is represented with dlog2 pe bits.

14