Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions

We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical. Quantum public-key encryption from one-way functions (or weaker primitives such as pseudorandom function-like states) are also proposed in some recent works [Morimae-Yamakawa, eprint:2022/1336; Coladangelo, eprint:2023/282; Barooti-Grilo-Malavolta-Sattath-Vu-Walter, TCC 2023]. However, they have a huge drawback: they are secure only when quantum public keys can be transmitted to the sender (who runs the encryption algorithm) without being tampered with by the adversary, which seems to require unsatisfactory physical setup assumptions such as secure quantum channels. Our construction is free from such a drawback: it guarantees the secrecy of the encrypted messages even if we assume only unauthenticated quantum channels. Thus, the encryption is done with adversarially tampered quantum public keys. Our construction is the first quantum publickey encryption that achieves the goal of classical public-key encryption, namely, to establish secure communication over insecure channels, based only on one-way functions. Moreover, we show a generic compiler to upgrade security against chosen plaintext attacks (CPA security) into security against chosen ciphertext attacks (CCA security) only using one-way functions. As a result, we obtain CCA secure quantum public-key encryption based only on one-way functions.

We redefine the syntax of QPKE. The difference from the previous definitions is that the key generation algorithm outputs a classical verification key together with the secret key. Also, this verification key is given to the encryption algorithm with a quantum public key and a message so that the encryption algorithm can check the validity of the given quantum public key. We require ciphertexts to be classical. We require a QPKE scheme to satisfy the following two basic security notions.

• Indistinguishability against public key tempering chosen plaintext attacks (IND-pkT-CPA security). Roughly speaking, it guarantees that indistinguishability holds even if messages are encrypted by a public key tampered with by an adversary. More specifically, it guarantees that no efficient adversary can guess the challenge bit b with a probability significantly better than random guessing given Enc(vk, pk ′ , msg b ), where vk is the correct verification key and (pk ′ , msg 0 , msg 1 ) are generated by the adversary who is given the verification key vk and multiple copies of the correctly generated quantum public keys. IND-pkT-CPA security captures the setting where the classical verification key is sent via a classical authenticated channel. Thus, everyone can obtain the correct verification key. However, a quantum public key is sent via an unauthenticated quantum channel and thus can be tampered with by an adversary.

• Decryption error detectability. In our setting, an adversary may try to cause a decryption error by tampering with the quantum public key. To address this issue, we introduce a security notion that we call decryption error detectability. It roughly guarantees that a legitimate receiver of a ciphertext can notice if the decrypted message is different from the message intended by the sender.

IND-pkT-CPA security considers adversaries that may tamper with quantum public keys but only passively observe ciphertext. For classical PKE, the golden standard security notion is indistinguishability against chosen ciphertext attacks (IND-CCA security) that considers active adversaries that may see decryption results of any (possibly malformed) ciphertexts. Thus, we also define its analog for QPKE. In Section 1.3, we discuss its importance in a natural application scenario.

• Indistinguishability against public key tempering chosen ciphertext attacks (IND-pkT-CCA security). This is similar to IND-pkT-CPA security except that the adversary is given access to the decryption oracle that returns a decryption result on any ciphertext other than the challenge ciphertext. Moreover, we allow the adversary to learn one-bit information indicating if the challenge ciphertext is decrypted to ⊥ or not. We note that it is redundant for classical PKE since the challenge ciphertext is always decrypted to the challenge message, which is not ⊥, by decryption correctness. On the other hand, it may give more power to the adversary for QPKE since if the adversary tempers with the public key that is used to generate the challenge ciphertext, decryption correctness may no longer hold.

We propose a QPKE scheme satisfying IND-pkT-CPA security from a digital signature scheme that can be constructed from OWFs. Our construction is inspired by the duality between distinguishing and swapping shown by Aaronson, Atia, and Susskind [AAS20] and its cryptographic applications by Hhan, Morimae, and Yamakawa [HMY23]. Our construction has quantum

We could also consider QPKE schemes with quantum ciphertexts if we