Guided syndrome decoding under posterior leakage

Andrés Florián-Quitián; Valérie Gauthier-Umaña; Estefanía Laverde-Becerra; Ricardo Villanueva-Polanco; Andrés Florián-Quitián; Valérie Gauthier-Umaña; Estefanía Laverde-Becerra; Ricardo Villanueva-Polanco

doi:10.3934/math.2026722

AIMS Mathematics

2026, Volume 11, Issue 6: 17673-17721. doi: 10.3934/math.2026722

Previous Article Next Article

Research article

Guided syndrome decoding under posterior leakage

1.
Department of Systems and Computing Engineering, Universidad de los Andes, Bogotá, Colombia
2.
Department of Systems and Computing Engineering, Universidad del Norte, Barranquilla, Colombia

Received: 21 March 2026 Revised: 15 May 2026 Accepted: 27 May 2026 Published: 17 June 2026
MSC : 11T61, 81P94

The syndrome decoding problem (SDP) is the computational foundation of code-based cryptography, underlying schemes such as McEliece, Niederreiter, and the Hamming quasi-cyclic key encapsulation mechanism standardized in 2025. While these constructions are secure in the standard model, practical implementations may still leak partial information about secret error vectors through physical attacks such as cold boot attacks and related side-channel scenarios. Motivated by this setting, we study syndrome decoding in the presence of probabilistic leakage. We adopt a bitwise Bayesian leakage model (BBLM) that represents leakage as coordinate-wise posterior beliefs over the secret error vector, providing a generic abstraction for noisy bitwise leakage. Building on this model, we develop a posterior-guided decoding framework that integrates leakage-derived information directly into the information set decoding (ISD) process through conditioned decoding and recursive instance reduction. The framework is decoder-agnostic and can be combined with different ISD variants and subset-enumeration strategies. As a proof of concept, we instantiate the framework using a genetic-algorithm-based enumerator guided by posterior-informed fitness functions. Experimental results on random linear codes and Reed–Muller (RM) codes show that informative leakage can guide subset selection toward conditioned instances that are substantially easier to decode under realistic asymmetric noise conditions.
- cryptography,
- quantum computing,
- side-channel attacks,
- information security,
- parity check codes,
- error correction codes,
- genetic algorithms
Citation: Andrés Florián-Quitián, Valérie Gauthier-Umaña, Estefanía Laverde-Becerra, Ricardo Villanueva-Polanco. Guided syndrome decoding under posterior leakage[J]. AIMS Mathematics, 2026, 11(6): 17673-17721. doi: 10.3934/math.2026722

Related Papers:

Abstract

The syndrome decoding problem (SDP) is the computational foundation of code-based cryptography, underlying schemes such as McEliece, Niederreiter, and the Hamming quasi-cyclic key encapsulation mechanism standardized in 2025. While these constructions are secure in the standard model, practical implementations may still leak partial information about secret error vectors through physical attacks such as cold boot attacks and related side-channel scenarios. Motivated by this setting, we study syndrome decoding in the presence of probabilistic leakage. We adopt a bitwise Bayesian leakage model (BBLM) that represents leakage as coordinate-wise posterior beliefs over the secret error vector, providing a generic abstraction for noisy bitwise leakage. Building on this model, we develop a posterior-guided decoding framework that integrates leakage-derived information directly into the information set decoding (ISD) process through conditioned decoding and recursive instance reduction. The framework is decoder-agnostic and can be combined with different ISD variants and subset-enumeration strategies. As a proof of concept, we instantiate the framework using a genetic-algorithm-based enumerator guided by posterior-informed fitness functions. Experimental results on random linear codes and Reed–Muller (RM) codes show that informative leakage can guide subset selection toward conditioned instances that are substantially easier to decode under realistic asymmetric noise conditions.

References

[1]	J. Justesen, T. Høholdt, A course in error-correcting codes, European Mathematical Society Zürich, 2004.
[2]	I. S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Ind. Appl. Math., 8 (1960), 300–304, https://doi.org/10.1137/0108018 doi: 10.1137/0108018
[3]	D. E. Muller, Application of boolean algebra to switching circuit design and to error detection, Trans. IRE Prof. Group Electron. Comput., EC-3 (1954), 6–12. https://doi.org/10.1109/IREPGELC.1954.6499441 doi: 10.1109/IREPGELC.1954.6499441
[4]	V. D. Goppa, A new class of linear correcting codes, Probl. Peredachi Inf., 6 (1970), 24–30.
[5]	R. J. McEliece, A public-key cryptosystem based on algebraic, Coding Theory, 4244 (1978), 114–116.
[6]	M. Baldi, F. Chiaraluce, Cryptanalysis of a new instance of mceliece cryptosystem based on QC-LDPC codes, 2007 IEEE International Symposium on Information Theory, 2007. https://doi.org/10.1109/ISIT.2007.4557609
[7]	V. M. Sidelnikov, A public-key cryptosystem based on binary reed-muller codes, Discrete Math. Appl., 4 (1994), 191–208, https://doi.org/10.1515/dma.1994.4.3.191 doi: 10.1515/dma.1994.4.3.191
[8]	E. M. Gabidulin, A. V. Paramonov, O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, In: D. W. Davies, Advances in cryptology — EUROCRYPT '91, Springer Berlin Heidelberg, 1991,482–489. https://doi.org/10.1007/3-540-46416-6_41
[9]	National Institute of Standards and Technology, Pqc standardization process, 2017. Avaible from: https://www.nist.gov/pqcrypto.
[10]	C. Aguilar-Melchor, J. C. Deneuville, A. Dion, Hamming quasi-cyclic (hqc), Technical report, 2025.
[11]	National Institute of Standards and Technology, Pqc standardization process: announcing four candidates to be standardized, plus fourth round candidates, 2022. Avaible from: https://csrc.nist.gov/news/2022/pqc-candidates-to-be-standardized-and-round-4.
[12]	F. X. Standaert, Introduction to side-channel attacks, In: I. M. R. Verbauwhede, Secure integrated circuits and systems, Springer, 2009, 27–42. https://doi.org/10.1007/978-0-387-71829-3_2
[13]	R. V. Polanco, Cold boot attacks on post-quantum schemes, Ph.D. Thesis, Royal Holloway, University of London, 2019.
[14]	J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, et al., Lest we remember: cold-boot attacks on encryption keys, Commun. ACM, 52 (2009), 91–98. https://doi.org/10.1145/1506409.1506429 doi: 10.1145/1506409.1506429
[15]	N. Heninger, H. Shacham, Reconstructing RSA private keys from random key bits, In: S. Halevi, Advances in cryptology - CRYPTO 2009, Springer Berlin Heidelberg, 2009. https://doi.org/10.1007/978-3-642-03356-8_1
[16]	W. Henecka, A. May, A. Meurer, Correcting errors in RSA private keys, In: T. Rabin, Advances in cryptology – CRYPTO 2010, Springer Berlin Heidelberg, 2010,351–369. https://doi.org/10.1007/978-3-642-14623-7_19
[17]	K. G. Paterson, A. Polychroniadou, D. L. Sibborn, A coding-theoretic approach to recovering noisy RSA keys, In: Advances in cryptology – ASIACRYPT 2012, Springer Berlin Heidelberg, 2012,386–403.
[18]	H. T. Lee, H. Kim, Y. J. Baek, J. H. Cheon, Correcting errors in private keys obtained from cold boot attacks, In: H. Kim, Information security and cryptology - ICISC 2011, Springer Berlin Heidelberg, 2012, 74–87. https://doi.org/10.1007/978-3-642-31912-9_6
[19]	B. Poettering, D. L. Sibborn, Cold boot attacks in the discrete logarithm setting, In: K. Nyberg, Topics in cryptology — CT-RSA 2015, Springer International Publishing, 2015,449–465. https://doi.org/10.1007/978-3-319-16715-2_24
[20]	M. Albrecht, C. Cid, Cold boot key recovery by solving polynomial systems with noise, In: J. Lopez, G. Tsudik, Applied cryptography and network security, Springer Berlin Heidelberg, 2011, 57–72. https://doi.org/10.1007/978-3-642-21554-4_4
[21]	A. A. Kamal, A. M. Youssef, Applications of SAT solvers to AES key recovery from decayed key schedule images, 2010 Fourth International Conference on Emerging Security Information, Systems and Technologies, 2010,216–220. https://doi.org/10.1109/SECURWARE.2010.42
[22]	K. G. Paterson, R. Villanueva-Polanco, Cold boot attacks on NTRU, In: A. Patra, N. P. Smart, Progress in cryptology – INDOCRYPT 2017, Springer International Publishing, 2017,107–125. https://doi.org/10.1007/978-3-319-71667-1_6
[23]	R. Villanueva-Polanco, Cold boot attacks on bliss, In: P. Schwabe, N. Thériault, Progress in cryptology – LATINCRYPT 2019, Springer International Publishing, 2019, 40–61. https://doi.org/10.1007/978-3-030-30530-7_3
[24]	R. Villanueva-Polanco, E. Angulo-Madrid, Cold boot attacks on the supersingular isogeny key encapsulation (SIKE) mechanism, Appl. Sci., 11 (2021), 193. https://doi.org/10.3390/app11010193 doi: 10.3390/app11010193
[25]	M. R. Albrecht, A. Deo, K. G. Paterson, Cold boot attacks on ring and module LWE keys under the NTT, IACR Trans. Cryptographic Hardware Embedded Syst., 2018 (2018), 173–213, https://doi.org/10.13154/tches.v2018.i3.173-213 doi: 10.13154/tches.v2018.i3.173-213
[26]	G. Banegas, R. Villanueva-Polanco, On recovering block cipher secret keys in the cold boot attack setting, Cryptography Commun., 17 (2025), 311–335. https://doi.org/10.1007/s12095-022-00625-z doi: 10.1007/s12095-022-00625-z
[27]	G. Teseleanu, Partial exposure attacks against a family of rsa-like cryptosystems, Cryptography, 9 (2025), 2. https://doi.org/10.3390/cryptography9010002 doi: 10.3390/cryptography9010002
[28]	A. Esser, A. May, J. Verbel, W. Wen, Partial key exposure attacks on bike, rainbow and NTRU, In: Y. Dodis, T. Shrimpton, Advances in cryptology – CRYPTO 2022, Springer Nature Switzerland, 2022,346–375. https://doi.org/10.1007/978-3-031-15982-4_12
[29]	E. Kirshanova, A. May, Decoding mceliece with a hint – secret Goppa key parts reveal everything, In: C. Galdi, S. Jarecki, Security and cryptography for networks, Springer International Publishing, 2022, 3–20. https://doi.org/10.1007/978-3-031-14791-3_1
[30]	G. D'Alconzo, A. Esser, A. Gangemi, C. Sanna, Sneaking up the ranks: partial key exposure attacks on rank-based schemes, Designs Codes Cryptography, 94 (2024), 15. https://doi.org/10.1007/s10623-025-01738-1 doi: 10.1007/s10623-025-01738-1
[31]	Y. Seto, H. Furue, A. Takayasu, Partial key exposure attacks on UOV and its variants, Cryptology ePrint Arch., 2025.
[32]	V. Gauthier-Umaña, A. M. Ochoa-Toro, R. Villanueva-Polanco, Seed recovery from probabilistic leakage via resource-aware, posterior-guided enumeration, IEEE Access, 14 (2026), 17264–17277. https://doi.org/10.1109/ACCESS.2026.3659061 doi: 10.1109/ACCESS.2026.3659061
[33]	E. Prange, The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8 (1962), 5–9. https://doi.org/10.1109/TIT.1962.1057777 doi: 10.1109/TIT.1962.1057777
[34]	I. Reed, A class of multiple-error-correcting codes and the decoding scheme, Trans. IRE Prof. Group Inf. Theory, 4 (1954), 38–49. https://doi.org/10.1109/TIT.1954.1057465 doi: 10.1109/TIT.1954.1057465
[35]	E. Abbe, A. Shpilka, M. Ye, Reed–Muller codes: theory and algorithms, IEEE Trans. Inf. Theory, 67 (2020), 3251–3277. https://doi.org/10.1109/TIT.2020.3004749 doi: 10.1109/TIT.2020.3004749
[36]	M. Plotkin, Binary codes with specified minimum distance, IRE Trans. Inf. Theory, 6 (1960), 445–450. https://doi.org/10.1109/TIT.1960.1057584 doi: 10.1109/TIT.1960.1057584
[37]	J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, et al., Lest we remember: cold-boot attacks on encryption keys, Commun. ACM, 52 (2009), 91–98. https://doi.org/10.1145/1506409.150642 doi: 10.1145/1506409.150642
[38]	S. Lindenlauf, H. Höfken, M. Schuba, Cold boot attacks on DDR2 and DDR3 SDRAM, 2015 10th International Conference on Availability, Reliability and Security, 2015,287–292. https://doi.org/10.1109/ARES.2015.28
[39]	Y. S. Won, J. Y. Park, D. G. Han, S. Bhasin, Practical cold boot attack on IoT device - case study on Raspberry Pi -, 2020 IEEE International Symposium on the Physical and Failure Analysis of Integrated Circuits (IPFA), 2020. https://doi.org/10.1109/IPFA49335.2020.9260613
[40]	J. Stern, A method for finding codewords of small weight, Proceedings of the 3rd International Colloquium on Coding Theory and Applications, 1988,106–113. https://doi.org/10.5555/646721.702702
[41]	A. Becker, A. Joux, A. May, A. Meurer, Decoding random binary linear codes in 2$^{n/20}$: How 1+ 1 = 0 improves information set decoding, In: D. Pointcheval, T. Johansson, Advances in cryptology – EUROCRYPT 2012, Springer, 2012,520–536. https://doi.org/10.1007/978-3-642-29011-4_31
[42]	A. May, I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, In: E. Oswald, M. Fischlin, Advances in cryptology – EUROCRYPT 2015, Springer, 2015,203–228. https://doi.org/10.1007/978-3-662-46800-5_9
[43]	D. Dachman-Soled, H. Gong, M. Kulkarni, A. Shahverdi, Partial key exposure in ring-lwe-based cryptosystems: attacks and resilience, Cryptology ePrint Arch., 2018.
[44]	A. Esser, A. May, J. Verbel, W. Wen, Partial key exposure attacks on bike, rainbow and NTRU, Ann. Int. Cryptology Conference, Springer, 2022,346–375.
[45]	Q. Guo, D. Nabokov, E. Suvanto, T. Johansson, Key recovery attacks on approximate homomorphic encryption with non-worst-case noise flooding countermeasures, 33rd USENIX Security Symposium (USENIX Security 24), 2024, 7447–7461.
[46]	A. L. Horlemann, S. Puchinger, J. Renner, T. Schamberger, A. Wachter-Zeh, Information-set decoding with hints, In: A. Wachter-Zeh, H. Bartz, G. Liva, Code-based cryptography, Springer International Publishing, 2022, 60–83. https://doi.org/10.1007/978-3-030-98365-9_4
[47]	Q. Guo, A. Johansson, T. Johansson, A key-recovery side-channel attack on classic McEliece implementations, IACR Trans. Cryptographic Hardware Embedded Syst., 2022 (2022), 800–827. https://doi.org/10.46586/tches.v2022.i4.800-827 doi: 10.46586/tches.v2022.i4.800-827
[48]	D. Dachman-Soled, L. Ducas, H. Gong, M. Rossi, Lwe with side information: Attacks and concrete security estimation, In: D. Micciancio, T. Ristenpart, Advances in cryptology – CRYPTO 2020, Springer, 2020,329–358. https://doi.org/10.1007/978-3-030-56880-1_12
[49]	L. D'Achille, A. Esser, N. Kraus, Syndrome decoding with hints, Cryptology ePrint Arch., 2026.
[50]	P. Simmons, Security through amnesia: a software-based solution to the cold boot attack on disk encryption, Proceedings of the 27th Annual Computer Security Applications Conference, 2011, 73–82. https://doi.org/10.1145/2076732.207674
[51]	M. Neagu, S. Manich, Defending cache memory against cold-boot attacks boosted by power or em radiation analysis, Microelectron. J., 62 (2017), 85–98. https://doi.org/10.1016/j.mejo.2017.02.010 doi: 10.1016/j.mejo.2017.02.010
[52]	T. Farheen, S. Roy, A. Cannon, J. Di, S. Tajik, D. Forte, Amnesiac memory: a self-destructive polymorphic mechanism against cold boot data remanence attack, Proceedings of the Great Lakes Symposium on VLSI 2024, 2024,564–568. https://doi.org/10.1145/3649476.3658778
[53]	P. Jedlicka, L. Malina, P. Socha, T. Gerlich, Z. Martinasek, J. Hajny, On secure and side-channel resistant hardware implementations of post-quantum cryptography, Proceedings of the 17th International Conference on Availability, Reliability and Security, 2022,144. https://doi.org/10.1145/3538969.3544423
[54]	A. Azouaoui, I. Chana, M. Belkasmi, Efficient information set decoding based on genetic algorithms, Int. J. Commun. Network Syst. Sci., 5 (2012), 423–429. https://doi.org/10.4236/ijcns.2012.57052 doi: 10.4236/ijcns.2012.57052
[55]	A. Esser, J. Verbel, F. Zweydinger, E. Bellini, Sok: cryptographicestimators – a software library for cryptographic hardness estimation, Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, 2024,560–574. https://doi.org/10.1145/3634737.3645007
[56]	I. Márquez-Corbella, J. P. Tillich, Using reed-solomon codes in the $(u\| u+ v)$ construction and an application to cryptography, 2016 IEEE International Symposium on Information Theory (ISIT), 2016,930–934. https://doi.org/10.1109/ISIT.2016.7541435
[57]	I. Márquez-Corbella, J. P. Tillich, Attaining capacity with iterated $(u\| u+ v)$ codes based on AG codes and Koetter–Vardy soft decoding, 2017 IEEE International Symposium on Information Theory (ISIT), 2017, 6–10. https://doi.org/10.1109/ISIT.2017.8006479
[58]	T. Debris-Alazard, N. Sendrier, J. P. Tillich, Wave: a new code-based signature scheme, IACR Cryptology ePrint Arch., 2018.
[59]	T. Debris-Alazard, N. Sendrier, J. P. Tillich, Surf: a new code-based signature scheme, IACR Cryptology ePrint Arch., 2022.
[60]	J. Cho, J. S. No, Y. Lee, Z. Koo, Y. S. Kim, Enhanced pqsigrm: code-based digital signature scheme with short signature and fast verification for post-quantum cryptography, Cryptology ePrint Arch., 2022.
[61]	J. Stern, A method for finding codewords of small weight, International Colloquium on Coding Theory and Applications, Springer, 1988,106–113.
[62]	A. May, A. Meurer, E. Thomae, Decoding random linear codes in $\tilde{O}(2^{0.054n})$, In: D. H. Lee, X. Wang, Advances in cryptology – ASIACRYPT 2011, Springer, 2011,107–124. https://doi.org/10.1007/978-3-642-25385-0_6

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)