### 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.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
Code-based cryptography OHCP OCP worst-case to average-case search-to-decision reduction
Contact author(s)
maxime bombar @ inria fr
alain couvreur @ inria fr
thomas debris @ inria fr
History
2022-12-27: approved
See all versions
Short URL
https://ia.cr/2022/1751

CC BY

BibTeX

@misc{cryptoeprint:2022/1751,
author = {Maxime Bombar and Alain Couvreur and Thomas Debris-Alazard},
title = {On The Pseudorandomness of the Decoding Problem via the Oracle Comparison Problem},
howpublished = {Cryptology ePrint Archive, Paper 2022/1751},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1751}},
url = {https://eprint.iacr.org/2022/1751}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.