International Association for Cryptologic Research

International Association
for Cryptologic Research


Publicly Verifiable Deletion from Minimal Assumptions

Fuyuki Kitagawa , NTT Social Informatics Laboratories
Ryo Nishimaki , NTT Social Informatics Laboratories
Takashi Yamakawa , NTT Social Informatics Laboratories
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: We present a general compiler to add the publicly verifiable deletion property for various cryptographic primitives including public key encryption, attribute-based encryption, and quantum fully homomorphic encryption. Our compiler only uses one-way functions, or more generally hard quantum planted problems for NP, which are implied by one-way functions. It relies on minimal assumptions and enables us to add the publicly verifiable deletion property with no additional assumption for the above primitives. Previously, such a compiler needs additional assumptions such as injective trapdoor one-way functions or pseudorandom group actions [Bartusek-Khurana-Poremba, CRYPTO 2023]. Technically, we upgrade an existing compiler for privately verifiable deletion [Bartusek-Khurana, CRYPTO 2023] to achieve publicly verifiable deletion by using digital signatures.
  title={Publicly Verifiable Deletion from Minimal Assumptions},
  author={Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa},