The Self-Anti-Censorship Nature of Encryption: On the Prevalence of Anamorphic Cryptography

Authors: Miroslaw Kutylowski (Wroclaw University of Science and Technology, and NASK), Giuseppe Persiano (Università di Salerno and Google LLC), Duong Hieu Phan (Telecom Paris, Institute Polytechnique de Paris), Moti Yung (Google LLC and Columbia University), Marcin Zawada (Wroclaw University of Science and Technology)

Volume: 2023
Issue: 4
Pages: 170–183

Download PDF

Abstract: As part of the responses to the ongoing crypto wars, the notion of Anamorphic Encryption was put forth. The notion allows private communication in spite of a dictator who is engaged in an extreme form of surveillance and or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish Single-Receiver Encryption for many to one communication, and Multiple-Receiver Encryption for many to many communication within the group of conspiring users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and we give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use. Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing crypto-wars): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. While the actual implications of what we show here and what it means in practice require further policy and legal analyses and perspectives, the technical aspects regarding the issues are clearly showing the futility of the war against Cryptography.

Keywords: privacy, Anamorphic Encryption

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.