Invertible Extractors and Wiretap Protocols

Invertible Extractors and Wiretap Protocols. Cheraghchi, M., Didier, F., & Shokrollahi, A. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 1934–1938, 2009. Extended version in IEEE Transactions on Information Theory.

Link

Paper doi abstract bibtex

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. As a by-product of the constructions, new explicit extractors for a restricted family of affine sources over large fields is obtained (that in particular generalizes the notion of symbol-fixing sources) which is of independent interest. These extractors are able to extract the entire source entropy with zero error.

@INPROCEEDINGS{ref:conf:CDS09,
  author =	 {Mahdi Cheraghchi and Fr\'ed\'eric Didier and Amin
                  Shokrollahi},
  title =	 {Invertible Extractors and Wiretap Protocols},
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  year =	 2009,
  pages =	 {1934--1938},
  note =	 {Extended version in IEEE Transactions on Information
                  Theory.},
  doi =		 {10.1109/ISIT.2009.5205583},
  url_Link =	 {https://ieeexplore.ieee.org/document/5205583},
  url_Paper =	 {https://arxiv.org/abs/0901.2120},
  abstract =	 {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.  As a
                  by-product of the constructions, new explicit
                  extractors for a restricted family of affine sources
                  over large fields is obtained (that in particular
                  generalizes the notion of symbol-fixing sources)
                  which is of independent interest. These extractors
                  are able to extract the entire source entropy with
                  zero error.  },
  keywords =	 {Wiretap Channel, Extractors, Network Coding, Active
                  Intrusion, Exposure Resilient Cryptography}
}

Downloads: 0