Towards Unconditional Uncloneable Encryption

Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext, such that two quantum adversaries are limited in their capacity of being able to simultaneously decrypt, given the key and quantum side-information produced from the ciphertext. Since its initial proposal and scheme in the random oracle model by Broadbent and Lord [TQC 2020], uncloneable encryption has developed into an important primitive at the foundation of quantum uncloneability for cryptographic primitives. Despite sustained efforts, however, the question of unconditional uncloneable encryption (and in particular of the simplest case, called an “uncloneable bit”) has remained elusive. Here, we propose a candidate for the unconditional uncloneable bit problem, and provide strong evidence that the adversary’s success probability in the related security game converges quadratically as 1/2+1/2√(K), where K is polynomial in the size of the encoding, representing the number of keys and 1/2 is trivially achievable. We prove this bound’s validity for K ranging from 2 to 7 and demonstrate the validity up to K=17 using computations based on the NPA hierarchy. We furthermore provide compelling heuristic evidence towards the general case. In addition, we prove an asymptotic upper-bound of 5/8 and give a numerical upper-bound of ≈0.5980, which to our knowledge is the best-known value in the unconditional model.