Perfect Omniscience, Perfect Secrecy, and Steiner Tree Packing
From MaRDI portal
Publication:5281197
DOI10.1109/TIT.2010.2081450zbMATH Open1366.94563arXiv1008.1079MaRDI QIDQ5281197FDOQ5281197
Authors: Sirin Nitinawarat, Prakash Narayan 
Publication date: 27 July 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We consider perfect secret key generation for a ``pairwise independent network model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Third, when a single ``helper terminal assists the remaining ``user terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a ``weak helper is shown to be sufficient for optimality.
Full work available at URL: https://arxiv.org/abs/1008.1079
This page was built for publication: Perfect Omniscience, Perfect Secrecy, and Steiner Tree Packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281197)
