eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2023/538

Publicly Verifiable Deletion from Minimal Assumptions

Fuyuki Kitagawa, NTT Social Informatics Laboratories
Ryo Nishimaki, NTT Social Informatics Laboratories
Takashi Yamakawa, NTT Social Informatics Laboratories

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.

Note: Corrected typos.

Available format(s)
Publication info
Published by the IACR in TCC 2023
quantum cryptographycertified deletionpublic verifiability
Contact author(s)
fuyuki kitagawa @ ntt com
ryo nishimaki @ ntt com
takashi yamakawa @ ntt com
2023-09-21: revised
2023-04-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa},
      title = {Publicly Verifiable Deletion from Minimal Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/538},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/538}},
      url = {https://eprint.iacr.org/2023/538}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.