1 Introduction

The Naccache-Stern cryptosystem (ns), introduced a decade ago in [NS97], is a

public-key cryptosystem based on the following problem:

n’1

given p, c and a set {pi }, ¬nd a binary vector x such that c = pxi mod p.

i

i=0

Trivially, if the pi -s are relatively prime and much smaller than p, the above

problem can be solved in polynomial time by factoring c in N.

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

c Springer-Verlag Berlin Heidelberg 2008

328 B. Chevallier-Mames, D. Naccache, and J. Stern

A trapdoor is obtained by extracting a secret (s-th) modular root of each pi

√

and publishing these roots, denoted vi = s pi mod p. By raising a product of

such roots to the s-th power, each vi shrinks back to a much smaller pi and x

can be found by factoring the result in N.

Unfortunately, no security proofs linking ns™s security to standard complex-

ity assumptions are known, but at the same time, no e¬cient chosen-plaintext

attacks against ns™s one-wayness are known either.

More formally, let p be a large public prime1 and denote by n the largest

integer such that:

n’1

p> pi where pi is the i-th prime (start from p0 = 2).

i=0

The secret-key 0 < s < (p ’ 1) is a random integer such that gcd(p ’ 1, s) = 1

and the public-keys are the n roots:

√

vi = s pi mod p.

n’1 n’1

2i mi , where mi ∈ {0, 1}, is encrypted as c = m

vi i mod p

A message m =

i=0 i=0

and recovered by:

§ «

n’1

2i © gcd(pi , cs mod p) ’ 1⎭.

—

m=

pi ’ 1

i=0

Denoting by ln(x) natural logarithms and by log(x) base-2 logarithms, it is

easy to see that ns™s bandwidth is sublinear: As pi ∼ i ln i, we have

n

ln p ∼ ln pi ∼ n ln n ’ ln ln p ∼ ln n,

i=0

which in turn gives:

ln p log p

n∼∼ .

ln ln p log log p

In a typical setting, a 2048-bit p corresponds to a sixteen kilobyte public-key

and allows encrypting 233-bit messages.

[NS97] also describes a variant depending on a parameter ∈ N. Here, p is

such that

n’1

p> pi .

i=0

n’1

( + 1)i mi , expressed in base ( + 1) (here mi ∈ [0, ]), is encrypted as

m=

i=0

n’1

m

vi i mod p,

c=

i=0

1

For technical reasons, p must be a safe prime, cf. to Sections 2.4 of [NS97] or 5.

Linear Bandwidth Naccache-Stern Encryption 329

and decryption is straightforwardly modi¬ed. In this paper, we refer this version

as the “( + 1)-base variant”.

The goal of this work is to improve the scheme™s bandwidth using more so-

phisticated arithmetic encoding approaches. Indeed, 233-bit plaintexts are often

insu¬ciently large in practice to include the message, the randomizer (typically

128 bits) and the redundancy (at least 160 bits, or better 256 bits) that one needs

to use chosen-ciphertext secure transformations such Fujisaki and Okamoto™s

[FO99, FO00].

In the next section, we propose a technique based on modular fractions that

1.58 for binary-message ns.2 Section 3 de-

multiplies bandwidth by log2 3

scribes a new message encoding technique that dramatically increases bandwidth

(to become linear in log p). Section 4 extends the previous idea to ( + 1)-base

ns, thereby further increasing bandwidth. Final ¬gures are given in Section 4.3.

In Section 5, we examine the security of the proposed improvements. Finally,

Section 6 describes combinatorial problems whose solutions might yield even

more e¬cient ns variants.

2 Fractional Message Encoding

In this section, we show that using signed message bits allows to increase band-

width at no cost. Consider a message represented in a signed binary

notation, i.e.,

n’1

where mi ∈ {’1, 0, 1}

2 i mi

m=

i=0

and an unchanged encryption procedure. During decryption, the receiver recovers

a u such that:

§

⎪a = pi

⎨

a mi =1

u = cs = mod p, with and gcd(a, b) = 1.

⎪b =

b © pi .

mi =’1

The following theorem shows that, given u, one can recover a and b e¬ciently

using Gauss™s algorithm for ¬nding the shortest vector in a two-dimensional

lattice [Val91].

Theorem 1 ([FSW02]). Let a, b ∈ Z such that |a| ¤ A and 0 < b ¤ B. Let

p be a prime such that 2AB < p. Let u = a/b mod p. Then given {A, B, u, p},

one can recover {a, b} in polynomial time.

√

p ’ 1, we have that 2AB < p. If we assume in addition that

Taking A = B =

m was such that 0 ¤ a ¤ A and 0 < b ¤ B, we can recover a and b from s in

polynomial time. And by testing the divisibility of a and b by the small primes

pi , the receiver can eventually recover m as before.

2

This factor becomes log1+ (2 + 1) for the ( + 1)-base variant.

330 B. Chevallier-Mames, D. Naccache, and J. Stern

But what happens if |a| > A or b > B?

n’1

To tackle this case too, let us tweak the de¬nition of p to p > 2w — pi ,

i=0

for some small integer w ≥ 1 (we suggest to take w = 50), and de¬ne a ¬nite

sequence {Ai , Bi } of integers such that:

p’1

Ai = 2wi and Bi = .

2Ai

For all i > 0, we have that ab < 2Ai Bi < p. Moreover, there must exist at

least one index i such that 0 ¤ a ¤ Ai and 0 < b ¤ Bi . Then using the algorithm