KIT | KIT-Bibliothek | Impressum | Datenschutz

On Pseudorandom Encodings

Agrikola, Thomas; Couteau, Geoffroy; Ishai, Yuval; Jarecki, Stanisław; Sahai, Amit

Abstract (englisch):
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.

DOI: 10.1007/978-3-030-64381-2_23
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Publikationstyp Buchaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISBN: 978-3-030-64381-2
ISSN: 0302-9743
KITopen-ID: 1000127824
Erschienen in Theory of Cryptography – 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III. Ed.: R. Pass
Verlag Springer International Publishing
Seiten 639–669
Serie Lecture Notes in Computer Science ; 12552
Vorab online veröffentlicht am 09.12.2020
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page