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.

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution (SIS) problem to the Learning with Errors (LWE) problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry[CLZ22] that this reduction can be made more powerful by replacing the LWE problem with a quantum equivalent, where the errors are given in quantum superposition. In parallel, Regev's reduction has recently been adapted in the context of code-based cryptography by Debris, Remaud and Tillich[DRT23], who showed a reduction between the Short Codeword Problem and the Decoding Problem (the DRT reduction). This motivates the study of the Quantum Decoding Problem (QDP), which is the Decoding Problem but with errors in quantum superposition and see how it behaves in the DRT reduction. The purpose of this paper is to introduce and to lay a firm foundation for QDP. We first show QD Pis likely to be easier than classical decoding, by proving that it can be solved in quantum polynomial time in a large regime of noise whereas no non-exponential quantum algorithm is known for the classical decoding problem. Then, we show that QDP can even be solved (albeit not necessarily efficiently) beyond the information theoretic Shannon limit for classical decoding. We give precisely the largest noise level where we can solve QDP giving in a sense the information theoretic limit for this new problem. Finally, we study how QDP can be used in the DRT reduction. First, we show that our algorithms can be properly used in the DRT reduction showing that our quantum algorithms for QDP beyond Shannon capacity can be used to find minimal weight codewords in a random code. On the negative side, we show that the DRT reduction cannot be, in all generality, a reduction between finding small codewords and QDP by exhibiting quantum algorithms for QDP where this reduction entirely fails. Our proof techniques include the use of specific quantum measurements, such as q-ary unambiguous state discrimination and pretty good measurements as well as strong concentration bounds on weight distribution of random shifted dual codes, which we relate using quantum Fourier analysis.

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.