This is the full version of the extended abstract which appears in

the 9th International Conference on Theory and Practice in Public Key Cryptography – PKC 2006
(24–26 april 2006, New York, USA)
M. Yung Ed. Springer-Verlag, LNCS 3958, pages 91–104.

Encoding-Free ElGamal Encryption

Without Random Oracles

Benoı̂t Chevallier-Mames1,2 , Pascal Paillier3 , and David Pointcheval2

1
Gemplus, Security Technology Department,
La Vigie, Avenue du Jujubier, ZI Athélia IV,
F-13705 La Ciotat Cedex, France
benoit.chevallier-mames@gemplus.com
2
École Normale Supérieure,
Département d’Informatique, 45 rue d’Ulm,
F-75230 Paris 05, France
david.pointcheval@ens.fr
3
Gemplus, Security Technology Department,
34 rue Guynemer,
F-92447 Issy-les-Moulineaux, France
pascal.paillier@gemplus.com

Abstract. ElGamal encryption is the most extensively used alternative to RSA. Easily adaptable to
many kinds of cryptographic groups, ElGamal encryption enjoys homomorphic properties while remaining
semantically secure providing that the DDH assumption holds on the chosen group. Its practical use,
unfortunately, is intricate: plaintexts have to be encoded into group elements before encryption, thereby
requiring awkward and ad hoc conversions which strongly limit the number of plaintext bits or may partially
destroy homomorphicity. Getting rid of the group encoding (e.g., with a hash function) is known to ruin
the standard model security of the system.
This paper introduces a new alternative to group encodings and hash functions which remains fully compat-
ible with standard model security properties. Partially homomorphic in customizable ways, our encryptions
are comparable to plain ElGamal in efficiency, and boost the encryption ratio from about 13 for classical
parameters to the optimal value of 2.

Keywords: Cryptography, ElGamal encryption, Diffie-Hellman, Residuosity classes,

Group encodings.

1 Introduction
Since the discovery of public-key cryptography [7], very few practical cryptosystems have been
suggested that sustain a strong evidence of security in the standard model.

Factoring vs. Discrete-Log Encryption Schemes. In brief, there exist two main fam-
ilies of provably secure cryptosystems. The first family relates to integer factoring (Rabin [21],
RSA [22], Naccache-Stern [16], Okamoto-Uchiyama [18], Paillier [19]). The others are based on
the discrete logarithm or the Diffie-Hellman problems. Within this family, ElGamal encryp-
tion [8] is certainly the most extensively used for cryptographic applications.
Cryptosystems belonging to the first family support the encryption of messages without
prior formatting in the sense that any fixed-size integer is a proper input of the encryption
algorithm. However, all known discrete-log-based encryption schemes which feature standard-
model security such as Cramer-Shoup encryption [5], are restricted to encrypt group elements.
This drawback, often overlooked, seems inherent to the nature of these cryptosystems. Vari-
ants and alternate designs either drastically degrade bandwidth and efficiency, or imply extra
(and possibly questionable) assumptions in their security analysis.

c IACR 2006.

 Historically, the first designs suggested to work in the largest possible subgroup over which
the encryption takes place. By virtue of the fact that invoking the DDH assumption requires to
use a prime order subgroup (or at least a subgroup which order does not have small factors), the
subgroup of quadratic residues in Z∗p appears as the best choice in this respect. However, one
then has to perform operations in the group of order q = (p−1)/2 which implies exponentiations
with large exponents.
A standard lesser evil consists in applying a hash function to the Diffie-Hellman session key
before masking the plaintext. The price to pay then amounts to making stronger assumptions,
such as the Hash Diffie-Hellman assumption [1, 12] or the random oracle model [2].

Our Contributions. This paper introduces a novel encryption technique that does not re-
quire message encoding before encryption and enjoys strong security against chosen-plaintext
attacks without any extra assumption i.e., the security of our cryptosystems stands in the stan-
dard model. One-wayness and indistinguishability rely on the use of new specifically introduced
integer-theoretic problems which we call the (computational/decision) Class Diffie-Hellman
problems (CCDH, resp. DCDH).
Most interestingly, we provide a proof that CCDH is in fact equivalent to CDH, meaning that
the one-wayness of our schemes is identical to the one of ElGamal encryption while providing an
optimal encryption ratio of 2 instead of 13. The study of DCDH, however, remains a challenging
open problem.
In terms of performance, the encryption and decryption procedures are equivalent to respec-
tively 6 and 5 exponentiations in a subgroup of prime order q with e.g., log q = 160. No group
encoding is required before encryption. Finally the ciphertext size is identical to an ElGamal
ciphertext, although the encryption ratio reaches its optimum level: one may encrypt 1024-bit
strings into a 2048-bit ciphertext while still relying on a 160-bit subgroup.
Our cryptosystems also provide a weak form of additive or multiplicative homomorphic
property, in the sense that one can add a constant or multiply by a constant an encrypted value.
However, one cannot re-randomize encryptions. This amounts to say that if two ciphertexts were
created using this property (with the same random coins), every one may recover the difference
or the ratio between the plaintexts, without any private material.
Our encryption schemes are based on the mathematical properties of integers modulo p2
where p is a prime number. Interestingly, one would note that homomorphicity has often been
achieved by relying on the properties of special moduli: Okamoto and Uchiyama [18] use prop-
erties of integers modulo n = p2 q, while Paillier [19] and Bresson, Catalano and Pointcheval [3]
rather employ moduli of the form n2 . Damgård and Jurik [6] use operations modulo ns for
s > 2. In all of these schemes, however, various forms of RSA moduli constitute basic scheme
parameters and the trapdoor technique relates to factoring rather than to discrete-log problems.
Our work, by opposition, makes exclusive use of prime-order groups.

Outline of the paper. Our work is divided as follows. Section 2 reviews standard definitions
and security notions for public-key encryption. Section 3 briefly recalls ElGamal encryption and
variants thereof. In Section 4, we introduce the Class Diffie-Hellman problems, then proceed to
define and comment on our encryption schemes. Their security is further discussed in Section 5.
We finally provide extensions to Zpk in Section 6.

2
2 Preliminaries
2.1 Public-Key Encryption
We identify a public-key encryption scheme S to a tuple of probabilistic algorithms S = (K, E, D)
defined as follows:

Key Generation. Given a security parameter k, K(1k ) produces a pair (pk, sk) of public and
private keys.

Encryption. Given a message m and a public key pk, Epk (m) produces a ciphertext c. If the
procedure is probabilistic, we write c = Epk (m; r) where r denotes the randomness used by E.

Decryption. Given a ciphertext c and a private key sk, Dsk (c) returns a plaintext m or
possibly ⊥ if the ciphertexts is invalid.

2.2 Security Notions for Encryption Schemes

One-Wayness. A most important security notion that one would expect from an encryption
scheme to fulfil is the property of one-wayness (OW): an attacker should not be able to recover
the plaintext matching a given ciphertext. We capture this notion more formally by saying that
for any adversary A, succeeding in inverting the effects of E on a ciphertext c should occur with
negligible probability. A is said to (k, ε, τ )-break OW when
k
Succow
S (A) = Pr [(pk, sk) ← K(1 ) : A(pk, Epk (m; r)) = m] ≥ ε ,
m,r

where the probability is taken over the random coins of the experiment and the ones of the
adversary, and A halts after τ elementary steps. An encryption scheme is said to be one-way if
no probabilistic algorithm (k, ε, τ )-breaks OW for τ ≤ poly (k) and ε ≥ 1/poly (k).

Semantic Security. The notion of semantic security (IND) [13], a.k.a., indistinguishability
of encryptions captures a strong notion of privacy. Here, the attacker should not learn any
information whatsoever about a plaintext given its encryption. The adversary A = (A 1 , A2 ) is
said to (k, ε, τ )-break IND when

(pk, sk) ← K(1k ), (m0 , m1 , s) ← A1 (pk),

 
ind
AdvS (A) = 2 × Pr − 1 ≥ ε,
b,r c = Epk (mb ; r) : A2 (m0 , m1 , s, c) = b

where again the probability is taken over the random coins of the experiment as well as the ones
the adversary. A must run in at most τ steps and it is imposed that |m0 | = |m1 |. An encryption
scheme is said to be semantically secure or indistinguishable if no probabilistic algorithm can
(k, ε, τ )-break IND for τ ≤ poly (k) and ε ≥ 1/poly (k).

2.3 Computational Assumptions

We now briefly recall the definition of the discrete-log and related problems needed for the sake
of this work. In what follows, G denotes an abelian group (denoted multiplicatively) of prime
order q. We also consider a generator g of G = hgi.

3
Definition 1 (Discrete Logarithm – DL). Given g x ∈ G where x ← Zq , compute x.
Definition 2 (Computational Diffie-Hellman – CDH). Given g x ∈ G and g y ∈ G for
x, y ← Zq , compute g xy ∈ G.
Definition 3 (Decision Diffie-Hellman – DDH). Let us consider the two distributions D =
(g x , g y , g xy ) and R = (g x , g x, g z ) for randomly distributed x, y, z ← Zq . Distinguish D from R.
It is easily seen that DDH ⇐ CDH ⇐ DL where ⇐ denotes polynomial reduction between
computational problems. In most cryptographic applications, the structure of the group G is
chosen in such a way that these three computational problems seem intractable. A typical
example is to choose G ⊆ F∗p where q divides (p − 1) where classically, p is a 1024-bit prime
and q a 160-bit prime. Another widely used family of groups is elliptic curves over large prime
fields [15, 14].

3 The ElGamal Cryptosystem

ElGamal encryption was introduced by T. ElGamal in 1985 [8]. The algebraic framework re-
quires a cryptographic group G of order q given with some generator g.
One generates a public-private key pair by randomly selecting x ← Zq and computing
y = g x . The public key is then y while the private key is x. In order to encrypt a message m,
one randomly selects r ← Zq and computes u = g r and v = y r m. The ciphertext is c = (u, v).
Using the private key x, the ciphertext c = (u, v) can be decrypted as m = v · u−x .
The key point here resides in the definition of the message space M. As defined originally in
[8], the group G was chosen to be the set of integers modulo a large prime p (i.e., G = Zp ), q was
set to p − 1 and M was identified to Z∗p . Unfortunately, using this definition, the cryptosystem
is not indistinguishable: given a ciphertext c = (u, v), an attacker can well decide with non
negligible probability whether c encrypts a given message m0 . To this end, the attacker computes
v 0 = v · m−1
0 , and then computes a = u
(p−1)/2
and b = v 0(p−1)/2 . If only one of the elements a or
b is equal to 1, the adversary knows that c does not encrypt m0 . This simple attack actually
checks the parity of the logarithms of u and v 0 with respect to g and y respectively: if c = (u, v)
encrypts m0 , it is needed that these parities be identical.
This attack against indistinguishability shows that the order of the group G must be rela-
tively prime to any small integer (the attack described just above can be extended trivially for
any small divisor of q), and most preferably, the order of group G must be chosen to be prime.
Description. Unfortunately, the above constraint translates into a restriction on the message
space M: it has to be embedded into the group G. Hence, before encryption takes place, the
message must be encoded into a group element, and this group encoding must be efficiently
invertible in order to allow the original message to be recovered during the decryption process.
Such an encoding may be time-consuming, and may also partially or totally destroy the inherent
homomorphic property of the system. Also, using a group encoding remains incompatible with
the optimization which consists in working in a small subgroup of Z∗p of prime order q where q
is a 160-bit prime, a setting in which group exponentiations are much faster.
Set up: Let p be an `p -bit prime and q an `q -bit prime so that q divides (p − 1). Let G be the
subgroup of Z∗p of order q, and g be a generator of G. Let Ω be a one-to-one encoding map
from Zq onto G.

4
Key generation: The private key is x ← Zq . The corresponding public key is y = g x .
Encryption: To encrypt a message m ∈ Zq , one encodes m by computing ω = Ω(m), randomly
selects r ← Zq and computes (u, v) = (g r , y r ω). The ciphertext is c = (u, v).
Decryption: To decrypt a ciphertext c = (u, v), one computes ω = v · u−x and recovers the
original plaintext m = Ω −1 (ω).
This cryptosystem is known to be one-way under the CDH assumption, and indistinguisha-
bility holds under the DDH assumption. These security notions are reached in the context of
chosen-plaintext attacks, in the standard model.

3.1 The Hash-ElGamal Cryptosystem

In order to overcome the issue of group encoding, a hash variant of ElGamal encryption was
suggested.
Set up: Let p be an `p -bit prime and q an `q -bit prime so that q divides (p − 1). Let G be
the subgroup of order q of Z∗p , and g be a generator of G. Let H : G → {0, 1}`m be a hash
function.
Key generation: The private key is again x ← Zq . The corresponding public key is y = g x .
Encryption: To encrypt a message m ∈ {0, 1}`m , one randomly selects r ← Zq and computes
(u, v) = (g r , H(y r ) ⊕ m). The ciphertext is c = (u, v).
Decryption: To decrypt a ciphertext c = (u, v), one computes m = H(ux ) ⊕ v.
This cryptosystem features one-wayness and indistinguishability under chosen plaintext
attacks under the sole CDH assumption. The security proof, however, stands in the random
oracle model. Alternatively, under the DDH assumption, one can apply a randomness extractor
in place of the random oracle, in order to generate a truly random mask. But this either requires
large groups, or drastically reduces the size of the mask [4].

4 Encoding-Free ElGamal Encryption

We now proceed to describe our new technique for encoding-free ElGamal encryption. Our
cryptosystems enjoy performances similar to plain ElGamal but do not require group encoding,
nor randomness extractors. Furthermore, their security holds in the standard model under new
intractability assumptions that we introduce below. We start by providing definitions as well
as the mathematical facts underlying our proposal.

4.1 The Class Function

Let p and q be prime numbers such that q | p − 1. Let g be an integer of order pq modulo p2 and
G = hgi the group formed by all elements of order pq modulo p2 . Hence Gp = hg mod pi is the
subgroup of order q in Z∗p . By the Chinese Remainder Theorem, there is a canonical mapping
between Zp × Zq and Zpq . For any x ∈ Zp and y ∈ Zq , hx, yi stands for the unique integer
modulo pq such that hx, yi = x mod p and hx, yi = y mod q.
Definition 4 (Class of an element of G). Each and every element w of G can be written
as w = g hx, yi mod p2 for a unique x ∈ Zp and a unique y ∈ Zq . The integer x = [[w]] is said to
be the class of w with respect to g.

5
 It is easily seen that if w = g hx, yi mod p2 , then w = g y mod p. In other words, y is the
discrete log of w mod p with respect to g mod p. This means that, unless extracting discrete
logs over Gp is easy, y cannot be easily computed from w. It appears, however, that computing
the class of elements of G can be done publicly and efficiently.

Lemma 5. Define over G the function L(w) = (w q −1 mod p2 )/p. The class of w = g hx, yi mod
p2 can be computed as x = L(w)L(g)−1 mod p.

This property is well-known and we refer the reader to [18, 19] for a proper proof. Now let a
be an integer modulo q and consider w = g a mod p. Since w can also be viewed as an element
of G, there exist integers x, y such that w = g hx, yi mod p2 . However, g hx, yi = g y mod p and
therefore y = a by unicity of y. It appears that the value of x can be recovered as a function of
a:

Lemma 6. Let us define

g a mod p2 − g a mod p
Upper(g a ) =
p

and
q Upper(g a )
∆(g a ) = · mod p .
L(g) ga
Then
[[g a mod p]] = a − ∆(g a ) mod p .

Proof. Noting g a = A + p · Ā mod p2 for A, Ā ∈ Zp with A 6= 0, and using the identity

1 + p · L(g) = g hq, 0i mod p2 , we have
 
Ā Ā q Ā
a
g =A 1+p· = A (1 + p) A = A · g h L(g) A , 0i mod p2 .
A

Taking the class of the left and right terms, we get a · [[g]] = [[A]] + ∆(g a ) which leads to the
above using the trivial fact that [[g]] = 1. t
u

Lemma 7. The mapping a → [[g a mod p]] is random self-reducible.

Proof. Assume we want [[A]] for some given A = g a mod p. We make use of the fact that for
any r ∈ Zq , we have

[[Ar mod p]] = [[Ar mod p2 ]] − ∆(Ar ) = r · [[A]] − ∆(Ar ) mod p .

If r is drawn uniformly at random from Z∗q , Ar mod p is a random element of Gp . Knowing

[[Ar mod p]] and r, [[A]] is easily recovered as

[[A]] = r −1 ([[Ar mod p]] + ∆(Ar )) mod p .

t
u

6
4.2 The Class Diffie-Hellman Problems
We now turn to defining the computational problems over which we base the encryption schemes
suggested in the forthcoming sections.
Definition 8 (Computational Class Diffie-Hellman). Let Gp = hg mod pi be defined as
above. Given group elements g a mod p and g b mod p, compute [[g ab mod p]].
Definition 9 (Decision Class Diffie-Hellman). Distinguish the two distributions D =
(g a mod p, g b mod p, [[g ab mod p]]) and R = (g a mod p, g b mod p, z) for a, b ← Zq and z ← Zp .
We denote these problems CCDH and DCDH throughout the paper. As we shall now see,
CCDH is in fact closely related to CDH.
Theorem 10. CCDH and CDH are equivalent.
Proof. [CCDH ⇐ CDH]. Assume we are given a probabilistic algorithm A such that A(g a mod
p, g b mod p) outputs g ab mod p with probability ε and time bound τ , the success probability
being taken over the random variables of A and the random selections a, b ← Zq . Given A, B ←
Gp , we run A(A, B) to get DH(A, B) and deduce [[DH(A, B)]], thereby succeeding in solving
CCDH with probability ε and no more than τ + poly (log p) steps.
[CDH ⇐ CCDH]. Assume there exists a probabilistic algorithm A which solves CCDH. By virtue
of Lemma 7, we may assume that the input distribution of A need not be uniform and that
the success probability of A is overwhelming. We build a reduction algorithm B that computes
C = DH(A, B) for arbitrary elements A, B ← Gp . B first runs A(A, B) to get [[C]]. B now sets
A0 = Ag mod p and runs A again to get [[C 0 ]] = A(A0 , B) where C 0 = DH(A0 , B) = BC mod p.
We must have

[[C 0 ]] = [[BC mod p]] = [[BC mod p2 ]] − ∆(BC) = [[B]] + [[C]] − ∆(BC)

wherefrom ∆(BC) = [[B]] + [[C]] − [[C 0 ]] mod p. Since

 
0 0 L(g)
BC = C + p · Upper(BC) = C 1 + p · · ∆(BC) mod p2 ,
q
B now remains with the problem of finding a solution to the modular equation
 
C −1 L(g)  0
=B 1+p· · [[B]] + [[C]] − [[C ]] mod p2 (1)
C0 q
where the unknowns are C, C 0 ∈ Zp . Setting the right-hand term to µ < p2 , B applies the
extended Euclidean algorithm to µ and p2 in order to find small solutions C, C 0 < p satisfying
C/C 0 = µ mod p2 . The validity of C is easily checked by making sure that C 0 C −1 mod p is
equal to B. This stage finishes with probability one in time bounded by log 3 p resulting in that
C = DH(A, B) is found with no more than two calls to A and polynomial extra time. t
u
So far, the study of DCDH remains a challenging open question. In particular, the relations
between DCDH and DDH are somewhat unclear. Although we do not provide evidence of that
fact, we suspect these two problems to be extremely closely connected. We will make the
assumption that DCDH is intractable throughout the rest of this paper.

7
4.3 Encoding-Free Additive Encryption

As discussed above, our goal is to render ElGamal encryption truly practical by getting rid of
intricate group encoding mechanisms while maintaining a security level in the standard model
(in opposition to Hash-ElGamal encryption for instance). The basic idea, instead of embedding
the message into a group element, consists in converting the session key output by the Diffie-
Hellman exchange1 into an integer modulo p using the class function.

Set up: Let p an `p -bit prime and q an `q -bit prime divisor of p − 1. Let g be a generator of
the subgroup Gp of order q of Z∗p .
Key generation: The private key is a random number x ∈ Zq . The corresponding public key
is y = g x mod p.
Encryption: To encrypt a message m ∈ Zp , one picks a random r ∈ Zq and computes u =
g r mod p and v = [[y r mod p]] + m mod p. The ciphertext is c = (u, v).
Decryption: To decrypt a ciphertext c = (u, v), one simply computes m = v−[[ux mod p]] mod
p.

4.4 Encoding-Free Multiplicative Encryption

Since the message and the class of g xy mod p are both integers modulo p, encryption may also
be performed using modular multiplication instead of modular addition.

Set up: Let p an `p -bit prime and q an `q -bit prime divisor of p − 1. Let g be a generator of
the subgroup Gp of order q of Z∗p .
Key generation: The private key is a random number x ∈ Zq . The corresponding public key
is y = g x mod p.
Encryption: To encrypt a message m ∈ Z∗p , one picks a random r ∈ Zq and computes u =
g r mod p and v = [[y r mod p]] · m mod p. The ciphertext is c = (u, v).
Decryption: To decrypt a ciphertext c = (u, v), one simply computes m = v[[ux mod p]]−1 mod
p.

4.5 Properties of our encryption schemes

No conversion. Our encryption schemes do not require any conversion: the message space is
really the ring Zp (or the multiplicative subgroup Z∗p in the multiplicative version.) Therefore,
any string of bitlength lesser than k, where p > 2k , can be encrypted directly. This is a strong
property since we may have q much smaller than p without impact on the encryption and
decryption procedures.

Efficiency. It is easily seen that ciphertexts have a similar size as with ElGamal encryption.
The bandwidth is exactly 21 (i.e., the encryption ratio is exactly 2), by opposition to ElGamal
q
encryption for which the bandwidth is 2p . We recall that for p = 1024 and q = 160, the
1
bandwidth of ElGamal is close to 13 ).
1
ElGamal encryption can indeed be viewed as a Diffie-Hellman key exchange where the publication of the public-key y
plays the role of the first pass.

8
 From the viewpoint of computational performances, it appears that in addition to the two
exponentiations that are inherent to ElGamal encryption, we require an additional exponenti-
ation in Zp2 with a `q -bit exponent. This amounts to four times the execution time of the same
exponentiation in Zp . Totaling everything, we need 6 exponentiations vs. 2 exponentiations in
ElGamal. However, no encoding is needed, which are basically done with exponentiations.
When decrypting an ElGamal encryption, an exponentiation of `q bits in Zp is required, as
well as a group decoding. In our schemes, however, we require an exponentiation in Zp2 with an
exponent of size `q and another exponentiation with an exponent of size `q . Finally, we require
5 exponentiations to be compared to the single exponentiation needed in ElGamal. Once again,
no inverse of the encoding is needed.

Multiplicative or Additive Homomorphism. Last but not least, our schemes feature a
partial homomorphic property over the ring of integers modulo p. We mean for instance that one
could add some constant to an encrypted plaintext without needing the private key. Although
these properties do forbid resistance against chosen-ciphertext attacks, these are perceived as
most desirable in many cryptographic applications such as electronic voting, and we expect to
see applications of our work in this regard. However, our schemes do not allow to re-randomize
a ciphertext per se.

5 Security Analysis

We now proceed to assessing the security of our schemes. Obviously, one cannot prevent chosen-
ciphertext attacks due to the partial malleability described above. However, generic conver-
sions do exist to convert CPA-secure schemes into CCA-secure schemes (in the random oracle
model)[9–11, 20, 17] when the context of use demands CCA security.

One-Wayness. Focusing on the additive version of our encoding-free encryption scheme, we

state:

Theorem 11. Let A be an adversary which can invert our cryptosystem with success probability
ε under a chosen-plaintext attack within time τ . Then the Computational Class Diffie-Hellman
problem can be solved with success probability ε within time similar to τ .

Proof. Given a Computational Class Diffie-Hellman instance (g, y = g x mod p, w = g s mod p),
our goal is to compute z = [[g xs mod p]]. To this aim, we use the OW − CPA attacker A against
our scheme, where g is the public generator, and set the public key to y. We submit to A the
ciphertext (u, v) = (w, a) for a randomly chosen a ∈ Zp . This is a truly random ciphertext of
a random message, for which we have set r = s, and so A succeeds with probability ε to find
the corresponding plaintext m. If A succeeds, we thus learn [[g xs mod p]], our expected result
z = a − m mod p. t
u

It is easily seen that the same theorem holds for the multiplicative encryption scheme. One
would simply note that the message space in this latter version is Z∗p , and not Zp , as one needs
to compute the inverse m−1 mod p to deduce z from a and m.

9
Indistinguishability. About indistinguishability, we state a similar result:

Theorem 12. Let A be an adversary breaking the indistinguishability of our cryptosystem with
advantage ε under a chosen-plaintext attack within time τ . Then the Decisional Class Diffie-
Hellman problem can be solved with advantage ε/2 within time similar to τ .

Proof. Assume we are given an instance (g, y = g x mod p, w = g s mod p, z) of the Decisional
Class Diffie-Hellman problem in Zp , and want to decide whether z is randomly selected in Zp
or whether z = [[g xs mod p]].
As above, we make use an IND − CPA attacker A against our scheme, where g is the public
generator, and set the public key to y. We let the adversary to choose two messages m 0 and
m1 , pick a random bit b, and encrypt mb as (u, v) = (w, z + mb mod p). Finally, we send this
ciphertext to the A as the challenge ciphertext.
Clearly, if z = [[g xs mod p]], c is a valid ciphertext of mb , where we set r = s, and consequently
the attacker A can guess the value b with advantage ε. On the contrary, if z is a random element
of Zp , z 0 = z + mb mod p is also a random element of Zp , thereby making the ciphertext
independent from the message mb . The advantage of A is then necessarily zero.
Hence, to solve our decisional problem, we reply True if the guess of A is correct, otherwise
a random bit is replied. Our reduction solves DCDH with advantage at least ε/2. t
u

6 Generalization to Zpk

As the scheme suggested by Damgård-Jurik [6] is a generalization of Paillier encryption, we

may generalize our systems using Zpk for any integer k > 2. For any integer k > 2, we
q k
denote naturally Lk the function defined by X 7→ X −1 pmod p , and let the class of w as
[[w]]k = Lk (w)Lk (g)−1 mod pk−1 . Then the generalization of our technique to Zpk is as follows:

Set up: Let p an `p -bit prime and q an `q -bit prime divisor of (p − 1). Let g be a generator of
the subgroup Gp of order q of Zp .
Key generation: The private key is a random number x ∈ Zq . The corresponding public key
is y = g x mod p.
Encryption: To encrypt a message m ∈ Zpk−1 , one picks a random r ∈ Zq and computes
u = g r mod p and v = [[y r mod p]]k + m mod pk−1 . The ciphertext is c = (u, v).
Decryption: To decrypt a ciphertext c = (u, v), one simply computes

m = v − [[ux mod p]]k mod pk−1 .

We may equally well use modular multiplication instead of addition of course. In these
cryptosystems, the encryption bandwidth is equal to k−1 k
, and therefore can be made nearly
optimal. Furthermore, the property of partial malleability is still a feature of the scheme.
Regarding security, one refer the reader to [6] for proofs that the generalizations of CCDH and
DCDH are equivalent to their version for k = 2. We then adapt the proof of the scheme in
Zp2 to show that the one-wayness and that indistinguishability of the generalized schemes are
identical to the extended versions of CCDH and DCDH.

10
7 Conclusion and Open Issues
In this paper, we have proposed new cryptosystems based on new computational problems
related to the Diffie-Hellman problems. Encryption does not require messages to be converted
into group elements by opposition to all known discrete-log-based cryptosystem proven secure
in the standard model.
Our cryptosystems feature a better encryption ratio (decreased by a factor 6.5 for common
parameters), an identical ciphertext size, and remain comparable in speed with ElGamal en-
cryption. Their security in the standard model under chosen-plaintext attacks is based on the
CDH assumption for one-wayness, and on the assumption that the Decision Class Diffie-Hellman
for indistinguishability.
Our encryption schemes are partially homomorphic, either additively or multiplicatively.
To the best of our knowledge, this gives the only example of an additive encryption (even if
partial) featuring standard-model security in the discrete-log setting.
An open research area would be to find a discrete-log-based cryptosystem that would provide
a fully additive or multiplicative homomorphism. Another independent but challenging topic
would be to provide a more accurate study on the connections between DCDH and DDH.

Acknowledgements
The first author would like to thank Jean-François Dhem and Philippe Proust, as well as his
colleague Eric Brier for fruitful and enjoying discussions about the difficulty of the DCDH
problem.
This work was funded in part by the European project Ecrypt and in part by the French
RNRT project Crypto++ .

References
1. M. Abdalla, M. Bellare, and P. Rogaway. DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem.
Submission to IEEE P1363a. September 1998.
Available from http://grouper.ieee.org/groups/1363/.
2. M. Bellare and P. Rogaway. Optimal Asymmetric Encryption – How to Encrypt with RSA. In Eurocrypt ’94, LNCS
950, pages 92–111. Springer-Verlag, Berlin, 1995.
3. E. Bresson, D. Catalano, and D. Pointcheval. A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption
Mechanism and its Applications. In Asiacrypt ’03, LNCS 2894, pages 37–54. Springer-Verlag, Berlin, 2003.
4. O. Chevassut, P.-A. Fouque, P. Gaudry, and D. Pointcheval. The Twist-Augmented Technique for Key Exchange.
In PKC ’06, LNCS. Springer-Verlag, Berlin, 2006.
5. R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext
Attack. In Crypto ’98, LNCS 1462, pages 13–25. Springer-Verlag, Berlin, 1998.
6. I. Damgård and M. Jurik. A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic
Public-Key System. In PKC ’01, LNCS 1992, pages 119–137. Springer-Verlag, Berlin, 2001.
7. W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT–
22(6):644–654, November 1976.
8. T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions
on Information Theory, IT–31(4):469–472, July 1985.
9. E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. In PKC
’99, LNCS 1560, pages 53–68. Springer-Verlag, Berlin, 1999.
10. E. Fujisaki and T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Crypto ’99,
LNCS 1666, pages 537–554. Springer-Verlag, Berlin, 1999.
11. E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. IEICE
Transaction of Fundamentals of Electronic Communications and Computer Science, E83-A(1):24–32, January 2000.

11
12. R. Gennaro, H. Krawczyk, and T. Rabin. Secure Hashed Diffie-Hellman over Non-DDH Groups. In Eurocrypt ’04,
LNCS 3027, pages 361–381. Springer-Verlag, Berlin, 2004.
13. S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28:270–299, 1984.
14. N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177):203–209, January 1987.
15. V. Miller. Uses of Elliptic Curves in Cryptography. In Crypto ’85, LNCS 218, pages 417–426. Springer-Verlag,
Berlin, 1986.
16. D. Naccache and J. Stern. A New Public-Key Cryptosystem. In Eurocrypt ’97, LNCS 1233, pages 27–36. Springer-
Verlag, Berlin, 1997.
17. T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In CT
– RSA ’01, LNCS 2020, pages 159–175. Springer-Verlag, Berlin, 2001.
18. T. Okamoto and S. Uchiyama. A New Public Key Cryptosystem as Secure as Factoring. In Eurocrypt ’98, LNCS
1403, pages 308–318. Springer-Verlag, Berlin, 1998.
19. P. Paillier. Public-Key Cryptosystems Based on Composite-Degree Residuosity Classes. In Eurocrypt ’99, LNCS
1592, pages 223–238. Springer-Verlag, Berlin, 1999.
20. D. Pointcheval. Chosen-Ciphertext Security for any One-Way Cryptosystem. In PKC ’00, LNCS 1751, pages 129–146.
Springer-Verlag, Berlin, 2000.
21. M. O. Rabin. Digitalized Signatures and Public Key Functions as Intractible as Factorization. Technical Report
MIT/LCS/TR-212, Massachusetts Institute of Technology – Laboratory for Computer Science, January 1979.
22. R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems.
Communications of the ACM, 21(2):120–126, February 1978.

12