Paper 2022/1751

On The Pseudorandomness of the Decoding Problem via the Oracle Comparison Problem

Abstract

Code-based cryptography relies, among other things, on the hardness of the Decoding Problem. If the search version is well understood, both from practical and theoretical standpoints, the decision version has been less studied in the literature. Until the work of Brakerski et al. (Eurocrypt 2019), no worst-case to average-case reduction was even known, and most reductions focus on the plain unstructured Decoding Problem. In the world of Euclidean lattices though, the situation is rather different and many reductions exist, both for unstuctured and structured versions of the underlying problems. For the latter versions, a powerful tool called the O(H)CP framework has been introduced by Peikert et al. (STOC 2017) and has proved itself very useful as a black box inside reductions. In this work, we adapt this technique to the coding-theoretic setting, and give a new worst-case hardness of the decision Decoding Problem, as well as a new (average-case) search-to-decision reduction. We then turn to the structured version and explain why this is not as straightforward as for Euclidean lattices. If we fail to give a search-to-decision reduction in this case, we believe that our work opens the way towards new reductions for structured codes given that the O(H)CP framework proved itself to be so powerful in lattice–based cryptography. Furthermore, we also believe that this technique could be extended to codes endowed with other metrics, such as the rank metric, for which no search-to-decision reduction is known.