As a consequence, the decryption function associated to EG,k,g will be a surjective

morphism from (G, —) to (Z/kZ, +), and a cryptosystem based on the EG,k,g

primitive will be additively homomorphic. As the scheme is homomorphic, it

also enjoys the “self-blinding” property: given c an encryption of m, one can

produce another valid ciphertext c of m by computing c := cρ , where ρ is a

random element of Gk .

Private Key and Decryption Algorithm. The integer » is a trapdoor for

the EG,k,g function. Let c ← EG,k,g (m). There exists an element ρ ∈ Gk such

that c = g m ρ. According to Theorem 1, 3., c» = g m» . Thanks to the public

algorithm for the discrete logarithm problem in g , we can recover m» in the

ring Z/kZ, and them m, as » and k are coprime.

One-Wayness. Let us de¬ne a new computational problem.

De¬nition 2. Given c an element of G we will call the residuosity class of

degree k of c the element m of Z/kZ such that m = log π(g) π(c) . We will

denote Class G,k,g , the problem of computing the residuosity class of degree k of

elements of G.

1

This condition is technical, in order to prove the equivalence in Theorem 3. We will

see that in practice, (cf. section 4), given G and k, it will be easy to ¬nd an element

of order k in G.

96 G. Castagnos

A scheme built from the EG,k,g function will be one-way if and only if the

Class G,k,g problem is hard. It is easy to see that this problem is random self-

reducible (so all the instances of the problem have the same complexity) and does

not depend of the choice of the element g of order k, thanks to the properties of

the discrete logarithm.

In the decryption algorithm, we have seen that one can decrypt an encryption

c = g m ρ of m thanks to the knowledge of ». It is also possible to decrypt c by

computing the element x of G such that xk ≡ c (mod G» ). Note that x is indeed

unique modulo G» = g , the subgroup of k th roots of unity. As

m = log π(g) π(c) = log π(g) π(c/xk ) ,

and as c/xk is an element of G» = g , one can recover m by computing the

discrete logarithm of c/xk to base g in g . As a consequence of the existence

of this decryption process, we de¬ne another computational problem in order to

analyse the Class G,k,g problem.

De¬nition 3. We will denote C“RSA G,k , the following problem: Given c an

element of G, ¬nd x such that xk ≡ c (mod G» ).

Remark 1. If one knows how to manipulate the elements of G/G» and to lift

them in G, the C“RSA G,k problem is equivalent to the problem of the local

inversion of the automorphism x ’ xk of G/G» , which is a generalization of the

RSA function (G/G» has order » which is prime to the exponent k).

If one knows », i. e., the order of G, one can solve the C“RSA G,k problem: given

c ∈ G, the element

’1

x := ck mod »

veri¬es xk ≡ c (mod G» ). As a consequence, we can state the following theorem

which generalizes Theorem 1 and 2 of [Pai99].

Theorem 2. Let G be a ¬nite multiplicative abelian group, k a nonnegative

integer such that k divides |G| and that k and |G| /k are coprime, and let g be

an element of G of order k. We have the following reductions:

P P

Class G,k,g ⇐= C“RSA G,k § Dlog ⇐= Order G § Dlog .

g g

where Dlog g denotes the discrete logarithm problem in g and Order G the

problem of computing |G|.

Remark 2. The problem Dlog g appears in the previous theorem for complete-

ness, but in practice, as we said earlier, we will hope that this problem is easy

in order to be able to decrypt e¬ciently.

Semantic Security

Theorem 3. Let G be a ¬nite multiplicative abelian group, k a nonnegative

integer such that k divides |G| and that k and |G| /k are coprime, and let g be

Two Generic Constructions of Probabilistic Cryptosystems 97

an element of G of order k. An encryption scheme built from the EG,k,g primitive

is semantically secure against Chosen-Plaintext Attacks if and only there exists

no polynomial algorithm to solve the decision residuosity problem of degree k in

G.

Proof. To prove that a scheme is semantically secure, one can use the “real or

random property”: i. e., prove that no polynomial time algorithm can distinguish

an encryption of a chosen message, m, from an encryption of a random message.

In our construction, an encryption of a random message is a random element of

G. So we have to distinguish a random element of G from an encryption of m.

As the scheme is homomorphic, this is equivalent to distinguish encryption of 0

in G, that is an element of Gk , in G.

Generation of Random Elements of Gk . To generate random elements of

Gk , one can just take at random elements of G and raise them to the power of k.

If one can work in the quotient group G/G» and lift the elements of this group

in G, one can also use the isomorphism G/G» ’ Gk , x ’ xk . The encryption

function becomes:

∼

Z/kZ — G/G» ’’ G

EG,k,g :

(m , ρ) ’’ g m ρk

It is trivial to see that EG,k,g is a group isomorphism.

Remark 3. If one can not generate random elements of G or random elements

of G/G» , a solution to generate elements of Gk is to publish an element ρ of

Gk of high order and to generate others k th powers by raising ρ to a random

power. Note that in this case, the semantic security of the scheme relies on a

slightly di¬erent problem: the decision problem of distinguishing the elements of

ρ in G.

IND-CCA2 Variant in the Standard Model. The system of Paillier, gener-

alized by the previous construction, has been used in [CS02] to build an IND-

CCA2 cryptosystem in the standard security model by an application of a general

framework built from a subset membership problem and some projective hash

families. Our construction with the decision residuosity problem can be easily

adapted to ¬t the framework of [CS02] with only one extra hypothesis. We refer

the reader to [CS02] for de¬nitions.

Suppose that the group G is cyclic. Denote H = Hom(G, G). Then, from the

example 7.4.2 in [CS02], one can prove that the group system G := (H, G, Gk , G)

is diverse and that the projective hash family derived from G is 1/˜-universal

p

where p is the smallest prime dividing » (Theorem 2 of [CS02]). With this, we get

˜

an 1/˜-universal hash proof system (UHPFS). Following the general construction

p

of [CS02], from this UHPFS, one can build a scheme that is IND-CCA2 secure

in the standard model, providing that p is su¬ciently large, and assuming the

˜

hardness of the decision residuosity problem.

98 G. Castagnos

3 Non-homomorphic Trapdoor Function

In this section, we change the previous construction in order to reduce the en-

cryption and decryption costs. The idea is to replace the most costly step of the

encryption process: the evaluation of the function x ’ xk . This exponentiation

will be replaced by a function f , cheaper to evaluate. This idea corresponds to

the scheme of [CGH+ 01], which uses a function built from the RSA function.

By doing this, we will loose the homomorphic property.

We have to build the function f in order to still have an e¬cient way to

decrypt. In the previous section, we saw that if was possible to decrypt by

inverting the automorphism x ’ xk of G/ g . We are going to replace this

automorphism by a known determinist trapdoor function f , permutation of a

subset of G/ g . The function f will be built from f . As a consequence, the

construction of this section will enable oneself to build a probabilistic trapdoor

function from a determinist one.

Construction of f . We suppose that we know a trapdoor permutation f

of a subset Λ of G/ g . In this section, π will denote the canonical surjection

G ’ G/ g . We suppose that π is computable at low cost for anyone who knows

G and g.

We de¬ne © := π ’1 (Λ) and Λ, a subset of © such that Λ be a representative

set of Λ, i. e., π(Λ) = π(©) = Λ and π is a bijection from Λ to Λ. We suppose

that it is easy to ¬nd the unique representative of a class of Λ in Λ. Let f be a