Cheraghchi, Mahdi
Didier, Fredric
Shokrollahi, Amin
Invertible Extractors and Wiretap Protocols
Ieee Transactions On Information Theory
Ieee Transactions On Information Theory
Ieee Transactions On Information Theory
Ieee Transactions On Information Theory
58
Active intrusion
exposure resilient cryptography
extractors
network coding
wiretap channel
Exposure-Resilient Cryptography
Ramanujan Graphs
Affine Extractors
Tap Channel
Codes
Encryption
Security
Messages
Fields
Error
algoweb_tcs
algoweb_cryptography
2012
2012
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, the notion of efficiently invertible extractors is studied and it is shown that a wiretap protocol can be constructed from such an extractor. Then, invertible extractors for symbol-fixing, affine, and general sources are constructed and used 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). The results are further applied 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.
Ieee Transactions On Information Theory
Journal Articles
10.1109/TIT.2011.2170660