Andre Chailloux

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called ``decoded quantum interferometry'' that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS_\infty problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.

Device-independent cryptographic protocols are by definition more secure than their device-dependent counterparts, since they do not rely on any assumptions regarding the internal workings of the apparatus used to implement them. Thus far, the device-independent approach has been successfully applied to problems such as quantum-key distribution and randomness generation, but it is not a priori clear whether it can be applied to protocols in the mistrustful cryptography class, where the parties do not trust one another. In this work we show that for bit-commitment and coin flipping a device-independent treatment is possible.

Position verification is a cryptographic primitive aiming at securely certifying the location of a party in space. Informationally-secure PV was shown to be impossible through the existence of universal attacks both in the classical setting [Chandran et al., 2009] and in the quantum setting [Buhrman et al., 2014; Beigi and König,2011]. However, while classical attacks require the same amount of resources than the protocol, known universal quantum attacks make use of an exponential amount of entanglement through a technique known as Instantaneous Nonlocal Quantum Computation. In this paper, we characterize attacks to a "BB84-like" protocol already proposed in previous work [Kent et al., 2011], based on single photons polarized at an angle θ. We consider adversaries sharing maximally entangled pairs of qudits and find low-dimensional INQC attacks. We find exact attacks against some rational angles, including some sitting outside of the Clifford hierarchy (e.g. π/6), and show no θ allows to tolerate errors higher than ~0.5% against adversaries holding two ebits per protocol's qubit.