Contributed Talks 5a: Encryption and coin-flipping (Chairs: Sevag Gharibian and Or Sattath)

Abstract: Given a ciphertext, is it possible to prove the deletion of the underlying plaintext? Since classical ciphertexts can be copied, clearly such a feat is impossible using classical information alone. In stark contrast to this, we show that quantum encodings enable certified deletion. More precisely speaking, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements; the scheme is also robust against noise in these devices. Furthermore, we provide an analysis that is suitable in the finite-key regime

Abstract: Indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) is usually considered the most desirable security notion for classical encryption. In this work, we investigate its adaptation in the quantum world, when an adversary can perform superposition queries. The security of quantum-secure classical encryption has first been studied by Boneh and Zhandry (CRYPTO'13), but they restricted the adversary to classical challenge queries, which makes the indistinguishability only hold for classical messages (IND-qCCA2). In this work, we give the first security notions for fully quantum indistinguishability under quantum adaptive chosen-ciphertext attacks, where the indistinguishability holds for superposition of plaintexts (qIND-qCCA2). This resolves an open problem asked by Gagliardoni et al. (CRYPTO'16). The qCCA2 security is defined in Boneh-Zhandry's paper using string copying and comparison, which is inherent in the classical setting. Quantumly, it is unclear what it means for a ciphertext to be different from the challenge ciphertext, and how the challenger can check the equality. The classical approach would either violate the no-cloning theorem or lead to perturbing the adversary's state, which may be detectable. To remedy these problems, from the recent groundbreaking compressed oracle technique introduced by Zhandry (CRYPTO'19), we develop a generic framework that allows to record quantum queries for probabilistic functions. We then give definitions for fully quantum real-or-random indistinguishability under adaptive chosen-ciphertext attacks (qIND-qCCA2). In the symmetric setting, we show that various classical modes of encryption are trivially broken in our security notions. We then provide the first formal proof for quantum security of the Encrypt-then-MAC paradigm, which also answers an open problem posed by Boneh and Zhandry. In the public-key setting, we show how to achieve these stronger security notions (qIND-qCCA2) from any encryption scheme secure in the sense of Boneh-Zhandry (IND-qCCA2). Along the way, we also give the first definitions of non-malleability for classical encryption in the quantum world and show that the picture of the relations between these notions is essentially the same as in the classical setting.

Abstract: Weak coin flipping (WCF) is a fundamental cryptographic primitive, where two distrustful parties need to remotely establish a shared random bit, whilst having opposite preferred outcomes. A WCF protocol is said to have bias ε if neither party can force their preferred outcome with probability greater than 1/2+ε. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. A lower bias can only be achieved by employing extra assumptions, such as computational hardness. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias ε(k) = 1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC’19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon’s proof. The construction of an explicit WCF protocol approaching bias 1/14 is illustrated as an example.