26 citations · 51 across the 14 of their papers we have counts for
14 papers · 1 filter
The complexity of entangled graph colouring via polymorphisms
Eric Culf
Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of clas…
Statistically secure uncloneable encryption of arbitrary messages
Archishna Bhattacharyya, Anne Broadbent, Eric Culf
Unconditional uncloneable encryption of a single bit with efficient encryption and decryption is now possible. However, whether the extension to messages of arbitrary length achiev…
The uncloneable bit exists
Archishna Bhattacharyya, Anne Broadbent, Eric Culf
We establish quantum uncloneable encryption with unconditional security, preventing two non-communicating adversaries from simultaneously decrypting a single ciphertext even wh…
The quantum smooth label cover problem is undecidable
Eric Culf, Kieran Mastel, Connor Paddock +1
We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a…
Optimal Untelegraphable Encryption and Implications for Uncloneable Encryption
Anne Broadbent, Eric Culf, Denis Rochette
We investigate the notion of untelegraphable encryption (UTE), a quantum encryption primitive that is a special case of uncloneable encryption (UE), where the adversary's capabilit…
Existence and nonexistence of commutativity gadgets for entangled CSPs
Eric Culf, Josse van Dobben de Bruyn, Matthijs Vernooij +1
Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSP…
Uncloneable Encryption from Decoupling
Archishna Bhattacharyya, Eric Culf
We show that uncloneable encryption exists with no computational assumptions, with security in the security parameter .
Towards Unconditional Uncloneable Encryption
Pierre Botteron, Anne Broadbent, Eric Culf +3
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…
RE-completeness of entangled constraint satisfaction problems
Eric Culf, Kieran Mastel
Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. S…
Approximation algorithms for noncommutative CSPs
Eric Culf, Hamoon Mousavi, Taro Spirig
Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their app…
New Approaches to Complexity via Quantum Graphs
Eric Culf, Arthur Mehta
Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. Defining well-fo…
Uncloneable Cryptographic Primitives with Interaction
Anne Broadbent, Eric Culf
Much of the strength of quantum cryptography may be attributed to the no-cloning property of quantum information. We construct three new cryptographic primitives whose security is…
Group coset monogamy games and an application to device-independent continuous-variable QKD
Eric Culf, Thomas Vidick, Victor V. Albert
We develop an extension of a recently introduced subspace coset state monogamy-of-entanglement game [Coladangelo, Liu, Liu, and Zhandry; Crypto'21] to general group coset states, w…
Rigidity for Monogamy-of-Entanglement Games
Anne Broadbent, Eric Culf
In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee's measurement outcome on a shared quantum state they prepared. We…