2

that at least one wire among these u wires is honest. S now re-sends mS by

2

executing the steps given in Table 9. This will take ˜(u) phases.

Lemma 6. If Y R is correctly received by S over more than u + 1 wires during

2

Phase II and if the corresponding |LSault | ≥ (t ’ u + 1), then with very high

f 2

S

probability, S will be able to correctly re-send m by executing the steps in Table

9 by incurring a communication overhead of O(|mS |) ¬eld elements.

Theorem 5. If mS is a message containing ¬eld elements where ≥ (t ’ u + 2

1)n2 , then there exists an O(u) phase URMT protocol which reliably sends mS

with very high probability by communicating O( ) ¬eld elements. In terms of bits,

the protocol sends κ bits by communicating O( κ) bits.

Remark 1. In Π URMT , we assumed that u ¤ t. If u > t, then we can modify the

protocol to reliably send a message containing ( u + 1)n2 = ˜(n3 ) ¬eld elements

2

with a communication overhead of O(n3 ) ¬eld elements.

5 Communication Optimal USMT Protocol

We now design an O(u) phase USMT protocol called Π USMT , which sends a

message MS containing ¬eld elements by communicating O(n3 ) ¬eld elements

with very high probability. If the full bottom band is corrupted then = ˜(n2 u),

otherwise = ˜(n3 ). The protocol is as follows:

1. Depending upon whether the full bottom band is corrupted or not, S and R

securely establishes a random non-zero one time pad P ad of length ˜(n2 u) or

˜(n3 ) with very high probability by executing the protocol Π P ad .

2. If P ad is of length ˜(n2 u), then S selects a secret message MS of length ˜(n2 u).

S then computes C = MS • P ad and reliably sends C to R with very high

probability by executing the protocol Π U RM T . R correctly receives C with very

high probability and recovers MR = C • P ad. On the other hand, if P ad is of

length ˜(n3 ), then S and R does the same computation, except that MS and C

(and hence MR ) will be of length ˜(n3 ).

6 Lower Bound on the Communication Complexity

An obvious lower bound on communication complexity of URMT protocols to

send a message containing ¬eld elements is ©( ). Since, we have already shown

that this bound is tight by designing Π URMT , we need not have to prove the

lower bound for URMT. Similarly, if at least one wire in the bottom band is

uncorrupted, then ©( ) is a trivial lower bound on the communication complexity

of any USMT protocol to securely send ¬eld elements. Again, since we have

already shown that this bound is tight by designing Π USMT (which securely

sends ¬eld elements by communicating ¬eld elements if there exists at least

one uncorrupted wire in the bottom band), we need not have to prove the lower

bound for this case. The lower bound for remaining case is given by Theorem 6.

Unconditionally Reliable and Secure Message Transmission 325

Theorem 6. Suppose there exists u ¤ t wires in the bottom band and n =

max(2t ’ u + 1, t + 1) wires in the top band. Moreover, the entire bottom band

is corrupted. Then any multiphase USMT protocol to send a message M S con-

taining ¬eld elements from F, needs to communicate ©( n ) ¬eld elements. In

u

n

terms of bits, the protocol needs to communicate ©( u κ) bits to send κ bits.

Proof: The lower bound is derived by using entropy based arguments. We do

not give the proof here due to space constraint. For complete proof see [7]. The

lower bound in Theorem 6 is tight. Speci¬cally, if the entire bottom band is

2

corrupted, then protocol Π USMT satis¬es the lower bound.

7 Conclusion and Open Problems

In this paper we have designed communication optimal URMT and USMT pro-

tocol in directed networks, which are ¬rst of their kind. It would be interesting

to reduce the phase complexity of our URMT and USMT protocols. Our URMT

and USMT protocols are communication optimal in amortized sense; i.e., they

achieve bit optimality for su¬ciently large message size ( ). We leave the issue of

designing communication optimal URMT/USMT protocols in directed networks

for small sized message as an open problem.

References

1. Beerliov´-Trub´

a ±niov´, Z., Hirt, M.: E¬cient multi-party computation with dispute

a

control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305“328.

Springer, Heidelberg (2006)

2. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-

cryptographic fault-tolerant distributed computation. In: STOC, pp. 1“10 (1988)

3. Chaum, D., Cr´peau, C., Damg˚ I.: Multiparty unconditionally secure protocols

e ard,

(extended abstract). In: Proc. of FOCS 1988, pp. 11“19 (1988)

4. Desmedt, Y., Wang, Y.: Perfectly secure message transmission revisited. In: Knud-

sen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 502“517. Springer, Hei-

delberg (2002)

5. Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly secure message transmission.

JACM 40(1), 17“47 (1993)

6. Franklin, M., Wright, R.: Secure communication in minimal connectivity models.

Journal of Cryptology 13(1), 9“30 (2000)

7. Patra, A., Choudhary, A., Pandu Rangan, C.: Unconditionally reliable and secure

message transmission in directed networks revisited. Cryptology ePrint Archive,

Report 2008/262

8. Patra, A., Choudhary, A., Srinathan, K., Pandu Rangan, C.: Unconditionally reli-

able and secure message transmission in undirected synchronous networks: Possi-

bility, feasibility and optimality. Cryptology ePrint Archive, Report 2008/141

9. Rabin, T., Ben-Or, M.: Veri¬able secret sharing and multiparty protocols with

honest majority (extended abstract). In: STOC, pp. 73“85 (1989)

10. Shanker, B., Gopal, P., Srinathan, K., Pandu Rangan, C.: Unconditional reliable

message transmision in directed networks. In: Proc. of SODA 2008 (2008)

326 A. Patra, A. Choudhary, and C.P. Rangan

11. Srinathan, K., Narayanan, A., Rangan, C.P.: Optimal perfectly secure message

transmission. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 545“561.

Springer, Heidelberg (2004)

12. Wang, Y., Desmedt, Y.: Perfectly secure message transmission revisited

(manuscript), www.sis.uncc.edu/yonwang/

13. Yao, A.C.: Protocols for secure computations. In: Proc. of 23rd IEEE FOCS, pp.

160“164 (1982)

Linear Bandwidth Naccache-Stern Encryption

Benoˆ Chevallier-Mames1 , David Naccache2 , and Jacques Stern2

±t

1

dcssi, Laboratoire de cryptographie,

51, Boulevard de la Tour Maubourg

75700 Paris, France

benoit.chevallier-mames@sgdn.gouv.fr

2 ´ ´

Ecole normale sup´rieure, Equipe de cryptographie,

e

45 rue d™Ulm, f-75230 Paris cedex 05, France

{david.naccache,jacques.stern}@ens.fr

Abstract. The Naccache-Stern (ns) knapsack cryptosystem is an orig-

inal yet little-known public-key encryption scheme. In this scheme, the

ciphertext is obtained by multiplying public-keys indexed by the mes-

sage bits modulo a prime p. The cleartext is recovered by factoring the

ciphertext raised to a secret power modulo p.

ns encryption requires a multiplication per two plaintext bits on the

average. Decryption is roughly as costly as an rsa decryption. However,

ns features a bandwidth sublinear in log p, namely log p/ log log p. As

an example, for a 2048-bit prime p, ns encryption features a 233-bit

bandwidth for a 59-kilobyte public key size.

This paper presents new ns variants achieving bandwidths linear in

log p. As linear bandwidth claims a public-key of size log3 p/ log log p, we

recommend to combine our scheme with other bandwidth optimization

techniques presented here.

For a 2048-bit prime p, we obtain ¬gures such as 169-bit plaintext

for a 10-kilobyte public key, 255-bit plaintext for a 20-kilobyte public

key or a 781-bit plaintext for a 512-kilobyte public key. Encryption and

decryption remain una¬ected by our optimizations: As an example, the

781-bit variant requires 152 multiplications per encryption.

Keywords: Public key cryptography, ns cryptosystem, multiplicative