1 Introduction

In 1984, Goldwasser and Micali have designed the ¬rst probabilistic cryptosystem

and de¬ned the adequate notion of security for this type of scheme: the notion

of semantic security. After this system, based on quadratic residuosity, many

probabilistic schemes built from the same principle have been proposed: chrono-

logically by Benaloh ([Ben88]), Naccache and Stern ([NS98]), Okamoto and

Uchiyama ([OU98]) and at last, the most achieved system have been proposed

by Paillier ([Pai99]) and then generalized by Damg˚ and Jurik (cf. [DJ01]),

ard

allowing to encrypt larger messages. All these schemes use quotients of Z, their

one-wayness is based on factoring and their semantic security is based on the

hardness of distinguishing some powers. Moreover, these schemes are additively

homomorphic, i. e., if we got a multiplicative group structure on the ciphertexts

set and an additive one on the plaintexts set, then, if ci is a valid encryption of

mi , with i ∈ {1, 2}, c1 c2 is a valid ciphertext of m1 +m2 . This property has many

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 92“108, 2008.

c Springer-Verlag Berlin Heidelberg 2008

Two Generic Constructions of Probabilistic Cryptosystems 93

applications, for example the systems of Paillier and Damg˚ and Jurik can be

ard

+

used to design electronic vote systems (cf. [BFP 01, Jur03]), for Private Infor-

mation Retrieval (cf. [Lip05]), or for building Mix-nets (cf. [NSNK06, Jur03]).

At the present time, the Paillier and Damg˚ ard-Jurik cryptosystems are almost

the only schemes that are additively homomorphic and practical. The system

of Paillier has also been adapted in elliptic curves over Z/n2 Z by Galbraith

in [Gal02]. Another ¬nite group, simpler than elliptic curves over ¬nite ring can

be used to adapt this system: the group of norm 1 quadratic integers modulo n,

where n is an RSA integer (this adaptation was only brie¬‚y sketched in [Cas07]).

A fast and non-homomorphic variant of the Paillier scheme has been pro-

posed by Catalano, Gennaro et al. in [CGH+ 01], and later adapted in elliptic

curves by Galindo, Mart´ et al. (cf. [GMMV03]) and again in quadratic ¬elds

±n

quotients in [Cas07]. These schemes can also be seen like probabilistic variants

of deterministic trapdoor functions: respectively RSA, KMOV (cf. [KMOV92])

and LUC (cf. [SL93]).

In this paper, we propose two generic constructions that capture the ideas of

all these schemes. In section 2, we show how to build a generic homomorphic

encryption trapdoor whose semantic security is based on the hardness of the

problem of distinguishing k th powers of a group, for a well-chosen integer k.

Note that this construction is essentially known as it is a direct generalization of

the Paillier scheme. We include it here for completeness as a formal exposition is

not known by the author. Then, in section 3, we modify the previous construction

in order to get more e¬cient schemes. This will result in a method to build a

probabilistic trapdoor function from a deterministic trapdoor function which

satis¬es some properties.

For each construction, we do a careful study of both one-wayness and semantic

security. For the ¬rst one, we begin with a scheme secure against chosen-plaintext

attacks (the homomorphic schemes can not be secure against chosen-ciphertext

attacks because of their obvious malleability) and then we show that we can

modify this construction to use universal hash proof systems (cf. [CS02]) in order

to build an IND-CCA2 scheme in the standard model. The second construction

can be viewed as a simple way to transform a deterministic trapdoor function

into an encryption primitive IND-CPA secure in the standard model against a

decision problem relative to the properties of the deterministic trapdoor function

used. We also present a variant IND-CCA2 secure in the random oracle model

by using standard techniques.

In section 4, we apply these generic constructions in quotients of Z, elliptic

curves and quadratic ¬elds quotients. By doing this, we will see that a large

number of probabilistic schemes proposed these last years can be considered as

applications of the generic constructions. This study also leads to an historical

treatment of probabilistic encryption based on factoring. With quadratic ¬elds

quotients, the application of the generic construction of section 2 leads to a

concise but detailed description of the practical homomorphic cryptosystem only

brie¬‚y sketched at the end of [Cas07]. Moreover, we will show that this scheme

can be transformed to build an IND-CCA2 secure cryptosystem in the standard

model.

94 G. Castagnos

Notations: In all the paper, G will denote a ¬nite multiplicative abelian group,

k a nonnegative integer and g an element of G of order k. We will denote |G| the

order of the group G. Let Gk be the subgroup of k th power of G. We will suppose

that k |G| and denote » := |G| /k. Moreover, we will suppose that » and k are

coprime. Given a group element h, h will denote the group generated by h.

Given an integer i, |i|2 will denote the size of i in bits, i. e., |i|2 := log2 k + 1.

We will denote by n an RSA integer, i. e., n will be the product of two distinct

odd primes p and q, large enough, such that the factorization of n is infeasible

in reasonable time (i. e., |n|2 ≥ 1024).

P

For two algorithmic problems A and B, we will denote A ⇐= B whenever A

P

is polynomial-time reducible to B, and A ⇐’ B whenever the two problems are

polynomial-time equivalent.

2 Additively Homomorphic Trapdoor Function

Let us ¬rst state a straightforward result of group theory.

Theorem 1. 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, then

the order of Gk is »;

1.

the order of the quotient group G/Gk is k;

2.

Gk = x ∈ G, x» = 1 ;

3.

If g is an element of G of order k then G/Gk is cyclic and G/Gk = π(g)

4.

where π denotes the canonic surjection π : G ’ G/Gk .

Proof (sketch). We use the decomposition of G in a direct sum of cyclic groups,

and the fact that in a cyclic group of order n, the equation xk = 1 has zero or

gcd(n, k) roots. As a consequence, there are k k th roots of unity in G and the

kernel of the map x ’ xk has order k. This proves 1. and 2.; to prove 3. and 4.,

one uses the fact that » and k are coprime.

From this theorem, one can also deduce that G» has order k and that G» is

actually the subgroup of k th roots of unity of G. Note that g will be a generator

of G» , i. e., G» = g . One can see that there is an isomorphism:

∼

G» — Gk ’’ G.

The evaluation of this isomorphism if easy: one simply multiply the two elements.

The decomposition of an element of G in a product of a k th root of unity by a k th

power is less obvious, unless one knows the values of » and k. As these integers

» νk

are coprime, there exists μ and ν such that μ» + νk = 1 and c = cμ c.

In the following, we are going to use this isomorphism to build the trapdoor

function. Before that, we de¬ne a decision problem.

Two Generic Constructions of Probabilistic Cryptosystems 95

De¬nition 1. We will call the decision residuosity problem of degree k in G,

and will denote Res G,k,g , the following problem: Given c an element of G and g

an element of order k 1 , decide whether c ∈ Gk or not.

We want to build an homomorphic encryption whose semantic security is based

on the di¬culty of the decision residuosity problem of degree k in G. This con-

struction will generalize, among others, the system of Paillier (cf. [Pai99]) where

—

G = Z/n2 Z with n an RSA integer and k = n.

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 to generate random elements of Gk , and an e¬cient algorithm

to compute the discrete logarithm to base g in g .

Encryption Primitive:

Z/kZ ’’ G

EG,k,g :

m ’’ g m ρ

where ρ is a random element of Gk .

According to Theorem 1, 4., if π denotes the canonic surjection π : G ’ G/Gk ,

π(g) is a generator of the quotient group G/Gk . So if c ∈ G is an encryption of

m ∈ Z/kZ, we will have