of

O” denotes the ring of integers of Q( ”). We will denote •” (a) the order of

the group (O” /aO” )§ .

We refer the reader to [Cas07] for the basic properties of this group. We only

recall that exponentiation can be e¬ciently computed in this group by using

the Lucas sequence, and that if n is prime to ”, then for s > 1, the order of

§

O” /ns+1 O” is

” ”

•” (ns+1 ) = ns •” (n) = ns p ’ q’ ,

p q

”

where denotes the well-known Legendre symbol. Moreover, note that the

p

§

group (O” /ps O” ) is cyclic (the same holds modulo q s ).

§

G = O” /n2 O” , k = n,. We apply the construction of section 2 with

§

G = O” /n2 O” , where ” is a non-square integer prime to n. The order of

G is n •” (n), so we set k = n and » = •” (n) and suppose that k and Λ are

coprime.

Element of order n: As previously seen, we look for an element of order n

§ §

in the kernel of the reduction modulo n from O” /n2 O” to (O” /nO” ) .

√

This reduction is surjective by the Hensel Lemma. The element g ≡ 1 + n√”

(mod n2 ) is a generator of this kernel and g is indeed of order n as g r ≡ 1+nr ”

(mod n2 ) for all integer r. As a consequence of this expression of g r , the discrete

logarithm problem in g is easy.

k th powers generation: To simplify, we suppose that ” is neither a square modulo

p nor modulo q. It is easy to see that the map ± ’ ±/± from (O” /nO” )— to

§ —

(O” /nO” ) is surjective and that its kernel is (Z/nZ) . As a consequence, the

map √

2r √

r2 + ”

r+ ”

√ =2

Ψ :r’ +2 ”,

r ’” r ’”

r’ ”

from Z/nZ to (O” /nO” )§ is well-de¬ned, injective and is almost surjective (we

only miss 1 and elements that allow to factor n (elements di¬erent from 1 and

that are congruent to 1 modulo p or 1 modulo q). Moreover, the map β ’ β n

§

from (O” /nO” ) to Gn is an isomorphism. As a consequence, the map

Z/nZ ’ Gn : r ’ Ψ (r)n ,

is still injective and almost surjective.

Two Generic Constructions of Probabilistic Cryptosystems 105

Encryption function: The encryption function is

—

Z/nZ — (Z/nZ) ’’ G

’’ g Ψ (r)n

m

(m , r)

where m is the plaintext and r a random element, and the public key is (n, ”)

where n = pq is an RSA integer, ” is a non-square integer, prime to n and ” is

neither a square modulo p nor modulo q.

Decryption algorithm: The trapdoor is » = •” (n). The decryption algorithm

is the same as the generic one. Note that it can be sped up by using Chinese

remaindering (this is true for all the others schemes presented in this paper).

Security: The one-wayness of the scheme is based on the Class G,k,g problem

and the reductions of Theorem 2 hold. The semantic security is based on the the

di¬culty of distinguishing the elements of Gn in G (As the map r ’ Ψ (r)n is in-

jective and almost surjective, almost all the element of Gn can be produced. The

ones that are not produced are either easy to distinguish or allow to factor n).

Expansion: The cryptosystem expansion is 4, a priori, but can be reduced to

§

§

3. One de¬nes a lifting L of the elements of (O” /nO” ) in O” /n2 O” .

§

Then, an element ± of O” /n2 O” is represented by the couple (k, ± mod n) ∈

√

§

Z/nZ — (O” /nO” ) with k such that ± = (1 + n ”)k L(± mod n). Note that

the computation of this representation (by using the Hensel Lemmma) only costs

a few multiplications and one inversion. This method can also be applied for the

system of Galbraith.

Comparison with others additively homomorphic systems: In the following table,

we compare this system with the Paillier and Galbraith schemes. The unity of

complexity is the cost of a multiplication modulo n. We use the following esti-

mations: a multiplication modulo n2 costs as much as 3 multiplications modulo

n (by using radix n representation), a multiplication modulo p2 costs as much as

a multiplication modulo n and three multiplications modulo p as much as a mul-

tiplication modulo n. An inversion modulo n costs as much as 10 multiplications

modulo n. We have used Chinese remaindering for all the schemes.

Cryptosystem Paillier Galbraith QF scheme

— §

O” /n2 O”

Z/n2 Z E/(Z/n2 Z)

Group

|n|2 + 1 35 |n|2 + 3 9 |n|2 + 20

9

Encryption 2

|n|2 + 21 |n|2 + 3 |n|2 +

3 5 5 4

Decryption 2 3 3 3

We see that the scheme in quadratic ¬elds is much more faster than the

system that uses elliptic curves, thanks to e¬cient exponentiation using Lucas

106 G. Castagnos

sequences. This scheme complexity is not far from the Paillier cryptosystem (the

factor two is inherited from the respective costs of exponentiation in Z/n2 Z and

§

in O” /n2 O” ). As a result, this scheme is still practical.

If all the schemes are based on factorization, from Theorem 2, we see that

the intermediate problems on which the one-wayness of the schemes are based

are not the same. For Paillier, it is the RSAn problem i. e., the inversion of the

—

map x ’ xn in (Z/nZ) . For the presented scheme, it is the adaptation of this

§

problem in (O” /nO” ) , i. e., the inversion of the map ± ’ ±n . We do not know

if one problem is easier than the other (as the only known way to solve them is to

factor n), but this scheme brings some diversity as the Paillier scheme is almost

the only practical additively homomorphic scheme known. Another advantage

of this scheme is that one has more choice for the public key than for the Paillier

scheme: one can choose freely the modulus n and the discriminant ”.

Generalization: This scheme can also be generalized by working modulo ns+1

with s > 1 in order to encrypt messages of Z/ns Z. One has only to ¬nd an ele-

ment g of order ns and an e¬cient algorithm for the discrete logarithm problem.

One can see that the following element:

√ 1 1 1 5

g := n ” + 1 + ”n2 ’ 3 ”2 n4 + 4 ”3 n6 ’ 7 ”4 n8 + · · ·

2 2 2 2

obtained by successive applications of the Hensel Lemma is indeed of order

ns . Given g k , one can still compute the discrete logarithm k at low cost, by

computing recursively k mod n2 , k mod n4 , . . .

IND-CCA2 variant of this scheme: Similarly to the Paillier cryptosystem, one

can design a variant that is IND-CCA2 in the standard model. A cyclic group

is obtained in the same way, by using primes p and q such that (p ’ (”/p))/2

and (q ’ (”/q))/2 are both primes. Then, one obtains a subgroup of order

n •” (n)/2. Note that some optimisations used by Cramer and Shoup in [CS02]

to get compact ciphertexts for the adaptation of the Paillier scheme can also be