Contributed Talks 1b: Mostly Theory (Chairs: Omar Fawzi and Carl Miller)

Abstract: Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al. (Crypto 2001) shows that a general obfuscator that obfuscates classical circuits into classical circuits can- not exist. A promising direction that circumvents this impossibility result is to obfuscate classical circuits into quantum states, which would potentially be better capable of hiding information about the obfuscated circuit. We show that, under the assumption that learning-with-errors (LWE) is hard for quantum computers, this quantum variant of virtual black-box obfuscation of classical circuits is generally impossible. On the way, we show that under the presence of dependent classical auxiliary input, even the small class of classical point functions cannot be quantum virtual black-box obfuscated.

Abstract: Efficiently sampling a quantum state that is hard to distinguish from a truly random quantum state is an elementary task in quantum information theory that has both computational and physical uses. This is often referred to as pseudorandom (quantum) state generator, or PRS generator for short. In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an n-qubit PRS is roughly n. Perhaps counter-intuitively, n-qubit PRS are not known to imply k-qubit PRS even for k<n. Therefore the question of \emph{scalability} for PRS was thus far open: is it possible to construct n-qubit PRS generators with security parameter m for all n, m. Indeed, we believe that PRS with tiny (even constant) n and large m can be quite useful. We resolve the problem in this work, showing that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a \emph{statistically} secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security. However, our methods deviate significantly from prior works since scalable pseudorandom states require randomizing the amplitudes of the quantum state, and not just the phase as in all prior works. We show how to achieve this using Gaussian sampling.

Abstract: We put forward the idea that classical blockchains and smart contracts are potentially useful primitives not only for classical cryptography, but for quantum cryptography as well. Abstractly, a smart contract is a functionality that allows parties to deposit funds, and release them upon fulfillment of algorithmically checkable conditions, and can thus be employed as a formal tool to enforce monetary incentives. In this work, we give the first example of the use of smart contracts in a quantum setting. We describe a simple hybrid classical-quantum payment system whose main ingredients are a classical blockchain capable of handling stateful smart contracts, and quantum lightning, a strengthening of public-key quantum money introduced by Zhandry (Eurocrypt'19). Our hybrid payment system employs quantum states as banknotes and a classical blockchain to settle disputes and to keep track of the valid serial numbers. It has several desirable properties: it is decentralized, requiring no trust in any single entity; payments are as quick as quantum communication, regardless of the total number of users; when a quantum banknote is damaged or lost, the rightful owner can recover the lost value.

Abstract: Paradigmatic QKD protocols establish secure keys between pairs of users, however when more than two parties want to communicate, recently introduced quantum conference quantum key agreement (CKA) protocols can outperform 2-party primitives in terms of resource cost. In this contribution we report an implementation of a four-user quantum CKA protocol using polarisation-encoded multi-partite GHZ states at telecom wavelength. We distribute these states over up to 50km of optical fibre and implement custom multiparty error correction and privacy amplification on the resulting raw keys. From a finite-key analysis, we establish an information-theoretic secure key of up to 1.15 × 10^6 bits, which is used to encrypt and securely share an image between the four users. Surpassing the previous maximum distance for GHZ state transmission by more than an order of magnitude, these results demonstrate the viability of network protocols relying on multi-partite-entanglement. Future applications beyond quantum CKA include entanglement-assisted remote clock-synchronization, quantum secret sharing, and GHZ-based repeater protocols.