Denis Rochette

Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions—subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of quantum tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of the min-entropy and fixed-point restrictions in the classical setting. Our results unify and extend previous work, subsuming both the classical and unitary-only adversarial families. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection (which allows either rejection or recovery of the original message) cannot protect even against the family of constant functions. This family is of size $2^n$. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to $2^{2^{\alpha n}}$ for any constant $\alpha <\frac{1}{2}$, leading to our conjecture on the existence of what we call \emph{universal} quantum tamper detection. Taken together, our results provide evidence that quantum tamper detection is strictly more powerful than its classical counterpart.

We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) nonlocal game for which the value of the Navascués, Pironio, and Acín (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE. As a first step, we construct a mapping from Turing machines to elements of the tensor product of free algebras, showing that deciding positivity of those elements is coRE-hard. As a second step, we extend this mapping to further realize these elements as game polynomials for BCS games.

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 capabilities are restricted to producing purely classical information rather than arbitrary quantum states. We present an unconditionally secure construction of UTE that achieves untelegraphable-indistinguishability security, together with natural multi-ciphertext and bounded collusion-resistant extensions, without requiring any additional assumptions. We also extend this to the unbounded case, assuming pseudo-random unitaries, yielding everlasting security. Furthermore, we derive results on UE using approaches from UTE in the following ways: first, we provide new lower bounds on UTE, which give new lower bounds on UE; second, we prove an asymptotic equivalence between UTE and UE in the regime where the number of adversaries in UE grows. These results suggest that UTE may provide a new path toward achieving a central open problem in the area: indistinguishability security for UE in the plain model.

Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions—subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of quantum tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of the min-entropy and fixed-point restrictions in the classical setting. Our results unify and extend previous work, subsuming both the classical and unitary-only adversarial families. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection (which allows either rejection or recovery of the original message) cannot protect even against the family of constant functions. This family is of size $2^n$. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to $2^{2^{\alpha n}}$ for any constant $\alpha <\frac{1}{2}$, leading to our conjecture on the existence of what we call \emph{universal} quantum tamper detection. Taken together, our results provide evidence that quantum tamper detection is strictly more powerful than its classical counterpart.

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 capabilities are restricted to producing purely classical information rather than arbitrary quantum states. We present an unconditionally secure construction of UTE that achieves untelegraphable-indistinguishability security, together with natural multi-ciphertext and bounded collusion-resistant extensions, without requiring any additional assumptions. We also extend this to the unbounded case, assuming pseudo-random unitaries, yielding everlasting security. Furthermore, we derive results on UE using approaches from UTE in the following ways: first, we provide new lower bounds on UTE, which give new lower bounds on UE; second, we prove an asymptotic equivalence between UTE and UE in the regime where the number of adversaries in UE grows. These results suggest that UTE may provide a new path toward achieving a central open problem in the area: indistinguishability security for UE in the plain model.