Secure signatures and chosen ciphertext security in a quantum computing world

Dan Boneh, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations

Abstract

We initiate the study of quantum-secure digital signatures and quantum chosen ciphertext security. In the case of signatures, we enhance the standard chosen message query model by allowing the adversary to issue quantum chosen message queries: given a superposition of messages, the adversary receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary receives a superposition of their decryptions. These adversaries model a natural ubiquitous quantum computing environment where end-users sign messages and decrypt ciphertexts on a personal quantum computer. We construct classical systems that remain secure when exposed to such quantum queries. For signatures, we construct two compilers that convert classically secure signatures into signatures secure in the quantum setting and apply these compilers to existing post-quantum signatures. We also show that standard constructions such as Lamport one-time signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving signatures whose quantum security is based on generic assumptions. For encryption, we define security under quantum chosen ciphertext attacks and present both public-key and symmetric-key constructions.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings
Pages361-379
Number of pages19
EditionPART 2
DOIs
StatePublished - Sep 26 2013
Externally publishedYes
Event33rd Annual International Cryptology Conference, CRYPTO 2013 - Santa Barbara, CA, United States
Duration: Aug 18 2013Aug 22 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume8043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other33rd Annual International Cryptology Conference, CRYPTO 2013
CountryUnited States
CitySanta Barbara, CA
Period8/18/138/22/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Quantum computing
  • encryption
  • quantum security
  • signatures

Fingerprint Dive into the research topics of 'Secure signatures and chosen ciphertext security in a quantum computing world'. Together they form a unique fingerprint.

  • Cite this

    Boneh, D., & Zhandry, M. (2013). Secure signatures and chosen ciphertext security in a quantum computing world. In Advances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings (PART 2 ed., pp. 361-379). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8043 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-40084-1_21