Randomness and Dependencies Extraction via Polarization, With Applications to Slepian–Wolf Coding and Secrecy

Author

Abbe, Emmanuel

Author_Institution

Sch. of Commun. & Comput. Sci., Ecole Polytech. Fed. de Lausanne, Lausanne, Switzerland

Volume

61

Issue

5

fYear

2015

fDate

42125

Firstpage

2388

Lastpage

2398

Abstract

The polarization phenomenon for a single source is extended to a framework with multiple correlated sources. It is shown in addition to extracting the randomness of the source, the polar transforms take the original arbitrary dependencies to extremal dependencies. Polar coding schemes for the Slepian-Wolf (SW) coding problem and for secret key generations are then proposed based on this phenomenon. In particular, secret keys achieving the secrecy capacity and compression schemes achieving the SW capacity region are obtained with a complexity of O(n log (n)) .

Keywords

channel capacity; channel coding; communication complexity; private key cryptography; O(nlog(n)) complexity; SW capacity region; Slepian-Wolf coding problem; compression scheme; dependencies extraction; polar coding scheme; polar transform; polarization phenomenon; randomness extraction; secrecy capacity; secret key generation; Complexity theory; Decoding; Encoding; Entropy; Joints; Protocols; Vectors; Polar codes; Slepian-Wolf coding; polarization; randomness extraction; secret key generation;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2015.2410253

Filename

7055362