nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Publicly Verifiable Deletion from Minimal Assumptions

verfasst von : Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \(\textsf{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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Public-Key Encryption with Quantum Keys

Nächstes Kapitel One-Out-of-Many Unclonable Cryptography: Definitions, Constructions, and More

SKE, COM, ABE, TRE, and WE stand for secret key encryption, commitment, attribute-based encryption, time-release encryption, and witness encryption, respectively. Although Bartusek et al. [7] did not mention, we can apply their transformation to SKE and COM as the results by Bartusek and Khurana [8].

We do not abbreviate when we refer to this type to avoid confusion.

Although Bartusek and Khurana [8] did not mention, we can apply their transformation to SKE.

SKE, PKE, ABE, (Q)FHE, TRE, and WE fall into this category.

WE does not seem to imply one-way functions.

The compilers of [8, 9] are also applicable to schemes that have quantum encryption and decryption (or committing) algorithms though they do not explicitly mention it.

For simplicity, we state a simplified version of the lemma that is sufficient for the conversion for PKE, FHE, TRE, and WE, but not for ABE. See Lemma 4.1 for the general version.

We write \(\textsf{Enc}(\theta ,b \oplus \bigoplus _{j: \theta _j = 1} x_j)\) to mean an encryption of the message \((\theta ,b \oplus \bigoplus _{j: \theta _j = 1} x_j)\) where we omit the encryption key.

We assume that the verification algorithm of Z with \(\text {PVD}\) is a classical deterministic algorithm. If we allow it to be a quantum algorithm, we have to consider hard quantum planted problems for \(\textsf{QCMA}\), which are also sufficient to instantiate our compiler.

The definitions in [8] only consider privately verifiable deletion, but it is straightforward to extend them to ones with publicly verifiable deletion.

Aaronson, S., Liu, J., Liu, Q., Zhandry, M., Zhang, R.: New approaches for quantum copy-protection. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part I. LNCS, vol. 12825, pp. 526–555. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_19CrossRef

Agrawal, S., Kitagawa, F., Nishimaki, R., Yamada, S., Yamakawa, T.: Public key encryption with secure key leasing. IACR Cryptol. ePrint Arch., p. 264 (2023). https://eprint.iacr.org/2023/264, eurocrypt 2023 (to appear)

Amos, R., Georgiou, M., Kiayias, A., Zhandry, M.: One-shot signatures and applications to hybrid quantum/classical authentication. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) 52nd ACM STOC, pp. 255–268. ACM Press, June 2020. https://doi.org/10.1145/3357713.3384304

Ananth, P., La Placa, R.L.: Secure software leasing. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021, Part II. LNCS, vol. 12697, pp. 501–530. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_17CrossRef

Ananth, P., Poremba, A., Vaikuntanathan, V.: Revocable cryptography from learning with errors. Cryptology ePrint Archive, Report 2023/325 (2023). https://eprint.iacr.org/2023/325

Barak, B., et al.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6:1–6:48 (2012)

Bartusek, J., et al.: Obfuscation and outsourced computation with certified deletion. Cryptology ePrint Archive, Report 2023/265 (2023). https://eprint.iacr.org/2023/265

Bartusek, J., Khurana, D.: Cryptography with certified deletion. Cryptology ePrint Archive, Report 2022/1178 (2022). https://eprint.iacr.org/2022/1178

Bartusek, J., Khurana, D., Poremba, A.: Publicly-verifiable deletion via target-collapsing functions. IACR Cryptol. ePrint Arch. p. 370 (2023). https://eprint.iacr.org/2023/370

10.

Broadbent, A., Islam, R.: Quantum encryption with certified deletion. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 92–122. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_4CrossRef

11.

Broadbent, A., Jeffery, S., Lord, S., Podder, S., Sundaram, A.: Secure software leasing without assumptions. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part I. LNCS, vol. 13042, pp. 90–120. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_4CrossRef

12.

Coladangelo, A., Liu, J., Liu, Q., Zhandry, M.: Hidden Cosets and applications to unclonable cryptography. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part I. LNCS, vol. 12825, pp. 556–584. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_20CrossRef

13.

Coladangelo, A., Majenz, C., Poremba, A.: Quantum copy-protection of compute-and-compare programs in the quantum random oracle model. Cryptology ePrint Archive, Report 2020/1194 (2020). https://eprint.iacr.org/2020/1194

14.

Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 536–553. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_30CrossRef

15.

Hhan, M., Morimae, T., Yamakawa, T.: From the hardness of detecting superpositions to cryptography: quantum public key encryption and commitments. Cryptology ePrint Archive, Report 2022/1375 (2022). https://eprint.iacr.org/2022/1375

16.

Hiroka, T., Kitagawa, F., Morimae, T., Nishimaki, R., Pal, T., Yamakawa, T.: Certified everlasting secure collusion-resistant functional encryption, and more. Cryptology ePrint Archive, Report 2023/236 (2023). https://eprint.iacr.org/2023/236

17.

Hiroka, T., Morimae, T., Nishimaki, R., Yamakawa, T.: Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part I. LNCS, vol. 13090, pp. 606–636. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_21CrossRef

18.

Hiroka, T., Morimae, T., Nishimaki, R., Yamakawa, T.: Certified everlasting zero-knowledge proof for QMA. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I. LNCS, vol. 13507, pp. 239–268. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15802-5_9

19.

Kitagawa, F., Nishimaki, R.: Functional encryption with secure key leasing. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. LNCS, vol. 13794, pp. 569–598. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22972-5_20

20.

Kitagawa, F., Nishimaki, R., Yamakawa, T.: Secure software leasing from standard assumptions. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part I. LNCS, vol. 13042, pp. 31–61. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_2CrossRef

21.

Lamport, L.: Constructing digital signatures from a one-way function. Technical report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979

22.

Müller-Quade, J., Unruh, D.: Long-term security and universal composability. J. Cryptol. 23(4), 594–671 (2010). https://doi.org/10.1007/s00145-010-9068-8MathSciNetCrossRefMATH

23.

Poremba, A.: Quantum proofs of deletion for learning with errors. In: Kalai, Y.T. (ed.) 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, 10–13 January 2023. LIPIcs, vol. 251, pp. 90:1–90:14, MIT. Cambridge. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023). https://doi.org/10.4230/LIPIcs.ITCS.2023.90

24.

Unruh, D.: Revocable quantum timed-release encryption. J. ACM 62(6), 49:1–49:76 (2015)

Titel: Publicly Verifiable Deletion from Minimal Assumptions
verfasst von: Fuyuki Kitagawa
Ryo Nishimaki
Takashi Yamakawa
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48623-4

Electronic ISBN: 978-3-031-48624-1

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48624-1_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner