Foundations and Trends® in Communications and Information Theory > Vol 13 > Issue 2-3

Multiterminal Secrecy by Public Discussion

Prakash Narayan, University of Maryland, College Park, USA, prakash@umd.edu Himanshu Tyagi, Indian Institute of Science, Bangalore, India, htyagi@ece.iisc.ernet.in
 
Suggested Citation
Prakash Narayan and Himanshu Tyagi (2016), "Multiterminal Secrecy by Public Discussion", Foundations and Trends® in Communications and Information Theory: Vol. 13: No. 2-3, pp 129-275. http://dx.doi.org/10.1561/0100000072

Published: 28 Sep 2016
© 2016 P. Narayan and H. Tyagi
 
Subjects
Security,  Information theory and computer science,  Multiuser information theory,  Cryptography and information security
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
Part 1. Basic Tools
2. Notions of Secrecy and Their Relationships
3. Interactive Communication and Common Randomness
4. Secret Key Generation
5. Extracting Uniform Randomness
Part 2. Applications
6. Secret Key Capacity for the Multiterminal Source Model
7. Minimum Communication for Secret Key Capacity
8. Secure Function Computation with Trusted Parties
9. Secret Key Capacity for the Multiterminal Channel Model
Acknowledgements
References

Abstract

This monograph describes principles of information theoretic secrecy generation by legitimate parties with public discussion in the presence of an eavesdropper. The parties are guaranteed secrecy in the form of independence from the eavesdropper’s observation of the communication. Part I develops basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Various information theoretic and cryptographic notions of secrecy are compared. Emphasis is placed on central themes of interactive communication and common randomness as well as on core methods of balanced coloring and leftover hash for extracting secret uniform randomness. Achievability and converse results are shown to emerge from “single shot” incarnations that serve to explain essential structure. Part II applies the methods of Part I to secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are afforded privileged access to correlated observations of which the eavesdropper has only partial knowledge. Characterizations of secret key capacity bring out inherent connections to the data compression concept of omniscience and, for a specialized source model, to a combinatorial problem of maximal spanning tree packing in a multigraph. Interactive common information is seen to govern the minimum rate of communication needed to achieve secret key capacity in the two-terminal source model. Furthermore, necessary and sufficient conditions are analyzed for the secure computation of a given function in the multiterminal source model. Based largely on known recent results, this self-contained monograph also includes new formulations with associated new proofs. Supplementing each chapter in Part II are descriptions of several open problems.

DOI:10.1561/0100000072
ISBN: 978-1-68083-186-3
160 pp. $99.00
Buy book
 
ISBN: 978-1-68083-187-0
160 pp. $260.00
Buy E-book
Table of contents:
1. Introduction
Part 1. Basic Tools
2. Notions of Secrecy and Their Relationships
3. Interactive Communication and Common Randomness
4. Secret Key Generation
5. Extracting Uniform Randomness
Part 2. Applications
6. Secret Key Capacity for the Multiterminal Source Model
7. Minimum Communication for Secret Key Capacity
8. Secure Function Computation with Trusted Parties
9. Secret Key Capacity for the Multiterminal Channel Model
Acknowledgements
References

Multiterminal Secrecy by Public Discussion

This monograph describes the principles of information theoretic secrecy generation by legitimate parties with public discussion in the presence of an eavesdropper. The parties are guaranteed secrecy in the form of independence from the eavesdropper’s observation of the communication. The focus is on secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are given privileged access to correlated data of which the eavesdropper has only partial knowledge.

Part I is concerned with basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Part II applies the methods of Part I to secrecy generation for the multiterminal source and channel models.

Based largely on known recent results, this self-contained tutorial also includes new formulations with associated new proofs.

 
CIT-072