9) =

71 — 50 — 30 — 20

unrank( {1, 0, 0, 0}

10) =

71 — 50 — 30 — 21

unrank( {1, 0, 0, 1}

11) =

71 — 50 — 31 — 20

unrank( {1, 0, 1, 0}

12) =

71 — 51 — 30 — 20

unrank( {1, 1, 0, 0}

13) =

72 — 50 — 30 — 20

unrank( {2, 0, 0, 0}

14) =

√ √

m0 = 12 will be encrypted as encryption(12) = s 3 — s 7 = v2 — v4 mod p.

Decryption recovers 20 — 31 — 50 — 71 by exponentiation and determines that

m0 = rank({1, 0, 1, 0}) = 12.

The bandwidth improvement stems from the fact that we encrypt log(15)

bits where the ( + 1)-base variant only encrypts log(3). In other words, the

prime-packing idea ¬ts particularly well to the ( + 1)-base system.

Also, as is all practical instances γ+ will remain moderate (typically less

than one hundred), functions rank(·) and unrank(·) can be implemented as simple

lookup tables rather than as full-¬‚edged constructive combinatorial algorithms.

4.2 Formal Description

Let us describe now the scheme formally. Let ≥ 1 and γ be two integer pa-

rameters5 and consider n packs containing γ small primes each (the primes start

from p1 = 2). We pick a prime p such that:

n

pγi < p.

i=1

4

The attentive reader would rightly note that there are actually more pi products

smaller than p. This is true for very small primes in the ¬rst packs, but when one

¡

considers packs whose minimal and maximal pi -s are roughly equivalent in size, the

number of products quickly tends to γ+ .

5

ns corresponds to the case {γ, } = {1, 1} and the ( + 1)-base variant corresponds

to γ = 1.

Linear Bandwidth Naccache-Stern Encryption 335

As there are6 shows that there are γ+ di¬erent γ-tuples {d1 , . . . , dγ } such

that 0 ¤ dk and k dk ¤ , we de¬ne unrank(·) as an invertible function mapping

integers in [0, γ+ ’ 1] to {d1 , . . . , dγ }-tuples.

n’1 i

, i.e., m =

γ+ γ+

To encrypt a message expressed in base mi with

i=0

mi ∈ [0, ’ 1], one computes:

γ+

γ

n’1

c = encryption(m) = vγi+j di,j mod p

i=0 j=1

where {di,1 , . . . , di,γ } = unrank(mi ).

To decrypt c, the receiver simply factorizes cs mod p in N and recovers each

mi by:

mi = rank({di,1 , . . . , di,γ }).

4.3 Bandwidth Considerations

The table below shows that the variant described in this section features a better

bandwidth and smaller public-keys than the basic prime-packs encoding of Section

3. Data was generated for several public-key sizes (namely 10, 20, 50, and 500

kilobytes) and a 2048-bit p. The ¬rst line {γ, } = {1, 1} is the original ns:

γ+

γ+ ¡ log

plaintext bits = n log public key size = γn log p information rate= n

γ n log p

1 1 233 233 bits 59 kilobytes 0.11

8 66 5 169 bits 10 kilobytes 0.08

16 54 5 255 bits 20 kilobytes 0.12

64 73 3 398 bits 48 kilobytes 0.19

512 38 4 781 bits 512 kilobytes 0.38

128 10 16 781 bits 512 kilobytes 0.38

Note that encryption is very fast, since it requires · n multiplications e.g. in

the 781-bit setting an encryption claims 152 multiplications.

5 Security Considerations

As stressed previously, no security proof is known for the original ns, and we

have no hope nor claim that our modi¬cations may supplement this lack. In

this section we nonetheless recall certain security-related facts, some of which

are already known since [NS97], for the clarity and the self-containment of this

paper.

6

Cf. to Appendix A for a proof.

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

5.1 What Security Can Be Attained?

The most basic security property expected from any encryption scheme is one-

wayness (OW): an attacker should not be able to recover the plaintext given a

ciphertext. We capture this notion more formally by saying that for any adver-

sary A, success in inverting the e¬ect of encryption must occur with negligible

probability.

Semantic Security (IND) [GM84], also known as indistinguishability of en-

cryptions captures a stronger privacy notion. The adversary A is said to break

IND when, after choosing two same-length messages m0 and m1 , he can decide

whether a given ciphertext corresponds to m0 or to m1 . An encryption scheme is

said to be semantically secure (or indistinguishable) if no probabilistic algorithm

can break IND.

The original ns cryptosystem, or the variants presented in Sections 2, 3 or 4

can not ensure indistinguishability, since they are by nature deterministic. The

hope however is that there might be one-way. To achieve full-security with our

variants (or with ns), one can use generic transformations such as [FO99, FO00]:

nevertheless, as there are no formal reductions from a standard hard problem to

an attack of ns-type schemes (be these the original ns or the variants proposed

herein), the application of these generic rules cannot possibly achieve a provably

security, but only give empirical security arguments.

5.2 Security Arguments

Our schemes can be broken if one solves the discrete-logarithm. It

is clear that a discrete-logarithm oracle will totally break the ns scheme or the

variants presented in this paper. Indeed, to this aim, it is su¬cient to ask the

oracle for the discrete-logarithm of p1 in base v1 , which is actually the secret key

s. Even if the primes are permuted or made secret, the fact that primes must be

small makes them easily guessable.

Larger message Space may Make ns-type Problems Harder. As one

can see, the schemes presented in this paper are ” as is the original ns ”

multiplicative knapsacks. Even if no e¬cient algorithm solving this problem

is known, one must ensure that a brute-force attack consisting in testing all

products is impossible. More precisely, getting back the arguments put forward

in Section 2.3 of [NS97], the message space must at least exceed 160 bits, if

one requires an 80-bit security, or 256 bits, if one wants 128-bit security. In

this perspective, our bandwidth improvements indirectly improve security by

easing the attainment of a larger message space. However, we cannot claim that

the variants are stronger, as bandwidth improvements come along with larger

public-keys, which ” at least in the information theoretic sense ” give more

information to the attacker about the secret key.

Small Factors of (p ’ 1). As stressed in Section 2.4 of [NS97], the small

factors of (p ’ 1) are important. Denote by QRp and QRp the quadratic and

non-quadratic residues modulo p respectively. Let