Secure communication in minimal connectivity models

Matthew Franklin, Rebecca Wright

Research output: Contribution to journalArticle

78 Scopus citations


Problems of secure communication and computation have been studied extensively in network models. In this work we ask what is possible in the informationtheoretic setting when the adversary is very strong (Byzantine) and the network connectivity is very low (minimum needed for crash-tolerance). We concentrate on a new model called "multicast lines," and show a sizable gap between the connectivity required for perfect security and for almost perfect security. Our results also have implications to the commonly studied simple channel model and to general secure multiparty computation.

Original languageEnglish (US)
Pages (from-to)9-30
Number of pages22
JournalJournal of Cryptology
Issue number1
StatePublished - Dec 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Secure communication in minimal connectivity models'. Together they form a unique fingerprint.

  • Cite this