Trapdoor Permutation Polynomials of Z/nZ

and Public Key Cryptosystems

(Extended Abstract)

Guilhem Castagnos1 and Damien Vergnaud?2

1
DMI-XLIM, Université de Limoges,
123, avenue Albert Thomas, 87060 Limoges CEDEX, France
[Link]@[Link]
2
École normale supérieure
Département d’informatique, 45 rue d’Ulm, 75230 Paris cedex 05, France
[Link]@[Link]

Abstract. We define new algorithmic problems and discuss their prop-

erties (in particular, we present a careful study of their computational
complexity). We apply the new problems to design public key encryption
protocols with semantic security relative to their decisional variants. We
then show how to provide efficient schemes that are semantically secure
under adaptive chosen ciphertext attacks in the random oracle model.
Finally, we show that the ideas developed in this extended abstract can
be used to design the most efficient known cryptosystem with semantic
security under non-adaptive chosen ciphertext attacks in the standard
security model.
Keywords: Public Key Encryption, Semantic Security, Standard Model,
Random Oracle Model, Chosen-Ciphertext Attacks, Polynomial Diffie-
Hellman Problems.

1 Introduction
This paper describes new algorithmic problems using trapdoor permutation
polynomials of Z/nZ and new constructions of semantically secure public key
cryptosystem based on these problems, relative to different scenarios of attacks.

Background. A trapdoor permutation is a one-to-one function f that anyone

can compute efficiently; however, inverting f is hard unless some “trapdoor”
information is also given. Naively, a trapdoor permutation defines a simple public
key encryption scheme: the description of f is the public key and the trapdoor
is the secret key.
In 1978, Rivest, Shamir, and Adleman proposed the first candidate trapdoor
permutation [24]. The RSA setup consists of choosing two distinct large prime
?
This work was done while this author was a postdoctoral fellow in the Computer
Security group of the Bonn/Aachen International Center for Information Technology.
numbers p and q, and computing the RSA modulus n = pq. The public key is n
together with an exponent e (relatively prime to ϕ(n) = (p−1)(q−1)). The secret
key d is defined to be the multiplicative inverse of e modulo ϕ(n). Encryption
and decryption of a message in (Z/nZ)× are defined as follows: E(m) = me
mod n and D(c) = cd mod n. Hence, the encryption function is an evaluation
of the polynomial X e of Z/nZ[X] and the decryption is performed with the
polynomial X d .
In 1993, in [12], Demytko has suggested to replace the monomial X e by
division polynomials of “elliptic curves” defined over the ring Z/nZ. The same
year, Smith and Lennon [26] have proposed a system, LUC, which uses a special
type of Lucas sequences. The encryption and decryption functions can also be
seen as an evaluation of a polynomial of Z/nZ[X], a Dickson polynomial (cf. [19]).
As a consequence, the LUC cryptosystem is very similar to a system already
proposed by Müller and Nöbauer (cf. [20, 21]).
The security goal for a public key encryption scheme is to guarantee that no
partial information about a plaintext message is revealed from its ciphertext, a
notion often called semantic security or indistinguishability of ciphertexts [15].
Unfortunately, the naive public key system built from the three mentioned trap-
door functions is deterministic and hence cannot achieve this security notion.
Under a slightly stronger assumption than the intractability of the integer fac-
torization, these primitives give a cryptosystem that is only One-Way under
Chosen-Plaintext Attacks (a very weak level of security). The main purpose of
the present paper is to propose new combinations of these three polynomial
functions giving rise to semantically secure public key cryptosystem.

Several models of attacks have been defined. An encryption scheme that

is semantically secure under a Chosen-Plaintext Attack (resp. a non-Adaptive
Chosen-Ciphertext Attack, resp. an Adaptive Chosen-Ciphertext Attack) is said
to be IND-CPA secure (resp. IND-CCA1 secure, resp. IND-CCA2 secure). In [2],
it is shown that IND-CCA2 is strictly the strongest notion of semantic security,
IND-CCA1, the intermediary notion, and IND-CPA strictly the weakest. Indis-
tinguishably against Chosen-Ciphertext attack is considered to be the correct
notion of security for general-purpose public key encryption schemes.

Contributions of the paper. In this paper, we present new algorithmic prob-

lems (in section 2, after some notations). Then, in section 3, we give some argu-
ments to validate the cryptographic purpose of those problems, with a careful
study of their difficulty and their relations. It is possible to apply the new prob-
lems to design public key encryption protocols with semantic security (IND-CPA)
relative to the decisional variant of them. This is done in section 4. We then show,
in section 5, how these schemes can also be made IND-CCA2 secure assuming
the intractability of our decisional RSA variants by using well-known techniques
(in the random oracle model [5]). Finally, in section 6, we explain how the ideas
developed in this extended abstract can be used to design encryption schemes
with higher security in the standard model: for instance, we show that it is pos-

2
sible to construct the most efficient known IND-CCA1 secure cryptosystem with
security analysis in the standard model.

2 Permutation polynomials and new algorithmic

problems
2.1 Notations
Let A be a probabilistic Turing machine running in expected polynomial time
(a PPT, for short), and let x be an input for A. The probability space that
assigns to a string σ the probability that A, on input x, outputs σ is denoted
by A(x). Given a probability space S, a PPT that samples a random element
R R
according to S is denoted by x ← − S. For a finite set X, x ←
− X denotes a PPT
that samples a random element uniformly at random from X. We will use poly
and negl to denote respectively unspecified polynomial any negligible3 functions.
For any integer k ≥ 2, we denote Primes(k) = {p ∈ N, 2k < p < 2k+1 , p is prime}
and 2Factor(k) = {n ∈ N, n = pq, with p < q < 2p and p, q ∈ Primes(k)}. For
n ∈ N, ϕ(n) = #(Z/nZ)× denotes the Euler totient value of n.
P
For two algorithmic problems A and B, we denote A ⇐= B whenever A is
polynomial-time reducible to B, and A ∧ B the problem of solving together A
and B.

2.2 RSA and LUC

Let k ≥ 2, n = pq ∈ 2Factor(k) and e be an integer relatively prime to ϕ(n).
It is well-known that the polynomial X e of Z/nZ[X] induces a permutation
of (Z/nZ)× . The RSA encryption corresponds to an evaluation of this polyno-
mial. Moreover, this polynomial has a trapdoor: knowing d such that ed ≡ 1
mod ϕ(n) allows one to invert the evaluation of this polynomial at any point.
Another permutation polynomial is the LUC function used in the system
of [26]. Given two integers a and b such that a2 − 4b is a non-square, the Lucas
sequence V is given by a second-order linear recurrence relation:

∀k > 1, Vk+1 (a, b) = aVk (a, b) − bVk−1 (a, b), V1 (a, b) = a, V0 (a, b) = 2.

Let e be an integer relatively prime to (p2 − 1)(q 2 − 1). The LUC function, x 7→
Ve (x, 1) (mod n), is a permutation of the set {x ∈ N, 0 < x < n, gcd(x, n) =
1, gcd(x2 − 4, n) = 1}, whose inverse is x 7→ Vd (x, 1) (mod n), where d is the
multiplicative inverse of e modulo (p2 − 1)(q 2 − 1) (see [6] for more details on the
LUC function). One can see that Ve (X, 1) is in fact a polynomial of degree e,
be/2c  
X e e−i
Ve (X, 1) = X e−2i ,
i=0
e−i i
3
i. e., ∀c ≥ 0, ∃Kc ∈ N, ∀k ∈ [[Kc , +∞[[, negl(k) ≤ k−c

3
which is a special type of Dickson polynomial (cf. [19]) and, for that reason, a
permutation polynomial.
These two polynomials of degree e derived from the RSA and LUC cryp-
tosystems can be evaluated at low cost. If we denote |e| the size of e in bits, the
evaluation of the RSA polynomial needs (3/2)|e| multiplications modulo n on
the average, with the square and multiply algorithm, and 2|e| multiplications are
needed for the evaluation of the LUC polynomial, using the algorithm of [17].
In the following, we combine these two polynomials to define new algorith-
mic problems and build new systems. We will define our new problems in a
general setting, by considering arbitrary permutation polynomials of (Z/nZ)× .
The study will be identical as if we were working directly with the RSA and LUC
polynomials except for one thing: as the RSA polynomial induces a morphism of
(Z/nZ)× some extra reductions will be possible. Consequently, this specific case
of polynomial Q such that Q(xy) = Q(x)Q(y) for all elements x, y of (Z/nZ)×
will be considered in the study of our problems.
Remark 1. In order to design cryptosystems, one can also follow the ideas of
Schwenk and Huber (cf. [25]), and use more general permutation polynomials
for which the inverse function is not explicit.

2.3 Permutation polynomials and pointwise inversion

In this paragraph, we define the problem of pointwise inversion of an arbitrary

permutation polynomial (PP).

Definition 1. A PP generator is a PPTM that takes a security parameter k

as input and outputs a 4-tuple (n, p, q, P ) where n = pq ∈ 2Factor(k) and
P ∈ Z/nZ[X] is a permutation of (Z/nZ)× which can be evaluated at any value
of (Z/nZ)× in polynomial time in k. Let e : N −→ N. A PP generator Gen is said
to be a PP generator of degree e if for any k ∈ N and any (n, p, q, P ) ← Gen(k),
deg(P ) ≤ e(k).

The next definition quantifies the resistance to pointwise inversion for PP

generators (i. e., the problem: given α = P (a) ∈ (Z/nZ)× , compute a ∈ (Z/nZ)×
denoted P −1 (n)).

Definition 2. Let Gen be a PP generator. Let A be a PPTM that takes as input

a triple (n, P, y) ∈ N×Z/nZ[X]×(Z/nZ)× and outputs an element x ∈ (Z/nZ)× .
We consider the following random experiments, where k is a security parameter:
−1
Experiment ExpPGen,A (k)
R
(n, p, q, P ) ←
− Gen(k)
R
y←− (Z/nZ)×
x ← A(n, P, y)
Return 1 if P (x) = y, 0 otherwise

4
The success of A in solving the pointwise inversion problem is
−1 −1
SuccPGen,A (k) = Pr[ExpPGen,A (k) = 1].

Let τ be an integer and ε a real in [0, 1]. Gen is said to be (k, τ, ε)-P −1 -secure if
−1
no adversary A running in time τ has success SuccPGen,A (k) ≥ ε.

2.4 Permutation polynomials and polynomial Diffie-Hellman

problem

Definition 3. A PDH generator is a PPTM that takes a security parameter

k as input and outputs a 5-tuple (n, p, q, P, Q, R) where n = pq ∈ 2Factor(k),
P ∈ Z/nZ[X] and Q ∈ Z/nZ[X] are permutations of (Z/nZ)× which can be
evaluated at any value of (Z/nZ)× in polynomial time in k and R ∈ Z/nZ[X, Y ]
2
is a bivariate polynomial which can be evaluated at any value of (Z/nZ)× in
polynomial time in k. Let eP : N −→ N, eQ : N −→ N and eR : N −→ N. A PDH
generator Gen is said to be a PDH generator of degree (eP , eQ , eR ) if for any
k ∈ N and any (n, p, q, P, Q, R) ← Gen(k), deg(P ) ≤ eP (k), deg(Q) ≤ eQ (k),
degX (R) ≤ eR (k).

We now define a new family of algorithmic problems: the computational polyno-

mial Diffie-Hellman problems that generalizes the pointwise inversion problem:
Computational Polynomial DH: C-POL-DH(n, P, Q, R)
Given: α = P (a) ∈ (Z/nZ)× and β = Q(b) ∈ (Z/nZ)× ;
Find: R(a, b) ∈ (Z/nZ)× .
The problem is named after the Diffie-Hellman key exchange [13] because
of its similarity with it in the special case where Q = P and R(X, Y ) =
P (XY ). In

this paper, we deal only with the cases R(X, Y ) = XY , R(X, Y ) =
P (XY )` and R(X, Y ) = Q(X) that we denote respectively C-POL1(n, P, Q),
C-POL2(n, `, P, Q) and C-DPOL(n, P, Q).
The next definition quantifies the resistance to the computational polynomial
Diffie-Hellman problems for PDH generators.

Definition 4. Let Gen be a PDH generator. Let A be a PPTM that takes as

2
input a 6-tuple (n, P, Q, R, y, z) ∈ N × Z/nZ[X]2 × Z/nZ[X, Y ] × (Z/nZ)× and
outputs an element z ∈ (Z/nZ)× . We consider the following random experi-
ments, where k is a security parameter:

Experiment ExpC-POL-DH
Gen,A (k)
R
(n, p, q, P, Q, R) ←
− Gen(k)
R R
− (Z/nZ)× , y 0 ←
y← − P (y)
R R
z←− (Z/nZ)× , z 0 ←− Q(z)
x ← A(n, P, Q, R, y 0 , z 0 )
Return 1 if x = R(y, z), 0 otherwise

5
The success of A in solving the computational polynomial DH problem is

SuccC-POL-DH
Gen,A (k) = Pr[ExpC-POL-DH
Gen,A (k) = 1].

Let τ be an integer and ε ∈ [0, 1]. Gen is said to be (k, τ, ε)-C-POL-DH-secure if

no adversary A running in time τ has success SuccC-POL-DH
Gen,A (k) ≥ ε.

Now, we define the decision problem D-POL-DH(n, P, Q, R) where an ele-

ment from (Z/nZ)× is given and the algorithm has to decide whether it is a
valid candidate for the C-POL-DH(n, P, Q, R) problem.
Decision Polynomial DH: D-POL-DH(n, P, Q, R)
Given: α = P (a) ∈ (Z/nZ)× , β = Q(b) ∈ (Z/nZ)× and γ ∈ (Z/nZ)× ;
Decide whether: γ = R(a, b).
We define three decision problems D-POL1(n, P, Q), D-POL2(n, `, P, Q) and

finally D-DPOL(n, P, Q) for the cases R(X, Y ) = XY , R(X, Y ) = P (XY )`
and R(X, Y ) = Q(X) (respectively).

Remark 2. The D-DPOL(n, P, Q) decision problem can be rewritten (the same

holds for the computational problem) as follows: given P (a) and γ ∈ (Z/nZ)×
decide whether γ = Q(a). Hence, the C-DPOL(n, P, Q) and D-DPOL(n, P, Q)
problems are generalisations of the Dependent-RSA problems defined in [23].

3 Relations among the new problems

In this section, we discuss the problems defined in the previous section with
a careful study of both their difficulty and their relations. For clarity reasons,
when the reductions are simple, the theorems are stated with less formalism than
the definitions of the previous section. Throughout this section, for a security
parameter k, n, P and Q will correspond to the output of a PDH generator on
input k. For short, we will denote ep and eq the degrees of P and Q.

We define an extraction problem, E-POL-DH(n, P, Q, R): Given P (a), Q(b)

and R(a, b), find a and b. We denote as before E-POL1, E-POL2, E-DPOL the
extraction problems for the special values of R.
We first study the C-POL1 and C-POL2 classes of problems, then we will
analyse the C-DPOL class of problem and finally the relation between these
three classes.

3.1 The C-POL1 and C-POL2 problems

For the C-POL1 problem, we have the straightforward theorem:

P P
Theorem 1. D-POL1(n, P, Q) ⇐= C-POL1(n, P, Q) ⇐⇒ P −1 (n) ∧ Q−1 (n).

6
Proof. All the reductions follow from the definition of the C-POL1(n, P, Q) prob-
P
lem except C-POL1(n, P, Q) =⇒ P −1 (n) ∧ Q−1 (n). Suppose that we know P (a)
and we want to compute a. We choose a random b in (Z/nZ)× and we give the
value P (a) and Q(b) to an oracle for C-POL1(n, P, Q) which gives the value ab
in reply, so we can recover b. We can invert Q with a symmetric process. t
u

For the C-POL2 problem, we use the extraction problem to state a similar
theorem.

Theorem 2. For an RSA integer n, and two permutation polynomials P and

Q of (Z/nZ)× ,

P P C-POL2 P
C-POL2 ∧ E-POL2 ⇐⇒ P −1 ∧ Q−1 =⇒ =⇒ D-POL2 .
E-POL2

t
u

We now examine the difficulty of the decision problems.

Difficulty of D-POL1 and D-POL2 The best known way to solve these
problems is to solve the corresponding extraction problem (cf. [8]). We know
the values of P (a), Q(b) and R(a, b) and we want to find the values of a and b.
Suppose that eQ 6 eP (else the attack is done with the symmetric method). We
compute the resultant with respect to the variable Y :

S(X) = Res(R(X, Y ) − R(a, b), Q(Y ) − Q(b)).

Y

This gives a polynomial S(X) of degree eR eQ with S(a) = 0, so

(X − a) | gcd(S(X), P (X) − P (a)).

In fact, in many cases4 , we will have (X − a) = gcd(S(X), P (X) − P (a)), and

this method allows to recover a. If we are trying to solve the E-POL1 problem
we know ab, so we have also recovered b. Else, for the E-POL2 problem, we can
recover b by computing gcd(R(a, Y ) − R(a, b), Q(Y ) − Q(b)).

Remark 3. In the previous description, “the” resultant and “the” gcd of two
polynomials with coefficients in Z/nZ are understood as the results of the clas-
sical algorithms (described in [14] for instance) which compute the resultant
and the gcd of polynomials over a field. In the unlikely event, that a non-trivial
factor of n appears during this computation, the adversary simply aborts the
computation and uses this knowledge to solve the instance of its problem.
4
Some experimentations confirm that, but, we have not been able to prove this fact.
Note that in [8, 23] a similar fact is stated, without proof. Anyway, as our goal
is to estimate the size of the degrees to make our cryptosystems secure, only the
possibility of an attack matters.

7
The resultant can be computed with O(e2R eQ log2 (eR eQ ) log log(eR eQ )) opera-
tions in Z/nZ, according to [14, Corollary 11.18, p. 310]. Note that eR = 1 for
E-POL1 and eR = `eP for E-POL2, so, if ` is large enough, this method will be
infeasible even if eP is small.
According to [14, Corollary 11.6, p. 304], the computation of the first gcd can
be done in O(e log2 e log log e) operations in Z/nZ, where e = max(eR eQ , eP ) and
the computation of the second gcd in O(e log2 e log log e) operations in Z/nZ,
where e = max(eR , eQ ). This complexity of attacks on the extraction problems
will be used in the next section to set key sizes for the cryptosystems that we
will built.

Now, suppose that the polynomial Q induces a morphism of (Z/nZ)× (in

particular, if Q is associated to the RSA function). In this case, it is possible to
make another reduction from Q−1 (n) to C-POL2(n, `, P, Q) when ` = 1.
Theorem 3. Let eP : N −→ N, eQ : N −→ N and eR : N −→ N and let Gen
be a PDH generator of degree (eP , eQ , eR ). Suppose that, for any k ∈ N and
any (n, p, q, P, Q, R) ∈ Gen(k), Q is a morphism of (Z/nZ)× and P is not a
polynomial in X i for any i > 1. Let τ ∈ NN , ε ∈ [0, 1]N and A be an adversary
that (k, τ (k), ε(k))-solves the C-POL2(n, 1, P, Q) problem for any integer k ∈ N.
There exists an algorithm B that (k, τ 0 (k), ε0 (k))-solves the Q−1 (n) problem such
that
ε0 ≥ εeP − negl and τ 0 ≤ eP · τ + e3P · poly.
Proof. The algorithm A takes as input an instance of the C-POL2(n, 1, P, Q)
problem: for any k ∈ N, given (n, p, q, P, Q, R) ∈ Gen(k), P (a) and Q(b) in
(Z/nZ)× , he will return P (ab) ∈ (Z/nZ)× in time at most τ (k) with probability
at least ε(k).

P Let I be the subset of {1, . . . , eP (k)} of cardinality m > 1 such that P (X) =
i∈I p i X i
, where all the (pi )i∈I are non-zero elements of (Z/nZ)× . Since P is
not a polynomial in X i for any i > 1, the gcd of I is equal to 1.
Given an element Q(b) ∈ (Z/nZ)× , the algorithm B will recover b. It starts by
choosing randomly m couples (sj , tj ) ∈ (Z/nZ)× ×(Z/nZ)× , with j ∈ {1, . . . , m}
so that all the sj and the tj with j ∈ {1, . . . , m} are distinct.
For each j ∈ {1, . . . , m}, B gives the values P (sj ) and Q(btj ) = Q(b)Q(tj )
to the algorithm A which returns the value of P (sj tj b) with probability at least
ε(k)m (since the m queries are independent). After these queries, B gets the m
equations: X
pi (sj tj )i bi = P (sj tj b), for j ∈ {1, . . . , m}
i∈I
with the m unknowns (bi )i∈I . If we denote I := {i1 , i2 , . . . , im }, with 0 < i1 <
i2 < · · · < im = eP , the system of equations is associated with the following
matrix:
pi1 (s1 t1 )i1 pi2 (s1 t1 )i2 · · · pim (s1 t1 )im
 

M := 
 .. .. .. 
. . . 
pi1 (sm tm )i1 pi2 (sm tm )i2 · · · pim (sm tm )im

8
 The method successes if det(M ) ∈ (Z/nZ)× . We focus on the study of
det(M ) 6= 0 (another value of (Z/nZ) \ (Z/nZ)× will reveal the factorisation
of n).
We have
1 ci12 −i1 · · · c1im −i1
 
m
pij cij1  ... ... ..
Y
det(M ) =  .
j=1
1 cim2 −i1 · · · cm
im −i1

where cj := sj tj for j = 1, . . . , m. This last determinant, D, is a generalized

Vandermonde determinant. One can see that
 
Y
D= (cj − ci ) T (c1 , c2 , . . . , cm ),
1≤i<j≤m

where T is a polynomial of degree im − i1 − m + 1 in cm (see [11], for example,

for details on this polynomial). So, if all the (cj )j=1,...,m are distinct, once all the
(sj )j=1,...,m , all the (tj )j=1,...,m−1 have been chosen, less than (im − i1 − m + 1)2
values of tm can make the method fail.
So with standard Gauss elimination, B can recover the (bi )i∈I with O(eP (k)3 )
operations in Z/nZ and m independent queries to the oracle. As gcd(I) = 1,
there exists a linear combination of the elements of I that equals 1, therefore B
can recover b. t
u

Remark 4. If ` > 1, with the method used in the proof, we can only recover the
value of b` . Then, we can recover b by computing gcd(Q(Y ) − Q(b), Y ` − b` ).

3.2 The C-DPOL problem

As shown in Remark 2, the C-DPOL can be rewritten: Given P (a), find Q(a);
and the extraction problem, E-DPOL, can be rewritten: Given P (a) and Q(a),
find a. We then have the following (straightforward) theorem, that generalizes
([23], Theorem 3):

Theorem 4. Let Gen be a PDH generator. We have:

P P C-DPOL P
C-DPOL ∧ E-DPOL ⇐⇒ P −1 =⇒ =⇒ D-DPOL .
E-DPOL

Now let’s try to solve the E-DPOL problem. We know the values of P (a)
and Q(a) and we want to compute the value of a. We have (X − a) divides
gcd(P (X) − P (a), Q(X) − Q(a)) and again, in many cases, we will have an
equality. The complexity of the computation of the gcd is O(e log2 e log log e)
operations in Z/nZ, where e = max(eQ , eP ). If eQ and eP are greater than, say
260 , this method will fail. This method for solving E-DPOL problem allows to
break the D-DPOL problem. In conjunction with Theorem 4, this method also
leads to a reduction from the P −1 (n) problem to the C-DPOL(n, P, Q) problem
in O(e log2 e log log e) operations in Z/nZ.

9
 Again, suppose that the polynomial P induces a morphism of (Z/nZ)× : we
can also make another reduction from C-DPOL(n, P, Q) to P −1 .
Theorem 5. Let eP : N −→ N, eQ : N −→ N and eR : N −→ N and let Gen
be a PDH generator of degree (eP , eQ , eR ). Suppose that, for any k ∈ N and
any (n, p, q, P, Q, R) ∈ Gen(k), P is a morphism of (Z/nZ)× and Q is not a
polynomial in X i for any i > 1. Let τ ∈ NN , ε ∈ [0, 1]N and A be an adversary
that (k, τ (k), ε(k))-solves the C-DPOL(n, P, Q) problem for any integer k ∈ N.
There exists an algorithm B that (k, τ 0 (k), ε0 (k))-solves the P −1 (n) problem such
that
ε0 ≥ εeQ − negl and τ 0 ≤ eQ · τ + e3Q · poly.
t
u
The proof is analogous to that of Theorem 3.

3.3 Relations among the three classes of problems.

It is trivial to see that for all ` ≥ 1,
P
C-POL1(n, P, Q) =⇒ D-POL1(n, P, Q)
⇓P ⇑P
P
C-POL2(n, `, P, Q) =⇒ D-POL2(n, `, P, Q)
In the special case where the polynomial P induces a morphism of (Z/nZ)× ,
as P ((ab)` ) = P (ab)` and P (ab) = P (a)P (b), we have the following theorem.
Theorem 6. If P induces a morphism of (Z/nZ)× ,
P P
C-POL2(n, `, P, Q) ⇐= C-POL2(n, 1, P, Q) ⇐⇒ C-DPOL(n, Q, P ),
P P
D-POL2(n, `, P, Q) =⇒ D-POL2(n, 1, P, Q) ⇐⇒ D-DPOL(n, Q, P ).
t
u
In fact the idea of the proof of the previous theorem can be used to make
a reduction from D-POL1(n, P, Q) to D-DPOL(n, P, Q) if Q is a morphism.
Suppose that we know the values of P (a) and Q(b) and that we want to decide
if an element c equals ab. If this is the case, Q(c) = Q(a)Q(b). So we can submit
P (a) and Q(c)/Q(b) to an oracle of the D-DPOL(n, P, Q) problem to solve the
D-POL1(n, P, Q) problem.
P
As D-DPOL(n, Q, P ) ⇐⇒ D-DPOL(n, P, Q), we have proved the following
theorem:

Theorem 7. If P or Q induces a morphism of (Z/nZ)× ,

P
D-POL1(n, P, Q) ⇐= D-DPOL(n, P, Q).

t
u

10
4 IND-CPA-secure public key cryptosystems
Let f be a trapdoor permutation and g be another function with the following
pseudo-randomness property: the distribution of (f (k), g(k)) induced by a ran-
dom k cannot be distinguished (by a polynomially bounded adversary) from a
randomly distributed (f (k), r). Then the encryption E(m) = (f (k), g(k) ⊕ m) is
semantically secure (cf. [23, 7]). In this section, we revisit this approach by using
for the function g a trapdoor permutation.

Following this paradigm, we define three new encryption schemes where the
public key is (n, P, Q) or (n, P, Q, R) and the corresponding secret key is P −1
or (P −1 , Q−1 ), with the notations of the previous section (i. e., n, P , Q, R
correspond to the output of a PDH generator for a given security parameter).
To encrypt a message m ∈ (Z/nZ)× , a user picks at random r ∈ (Z/nZ)× (or
2
(r0 , r1 ) ∈ (Z/nZ)× ) and uses one of the three following encryption functions:


Function 1: (m, r0 , r1 ) 7→ P (r0 ), Q(r1 ), mR(r0 , r1 )


Function 2: (m, r) 7→ P (r), mQ(r)

Function 3: (m, r) 7→ P (mr), Q(r−1 )

To decrypt, a user uses his knowledge P −1 or (P −1 , Q−1 ) to recover r or

(r0 , r1 ) then m.

Theorem 8. The previous schemes are One-Way and semantically secure under
Chosen Plaintext Attack relative to the following problems:

Encryption function One-Wayness Semantic security

Function 1, R(X, Y ) = XY C-POL1(n, P, Q) D-POL1(n, P, Q)


Function 1, R(X, Y ) = P (XY )` C-POL2(n, `, P, Q) D-POL2(n, `, P, Q)
Function 2 C-DPOL(n, P, Q) D-DPOL(n, P, Q)
Function 3 C-POL1(n, P, Q) D-POL1(n, P, Q)(∗)
(∗)
If P or Q is a morphism.

Proof (Sketch). For the first three schemes, the proof relies on the analysis done
in [7]. The fourth encryption scheme mixes the one-time-pad masking approach
used above with the trapdoor property of the function induced by P . The se-
mantic security of this scheme can be rewritten: there is no polynomial algo-
rithm that can choose a value m ∈ (Z/nZ)× and then recognize the couples
(P (a), Q(b)) ∈ (Z/nZ)× × (Z/nZ)× , satisfying ab = m. It’s easy to see that if
P or Q is a morphism, this assertion is equivalent to the intractability of the
D-POL1(n, P, Q) decision problem. t
u

11
Efficiency considerations. From the encryption functions above, we design
five practical cryptosystems, three with Function 1, by setting R(X, Y ) = XY ,
R(X, Y ) = P (XY ) and R(X, Y ) = P (XY )` with ` > 1; one with Function 2;
and one with Function 3.

For the polynomial P we use the LUC polynomial Ve (X, 1) and for the poly-
nomial Q, the RSA polynomial of the same degree, i. e., Q(X) = X e . In order
to compare the efficiency of these schemes, we use an RSA modulus of 1024 bits
and we adjust the parameter e (and `) in order to achieve a 280 security. For this,
we use Theorem 8 and the analysis done in Section 3. These new cryptosystems
and the corresponding values of the parameters are given in the following table.

Scheme Ciphertext Public keys

e
Scheme 1 Ve (ro , 1), r1 , mr0 r1 e = 267 + 3.
Scheme 2 Ve (ro , 1), r1 e , mVe (r0 r1 ) e = 223 + 9.


Scheme 3 Ve (ro , 1), r1 e , mVe (r0 r1 )` e = 5 and ` = 231 + 65
Scheme 4 Ve (r, 1), mre e = 267 + 3.
Scheme 5 Ve (mr, 1), r−e e = 267 + 3.

Now, we compare the concrete efficiency of our new schemes with the one
from [7, 23]. For the D-RSA scheme of [23] we use e = 267 + 3 and for the scheme
of Catalano et al. ([7]), we use e = 216 + 1. The unity of complexity is the cost
of a multiplication modulo n. We use the following estimations: a multiplication
modulo n2 costs as much as three multiplications modulo n, an inversion costs
10 multiplications, a multiplication modulo p costs 1/3 multiplication modulo
n and a multiplication modulo p2 costs one multiplication modulo n. We use
the Chinese Remainder Theorem for the decryption process of all schemes. The
comparison is done in the following table.

Scheme D-RSA Catalano Scheme 1 Scheme 2 Scheme 3 Scheme 4 Scheme 5

Input 1024
Output 2048 3072 2048
Encryption 139 52 205 119 44 204 214
Decryption 567 570 1204 1234 1228 736 1196

One can remark that the new cryptosystems appear to be quite practical. If
the decryption phase of these schemes (except Scheme 4) suffers from the cost
of the simultaneous inversions of the LUC and RSA function, the encryption
process is very fast and Scheme 3 (which is an improvement of Scheme 2) can

12
encrypt faster than the D-RSA and Catalano et al. cryptosystems. Schemes 1
and 5 have a similar complexity and are the most efficient semantically secure
cryptosystems with One-Wayness proved equivalent to the problem of inverting
simultaneously RSA and LUC.

5 IND-CCA2-secure public key cryptosystems in the ROM

In this section, we apply standard techniques to obtain chosen ciphertext se-

curity (from these new primitives) in the random oracle model formalized by
Bellare and Rogaway in 1993 [5], in which cryptographic protocols are designed
and proved secure under the additional assumption that publicly available func-
tions that are chosen truly at random exist. These random oracles can only be
accessed in a black-box way, by providing an input and obtaining the corre-
sponding output. A similar method is used in [23] for instance.
Let h be a cryptographic hash function (seen like a random oracle). With
the previous notations, the public key is now (n, P, Q, h) or (n, P, Q, R, h), and
the corresponding secret key is P −1 or (P −1 , Q−1 ). To encrypt a message m of
2
(Z/nZ)× , a user picks at random r ∈ (Z/nZ)× (or (r0 , r1 ) ∈ (Z/nZ)× ) and
uses one of the three following encryption functions:

Function 1: (m, r0 , r1 ) 7→ (P (r0 ), Q(r1 ), mR(r0 , r1 ), h(m||r0 ||r1 ))

Function 2: (m, r) 7→ (P (r), mQ(r), h(m||r))

Function 3: (m, r) 7→ (P (mr), Q(r−1 ), h(m||r))

The decryption process is done as in Section 4 except that the message is

returned only if the hash value is correct.

Theorem 9. The previous schemes are semantically secure against Adaptive

Chosen Ciphertext Attack in the Random Oracle Model relative to the following
problems:

Encryption function Semantic security

Function 1, R(X, Y ) = XY D-POL1(n, P, Q)


Function 1, R(X, Y ) = P (XY )` D-POL2(n, `, P, Q)
Function 2 D-DPOL(n, P, Q)
Function 3 D-POL1(n, P, Q)(∗)

(∗)
If P or Q is a morphism.

Proof (Sketch). The proof is standard. The random oracle model is simulated in
the standard way and the instance of the decision problem is embedded in the
challenge ciphertext without updating the hash table. The hash table is used to

13
simulate the decryption oracle: when the adversary makes a decryption query,
the reduction looks in this table to get the pair (m, r) or the triple (m, r0 , r1 )
corresponding to the last element of the ciphertext. It returns the message m
only if the encryption of m with the value r or the pair (r0 , r1 ) produces the
same ciphertext; otherwise, it returns the reject symbol.
The simulation of the random oracle is perfect and the probability that a
decryption query is incorrect is exponentially small in the size of the hash values.
Details can be found in [23], for instance. t
u

Remark 5. As done in [23], it is also possible to modify our schemes in order to

make them IND-CCA2 in the random oracle model relative to the correspond-
ing computational problems. This transformation permits to use smaller degree
polynomials P and Q in the encryption procedure but unfortunately the result-
ing schemes are IND-CPA-secure only in the Random Oracle Model.

6 IND-CCA1-secure public key cryptosystems in the

standard model

6.1 Damgård’s Elgamal

Let G be an additive group of prime order q, let k be the bit size of the elements
of G and let P be a generator of G. In 1991, Damgård [10] presented a simple
variant of the Elgamal encryption scheme in G. In his proposal, Alice publishes
two public keys A1 = [a1 ] · P and A2 = [a2 ] · P and keeps secret their discrete
logarithms a1 and a2 . When Bob wants to send privately a message m ∈ {0, 1}k
to Alice, he picks uniformly at random an integer r ∈ [[1, q −1]] and transmits the
triple (Q1 , Q2 , C) where Q1 = [r] · P , Q2 = [r] · A1 and C = m ⊕ ([r] · A2 ). When
she receives the ciphertext (Q1 , Q2 , C), Alice checks whether the equality Q2 =
[a1 ]·Q1 holds: if it is the case, she retrieves the message m, as m = C ⊕([a2 ]·Q1 ),
otherwise she rejects the ciphertext.
Damgård proved that if the DDH problem is hard in G, then this scheme is
IND-CCA1-secure, if we assume the so-called knowledge-of-exponent assumption
[22]. Intuitively this assumption states that, without the knowledge of a1 , the
only way to generate couples (Q1 , Q2 ) ∈ G2 , satisfying Q2 = [a1 ] · Q1 , is to
choose an integer r ∈ [[1, q − 1]] and to compute Q1 = [r] · P and Q2 = [r] · A1 .
The knowledge-of-exponent assumption is a strong and non-standard one,
but to date it has not been proven false. It has been criticized for assuming
one can perform ”reverse engineering” of an adversary. It should therefore be
considered with caution, all the more since Bellare and Palacio [3] showed that
a somehow similar assumption used in [16] is false.
The function that maps r to ([r] · P, [r] · A1 ) is what Damgård called a One-
Way function with sparse image (i. e., only a very small fraction of G2 is in its
image and it seems computationally infeasible to sample an element of this set
without the knowledge of its preimage). Damgård predicts that such One-Way

14
functions would be extremely useful in other contexts. His proposal has indeed
found applications in identification and zero-knowledge protocols ([3, 4, 1, 16]),
but it has proved to be extremely difficult to find other examples that can be
reduced to reasonable assumptions. The purpose of the next paragraph is to
explain how our approach can be extended in order to propose such a function.

6.2 Knowledge of preimage assumption

Let Gen be a PDH generator. Suppose we are given (n, P1 , P2 , R, y, z) an ele-
ment of N × Z/nZ[X]3 × N output by Gen and want to output a pair (x, y) of
((Z/nZ)× )2 , such that P1−1 (x) = P2−1 (y). One way to do this is to pick some
a ∈ (Z/nZ)× and let x = P1 (a) and y = P2 (a). Intuitively, the knowledge of
preimage assumption (KPA) can be viewed as saying that this is the “only” way
to produce such a pair.
There are many ways in which the formulation can be varied to capture the
KPA. We will say that for any PPTM outputting a pair (P1 (a), P2 (a)), there is
an ”extractor” than can return the preimage a. For our purposes, it is necessary
to allow the adversary to be randomized as in [1] (in that case, it is important
that the extractor gets the coins of the adversary as an additional input, since
otherwise the assumption is clearly false).
Definition 5. Let Gen be a PDH generator and let A and A be two PPTM’s.
We consider the following random experiments, where k ∈ N is a security pa-
rameter:

Experiment Expkpa
Gen,A,A
(k)
R
(n, p, q, P1 , P2 , R) ←
− Gen(k)
r
(x, y) ←− A(n, P1 , P2 )
r
α← − A(n, P1 , P2 )
Return 1 if (x, y) ∈ ((Z/nZ)× )2 , ∃a ∈ (Z/nZ)× s.t.
(x, y) = (P1 (a), P2 (a)) and a 6= α,
Return 0 otherwise

We define the advantage of A relative to A in these experiments via

h i
Advkpa
Gen,A,A
(k) = Pr Exp kpa
Gen,A,A
(k) = 1 .

Let ε ∈ [0, 1]N ,

1. A is a ε-kpa-extractor for A if for all positive integers k,

Advkpa
Gen,A,A
(k) ≤ ε(k) .

2. We say that the knowledge-of-preimage assumption holds for Gen if for every
PPTM A, there exists a PPTM A and a negligible function ε such that A
is a ε-KPA-extractor for A.

15
3. We say that the strong knowledge-of-preimage assumption (SKPA) holds for
Gen if there exists a PPTM E such that for every PPTM A, there exists a
negligible function ε such that E is a ε-KPA-extractor for A.

6.3 New construction

Following Damgård’s technique, we define a new encryption scheme where the
public key is (n, P1 , P2 , Q) where P1 , P2 and Q are One-Way permutations
of (Z/nZ)× and the corresponding secret key is P −1 . To encrypt a message
m ∈ (Z/nZ)× , a user picks at random r ∈ (Z/nZ)× and uses the following
encryption function:


Function 1: (m, r) 7→ P1 (r), P2 (r), m · Q(r)

When he receives a ciphertext (x, y, C), a user uses his knowledge of P −1 to

check whether the equality P2 (P1−1 (x)) = y holds: if it is the case, he retrieves
the message m, as m = C/Q(P1−1 (x)), otherwise he rejects the ciphertext.

Theorem 10. The previous schemes is One-Way and semantically secure under
non-adaptive Chosen Ciphertext Attack relative to the following problems:

Encryption function One-Wayness Semantic security

Function 1 C-DPOL(n, P1 , Q) D-DPOL(n, P1 , Q) under SKPA

Proof (Sketch). Theorem 8 insures that this scheme is one-way assuming the
intractability of the C-DPOL(n, P1 , Q) problem and semantically secure under
chosen-plaintext attacks if the D-DPOL(n, P1 , Q) problem is intractable. Fol-
lowing [4], it is straightforward to see that the scheme is plaintext-aware (PA1)
assuming the strong knowledge of preimage assumption and Theorem 1 from this
paper implies that our new scheme is IND-CCA1-secure if the D-DPOL(n, P1 , Q)
problem is intractable and the strong knowledge of preimage assumption holds
for the underlying PDH generator. t
u

If one sets P1 (X) = X e , P2 (X) = (X + 1)e and Q(X) = (X + 2)e with

sufficiently large e in order to make the D-DPOL problem infeasible in reasonable
time (see the analysis of subsection 3.2 and section 4) one obtains an IND-CCA1-
secure system faster than the one of Damgård.

7 Conclusion
We have defined new algorithmic problems, derived from the RSA assumption,
and discuss their computational difficulty. We have applied them to design pub-
lic key encryption protocols with IND-CPA-security and IND-CCA2-security in
the random oracle model under the assumption of the intractability of their
decisional variants.

16
 The ideas developed in this extended abstract can be used to design encryp-
tion schemes with higher security. For instance, by using the approach proposed
by Cramer and Shoup in [9], we have been able to design a concrete encryption
scheme that is proven IND-CCA2-secure in the standard model based on the
difficulty of the new algorithmic problems. Details will appear elsewhere.

References

1. B. Barak, Y. Lindell, and S. Vadhan, Lower Bounds for Non-Black-Box Zero

Knowledge., Proceedings of the 44th IEEE Symposium on Foundations of Com-
puter Science (FOCS 2003) (M. Sudan, ed.), IEEE Computer Society, 2003,
pp. 384–393.
2. M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, Relations Among Notions
of Security for Public-Key Encryption Schemes., in Krawczyk [18], pp. 26–45.
3. M. Bellare and A. Palacio, The Knowledge-of-Exponent Assumptions and 3-
Round Zero-Knowledge Protocols., Advances in Cryptology - Crypto 2004 (M. K.
Franklin, ed.), Lect. Notes Comput. Sci., vol. 3152, Springer, 2004, pp. 273–289.
4. M. Bellare and A. Palacio, Towards Plaintext-Aware Public-Key Encryption With-
out Random Oracles., Advances in Cryptology - Asiacrypt 2004 (P. J. Lee, ed.),
Lect. Notes Comput. Sci., vol. 3329, Springer, 2004, pp. 48–62.
5. M. Bellare and P. Rogaway, Random Oracles are Practical: A Paradigm for Design-
ing Efficient Protocols., Proceedings of the First ACM Conference on Computer
and Communications Security (D. Denning, R. Pyle, R. Ganesan, R. Sandhu, and
V. Ashby, eds.), ACM Press, 1993, pp. 62–73.
6. G. Castagnos, An efficient probabilistic public-key cryptosystem over quadratic
fields quotients., Finite Fields Appl. 13 (2007), no. 3, 563–576.
7. D. Catalano, R. Gennaro, N. Howgrave-Graham, and P. Q. Nguyen, Paillier’s
cryptosystem revisited., Proceedings of the 8th ACM Conference on Computer and
Communications Security, 2001, pp. 206–214.
8. D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter, Low-Exponent RSA with
Related Messages., Advances in Cryptology - Eurocrypt’96 (U. M. Maurer, ed.),
Lect. Notes Comput. Sci., vol. 1070, Springer, 1996, pp. 1–9.
9. R. Cramer and V. Shoup, Design and Analysis of Practical Public-Key Encryption
Schemes Secure Against Adaptive Chosen Ciphertext Attack., SIAM J. Comput.
33 (2003), no. 1, 167–226.
10. I. B. Damgård, Towards Practical Public Key Systems Secure Against Chosen Ci-
phertext Attacks., Advances in Cryptology - Crypto’91 (J. Feigenbaum, ed.), Lect.
Notes Comput. Sci., vol. 576, Springer, 1992, pp. 445–456.
11. S. De Marchi, Polynomials arising in factoring generalized Vandermonde determi-
nants: an algorithm for computing their coefficients., Math. and Comput. Mod-
elling 34 (2001), no. 3–4, 271–281.
12. N. Demytko, A New Elliptic Curve Based Analogue of RSA., Advances in Cryp-
tology - Eurocrypt’93 (T. Helleseth, ed.), Lect. Notes Comput. Sci., vol. 765,
Springer, 1994, pp. 40–49.
13. W. Diffie and M. E. Hellman, New Directions in Cryptography., IEEE Trans. Inf.
Theory 22 (1976), 644–654.
14. J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge Univer-
sity Press., 1999.

17
15. S. Goldwasser and S. Micali, Probabilistic Encryption., J. Comput. Syst. Sci. 28
(1984), 270–299.
16. S. Hada and T. Tanaka, On the Existence of 3-Round Zero-Knowledge Protocols.,
in Krawczyk [18], pp. 408–423.
17. M. Joye and J. Quisquater, Efficient computation of full Lucas sequences., Elec-
tronics Letters 32, 6 (Mar. 1996), 1996, pp. 537–538.
18. H. Krawczyk (ed.), Advances in Cryptology - Crypto ’98, 18th Annual Inter-
national Cryptology Conference, Santa Barbara, California, USA, August 23-27,
1998, Proceedings, Lect. Notes Comput. Sci., vol. 1462, Springer, 1998.
19. R. Lidl, G. L. Mullen, and G. Turnwald, Dickson Polynomials., Pitman Mono-
graphs and Surveys in Pure and Applied Mathematics, vol. 65, Longman Scientific
& Technical, 1993.
20. W. B. Müller and R. Nöbauer, Some remarks on public-key cryptosystems., Sci.
Math. Hungar. 16 (1981), 71–76.
21. W. B. Müller and R. Nöbauer, Cryptanalysis of the Dickson-scheme., Proc. of
Eurocrypt’ 85, Springer-Verlag, 1986, pp. 50–61.
22. M. Naor, On Cryptographic Assumptions and Challenges., Advances in Cryptology
- Crypto 2003 (D. Boneh, ed.), Lect. Notes Comput. Sci., vol. 2729, Springer, 2003,
pp. 96–109.
23. D. Pointcheval, New Public Key Cryptosystems Based on the Dependent-RSA Prob-
lems., Advances in Cryptology - Eurocrypt’99 (J. Stern, ed.), Lect. Notes Com-
put. Sci., vol. 1592, Springer, 1999, pp. 239–254.
24. R. L. Rivest, A. Shamir, and L. M. Adleman, A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems., Comm. ACM 21 (1978), 120–126.
25. J. Schwenk and K. Huber, Public key encryption and digital signatures based on
permutation polynomials., Electronics Letters 34, 8 (Apr. 1998), 1998, pp. 759–760.
26. P. Smith and M. J .J Lennon, LUC: A new public key system, Proc. of the Ninth
IFIP Int. Symp. on Computer Security (1993), 1993, pp. 103–117.

18