Pseudorandomness of Decoding, Revisited: Adapting OHCP to Code-Based Cryptography
Pages 253 - 283
Abstract
Recent code-based cryptosystems rely, among other things, on the hardness of the decisional 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, and little is known about its relationships with the search version, especially for structured variants. On the other hand, in the world of Euclidean lattices, the situation is rather different, and many reductions exist, both for unstructured and structured versions of the underlying problems. For the latter versions, a powerful tool called the framework (for Oracle with Hidden Center Problem), which appears to be very general, has been introduced by Peikert et al. (STOC 2017) and has proved to be very useful as a black box inside reductions.
In this work, we revisit this technique and extract the very essence of this framework, namely the Oracle Comparison Problem (), to show how to recover the support of the error, solving an Oracle with Hidden Support Problem (), more suitable for code-based cryptography. This yields a new worst-case to average-case search-to-decision reduction for the Decoding Problem, as well as a new average-case to average-case reduction. We then turn to the structured versions and explain why this is not as straightforward as for Euclidean lattices. If we fail to give a search-to-decision reduction for structured codes, we believe that our work opens the way towards new reductions for structured codes, given that the framework proved 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 reduction is known.
References
[1]
Aguilar Melchor, C., et al.: BIKE. Round 4 Submission to the NIST Post-Quantum Cryptography Call, v. 5.1, October 2022. https://bikesuite.org
[2]
Aguilar Melchor, C., et al.: BIKE. Round 3 Submission to the NIST Post-Quantum Cryptography Call, v. 4.2, September 2021. https://bikesuite.org
[3]
Aguilar Melchor, C., et al.: HQC. Round 4 Submission to the NIST Post-Quantum Cryptography Call, October 2022. https://pqc-hqc.org/
[4]
Aguilar Melchor, C., et al.: HQC. Round 3 Submission to the NIST Post-Quantum Cryptography Call, June 2021. https://pqc-hqc.org/doc/hqc-specification_2021-06-06.pdf
[5]
Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11–14 October 2003, Cambridge, MA, USA, Proceedings, pp. 298–307. IEEE Computer Society (2003).
[6]
Barak B et al. Rogaway P et al. Leftover hash lemma, revisited Advances in Cryptology – CRYPTO 2011 2011 Heidelberg Springer 1-20
[7]
Barg, A., Forney., G.D.: Random codes: minimum distances and error exponents. IEEE Trans. Inf. Theory 48(9), 2568–2573 (2002).
[8]
Becker A, Joux A, May A, and Meurer A Pointcheval D and Johansson T Decoding random binary linear codes in 2n/20: how 1 + 1 = 0 improves information set decoding Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 520-536
[9]
Berlekamp E, McEliece R, and van Tilborg H On the inherent intractability of certain coding problems IEEE Trans. Inform. Theory 1978 24 3 384-386
[10]
Bombar M, Couteau G, Couvreur A, and Ducros C Handschuh H and Lysyanskaya A Correlated pseudorandomness from the hardness of quasi-abelian decoding Advances in Cryptology - CRYPTO 2023 2023 Cham Springer 567-601
[11]
Bombar, M., Couvreur, A., Debris-Alazard, T.: On codes and learning with errors over function fields. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 513–540. Springer, Cham (2022)., https://arxiv.org/pdf/2202.13990.pdf
[12]
Bombar, M., Couvreur, A., Debris-Alazard, T.: Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography (2023). Extended version: https://eprint.iacr.org/2022/1751
[13]
Both, L., May, A.: Optimizing BJMM with nearest neighbors: full decoding in and McEliece security. In: WCC Workshop on Coding and Cryptography, September 2017. http://wcc2017.suai.ru/Proceedings_WCC2017.zip
[14]
Boudgoust K, Jeudy C, Roux-Langlois A, and Wen W Moriai S and Wang H Towards classical hardness of module-LWE: the linear rank case Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 289-317
[15]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Micciancio D and Ristenpart T Efficient pseudorandom correlation generators from ring-LPN Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 387-416
[16]
Brakerski Z, Lyubashevsky V, Vaikuntanathan V, and Wichs D Ishai Y and Rijmen V Worst-case hardness for LPN and cryptographic hashing via code smoothing Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 619-635
[17]
Canto Torres R and Sendrier N Takagi T Analysis of information set decoding for a sub-linear error weight Post-Quantum Cryptography 2016 Cham Springer 144-161
[18]
Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., Tillich, J.: Statistical decoding 2.0: reducing decoding to LPN. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13794, pp. 477–507. Springer, Cham (2022)., https://eprint.iacr.org/2022/1000
[19]
Castryck W and Decru T Hazay C and Stam M An efficient key recovery attack on SIDH Advances in Cryptology - EUROCRYPT 2023 2023 Cham Springer 423-447
[20]
Debris-Alazard, T., Ducas, L., Resch, N., Tillich, J.: Smoothing codes and lattices: systematic study and new bounds. CoRR abs/2205.10552 (2022).
[21]
Debris-Alazard, T., Remaud, M., Tillich, J.: Quantum reduction of finding short code vectors to the decoding problem. preprint, November 2021. https://arxiv.org/abs/2106.02747, arXiv:2106.02747
[22]
Debris-Alazard, T., Resch, N.: Worst and average case hardness of decoding via smoothing bounds. Preprint, December 2022, eprint
[23]
Debris-Alazard T, Sendrier N, and Tillich J-P Galbraith SD and Moriai S Wave: a new family of trapdoor one-way preimage sampleable functions based on codes Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 21-51
[24]
Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of 5th Joint Soviet-Swedish International Workshop Informatics and Theory, pp. 50–52. Moscow (1991)
[25]
Fischer J-B and Stern J Maurer U An efficient pseudo-random generator provably as secure as syndrome decoding Advances in Cryptology — EUROCRYPT ’96 1996 Heidelberg Springer 245-255
[26]
Gaborit, P.: Shorter keys for code based cryptography. In: Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), pp. 81–91. Bergen, Norway, March 2005
[27]
Gaborit, P., Zémor, G.: Asymptotic improvement of the Gilbert-Varshamov bound for linear codes. In: Proceedings of IEEE International Symposium Information and Theory - ISIT 2006, pp. 287–291. Seattle, USA (Jun 2006)
[28]
Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75, 565–599 (2015). https://hal.archives-ouvertes.fr/hal-01240452
[29]
Lyubashevsky V, Peikert C, and Regev O Gilbert H On ideal lattices and learning with errors over rings Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 1-23
[30]
Maino L, Martindale C, Panny L, Pope G, and Wesolowski B Hazay C and Stam M A direct key recovery attack on SIDH Advances in Cryptology – EUROCRYPT 2023 2023 Cham Springer 423-447
[31]
May A and Ozerov I Oswald E and Fischlin M On computing nearest neighbors with applications to decoding of binary linear codes Advances in Cryptology – EUROCRYPT 2015 2015 Heidelberg Springer 203-228
[32]
Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 461–473 (2017)
[33]
Pellet-Mary, A., Stehlé, D.: On the hardness of the NTRU problem. In: ASIACRYPT 2021. LNCS, vol. 13090, pp. 3–35, Springer, Cham (2021)., https://hal.archives-ouvertes.fr/hal-03348022
[34]
Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962).
[35]
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22–24 May 2005, pp. 84–93 (2005).
[36]
Robert D Hazay C and Stam M Breaking SIDH in polynomial time Advances in Cryptology - EUROCRYPT 2023 Cham Springer 423-447
[37]
Rosca M, Stehlé D, and Wallet A Nielsen JB and Rijmen V On the ring-LWE and polynomial-LWE problems Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 146-173
[38]
Sendrier N Yang B-Y Decoding one out of many Post-Quantum Cryptography 2011 Heidelberg Springer 51-67
[39]
Stehlé D and Steinfeld R Paterson KG Making NTRU as secure as worst-case problems over ideal lattices Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 27-47
[40]
Stehlé D, Steinfeld R, Tanaka K, and Xagawa K Matsui M Efficient public key encryption based on ideal lattices Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 617-635
[41]
Stern J Cohen G and Wolfmann J A method for finding codewords of small weight Coding Theory and Applications 1989 Heidelberg Springer 106-113
[42]
Yu Yu and Zhang J Malkin T and Peikert C Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 473-501
Index Terms
- Pseudorandomness of Decoding, Revisited: Adapting OHCP to Code-Based Cryptography
Index terms have been assigned to the content through auto-classification.
Recommendations
Pseudorandomness for Approximate Counting and Sampling
We study computational procedures that use both randomness and nondeterminism. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.
Our main technical contribution allows one to "boost" a given hardness ...
Lossy Cryptography from Code-Based Assumptions
Advances in Cryptology – CRYPTO 2024AbstractOver the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. ...
Pseudorandomness and Average-Case Complexity via Uniform Reductions
CCC '02: Proceedings of the 17th IEEE Annual Conference on Computational ComplexityImpagliazzo and Wigderson (FOCS 2002) recently gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely, that EXP does not equal BPP). Unlike results in the nonuniform setting, their result does not ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© International Association for Cryptologic Research 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 December 2023
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in