Paper 2023/1270

Computational Wiretap Coding from Indistinguishability Obfuscation

Yuval Ishai, Technion – Israel Institute of Technology
Aayush Jain, Carnegie Mellon University
Paul Lou, University of California, Los Angeles
Amit Sahai, University of California, Los Angeles
Mark Zhandry, NTT Research
Abstract

A wiretap coding scheme for a pair of noisy channels $(\mathsf{ChB},\mathsf{ChE})$ enables Alice to reliably communicate a message to Bob by sending its encoding over $\mathsf{ChB}$, while hiding the message from an adversary Eve who obtains the same encoding over $\mathsf{ChE}$. A necessary condition for the feasibility of wiretap coding is that $\mathsf{ChB}$ is not a degradation of $\mathsf{ChE}$, namely Eve cannot simulate Bob’s view. While insufficient in the information-theoretic setting, a recent work of Ishai, Korb, Lou, and Sahai (Crypto 2022) showed that the non-degradation condition is sufficient in the computational setting, assuming idealized flavors of obfuscation. The question of basing a similar feasibility result on standard cryptographic assumptions was left open, even in simple special cases. In this work, we settle the question for all discrete memoryless channels where the (common) input alphabet of $\mathsf{ChB}$ and $\mathsf{ChE}$ is binary, and with arbitrary finite output alphabet, under standard (sub-exponential) hardness assumptions: namely those assumptions that imply indistinguishability obfuscation (Jain-Lin-Sahai 2021, 2022), and injective PRGs. In particular, this establishes the feasibility of computational wiretap coding when $\mathsf{ChB}$ is a binary symmetric channel with crossover probability $p$ and $\mathsf{ChE}$ is a binary erasure channel with erasure probability $e$, where $e>2p$. On the information-theoretic side, our result builds on a new polytope characterization of channel degradation for pairs of binary-input channels, which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Keywords
indistinguishability obfuscationwiretap coding
Contact author(s)
yuvali @ cs technion ac il
aayushja @ andrew cmu edu
pslou @ cs ucla edu
sahai @ cs ucla edu
mzhandry @ gmail com
History
2023-08-24: approved
2023-08-22: received
See all versions
Short URL
https://ia.cr/2023/1270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1270,
      author = {Yuval Ishai and Aayush Jain and Paul Lou and Amit Sahai and Mark Zhandry},
      title = {Computational Wiretap Coding from Indistinguishability Obfuscation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1270},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.