Paper 2020/445

On Pseudorandom Encodings

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


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 and efficiently 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 multiparty computation for randomized functionalities and questions in the domain of steganography.

Note: new unconditional static-to-adaptive reduction and implemented reviewer comments

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2020
encoding schemesinvertible samplingadaptive MPChoney encryptioncovert MPC
Contact author(s)
thomas agrikola @ gmail com
thomas agrikola @ kit edu
2020-10-06: last of 4 revisions
2020-04-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Agrikola and Geoffroy Couteau and Yuval Ishai and Stanislaw Jarecki and Amit Sahai},
      title = {On Pseudorandom Encodings},
      howpublished = {Cryptology ePrint Archive, Paper 2020/445},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.