ACM Conference on Post-Quantum and Quantum-based Security
Direct information lower bounds for one-way communication complexity problems: Applications to the demonstration of an unconditional quantum advantage and to cryptography (Short Paper)
Romain Alléaume, Gabriel Blanchot, Philippe Gaborit, Francesco Mazzoncini
Abstract
Information cost is often treated as a secondary quantity in communication complexity, even when the operational resource of interest is the information revealed by a protocol rather than its message length. This mismatch becomes particularly important in quantum communication and cryptography, where classical leakage must be compared directly with the information carried by quantum states. For this reason, we derive direct finite-size lower bounds, with explicit constants, on the information cost of one-way private-coin protocols for Hidden Matching, a communication-complexity problem, and two related tasks: Sampling Matching and Beta-Partial Matching. These bounds lead to two concrete applications. First, they provide a universal classical benchmark for coherent-state implementations of Sampling Matching, opening a route to an unconditional quantum advantage in information cost for a one-way communication complexity problem on a photonic platform. Second, they substantially tighten the analysis of HM-QCT, a recent everlastingly secure hybrid post-quantum/QKD protocol, bringing its implementation closer to realistic optical parameters while preserving the possibility of exceeding the fundamental rate-loss limits of standard QKD.