(Receiver) Anamorphic encryption, introduced by Persiano et al. at Eurocrypt 2022, considers the question of achieving private communication in a world where secret decryption keys are under the control of a dictator. The challenge here is to be able to establish a secret communication channel to exchange covert (i.e. anamorphic) messages on top of some already deployed public key encryption scheme. Over the last few years several works addressed this challenge by showing new constructions, refined notions and extensions. Most of these constructions, however, are either ad hoc, in the sense that they build upon specific properties of the underlying PKE, or impose severe restrictions on the size of the underlying anamorphic message space. In this paper we consider the question of whether it is possible to have realizations of the primitive that are both generic and allow for large anamorphic message spaces. We give strong indications that, unfortunately, this is not the case. Our first result shows that any black-box realization of the primitive, i.e. any realization that accesses the underlying PKE only via oracle calls, must have an anamorphic message space of size at most ( security parameter). Even worse, if one aims at stronger variants of the primitive (and, specifically, the notion of asymmetric anamorphic encryption, recently proposed by Catalano et al.) we show that such black-box realizations are plainly impossible, i.e. no matter how small the anamorphic message space is. Finally, we show that our impossibility results are rather tight: indeed, by making more specific assumptions on the underlying PKE, it becomes possible to build generic AE where the anamorphic message space is of size .

Limits of Black-Box Anamorphic Encryption

Catalano D.;Migliaro F.
2024-01-01

Abstract

(Receiver) Anamorphic encryption, introduced by Persiano et al. at Eurocrypt 2022, considers the question of achieving private communication in a world where secret decryption keys are under the control of a dictator. The challenge here is to be able to establish a secret communication channel to exchange covert (i.e. anamorphic) messages on top of some already deployed public key encryption scheme. Over the last few years several works addressed this challenge by showing new constructions, refined notions and extensions. Most of these constructions, however, are either ad hoc, in the sense that they build upon specific properties of the underlying PKE, or impose severe restrictions on the size of the underlying anamorphic message space. In this paper we consider the question of whether it is possible to have realizations of the primitive that are both generic and allow for large anamorphic message spaces. We give strong indications that, unfortunately, this is not the case. Our first result shows that any black-box realization of the primitive, i.e. any realization that accesses the underlying PKE only via oracle calls, must have an anamorphic message space of size at most ( security parameter). Even worse, if one aims at stronger variants of the primitive (and, specifically, the notion of asymmetric anamorphic encryption, recently proposed by Catalano et al.) we show that such black-box realizations are plainly impossible, i.e. no matter how small the anamorphic message space is. Finally, we show that our impossibility results are rather tight: indeed, by making more specific assumptions on the underlying PKE, it becomes possible to build generic AE where the anamorphic message space is of size .
2024
9783031683787
9783031683794
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/641212
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact