—

responds to an application of the EG,k,g encryption function with G = Z/n2 Z ,

and k = n. If we suppose that gcd(n, •(n)) = 1, as |G| = n•(n), k divides |G|

and k is prime to » := |G| /k = •(n). One can see that the subgroup G» of G, the

subgroup of nth roots of unity, is the kernel of the surjective homomorphism:

—

’ (Z/nZ)— . As a consequence, this subgroup is a cyclic group of

Z/n2 Z

order n, generated by g :≡ 1 + n (mod n2 ). Moreover, the discrete logarithm

problem in g is trivial as for all i ∈ Z/nZ, g i ≡ 1 + in (mod n2 ). To encrypt,

one can use the isomorphism EG,k,g de¬ned in section 2. The encryption function

is thus the isomorphism:

—

∼

—

Z/nZ — (Z/nZ) ’’ Z/n2 Z

’’ g m rn

(m , r)

where m is the plaintext and r a random element. The trapdoor is •(n), i. e.,

the factorization of n, and the decryption algorithm is the application of the

generic algorithm described in section 2. The expansion of this system is 2.

An IND-CCA2 variant of this scheme has been designed by Cramer and Shoup

in [CS02]. As previously said, this variant can also be obtained from the con-

struction of section 2, if the group G is cyclic. One can have a cyclic group by

choosing Sophie Germain primes for p and q: with this choice there exists a cyclic

— +

group of order n•(n)/2 in Z/n2 Z , isomorphic to Z/nZ — (Z/nZ) , where

—

+

(Z/nZ) is the subgroup of elements of Z/n2 Z that have a positive Jacobi

symbol (see [CS02] subsection 8.2 for details).

Damg˚ and Jurik have proposed in [DJ01] a generalization of the Pail-

ard

—

lier cryptosystem. They work in the group G = Z/ns+1 Z with s > 1 and

s

k = n . One obtains a system that allows oneself to encrypt messages of arbitrary

102 G. Castagnos

length (by increasing s). This can have many applications (cf. [DJ01, Jur03]).

The expansion of this scheme is 1 + 1/s.

—

G = Z/n2 Z , f = RSA, Catalano et al. (01). In [CGH+ 01], Catalano,

Gennaro et al. have proposed a probabilistic encryption scheme presented like a

fast variant of the Paillier cryptosystem. With the help of the generic construc-

tion of section 3, one can also see this scheme as a probabilistic version of the

—

RSA cryptosystem. Let G = Z/n2 Z , and g ≡ 1 + n (mod n2 ). The quotient

—

group G/ g is isomorphic to (Z/nZ) . We denote respectively © and Λ, the

sets of elements of G and G/ g , i. e.,

© := r ∈ N, 0 < r < n2 , gcd(r, n) = 1 ,

and

Λ := {r ∈ N, 0 < r < n, gcd(r, n) = 1} .

With the notation of section 3, one actually has Λ := Λ, and the set Λ is a

representative set of the classes of © modulo n. Let e be an integer prime to

•(n), the RSA function, f : x ’ (xe mod n) is a permutation of Λ. This function

is lifted from Λ to © by considering f : x ’ (xe mod n2 ), so that π —¦ f = f —¦ π.

To encrypt, we use the EG,f,g primitive and we obtain the following encryption

function:

Z/nZ — Λ ’’ ©

(m , r) ’’ g r mod n2

me

where m is the plaintext and r a random element. The decryption is done has

described in section 3: one reduces the ciphertext modulo n and recover r by

inverting the RSA function, thanks to the knowledge of d, the inverse of e modulo

•(n), the trapdoor of the function f .

—

Remark 5. The previous scheme can be generalized by taking G = Z/ns+1 Z

with s > 1, in order to decrease the expansion. One has to rede¬ne the set ©

accordingly and to lift f in f : x ’ xe mod ns+1 .

One can apply the non-homomorphic construction of section 3, with all the known

trapdoor functions of Z/nZ, e. g., Demytko™s (cf. [Dem94]) or LUC (cf. [SL93]).

Note that with the LUC function, one gets a scheme already proposed in [Cas07].

Schemes in Elliptic Curves over Z/ns+1 Z

4.2

Both constructions can be applied in elliptic curves. This leads respectively to the

systems of Galbraith (cf. [Gal02]) and Galindo, Mart´ et al. (cf. [GMMV03]).

±n

G = E/(Z/ns+1 Z), k = ns , Galbraith (02). In [Gal02], Galbraith has

adapted the Damg˚ and Jurik scheme (and hence the Paillier scheme) in el-

ard

liptic curves. This homomorphic scheme can also be viewed as an application of

Two Generic Constructions of Probabilistic Cryptosystems 103

the EG,k,g primitive of section 2. The group G is the group of points of an elliptic

curve over Z/ns+1 Z, i. e., the set of elements (X : Y : Z) of P2 (Z/ns+1 Z) such

that

Y 2 Z = X 3 + aXZ 2 + bZ 3 ,

where a and b are two elements of Z/ns+1 Z such that 4a3 + 27b2 is invertible.

We denote this group Ea,b /(Z/ns+1 Z) (See [Gal02] for more details on elliptic

curves over rings).

One can prove that the order of this group is ns |Ea,b /(Z/nZ)|. By taking

k = ns , and supposing that ns is prime to » := |Ea,b /(Z/nZ)|, one can apply

the generic construction. The tricky part of this adaptation is to ¬nd an element

g of G of order ns such that the discrete logarithm problem is easy in g . Once

again, we look for g in the kernel of the reduction modulo n from Ea,b /(Z/ns+1 Z)

to Ea,b /(Z/nZ). One can see that the element g := (n : 1 : n3 + an7 + bn9 + · · · )

is of order ns and that discrete logarithms are easy to compute in g (again

see [Gal02] for details on this element g, on the subgroup g and how to compute

the group law in this subgroup and in G).

To encrypt a message m of Z/ns Z, one use the EG,k,g primitive of section 2:

th

a ciphertext for m is a point of the form m.g + P where P is a random “ns

power”. To produce a such P , as it is di¬cult to produce an element of the curve

without knowing the factorization of n, one can not take a random element of

G or of Ea,b /(Z/nZ) and take it to the “power” ns . Hence, we use the method

th

exposed in Remark 3: a ns power is part of the public key.

A drawback of this scheme is its cost as one has to do costly scalar multi-

plications in elliptic curve over a huge base ring (as the security is based on

factorization and not on the discrete logarithm problem, we can not reduce the

size of this ring).

G = E/(Z/n2 Z), f = KM OV , Galindo et al. (03). In [GMMV03],

Galindo, Mart´ et al. have proposed a non-homomorphic scheme based on the

±n

KMOV trapdoor permutation (cf. [KMOV92]). This scheme is not a direct adap-

tation of the generic construction of section 3 as the KMOV function is not a

permutation of a subset of a group. Indeed, the KMOV function is a permutation

of the set

—

(x, y) ∈ Z/nZ — Z/nZ, y 2 ’ x3 ∈ (Z/nZ) ,

and maps (x, y) to e.(x, y), where the scalar multiplication is performed on the

elliptic curve E0,y2 ’x3 /(Z/nZ) where e is prime to (p + 1)(q + 1) and p and q

are chosen congruent to 2 modulo 3 (it is hard to take points on a ¬xed curve

without knowing p and q). So, one has to apply the generic construction with

a group G that depends on the plaintext message. One de¬ne ad hoc subsets Λ

and © of Z/n2 Z and lift the KMOV function from Λ to © by computing e.(x, y)

in a curve modulo n2 . See [GMMV03] for more details.

Again, one can generalize this scheme by working modulo ns with s > 2.

104 G. Castagnos

4.3 Additively Homomorphic Scheme in Quadratic Fields Quotients

In this subsection, we apply the generic construction of section 2 in another

¬nite group, not widely used in cryptography, the group of norm 1 elements of

a quadratic ¬eld modulo n. We will obtain the system only brie¬‚y sketched at

the end of [Cas07].

De¬nition 7. Let ” be a non-square integer, and a an odd integer prime to ”.

§