Cryptology ePrint Archive: Report 2020/445

On Pseudorandom Encodings

Thomas Agrikola and Geoffroy Couteau and Yuval Ishai and Stanislaw Jarecki and Amit Sahai

Abstract: We initiate a study of pseudorandom encodings: efficiently computable and decodable encoding functions that map messages from a given distribution to a random-looking distribution. For instance, every distribution that can be perfectly compressed admits such a pseudorandom encoding. Pseudorandom encodings are motivated by a variety of cryptographic applications, including password-authenticated key exchange, "honey encryption" and steganography.

The main question we ask is whether every efficiently samplable distribution admits a pseudorandom encoding. Under different cryptographic assumptions, we obtain positive and negative answers for different flavors of pseudorandom encodings, and relate this question to problems in other areas of cryptography. In particular, by establishing a two-way relation between pseudorandom encoding schemes and efficient invertible sampling algorithms, we reveal a connection between adaptively secure multi-party computation and questions in the domain of steganography.

Category / Keywords: foundations / encoding schemes, invertible sampling, adaptive MPC, honey encryption, covert MPC

Date: received 17 Apr 2020, last revised 7 Aug 2020

Contact author: thomas agrikola at gmail com,thomas agrikola@kit edu

Available format(s): PDF | BibTeX Citation

Note: new unconditional static-to-adaptive reduction and some corrections

Version: 20200807:121724 (All versions of this report)

Short URL: ia.cr/2020/445