Appears in P. Samarati, P. Ryan, D. Gollmann, R. Molva (Eds.):
Computer Security – ESORICS 2004,
Springer-Verlag LNCS 3193, pp. 335–351, ISBN 3-540-22987-6.

A Public-Key Encryption Schemewith Pseudo-Random Ciphertexts
Bodo Möller?
University of California, Berkeley
bmoeller@eecs.berkeley.edu

Abstract. This work presents a practical public-key encryption schemethat offers security under adaptive chosen-ciphertext attack (CCA) andhas pseudo-random ciphertexts, i.e. ciphertexts indistinguishable fromrandom bit strings. Ciphertext pseudo-randomness has applications insteganography. The new scheme features short ciphertexts due to theuse of elliptic curve cryptography, with ciphertext pseudo-randomness
achieved through a new key encapsulation mechanism (KEM) based on
elliptic curve Diffie-Hellman with a pair of elliptic curves where eachcurve is a twist of the other. The public-key encryption scheme resembles
the hybrid DHIES construction; besides by using the new KEM, it differsfrom DHIES in that it uses an authenticate-then-encrypt (AtE) rather
than encrypt-then-authenticate (EtA) approach for symmetric cryptography.

1

Introduction

Where encryption converts a message (plaintext) into a scrambled message (ciphertext) such that revealing the latter does not expose the former, steganographygoes further and seeks to hide even the fact that secret communication is taking
place. A cryptography-based approach is to encrypt the plaintext to be hidden, in
this context also known as the hiddentext, and embed the resulting ciphertext ina seemingly innocuous message, the covertext. The recipient extracts the ciphertext from the covertext and then uses the appropriate cryptographic decryption
key to recover the hiddentext. Formal treatments of public-key steganography
based on this approach have recently appeared in [3] and [5].
Public-key encryption schemes usually do not output ciphertexts that arepseudo-random in the sense of being indistinguishable from uniformly random
bit strings of the same length. Given just the public key, it is typically easy
to tell that certain bit strings cannot have come up during proper encryption(e.g., a bit string interpreted as an integer would exceed the modulus that would
have been used during encryption). Thus the prospects will often be good for anadversary who tries to distinguish actual ciphertexts from random bit strings: In
random bit strings, if an invalid encoding appears, this will clearly reveal that the
bit string in question is not an actual ciphertext. Conversely, depending on the?

Supported by a DAAD (German Academic Exchange Service) Postdoc fellowship.

1

probability that random data will give a valid encoding, seeing a valid encoding
or repeatedly seeing valid encodings can provide possibly strong indication thatthese values are not random.
The present work provides a public-key encryption scheme with pseudorandom ciphertexts as required for public-key steganography constructions likethose from [3] and [5]. Some previous schemes do exist (e.g. based on RSA encryption or Diffie-Hellman, see [3, Section 4]), but their downside is the lengthof ciphertexts; and the expense of having relatively long ciphertexts can be especially high in the context of steganography. (The number of bits available for
embedded ciphertexts typically is a small fraction of the covertext length. To
avoid detection of the steganographic communication, one would generally wantto have to use as little cover channel communication as possible.)
Our scheme uses elliptic curve cryptography to obtain short ciphertexts. Ciphertext pseudo-randomness is not immediate with any single cryptographicallysecure elliptic curve. Our trick to achieve it is to use a pair of elliptic curves overa field F2m such that each curve is a twist of the other. (The idea to use elliptic
curves with their twists has also come up in [21] and [22].)
The construction is hybrid and resembles DHIES [2] (also known as DHAES
from the earlier version [1] of that publication): it involves a key encapsulation mechanism (KEM), a one-time message authentication code (MAC), and a
stream cipher. While our elliptic curve KEM is novel and will be described indetail, a wide range of existing MACs and stream ciphers are available that canbe plugged into the construction.
Like DHIES, our scheme achieves security in a strong sense, namely security
under adaptive chosen-ciphertext attack (CCA). Besides by using a new KEM,
it differs from DHIES in that it applies the symmetric cryptographic primitives in a different order: While DHIES uses an encrypt-then-authenticate (EtA)
approach by computing the MAC on a symmetric ciphertext, our constructionuses an authenticate-then-encrypt (AtE) approach by computing the MAC of theplaintext and then symmetrically encrypting the MAC and the plaintext. This
modification is needed to prove ciphertext pseudo-randomness without requiring
additional security assumptions. Just as for DHIES, the security assumptions aremostly standard with the exception of a less conventional oracle Diffie-Hellman
assumption (which finds justification in the random-oracle model based on amore usual gap-Diffie-Hellman assumption [30], but is a concrete computational
assumption that can be expressed without resorting to this idealized model).
We also provide an appropriate pair of elliptic curves over F2163 to make theproposed scheme practical, thanks to Reynald Lercier who ran his point counting
algorithms to find suitable curves for the requirements of the scheme. The curve
pair is verifiably pseudo-random (like the well-known curves as in [13]) to allow
for independent verification that it has been generated properly from a seedvalue using a standardized process.
Section 2 gives formalizations of public-key encryption and key encapsulation with the relevant notions of security, CCA security and ciphertext pseudorandomness. Section 3 presents our elliptic curve KEM as the essential new2cryptographic primitive. Subsequently, Section 4 looks at well-known symmetric primitives, namely MACs and pseudo-random bit string generators for use
as stream ciphers. Section 5 puts the primitives together to build a public-key
encryption scheme, giving quantitative security results for CCA security andciphertext pseudo-randomness. Finally, Section 6 summarizes our conclusions.

2

Public-Key Cryptography with Pseudo-Random
Ciphertexts: Concepts

2.1

Public-Key Encryption

We formalize public-key encryption with two security notions, security under
adaptive chosen-ciphertext attack and ciphertext pseudo-randomness. Section 5
will show how to build a public-key encryption scheme with these properties
using appropriate primitives.
We start by describing the notion of public-key encryption in terms of its
interface. Note that algorithms are in general probabilistic.
Definition 1. A public-key encryption scheme PKE specifies a key generation
algorithm PKE.KeyGen and algorithms PKE.Encrypt and PKE.Decrypt. Algorithm PKE.KeyGen takes no input; it outputs a key pair (PK , SK ) consistingof a public key PK and a secret key SK . For a plaintext m (an arbitrary bit
string, possibly subject to length limitations for the specific public-key encryption
scheme),PKE.Encrypt(PK , m)returns a bit string c as ciphertext. On arbitrary input c0 ,PKE.Decrypt(SK , c0 )may either return some string m0 or fail and return the special value ⊥. If the
key pair (PK , SK ) has been output by PKE.KeyGen and c has been output by
PKE.Encrypt(PK , m), then evaluating PKE.Decrypt(SK , c) will return the original bit string m.
To capture security notions quantitatively, we assume that an adversary interacts with the cryptographic scheme in question in a specific attack game anddefine the adversary’s advantage in this game. An adversary is an interactive
probabilistic algorithm with bounded running time. Saying that a cryptographic
scheme is secure under some security notion means that the advantage will bevery low for every practical adversary (i.e. every adversary from some limitedclass of admissable adversaries), with details left open on what adversaries would
be considered practical and what advantage would be considered sufficiently low.
(Cryptographic schemes are often described as parameterized by an integer security parameter determining features such as the length of keys. Then security canbe formalized as a requirement that any polynomial-time adversary’s advantage
be negligible in the security parameter, i.e. asymptotically smaller than the reciprocal of any polynomial. We avoid explicit security parameters, which amounts3to having a fixed security parameter built into algorithms such as PKE.KeyGen.)
The security result for our public-key encryption scheme in Section 5 will relate
the security of the public-key encryption scheme to the security of its underlying
primitives: intuitively, if all primitives are secure under their respective security
notions, then the complete scheme will be secure.
As the first security notion for public-key encryption, we describe security
under adaptive chosen-ciphertext attack (CCA), CCA security for short. We use
a well-known find-then-guess attack game that expresses security as indistinguishability under CCA (IND-CCA). The term indistinguishability refers to theidea that adversaries should not be able to tell apart encryptions of any twoplaintexts, a notion due to [19]; the CCA scenario, which provides the adversary
with a decryption oracle, is due to [31]. For equivalent formalizations of CCA
security, see [8], [33], and [18, Chapter 5].
Definition 2. In the IND-CCA attack game, an adversary interacts with apublic-key encryption scheme PKE as follows.
1. The adversary queries a key generation oracle, which uses PKE.KeyGen to
determine a key pair (PK , SK ) and responds with PK (while secretly storing SK ).
2. The adversary makes a sequence of queries to a decryption oracle.
Each query is an arbitrary bit string s, and the oracle responds with
PKE.Decrypt(SK , s) before the adversary proceeds.
3. The adversary chooses plaintexts m0 and m1 with |m0 | = |m1 | (i.e., of thesame length) and sends them to an encryption oracle. This oracle choosesb ∈ {0, 1} uniformly at random and determinesc = PKE.Encrypt(PK , mb ),which is returned to the adversary as the challenge ciphertext.
4. The adversary again makes a sequence of queries to a decryption oracle as
in stage 2, where this time the decryption oracle refuses being asked for thedecryption of the challenge ciphertext c (responding ⊥ for this case).
5. The adversary outputs a value eb ∈ {0, 1}.
If A is any adversary in the IND-CCA attack game, its CCA advantage against
the public key encryption scheme isAdvIND-CCA= Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0 .
PKE,AThe value eb output by the adversary can be thought of as its guess for b.
The second (less usual) security notion for public-key encryption is ciphertext
pseudo-randomness. We describe it through a real-or-ideal (ROI) attack game.
Definition 3. In the real-or-ideal attack game for a public-key encryption
scheme PKE, an adversary interacts with PKE as follows.
1. The adversary queries a key generation oracle, which uses PKE.KeyGen to
determine a key pair (PK , SK ) and responds with PK .
4

2. The adversary makes a query to a real-or-ideal encryption oracle, or encryption oracle for short. The query consists of a plaintext m of any length valid
for PKE. The encryption oracle determines
c0 = PKE.Encrypt(PK , m),generates a uniformly random bit string c1 with |c1 | = |c0 |, chooses b ∈ {0, 1}
uniformly at random, and responds with cb .
3. The adversary outputs a value eb ∈ {0, 1}.
An adversary A in this attack game is also called a real-or-ideal distinguisher orsimply a distinguisher. Its real-or-ideal advantage against PKE is




e
e
AdvROI
PKE,A = Pr b = 1 | b = 1 − Pr b = 1 | b = 0 .
The real-or-ideal encryption oracle operates as a real encryption oracle if b = 0
and as an ideal encryption oracle if b = 1.
2.2

Key Encapsulation

Following Shoup [32], we use the term key encapsulation mechanism (KEM) fora scheme in public-key cryptography that is similar to public-key encryption
except that plaintexts cannot be arbitrarily specified by the party that creates aciphertext: instead, the randomized “encryption” algorithm, given some public
key, outputs both a pseudo-random plaintext and a corresponding ciphertext
such that the plaintext can be recovered from the ciphertext given the appropriate secret key. Such plaintexts can be used as keys for symmetric cryptography;
hence the term key encapsulation.
Definition 4. A key encapsulation mechanism KEM specifies a key generation
algorithm KEM.KeyGen and algorithms KEM.Encrypt and KEM.Decrypt. Algorithm KEM.KeyGen takes no input; it outputs a key pair (PK , SK ) consisting ofa public key PK and a secret key SK . Algorithm
KEM.Encrypt(PK )generates a bit string K of a fixed length KEM.OutLen and a ciphertext K of a
fixed length KEM.CipherLen, and outputs the pair (K, K). Evaluating
KEM.Decrypt(SK , K)
will return said bit string K if the key pair (PK , SK ) has been generated by
KEM.KeyGen. On arbitrary input K0 , the computation KEM.Decrypt(SK , K0 ) may
either return some bit string K 0 or fail and return the special value ⊥.
Similarly to Section 2.1, we use attack games to express two security notions:security under adaptive chosen-ciphertext attack (CCA security) and ciphertext
pseudo-randomness. Section 3 will describe a KEM based on elliptic curve DiffieHellman designed to meet these notions.
5Definition 5. In the real-or-random CCA attack game, an adversary interacts
with a key encapsulation mechanism KEM as follows (cf. [14, Section 7.1.2]).
1. The adversary queries a key generation oracle, which uses KEM.KeyGen tocompute a key pair (PK , SK ) and responds with PK .
2. The adversary makes a sequence of queries to a decryption oracle. Eachquery is an arbitrary bit string s of length KEM.CipherLen; the oracle responds with KEM.Decrypt(SK , s) before the adversary proceeds.
3. The adversary queries a real-or-random key encapsulation oracle, or key
encapsulation oracle for short. This oracle uses KEM.Encrypt(PK ) to obtaina pair (K0 , Koracle ), generates a uniformly random bit string K1 with |K1 | =|K0 |, chooses bKEM ∈ {0, 1} uniformly at random, and responds with
(KbKEM , Koracle )as challenge.
4. The adversary again makes a sequence of queries to a decryption oracle
as in stage 2, where this time the oracle refuses the specific query Koracle(responding ⊥ for this case).
5. The adversary outputs a value ebKEM ∈ {0, 1}.
If A is any adversary in the real-or-random CCA attack game, its CCA advantage against the key encapsulation mechanism KEM isAdvROR-CCA= Pr ebKEM = 1 | bKEM = 1 − Pr ebKEM = 1 | bKEM = 0 .
KEM,AThe real-or-random key encapsulation oracle operates as a real key encapsulation
oracle if bKEM = 0 and as a random key encapsulation oracle if bKEM = 1.
Definition 6. In the real-or-ideal attack game for a key encapsulation mechanism KEM, an adversary interacts with KEM as follows.
1. The adversary queries a key generation oracle, which uses KEM.KeyGen to
determine a key pair (PK , SK ) and responds with PK .
2. The adversary queries a real-or-ideal key encapsulation oracle, or
key encapsulation oracle for short. The key encapsulation oracle uses
KEM.Encrypt(PK ) to determine a pair (K, K0 ), generates a uniformly random bit string K1 of length KEM.CipherLen, chooses bKEM ∈ {0, 1} uniformly
at random, and responds with KbKEM .
3. The adversary outputs a value ebKEM ∈ {0, 1}.
An adversary A in this attack game is also called a real-or-ideal distinguisher orsimply a distinguisher. Its real-or-ideal advantage against KEM is




e
e
AdvROI
KEM,A = Pr bKEM = 1 | bKEM = 1 − Pr bKEM = 1 | bKEM = 0 .
The real-or-ideal key encapsulation oracle operates as a real key encapsulation
oracle if bKEM = 0 and as an ideal key encapsulation oracle if bKEM = 1.
6

3

An Elliptic Curve KEM with Random Ciphertexts

We need a key encapsulation mechanism (KEM) that is CCA-secure and provides
ciphertext pseudo-randomness.
First consider CCA security (Definition 5). The scheme DHIES from [2] uses
hash Diffie-Hellman (HDH) as a CCA-secure KEM. The idea of HDH is toemploy Diffie-Hellman [15] in some group followed by the application of a key
derivation function (KDF) to obtain pseudo-random bit strings from group elements. We will use HDH with elliptic curve Diffie-Hellman (ECDH, due to [28]and [23]) following the idea originally proposed in [28] that it suffices to transfer
just x-coordinates of points. The assumption that HDH schemes are CCA-secure
key encapsulation mechanisms amounts to accepting an oracle Diffie-Hellman
assumption; see [2]. (By appealing to the random-oracle model [9], this assumption can be justified based on a gap-Diffie-Hellman assumption [30], i.e. an assumption on the hardness of the computational Diffie-Hellman problem given adecisional Diffie-Hellman oracle; cf. [2] and [14, Theorem 9]. There are concerns
about the use of the random-oracle model [11], but here this idealized model
would be only a locally used tool to explain the plausibility of a specific security
assumption on the KEM; the oracle Diffie-Hellman assumption can be expressed
directly without employing the random-oracle model.)Now consider ciphertext pseudo-randomness (Definition 6). Our KEM will be
constructed to have ciphertexts that are uniformly random bit strings of length
KEM.CipherLen, which implies AdvROI
KEM,A = 0 for any adversary.
We arrive at the KEM by first presenting some preliminaries on elliptic curves(Section 3.1), then discussing system parameters (Section 3.2 with specific values
in Appendix A), and finally specifying the actual KEM (Section 3.3).
3.1

Preliminaries on Elliptic Curves

The KEM will use elliptic curves over some finite field F2m (refer to e.g. [10]for introductory material on elliptic curve cryptography). There are well-known
requirements for cryptographically secure elliptic curves over such fields [20],which we will take into account (Section 3.2). We require that m be an odd
prime as there are security concerns about F2m with m composite. Every nonsupersingular curve over F2m is isomorphic to a curve described by a curve
equation
Ea,b : y 2 + xy = x3 + ax2 + b
where coefficients a and b are elements of F2m , b 6= 0. The group Ea,b (F2m )of rational points on such a curve consists of the set of solutions (x, y) of that
equation with x, y ∈ F2m , and an additional point O. We have#Ea,b (F2m ) − 2m − 1 < 2 · 2m/2
(Hasse’s inequality). The group operation (see [10] or [20] for the definition) is
commutative, and by convention is written as addition. O, the point at infinity,
is the neutral element; the inverse of any element (x, y) is (x, x + y). The group7

operation canonically gives rise to scalar multiplication kP of a point P by an
integer k.
If TrF2m /F2 a = TrF2m /F2 a0 , the curves
Ea,b :

y 2 + xy = x3 + ax2 + b,

Ea0 ,b :y 2 + xy = x3 + a0 x2 + b

are isomorphic with a group isomorphism Ea,b (F2m ) → Ea0 ,b (F2m ) given by(x, y) 7→ (x, y + sx)
where s ∈ F2m satisfies a0 = a + s + s2 (such an s always exists in this case);otherwise Ea,b and Ea0 ,b are called twists of each other.
If Ea,b and Ea0 ,b are twists of each other, then for every x ∈ F2m there is ay ∈ F2m such that (x, y) is a point on one of the two curves. Specifically, each x
occurs exactly twice: either there√ are two different points (x, y) and (x, x + y) on
the same curve; or (x, y) = (0, b), which is a point on both curves. The total
number of points (taking into account O for each curve) is#Ea,b (F2m ) + #Ea0 ,b (F2m ) = 2m+1 + 2.
Hasse’s inequality implies #Ea,b (F2m ) ≈ 2m ≈ #Ea0 ,b (F2m ).
3.2

System Parameters

If in the situation of Section 3.1 we vary coefficient a for fixed b, we obtaincurves in one of two equivalence classes depending on whether TrF2m /F2 a = 0
or TrF2m /F2 a = 1. All curves within a single class are isomorphic; the otherclass contains their twists. We have TrF2m /F2 0 = 0 and TrF2m /F2 1 = 1 as m isodd, so we can use E0,b and E1,b as a canonical pair of curves that are twistsof each other. (The explicit isomorphism shown in Section 3.1 means that the
specific choices for a affect only y-coordinates.) Coefficient b remains to be chosensuch that the groups E0,b (F2m ) and E1,b (F2m ) are both cryptographically secure.
Requirements for suitable curves are ([12, Section 3.1.2.1], [4, Annex A.3.2]):– The group order #Ea,b (F2m ) must be a product ha,b pa,b with 1 ≤ ha,b ≤ 4
and pa,b prime.
– For said prime, it must hold that 2mB 6≡ 1 (mod pa,b ) for 1 ≤ B ≤ 20(the MOV condition [27]).
√ √ The curve E0,b has a point 4 b, b of order 4, so we will use h0,b = 4; notethat the group E0,b (F2m ) will then necessarily be cyclic. From #E0,b (F2m ) +#E1,b (F2m ) ≡ 2 (mod 4), it follows that h1,b = 2; thus E1,b (F2m ) will be cyclic
too. Define tb such that
#E0,b (F2m ) = 2m + 1 − tb = 4 p0,b ,#E1,b (F2m ) = 2m + 1 + tb = 2 p1,b ;8

a pair of suitable curves can be generated by choosing b ∈ F2m \ {0}, determining tb through point counting techniques (see [26] for fast algorithms), andverifying thatp0,b =

2m + 1 − tb4

andp1,b =

2m + 1 + tb
2

are indeed both prime and satisfy the MOV condition. Heuristically, for random b, the integer p0,b will be prime with probability about 1/m ([17] gives more
precise estimates), and p1,b will be prime as well with probability about 1/m;
the MOV condition is not likely to cause problems if b is actually random. Thus,
one has to expect to have to test approximately m2 random choices for b before
finding a suitable one.
It is common to use standardized pre-generated elliptic curves over appropriate fields instead of generating new curves as part of key generation. Parametersprovided to others are usually expected to be verifiably pseudo-random withb derived from some seed value through a standardized process, typically with
SHA-1 as specified in [4, Annex A.3.3.1] and [20, Annex A.12.6]. We provide averifiably pseudo-random pair of curves over F2163 in Appendix A.
Now let b ∈ F2m \ {0} be fixed such that the curves E0 = E0,b and E1 = E1,b
are both cryptographically suitable with orders#E0 (F2m ) = 4 p0 = n0

and#E1 (F2m ) = 2 p1 = n1

where p0 and p1 are prime. As additional parameters, for a ∈ {0, 1}, let Ga be a
generator of Ea (F2m ), i.e. any element of order na . Note that n0 +n1 = 2m+1 +2.
3.3

Specification

We assume that system parameters as discussed in Section 3.2 have been fixed,
and that mappings
encode : F2m → {0, 1}mand

decode : {0, 1}m → F2m

that are inverses of each other have been agreed upon (cf. FE2OSP and OS2FEPin [20] or FieldElement-to-OctetString and OctetString-to-FieldElement in [12]and [4]). We also assume that a key derivation function (KDF) that outputs bit
strings of some length KEM.OutLen has been specified (for a practical example,
see KDF1 in [20] or ANSI-X9.63-KDF in [12]). The KDF will be used only on
input bit strings of length 2m. We now show a key encapsulation mechanism
KEM with KEM.CipherLen = m.
KEM.KeyGen: Choose integers s0 and s1 independently uniformly at random
among those satisfying 0 < sa < na with sa and na relatively prime. Thencompute the points Pa = sa Ga for a ∈ {0, 1}. Output the public key PK =(P0 , P1 ) and the secret key SK = (s0 , s1 ).
9

n0 − 1n1 − 1
KEM.Encrypt(PK ): Choose a ∈ {0, 1} with probability m+1 for a = 0, m+1
2
2
for a = 1. Then choose a uniformly random integer u with 0 < u < na .
Compute Q = uGa and R = uPa in the group Ea (F2m ); these points will
never be O with valid system parameters and a valid public key, so they canbe written as coordinate pairs (xQ , yQ ) and (xR , yR ). Finally, set

K = KDF(K || encode(xR ) ,K = encode(xQ )(|| denotes concatenation) and return the pair (K, K).
KEM.Decrypt(SK , K): Set x = decode(K). Then determine a y ∈ F2m such that(x, y) is a point on E0 if there is such a y; if so, set a = 0. Otherwise,
determine a y ∈ F2m such that (x, y) is a point on E1 and set a = 1.In either
case, set Q = (x, y) and compute R = sa Q in the group Ea (F2m ). This point
will never be O with valid system parameters and a valid secret key, so it
can be written as a coordinate pair (xR , yR ). Finally, set

K = KDF(K || encode(xR )and return K.
Determining y given x in KEM.Decrypt amounts to performing point decompression; for algorithms, cf. [4, Section 4.22], [20, Annex A.12.9], or [12, Section 2.3.4].
In KEM.Encrypt, each element of F2m can come up as xQ with probability−m2(any given xQ appears exactly twice among the x-coordinates of the n0 − 1
points of E0,b (F2m ) \ {O} and the n1 − 1 points of E1,b (F2m ) \ {O}). Thus, thedistribution of K ∈ {0, 1}m is uniform.
Assuming that a has been correctly recovered, the point Q computed in
KEM.Decrypt will be either identical to or the inverse of the point Q originallyused in KEM.Encrypt; the same relationship will apply to the respective points R(we have ±R = ±uPa = ±usa Ga = ±sa Q); so xR will come out correctly as
inversion affects only y-coordinates. KEM.Decrypt √can unequivocally recover ain all cases except one, when x = 0 so that Q = (0, b) is the point of order 2 oneither E0 (F2m ) or E1 (F2m ); but in this case (of negligible probability) the same
result would be obtained in either group.
As discussed earlier, it is reasonable to make an oracle Diffie-Hellman assumption implying that this KEM provides CCA security. Ciphertexts generated
as described above are uniformly random. By Hasse’s inequality (Section 3.1),
a simplified variant of KEM.Encrypt that picks a uniformly random a ∈ {0, 1}
would still achieve ciphertext pseudo-randomness.

4

Symmetric Primitives

4.1

Message Authentication CodeThe usual notion of a message authentication code (MAC) allows using a single
key for authenticating multiple messages. Like DHIES, we only need a one-time
MAC.
10

Definition 7. A one-time message authentication code MAC specifies a key
length MAC.KeyLen, an output length MAC.OutLen, and a deterministic algorithm that, given a bit string K of length MAC.KeyLen (a key) and a bit string m,
returns a bit string MAC(K, m) of length MAC.OutLen (a tag).
The security of a one-time MAC is expressed as follows.
Definition 8. In the forgery attack game, an adversary interacts with a onetime MAC as follows.
1. The adversary submits a bit string m to a MAC oracle. This oracle generates
a uniformly random bit string K of length MAC.KeyLen and responds with
MAC(K, m).
2. The adversary outputs a list (m1 , t1 ), (m2 , t2 ), . . ., (ml , tl ) of pairs of bit
strings.
Let A be any adversary in the forgery attack game. (Its running time boundimplies a bound on the length l of the list.) We say that adversary A has produced
a forgery if there is some k such that MAC(K, mk ) = tk and mk 6= m. The
adversary’s forgery advantage against MAC, denoted AdvForge
MAC,A , is the probability
that it produces a forgery in the above game.
A popular MAC construction is HMAC [6]; a specific variant with MAC.KeyLen =160 and MAC.OutLen = 80 is HMAC-SHA1-80 [24].
4.2

Pseudo-Random Bit String Generator

Our hybrid construction for public-key encryption uses a stream cipher to perform symmetric encryption. While other notions of stream ciphers are conceivable, for simplicity we assume a stream cipher based on the usual XOR paradigm:
symmetric encryption and decryption are the same operation, namely XOR witha pseudo-random bit string generated from a key.
Definition 9. A pseudo-random bit string generator STREAM specifies a key
length STREAM.KeyLen and a deterministic algorithm that, given a bit string Kof length STREAM.KeyLen (a key) and an integer n, generates an output bit
string STREAM(K, n) of length n.
Security is described through a real-or-ideal attack game.
Definition 10. In the real-or-ideal attack game for a pseudo-random bit string
generator STREAM, an adversary interacts with STREAM as follows.
1. The adversary sends an integer n to a real-or-ideal bit string oracle. The
oracle generates a uniformly random K with |K| = STREAM.KeyLen, sets
stream 0 = STREAM(K, n),generates a uniformly random stream 1 with |stream 1 | = n, chooses bSTR ∈{0, 1} uniformly at random, and responds with stream b as challenge. (It is
understood that the adversary’s running time bound implies a bound on n.)
11

2. The adversary outputs a value ebSTR ∈ {0, 1}.
An adversary A in this attack game is also called a real-or-ideal distinguisher orsimply a distinguisher. Its real-or-ideal advantage against STREAM is




e
e
AdvROISTREAM,A = Pr bSTR = 1 | bSTR = 1 − Pr bSTR = 1 | bSTR = 0 .
An example implementation is the counter mode (CTR) of a symmetric blockcipher such as AES (see [7] and [29]). (For n ≤ STREAM.KeyLen, it is also
be possible to define STREAM(K, n) as simply the n-bit prefix of K; then any
distinguisher would have real-or-ideal advantage 0.)

5

Public-Key Encryption with Pseudo-Random
Ciphertexts: Hybrid Construction

Now we are ready to show how a public-key encryption scheme PKE as discussed
in Section 2.1 can be built from primitives KEM (Section 2.2 and Section 3), MAC(Section 4.1), and STREAM (Section 4.2). Section 5.1 presents the hybrid construction, which follows DHIES except that it uses an authenticate-then-encrypt(AtE) rather than an encrypt-then-authenticate (EtA) approach. Section 5.2
gives security results for CCA security and ciphertext pseudo-randomness.
5.1

Specification

We require that KEM.OutLen = MAC.KeyLen + STREAM.KeyLen. The key generation algorithm PKE.KeyGen is the same as KEM.KeyGen. The encryption algorithm determines PKE.Encrypt(PK , m) as follows.
1. Use KEM.Encrypt(PK ) to generate a pair (K, K).
2. Split K into bit strings KMAC of length MAC.KeyLen and KSTR of length
STREAM.KeyLen; i.e., K = KMAC || KSTR .
3. Compute M = MAC(KMAC , m).
4. Compute C = (M || m) ⊕ STREAM(KSTR , MAC.OutLen + |m|).
5. Return the ciphertext K || C.
We depict the resulting ciphertext structure with concatenation horizontally and
XOR vertically:Km

MAC(KMAC , m)
STREAM(KSTR )The decryption algorithm computes PKE.Decrypt(PK , c) as follows.
1. Abort with an error (return ⊥) if |c| < KEM.CipherLen + MAC.OutLen.
2. Split c into a part K of length KEM.CipherLen and a part C (i.e., c = K || C).
12

3. Compute
K = KEM.Decrypt(SK , K).
If this computation fails, abort with an error (return ⊥).
4. Split K into bit strings KMAC of length MAC.KeyLen and KSTR of length
STREAM.KeyLen (i.e., K = KMAC || KSTR ).
5. Compute
P = C ⊕ STREAM(KSTR , |C|).
6. Split P into a part M of length MAC.OutLen and a part m (i.e., P = M || m).
7. Computef = MAC(KMAC , m).
M
f 6= M, abort with an error (return ⊥).
If M
8. Return m as decryption result.
Let c be a ciphertext generated as PKE.Encrypt(PK , m). It is straightforward
to verify that PKE.Decrypt(SK , c) will indeed recover m if KEM is a key encapsulation mechanism according to Definition 4 and the key pair (PK , SK ) has
been generated properly. (Note that decryption step 3 cannot actually fail for
the KEM from Section 3 with valid system parameters and a valid secret key.)
In practical use for steganography, the exact length of the ciphertext to beconsidered may not always be known in advance when some postfix has been
added. In this case, multiple conceivable lengths can be tried during decryption.
Observe that many such decryption attempts can easily be combined into asingle algorithm such that KEM.Decrypt is used only once.
5.2

Security Results

We relate the security of the public-key encryption scheme PKE to the securityof the underlying primitives KEM, MAC, and STREAM.
First consider CCA security. Let A be an adversary attacking PKE in the
IND-CCA attack game (Definition 2). It can be shown that there are adversaries
A1 against KEM in a real-or-random CCA attack game, A2 against MAC, andA3 against STREAM, all having essentially the same running time as A, such
that

Forge
ROI
ROR-CCA
AdvIND-CCA
PKE,A ≤ 2 · AdvKEM,A1 + AdvMAC,A2 + AdvSTREAM,A3 .
The proof uses standard techniques (see e.g. [14]) and requires essentially nochanges for the hybrid AtE construction with a stream cipher compared withthe conventional hybrid EtA construction. We omit the details for lack of space.
Now consider ciphertext pseudo-randomness. Let A be an adversary attacking PKE in the real-or-ideal attack game (Definition 3). It can be shown that
there are adversaries A1 against KEM in a real-or-random CCA attack game,A2 against KEM in a real-or-ideal attack game, and A3 against STREAM, allhaving essentially the same running time as A, such that
ROR-CCAROI
ROI
AdvROI
PKE,A ≤ 2 · AdvKEM,A1 + AdvKEM,A2 + AdvSTREAM,A3 .
Details of the proof are given in Appendix B.
13

6Conclusions

A new variant of elliptic curve Diffie-Hellman employing a pair of curves where
each curve is a twist of the other provides a key encapsulation mechanism (KEM)with short random ciphertexts.
Such a KEM can be used for CCA-secure public-key encryption with pseudorandom ciphertexts, as needed for steganography. Our hybrid construction resembles DHIES, but uses an AtE rather than EtA approach in the interest of
provable ciphertext pseudo-randomness. In practice, the ciphertext length canbe as short as the length of the plaintext plus 243 bits (163 bits for the KEM
with elliptic curves over F2163 , 80 bits for the MAC).

References
1. Abdalla, M., Bellare, M., and Rogaway, P. DHAES: An encryption scheme
based on the Diffie-Hellman problem. Submission to IEEE P1363a. http://grouper.ieee.org/groups/1363/P1363a/Encryption.html, 1998.
2. Abdalla, M., Bellare, M., and Rogaway, P. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In Progress in Cryptology – CT-RSA 2001
(2001), D. Naccache, Ed., vol. 2020 of LNCS, pp. 143–158.
3. Ahn, L. v., and Hopper, N. Public key steganography. In Advances in Cryptology– EUROCRYPT 2004 (2004), C. Cachin and J. Camenisch, Eds., vol. 3027 of
LNCS, pp. 323–341.
4. American National Standards Institute (ANSI). Public key cryptography
for the financial services industry: The elliptic curve digital signature algorithm(ECDSA). ANSI X9.62, 1998.
5. Backes, M., and Cachin, C. Public-key steganography with active attacks. Cryptology ePrint Archive Report 2003/231 (revised 16 Feb 2004), 2004. Available fromhttp://eprint.iacr.org/.
6. Bellare, M., Canetti, R., and Krawczyk, H. Keying hash functions for message authentication. In Advances in Cryptology – CRYPTO ’96 (1996), N. Koblitz,
Ed., vol. 1109 of LNCS, pp. 1–15.
7. Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. A concrete security
treatment of symmetric encryption. In 38th Annual Symposium on Foundations ofComputer Science (FOCS ’97) (1997), IEEE Computer Society, pp. 394–403.
8. Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P. Relations amongnotions of security for public-key encryption schemes. In Advances in Cryptology– CRYPTO ’98 (1998), H. Krawczyk, Ed., vol. 1462 of LNCS, pp. 26–46.
9. Bellare, M., and Rogaway, P. Random oracles are practical: A paradigm fordesigning efficient protocols. In First Annual Conference on Computer and Communications Security (1993), ACM, pp. 62–73.
10. Blake, I. F., Seroussi, G., and Smart, N. P. Elliptic Curves in Cryptography, vol. 265 of London Mathematical Society Lecture Note Series. Cambridge
University Press, 1999.
11. Canetti, R., Goldreich, O., and Halevi, S. The random oracle methodology,
revisited. E-print cs.CR/0010019, 2000. Available from http://arXiv.org/abs/
cs/0010019.
12. Certicom Research. Standards for efficient cryptography – SEC 1: Elliptic curve
cryptography. Version 1.0, 2000. Available from http://www.secg.org/.

14

13. Certicom Research. Standards for efficient cryptography – SEC 2: Recommended elliptic curve cryptography domain parameters. Version 1.0, 2000. Available from http://www.secg.org/.
14. Cramer, R., and Shoup, V. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM Journal on
Computing. To appear. Available from http://shoup.net/papers/ (2003).
15. Diffie, W., and Hellman, M. E. New directions in cryptography. IEEE Transactions on Information Theory 22, 6 (1976), 644–654.
16. Fouquet, M., Gaudry, P., and Harley, R. Finding secure curves with the
Satoh-FGH algorithm and an early-abort strategy. In Advances in Cryptology –EUROCRYPT 2001 (2001), B. Pfitzmann, Ed., vol. 2045 of LNCS, pp. 14–29.
17. Galbraith, S., and McKee, J. The probability that the number of points onan elliptic curve over a finite field is prime. CACR Technical Report CORR 99-51,
1999. Available from http://www.cacr.math.uwaterloo.ca/techreports/1999/.
18. Goldreich, O. Foundations of Cryptography – Vol. II: Basic Applications. Cambridge University Press, 2004.
19. Goldwasser, S., and Micali, S. Probabilistic encryption. Journal of Computerand System Sciences 28 (1984), 270–299.
20. Institute of Electrical and Electronics Engineers (IEEE). IEEE standard specifications for public-key cryptography. IEEE Std 1363-2000, 2000.
21. Kaliski, Jr., B. S. A pseudo-random bit generator based on elliptic logarithms.
In Advances in Cryptology – CRYPTO ’86 (1987), A. M. Odlyzko, Ed., vol. 263
of LNCS, pp. 84–103.
22. Kaliski, Jr., B. S. One-way permutations on elliptic curves. Journal of Cryptology
3 (1991), 187–199.
23. Koblitz, N. Elliptic curve cryptosystems. Mathematics of Computation 48 (1987),
203–209.
24. Krawczyk, H., Bellare, M., and Canetti, R. HMAC: Keyed-hashing formessage authentication. RFC 2104. Available from http://www.ietf.org/rfc/
rfc2104.txt, 1997.
25. Lercier, R. Finding good random elliptic curves for cryptosystems defined overF2n . In Advances in Cryptology – EUROCRYPT ’97 (1997), W. Fumy, Ed.,
vol. 1233 of LNCS, pp. 379–392.
26. Lercier, R., and Lubicz, D. Counting points on elliptic curves over finite fieldsof small characteristic in quasi quadratic time. In Advances in Cryptology – EUROCRYPT 2003 (2003), E. Biham, Ed., vol. 2656 of LNCS, pp. 360–373.
27. Menezes, A., Okamoto, T., and Vanstone, S. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory
39 (1993), 1639–1646.
28. Miller, V. S. Use of elliptic curves in cryptography. In Advances in Cryptology –CRYPTO ’85 (1986), H. C. Williams, Ed., vol. 218 of LNCS, pp. 417–428.
29. National Institute of Standards and Technology. Recommendation forblock cipher modes of operation – methods and techniques. NIST Special Publication SP 800-38A, 2001.
30. Okamoto, T., and Pointcheval, D. A new class of problems for the security ofcryptographic schemes. In Public Key Cryptography – PKC 2001 (2001), K. Kim,
Ed., vol. 1992 of LNCS, pp. 104–118.
31. Rackoff, C. W., and Simon, D. R. Non-interactive zero-knowledge proof ofknowledge and chosen ciphertext attack. In Advances in Cryptology – CRYPTO’91 (1992), J. Feigenbaum, Ed., vol. 576 of LNCS, pp. 433–444.

1532. Shoup, V. A proposal for an ISO standard for public key encryption. Version 2.1,
December 20, 2001. http://shoup.net/papers/.
33. Watanabe, Y., Shikata, J., and Imai, H. Equivalence between semantic security
and indistinguishability against chosen ciphertext attacks. In Public Key Cryptography – PKC 2003 (2003), Y. G. Desmedt, Ed., vol. 2567 of LNCS, pp. 71–84.

A

Example Parameters

We use hexadecimal representations of octet strings and encode field elementsof F2163 as polynomials over F2 based on the reducing polynomial given as
0800000000000000000000000000000000000000C9;
see e.g. [12] for a detailed explanation. A suitable pair of elliptic curves for the
KEM in Section 3 is given byb = 05846d0fda255361606711bf7a99b0722e2ec8f76b.
This b has been generated verifiably pseudo-randomly with SHA-1 from the seedf391f2426f9ca3af80bc4537dd7224d43c1639aa.
following [4, Annex A.3.3.1] and [20, Annex A.12.6]. The curves E0,b and E1,b
have
n0 = 4 p0 = 4 · 2923003274661805836407371179614143033958162426611,
n1 = 2 p1 = 2 · 5846006549323611672814736302501978089331135490587
rational points, respectively, with both p0 and p1 prime. The curves Ea,b (F2163 )have points Ga = (xa , ya ) of order na for example for x0 = 0000. . .01 andx1 = 0000. . .02.
The above coefficient b was provided by Reynald Lercier, who applied thepoint counting algorithms described in [25] and [16] to a list of verifiably pseudorandom b values and factored the curve orders to detect suitable curve pairs. Outof the 30 000 (≈ 1632 ) choices for b examined, five had the desired properties.

B

Security Proof: Ciphertext Pseudo-Randomness

Let G0 denote the real-or-ideal attack game from Definition 3 where a distinguisher A attacks PKE. The encryption oracle stage in G0 can be expressed
as follows for PKE from Section 5.1: A submits m; the encryption oracle uses
KEM.Encrypt(PK ) to generate (Koracle , Koracle ), splits Koracle = KMAC ||KSTR , computes M = MAC(KMAC , m) and stream
 = STREAM(KSTR , MAC.OutLen + |m|),sets c0 = Koracle || (M || m) ⊕ stream , generates a uniformly random c1 with|c1 | = |c0 | and a uniformly random b ∈ {0, 1}, and finally responds with cb .
16

Let G1 be like G0 but with Koracle uniformly random (of appropriate length);G2 like G1 but with Koracle uniformly random; G3 like G2 but with stream uniformly
random. We can expose A to these different games and look at Pr Gi eb =
b . We will build adversaries A1 against KEM in a real-or-random CCA attack
game, A2 against KEM in a real-or-ideal attack game, and A3 against STREAM.
These adversaries run A and provide it with an encryption oracle by performing
the encryption oracle stage as above, using pre-generated values Koracle , Koracle ,and b.
A1 attacks KEM in a real-or-random CCA attack game (Definition 5). Firstit picks a uniform random b ∈ {0, 1} and queries its real-or-random key encapsulation oracle to obtain a pair (Koracle , Koracle ). Then it runs A (relaying PK fromits key generation oracle), playing the role of the encryption oracle. Finally, whenA outputs eb, A1 outputs 1 if eb = b and 0 otherwise. Observe that

Pr G1 eb = b − Pr G0 eb = b = AdvROR-CCA
KEM,A1(G1 corresponds to bKEM = 1, G0 to bKEM = 0).
A2 attacks KEM in a real-or-ideal attack game (Definition 6). First it generates b ∈ {0, 1} and a bit string Koracle of length KEM.OutLen uniformly at
random and queries its real-or-ideal key encapsulation oracle to obtain a bit
string Koracle . Then it runs A (relaying PK from its key generation oracle), playing the role of the encryption oracle. Finally, when A outputs eb, A2 outputs 1 if
eb = b and 0 otherwise. Observe that

Pr G2 eb = b − Pr G1 eb = b = AdvROI
KEM,A2(G2 corresponds to bKEM = 1, G1 to bKEM = 0).
A3 attacks STREAM (Definition 10). First it generates b ∈ {0, 1} and bit
strings Koracle of length KEM.OutLen and Koracle of length KEM.CipherLen uniformly at random. Then it runs A, playing the role of the key generation oracle(by using KEM.KeyGen) and the role of the encryption oracle. Finally, when A
outputs eb, A2 outputs 1 if eb = b and 0 otherwise. Observe that
Pr G3 eb = b − Pr G2 eb = b = AdvROI
STREAM,A3 1(G3 corresponds to bSTR = 1, G2 to bSTR = 0) and clearly Pr G3 eb = b = .
2
1
Since b is uniformly random, by definition we have AdvROI
=
2
·
−
Pr
G0
PKE,A
2
e
[b = b] ; putting all together, we obtain
X 




e
e
AdvROI
=
2
·
Pr
b
=
b
−
Pr
b
=
b
Gi
Gi−1
PKE,A
1≤i≤3


ROI
ROI
≤ 2 · AdvROR-CCA
KEM,A1 + AdvKEM,A2 + AdvSTREAM,A3 .

17