Compare Papers

Paper 1

Send the Key in Cleartext: Halving Key Consumption while Preserving Unconditional Security in QKD Authentication

Claudia De Lazzari, Francesco Stocco, Edoardo Signorini, Giacomo Fregona, Fernando Chirici, Damiano Giani, Tommaso Occhipinti, Guglielmo Morgari, Alessandro Zavatta, Davide Bacco

Year
2026
Journal
arXiv preprint
DOI
arXiv:2603.25496
arXiv
2603.25496

Quantum Key Distribution (QKD) protocols require Information-Theoretically Secure (ITS) authentication of the classical channel to preserve the unconditional security of the distilled key. Standard ITS schemes are based on one-time keys: once a key is used to authenticate a message, it must be discarded. Since QKD requires mutual authentication, two independent one-time keys are typically consumed per round, imposing a non-trivial overhead on the net secure key rate. In this work, we present the authentication-with-response scheme, a novel ITS authentication scheme based on $\varepsilon$-Almost Strongly Universal$_2$ ($\varepsilon$-ASU$_2$) functions, whose IT security can be established in the Universal Composability (UC) framework. The scheme achieves mutual authentication consuming a single one-time key per QKD round, halving key consumption compared to the state-of-the-art.

Open paper

Paper 2

The quantum smooth label cover problem is undecidable

Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig

Year
2025
Journal
arXiv preprint
DOI
arXiv:2510.03477
arXiv
2510.03477

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 result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.

Open paper