f

Λ © G

π

∼

Λ Λ G/ g

f

Public Key. The group G, the integer k and the element g will be public.

Plaintext messages will be the elements of Z/kZ. We will suppose known an

e¬cient algorithm that returns random elements of Λ, an e¬cient algorithm

to evaluate the function f , and an e¬cient algorithm to compute the discrete

logarithm to base g in g .

Encryption Primitive:

Z/kZ — Λ ’’ ©

EG,f,g :

(m , ρ) ’’ g m f (ρ)

It is easy to see that EG,f,g is well de¬ned as g f (Λ) = © and bijective:

suppose that g m1 f (ρ1 ) = g m2 f (ρ2 ) then π f (ρ1 ) = π f (ρ2 ) . As π —¦ f = f —¦ π,

π —¦ f is bijective so ρ1 = ρ2 . As a consequence, m1 = m2 in Z/kZ.

Two Generic Constructions of Probabilistic Cryptosystems 99

Private Key and Decryption Algorithm. The private key is the trapdoor

that allows to invert f . Let c ∈ © be a ciphertext. To decrypt c, we have to

recover m ∈ Z/kZ such that there exists ρ ∈ Λ such that c = g m f (ρ). We have

π(c) = π —¦ f (ρ) = f —¦ π(ρ). With the private key we recover π(ρ) and then its

representative ρ ∈ Λ. Then, by computing c/f (ρ) we get g m and then m thanks

to the algorithm for the discrete logarithm problem in g .

One-Wayness. Let us give the de¬nition of the problem on which relies the

one-wayness of a scheme built from the EG,f,g primitive.

De¬nition 4. We will denote Class G,f,g the following problem: given c an ele-

ment of ©, ¬nd m ∈ Z/kZ such that there exists ρ in Λ such that c = g m f (ρ).

Now we de¬ne two others problems and we give a theorem that links the three

problems.

De¬nition 5. We will denote HenselG,g ’ f the following problem: given c an

element of Λ = π(©), ¬nd the element c of © such that c = f (ρ) where ρ is the

element of Λ such that c = π(f (ρ)). We will denote Inv ’ f the problem of local

inversion of the trapdoor f , i. e., given c an element of Λ, ¬nd ρ in Λ such that

c = f (ρ).

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

integer, g an element of G of order k, Λ a subset of G/ g , Λ a representative

set of Λ in G and f a trapdoor permutation of Λ. We denote π the canonic

surjection from G to G/ g and f a function from Λ to © := π ’1 (Λ) such that

π —¦ f = f —¦ π. We have the following relations:

P P

Class G,f,g ⇐’ HenselG,g ’ f § Dlog ⇐= Inv ’ f § Dlog

g g

where Dlog denotes the discrete logarithm problem in g .

g

Proof. We prove the left equivalence, the reduction on the right will follow from

the decryption algorithm. Suppose that we have two oracles that solve respec-

tively the HenselG,g ’ f and Dlog g problems. Let c be an element of ©. We

want to recover m ∈ Z/kZ in the decomposition c = g m f (ρ) with ρ ∈ Λ. We

have π(c) = π f (ρ) . We give π(c) to the oracle for the HenselG,g ’ f problem.

We get the element c of © such that c = f (ρ). Given c/c , the oracle for the

Dlog g problem returns m.

For the opposite way, we have an oracle that solve the Class G,f,g problem.

If g is an element of g , we take a random element ρ in Λ. By giving g f (ρ)

to the oracle, we get m, the discrete logarithm of g to base g. Suppose now

that we have an element c, of Λ, for which we want to solve the HenselG,g ’ f

problem. We take m at random in Z/kZ. We denote c the element of Λ such

that π(c) = c. We give g m c ∈ © to the oracle (note that it is a random query

for the oracle). We then get from the oracle the element m of Z/kZ such that

g m c = g m f (ρ) with ρ element of Λ. As π(g m c) = c = π f (ρ) , the element

g m ’m c is a correct answer to the HenselG,g ’ f problem.

100 G. Castagnos

Remark 4. This theorem establishes that the security of a system built from the

EG,f,g primitive relies on the security of the trapdoor f . For the Catalano et al.

scheme, (cf. [CGH+ 01] and section 4), an instance of this construction in which

f is the classic RSA function, the result of [CNS02] states that the equivalence

actually holds. Unfortunately, the proof of this result uses intrinsic properties of

the RSA function and can not be exploited for the generalized case.

Semantic Security

De¬nition 6. Let us denote Res G,f,g , the problem of distinguishing the ele-

ments of f (Λ) in ©.

Theorem 5. An encryption scheme built from the EG,f,g primitive is semanti-

cally secure against Chosen-Plaintext Attacks if and only there exists no polyno-

mial algorithm that solve the decision Res G,f,g problem.

Proof. A scheme built from the construction of the previous section, and a

scheme built from EG,f,g shares a similar property:

c

(c ← EG,f,g (m)) ⇐’ ∈ f (Λ) .

gm

As a consequence, the proof of Theorem 3 can be easily adapted.

IND-CCA2 Variant in the ROM. Using standard techniques, one can modify the

EG,f,g primitive to make it resistant against adaptive chosen-ciphertext attacks

in the random oracle model. One can simply add h(m, ρ) to the ciphertext,

where h is an hash function viewed like a random oracle. One can also use the

Fujisaki-Okamoto conversion (cf. [FO99]) in order to reduce the ciphertexts size.

4 Applications

We will use the constructions of sections 2 and 3 in algebraic groups over

—

(Z/ns Z) where s is a nonnegative integer. RSA integers will allow to use the

group order as a trapdoor. This would lead to an historical of probabilistic cryp-

tography based on factoring.

The idea of working modulo ns with s > 1 is due to Paillier (cf. [Pai99]) and

Damg˚ and Jurik (cf. [DJ01]) for the case s > 2. As we shall see in the following,

ard

this enables oneself to meet the hypothesis of the generic construction: the subgroup

of nth roots of unity of the group considered will be the kernel of the reduction mod-

ulo n, and its elements will be easy to describe. As a consequence, we will exhibit

an element g of order n such that the discrete logarithm problem in g is easy.

4.1 Schemes in Quotients of Z

The ¬rst probabilistic cryptosystem, proposed by Goldwasser and Micali in

1984 (cf. [GM84]) is very similar to the generic construction explained in section

2. Its semantic security is based on a well-known problem, the quadratic resid-

uosity problem (i. e., k = 2), but its expansion is awful as one bit is encrypted

with |n|2 bits.

Two Generic Constructions of Probabilistic Cryptosystems 101

G = (Z/nZ)— , k Prime, k | •(n), Benaloh (88). The cryptosystem of

Goldwasser-Micali has been generalized by Benaloh in [Ben88]. The group G is

—

now (Z/nZ) , the integer k is an odd prime such that k divides •(n) and k does

not divide » := •(n)/k. Let g be an element of order k, to encrypt an element

m ∈ Z/kZ, one uses the encryption primitive EG,k,g de¬ned in section 2: an

—

encryption of m is g m rk where r is a random element of (Z/nZ) . The drawback

of this system is that k has to be small because there is no particular algorithm

for computing discrete logarithms in g . As a consequence, the expansion of the

system, |n|2 / |k|2 remains high.

—

G = (Z/nZ) , k Smooth, k | •(n), Naccache-Stern (98). Naccache and

—

Stern have improved in [NS98] the previous system. They still use G = (Z/nZ)

but k is chosen smooth. This leads to a more e¬cient algorithm for computing

discrete logarithms in g by using the Pohlig-Hellman algorithm. Naccache and

Stern state that the expansion can be reduced to 4.

Okamoto and Uchiyama have proposed in [OU98] to work modulo n = p2 q.

The following system is an improvement of their proposal.

—