Invertible Extractors and Wiretap Protocols

A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. In this paper we study the notion of efficiently invertible extractors and show that a wiretap protocol can be constructed from such an extractor. We will then construct invertible extractors for symbol-fixing, affine, and general sources and apply them to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). We will then apply our results to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding, network coding, and intruders observing arbitrary boolean functions of the encoding.

Published in:
Proceedings of the IEEE International Symposium on Information Theory (ISIT), 1934--1938
Presented at:
IEEE International Symposium on Information Theory (ISIT), 2009

Note: The status of this file is: EPFL only

 Record created 2009-09-30, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)