recover m. The problem is that we have just lost the guarantee that such an

{a, b} is unique. Namely, we could in theory hit another {a , b } whose modular

ratio gives the same u, for some other index i = i. But we expect this to happen

with negligible probability for large enough w.

Senders wishing to eliminate even the negligible probability that decryption

will produce more than one plaintext can still simulate the decryption™s Gaussian

phase and, in case, re-randomize m until decryption becomes unambiguous.

The e¬ect of this optimization is noteworthy as for the price of a constant

increase (e.g. 50 bits) in p, bandwidth is multiplied by a factor of log2 3.

It is important to underline that while di¬erent signed binary representations

of a given m exist (e.g. 101 = 011 i.e. 22 ’ 20 = 21 + 20 ), the above procedure

will recover the exact encoding used to encrypt m and not an equivalent one.

Note that as > 1 is used in conjunction with this technique (i.e., in the

( + 1)-base variant), bandwidth improvement tends to one bit per prime as

grows. Namely, fractional encoding increases bandwidth from n log(1 + ) to

n log(1 + 2 ).

3 Small Prime Packing

Let the integer γ ≥ 2 be a system parameter. We now group the small primes

pi into n packs containing γ small primes each.3 That is, the ¬rst pack will

contain primes p1 to pγ , the second pack will include primes pγ+1 to p2γ etc. As

previously, the pi -s are indexed in increasing order.

We also update the condition on the large prime p to:

n

pγi < p.

i=1

In other words, we do not request p to be larger than the product of all the

small primes. Instead, we only request p to be larger than the product of the

largest representatives of each pack.

3

For the sake of simplicity, we now de¬ne the ¬rst prime as p1 = 2.

Linear Bandwidth Naccache-Stern Encryption 331

We now represent m in base γ, i.e.,

n’1

γ i mi where mi ∈ [0, γ ’ 1]

m=

i=0

and encode m by picking in pack i the prime representing the message™s i-th

digit mi and multiplying all so chosen pi -s modulo p:

n’1

encoding(m) = pγi+mi +1 mod p.

i=0

We can now apply this encoding to the ns and re-de¬ne encryption as:

n’1

c = encryption(m) = encoding(m) =

s

vγi+mi +1 mod p.

i=0

To decrypt c, the receiver computes u = cs mod p and recovers m by factoring

u. Note that as soon as a representative of pack i is found, the receiver can stop

sieving within pack i and start decrypting digit i + 1.

3.1 A Small Example

We illustrate the mechanism by a small toy-example.

• key generation for n = 3 and γ = 4:

The prime p = 4931 > pγ — p2γ — p3γ = 7 — 19 — 37 and the secret s = 3079

yield the v-list:

√ √ √

§ § §

s s s

⎪ v1 ⎪ v5 ⎪ v9

= √2 modp = 1370 = √11 modp = 2544 = √23 modp = 4376

⎪ ⎪ ⎪

⎨ ⎨ ⎨

pack 1

pack 2

pack 3

s s s

v2 v6 v10

= √3 modp = 1204 = √13 modp = 3366 = √29 modp = 1921

s s s

⎪ v3 ⎪ v7 ⎪ v11

= √5 modp = 1455 = √17 modp = 1994 = √31 modp = 3537

⎪ ⎪ ⎪

© © ©

= s 7 modp = = s 19 modp = = s 37 modp =

v4 v8 v12

3234 3327 3747

• encryption of m = 35:

We start by writing m is base γ = 4, i.e., m = 35 = 2034 and encrypt it as:

c = v(0·4+3+1) — v(1·4+0+1) — v(2·4+2+1) = v4 — v5 — v11 mod 4931 = 4484.

• decryption:

By exponentiation, the receiver retrieves:

cs mod p = 44843079 mod 4931 = 7—11—31 = p(0·4+3+1) —p(1·4+0+1) —p(2·4+2+1) ,

whereby m = 2034 .

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

3.2 Bandwidth Considerations

The bandwidth gain stems from the fact that, for large i, we have pγi+1 pγi+γ

which allows the new format to accommodate log2 γ message bits at the price

of one single pγi+γ . This situation is much more favorable than the original ns,

where each message bit costs a new pi .

More precisely, pγi ∼ γi ln i yields an (n log γ)-bit bandwidth where:

n ∼ ln p/ln ln p ∼ log p/log log p

The bandwidth gain is thus a constant multiplicative factor (namely log γ)

and the increase in n is logarithmic. Note that at the same time, the vi -list

becomes γ times longer.

The following table shows the performances of the new encoding algorithm for

a 2048-bit p. The ¬rst row represents the original ns for the sake of comparison.

information rate= n log γ

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

γ n log p

233 233 bits 59 kilobytes 0.11

ns

2 208 207 bits 104 0.10

kilobytes

4 189 378 bits 189 0.18

kilobytes

8 172 516 bits 344 0.25

kilobytes

16 159 635 bits 636 0.31

kilobytes

32 147 734 bits 1176 0.36

kilobytes

64 137 821 bits 2192 0.40