n’1

m

vi i mod p.

c=

i=0

p’1

By computing a = c mod p, one gets

2

(’1)mi mod p,

a=

vi ∈QRp

which in turn leaks the value vi ∈QRp mi mod 2. This partial information leak-

age can also be applied to other small factors of (p’1). Therefore, [NS97] advised

to use a strong prime p, and to spare one mi to compensate the leakage (in other

words, they simply make vi ∈QRp mi mod 2 constant).

In our variants, it is not as simple to use same attacks. Indeed, in any given

prime pack, one expects to have some primes in QRp and others in QRp . For ex-

ample, with the variant of Section 3, getting c = encryption(m) = n’1 vγi+mi +1

i=0

p’1

mod p, the attacker may compute a = c mod p. As

2

a= (’1) mod p,

vγi+mi +1 ∈QRp

this reveals the parity of the number of message digits mi whose corresponding

primes are in QRp . Even if leakage is less precise than in the ns case, we still

recommend the use of a strong prime (and residue value compensation) with our

variants.

Can a Reduction from Attacking ns to Attacking our Variants Ex-

ist?. At a ¬rst glance, it might seem that reductions between ns and our variants

exist: indeed, one may hope that access to a decryption oracle D of one of our

schemes would yield an ns decryption oracle D .

However, a simple observation shows that this is certainly impossible: in our

case, the public key is longer and contains more elements related to the secret key.

Therefore, from an ns public key and a challenge, it may certainly be possible

to build a challenge for our variants, but there is little hope that one might

reconstruct the entire public key.

Thus, we have no formal proof that the security of the original ns is equivalent

to the security of the variants proposed herein.

6 Further Research

We conclude this paper with a couple of interesting combinatorial problems

whose solution might further improve the ns™s bandwidth.

Setting = 1, not all collections of γn integers allow encoding γ n combina-

tions. Let S = {S1 , ..., Sn } be n integer-sets, each of size γ and denote by Si [j]

the j-th element of Si . We call S an encoder if its Si -s can be used as a collection

of packs encoding exactly n log2 γ bits, or, in other words, if no collisions in the

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

integer sub-products of S occur. Improving the ns consists in ¬nding “better”

encoders.

To compare encoders, we use their head-products, namely:

n

h(S) = max (Si [j])

j

i=1

Head-products lower-bound the modulus p and hence “measure” bandwidth.

We saw that when the Si [j] are the ¬rst small primes, S is an encoder and

h(S) = n piγ (Section 3). We also saw that when the smallest element in

i=1

each Si is one, the resulting S is still an encoder whose head-product is h(S) =

n

i=1 pi(γ’1) (Section 3.4).

This gives raise to interesting combinatorial problems such as ¬nding algo-

rithms for e¬ciently testing that a given S is an encoder, or ¬nding algorithms for

constructing optimal encoders, i.e. encoders featuring a minimal head-product

(and consequently a maximal bandwidth).

As an example, a (rather ine¬cient) computer-aided exploration for n = 3

and γ = 4 discovered the optimal encoder S whose h(S) = 4 — 8 — 13 = 416:

S1 [1] S2 [1] S3 [1]

= 1 = 1 = 1

pack 2

pack 3

pack 1

S1 [2] S2 [2] S3 [2]

= 2 = 5 = 9

S1 [3] S2 [3] S3 [3]

= 3 = 7 = 11

S1 [4] S2 [4] S3 [4]

= 4 = 8 = 13

Interestingly, this encoder contains primes, but also powers of primes. Moreover,

throughout our search, non-optimal encoders containing composite integers (such

as 6) were found as well.

Decoding messages encoded with such complicated S-s might not always be

straightforward as in such atypical encoders, decoding is based on impossibilities

of certain factor combinations rather than on the occurrence of certain factors

in the product.

The above questions also generalize to packs of rationals.

References

[FO99] Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric

encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666,

pp. 537“554. Springer, Heidelberg (1999)

[FO00] Fujisaki, E., Okamoto, T.: How to enhance the security of public-key encryp-

tion at minimum cost. IEICE Transaction of Fundamentals of Electronic

Communications and Computer Science E83-A(1), 24“32 (2000)

[FSW02] Fouque, P.-A., Stern, J., Wackers, J.-G.: Cryptocomputing with rationals.

In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 136“146. Springer, Hei-

delberg (2003)

[GM84] Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer

and System Sciences 28(2), 270“299 (1984)

[NS97] Naccache, D., Stern, J.: A new public-key cryptosystem. In: Fumy, W.

(ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 27“36. Springer, Heidelberg

(1997)

Linear Bandwidth Naccache-Stern Encryption 339

[SW86] Stanton, D., White, D.: Constructive combinatorics. Springer, New York

(1986)

[Val91] Vall´e, B.: Gauss™ algorithm revisited. Journal of Algorithms 12(4), 556“572

e

(1991)

Computing R

A ,γ

In this appendix, we recall how we evaluate the number, denoted R ,γ , of di¬erent

γ-tuples {d1 , . . . , dγ } such that 0 ¤ dk and k dk ¤ .

γ+i’1

is the number of sequences of γ integers whose sum equals i. Therefore,

i

we have:

γ+i’1

R ,γ = .

i

i=0