Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions

• URL: http://arxiv.org/abs/2311.03512v1
• Date: Mon, 6 Nov 2023 20:41:25 GMT
• Title: Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions
• Authors: Samuel Bouaziz--Ermann, Alex B. Grilo, Damien Vergnaud, and Quoc-Huy Vu
• Abstract summary: It has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF.
• Score: 0.5999777817331317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al. (CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.

Related papers

• How (not) to Build Quantum PKE in Minicrypt [5.885896375772235]
  We re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM) Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich's results.
  arXiv  Detail & Related papers  (2024-05-30T17:44:03Z)
• Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution [16.06159998475861]
  Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. It has two main advantages: (i) The key is unconditionally hidden to the eyes of any attacker, and (ii) its security assumes only the existence of authenticated classical channels. We propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions.
  arXiv  Detail & Related papers  (2023-04-06T11:14:55Z)
• Encryption with Quantum Public Keys [1.7725414095035827]
  We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions. We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
  arXiv  Detail & Related papers  (2023-03-09T16:17:19Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• A Simple Construction of Quantum Public-Key Encryption from Quantum-Secure One-Way Functions [13.677574076242188]
  We show that quantum PKE can be constructed from any quantum-secure one-way function. Our construction is simple, uses only classical ciphertexts, and satisfies the strong notion of CCA security.
  arXiv  Detail & Related papers  (2023-03-02T10:45:16Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• From a quantum theory to a classical one [117.44028458220427]
  We present and discuss a formal approach for describing the quantum to classical crossover. The method was originally introduced by L. Yaffe in 1982 for tackling large-$N$ quantum field theories.
  arXiv  Detail & Related papers  (2020-04-01T09:16:38Z)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)
• Forging quantum data: classically defeating an IQP-based quantum test [0.0]
  We describe a classical algorithm that can convince the verifier that the (classical) prover is quantum. We show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits.
  arXiv  Detail & Related papers  (2019-12-11T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.