Solving a Modified Syndrome Decoding Problem using Integer Programming



Syndrome decoding, integer linear programming, simplex algorithm


In this article, we model a variant of the well-known syndrome decoding problem as a linear optimization problem. Most common algorithms used for solving optimization problems, e.g. the simplex algorithm, fail to find a valid solution for the syndrome decoding problem over a finite field. However, our simulations prove that a slightly modified version of the syndrome decoding problem can be solved by the simplex algorithm. More precisely, the algorithm returns a valid error vector when the syndrome vector is an integer vector, i.e.,the matrix-vector multiplication, is realized over Z, instead of Fq.


[1] Augot, D.; Finiasz, M.; Sendrier, N. (2005). A family of fast syndrome based cryptographic hash functions. In Ed Dawson, Serge Vaudenay (editors). Progress cryptology-Mycrypt First international conference on cryptology Malaysia, Springer LNCS, 3715, 64-83, Kuala Lumpur, Malaysia, Sept. 2005.

[2] Baldi, M.; Chiaraluce, F. (2007). Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, 2591-2595, Nice, France, June 2007.

[3] Bardet, M.; Chaulet, J.; Dragoi, V.; Otmani, A.; Tillich, J.-P. (2016). Cryptanalysis of the McEliece public key cryptosystem based on polar codes. In Post-Quantum Cryptography 2016, Springer LNCS, 9606, 118-143, Fukuoka, Japan, Feb. 2016.

[4] Bardet, M.; Dragoi, V.; Luque, J.; Otmani, A.(2016). Weak keys for the quasi-cyclic MDPC public key encryption scheme. In Progress in Cryptology - AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Springer LNCS, 9646, 346-367, Fes, Morocco, April 13-15, 2016.

[5] Berger, T.P.; Loidreau, P.(2005). How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr., 35(1),63-79, 2005.

[6] Berlekamp, E.; McEliece, R.; van Tilborg, H.(1978). On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, 24(3),384-386, May 1978.

[7] Bernstein, D.J. ; Lange, T.; Peters, C.(2010). Wild McEliece. In A. Biryukov, G. Gong, D. Stinson, editors, Selected Areas in Cryptography, Springer LNCS, 6544, 143-158, 2010.

[8] Bernstein, D.J. ; Lange, T.; Peters, C.(2011). Wild McEliece Incognito. In B.-Y. Yang, editor, Post-Quantum Cryptography 2011, Springer LNCS, 7071, 244-254. Springer Berlin Heidelberg, 2011.

[9] Borghoff, J.(2012). Mixed-integer linear programming in the analysis of trivium and ktantan. IACR Cryptology ePrint Archive, 2012. URL:

[10] Borghoff, J.; Knudsen, L.R.; Stolpe, M.(2009). Bivium as a mixed-integer linear programming problem. In Cryptography and Coding, Springer LNCS, 5921, 133-152. Springer Berlin Heidelberg, 2009.

[11] Chizhov, I.V.; Borodin, M.A.(2014). Effective attack on the McEliece cryptosystem based on Reed-Muller codes. Discrete Math. Appl., 24(5),273-280, 2014.

[12] Courtois, N.; Finiasz, M.; Sendrier, N.(2001). How to achieve a McEliece-based digital signature scheme. In Advances in Cryptology - ASIACRYPT 2001, Springer LNCS 2248, 157-174, 2001. Springer.

[13] Couvreur, A.; Gaborit, P.; Gauthier-Umaña, V.; Otmani, A., Tillich, J.-P. (2014). Distinguisherbased attacks on public-key cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr., 73 (2),641-666, 2014.

[14] Couvreur, A.; Márquez-Corbella, I.; Pellikaan, R.(2014). A polynomial time attack against algebraic geometry code based public key cryptosystems. In Proc. IEEE Int. Symposium Inf. Theory - ISIT 2014, 1446-1450, June 2014.

[15] Couvreur, A.; Otmani, A.; Tillich, J.-P.(2013). New identities relating wild Goppa codes. Finite Fields Appl., 29,178-197, 2014.

[16] Couvreur, A.; Otmani, A.; Tillich, J.-P.(2014). Polynomial time attack on wild McEliece over quadratic extensions. In P. Q. Nguyen and E. Oswald, editors, Advances in Cryptology - EUROCRYPT 2014, Springer LNCS, 8441, 17-39. Springer Berlin Heidelberg, 2014.

[17] Dragoi, V.; Talé Kalachi, H.(2018). Cryptanalysis of a public key encryption scheme based on QC-LDPC and QC-MDPC codes. IEEE Communications Letters, 22(2),264-267, Feb 2018.

[18] Dragoi, V.; Beiu, V.; Bucerzan, D.(2019). Vulnerabilities of the mceliece variants based on polar codes. In J.-L. Lanet and C. Toma, editors, Innovative Security Solutions for Information Technology and Communications, Springer LNCS,11359, 376-390, Cham, 2019. Springer International Publishing.

[19] Faugí¨re, J.-C. ; Otmani, A.; Perret, L.; de Portzamparc, F.; Tillich, J.-P. (2016). Folding alternant and Goppa Codes with non-trivial automorphism groups. IEEE Trans. Inform. Theory, 62(1), 184-198, 2016.

[20] Faure, C.; Minder, L.(2008). Cryptanalysis of the McEliece cryptosystem over hyperelliptic curves. In Proceedings of the eleventh International Workshop on Algebraic and Combinatorial Coding Theory, 99-107, Pamporovo, Bulgaria, June 2008.

[21] Ganian, R.; Ordyniak, S.(2019). Solving integer linear programs by exploiting variable-constraint interactions: A survey. Algorithms, 12(12),248, 2019.

[22] B.Gou (2008). Generalized integer linear programming formulation for optimal pmu placement. IEEE transactions on Power Systems, 23(3),1099-1104, 2008.

[23] Gueye, C.T. ; Mboup, E.H.M. (2013). Secure cryptographic scheme based on modified Reed Muller codes. International Journal of Security and Its Applications, 7(3),55-64, 2013.

[24] Hooshmand, R.; Shooshtari, M.K. ; Eghlidos, T.; Aref, M.(2014). Reducing the key length of McEliece cryptosystem using polar codes. In 2014 11th International ISC Conference on Information Security and Cryptology (ISCISC), 104-108. IEEE, 2014.

[25] Janwa, H.; Moreno, O. (1996). McEliece public key cryptosystems using algebraic-geometric codes. Des. Codes Cryptogr., 8(3),293-307, 1996.

[26] Johnson, E.L. ; Nemhauser, G.L. ; Savelsbergh, M.W.(2000) . Progress in linear programmingbased algorithms for integer programming: An exposition. Informs journal on computing, 12(1), 2-23, 2000.

[27] Karp, R.M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, 85-103. Springer, 1972.

[28] Landais, G.; Tillich, J.-P. (2013). An efficient attack of a McEliece cryptosystem variant based on convolutional codes. In P. Gaborit, editor, Post-Quantum Cryptography'13, Springer LNCS, 7932, 102-117. Springer, June 2013.

[29] Lenstra Jr, H.W.(1983). Integer programming with a fixed number of variables. Mathematics of operations research, 8(4),538-548, 1983.

[30] Loidreau, P.; Sendrier, N.(2001). Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inform. Theory, 47(3),1207-1211, 2001.

[31] Lí¶ndahl, C.; Johansson, T.(2012). A new version of McEliece PKC based on convolutional codes. In Information and Communications Security, ICICS, Springer LNCS, 7168, 461-470. Springer, 2012.

[32] McEliece, R.J. (1987). A Public-Key System Based on Algebraic Coding Theory, pages 114-116. Jet Propulsion Lab, 1978. DSN Progress Report 44.

[33] Minder,L.; Shokrollahi,A.(2007). Cryptanalysis of the Sidelnikov cryptosystem. In Advances in Cryptology - EUROCRYPT 2007, Springer LNCS, 4515, 347-360, Barcelona, Spain, 2007.

[34] Misoczki, R.; Tillich, J.-P.;Sendrier, N.; Barreto, P.S. L.M.(2013). MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, 2069-2073, 2013.

[35] Mizuno, S.(2016). The simplex method using tardos' basic algorithm is strongly polynomial for totally unimodular lp under nondegeneracy assumption. Optimization Methods and Software, 31 (6),1298-1304, 2016.

[36] Monico, C.; Rosentha, J.l; Shokrollahi, A.A.(2000). Using low density parity check codes in the McEliece cryptosystem. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, 215, Sorrento, Italy, 2000.

[37] Moufek, H.; Guenda, K. Gulliver, T.A. (2017). A new variant of the mceliece cryptosystem based on qc-ldpc and qc-mdpc codes. IEEE Communications Letters, 21(4),714-717, April 2017.

[38] Mouha, N.; Wang, Q.; Gu, D.; Preneel, B.(2012). Differential and linear cryptanalysis using mixed-integer linear programming. In C.-K. Wu, M. Yung, and D. Lin, editors, Information Security and Cryptology, 57-76. Springer Berlin Heidelberg, 2012.

[39] Niederreiter, H.(1985). A public-key cryptosystem based on shift register sequences. In Advances in Cryptology - EUROCRYPT 1985, Springer LNCS, 219, 35-39, 1985.

[40] Otmani, A.; Kalachi, H.T.(2015). Square code attack on a modified sidelnikov cryptosystem. In Codes, Cryptology, and Information Security, 173-183. Springer, 2015.

[41] Otmani, A.; Tillich, J.-P. ; Dallot, L.(2008). Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes. In Proceedings of First International Conference on Symbolic Computation and Cryptography, 69-81, Beijing, China, Apr. 28-30 2008. LMIB Beihang University.

[42] Persichetti, E.(2012). Compact McEliece keys based on quasi-dyadic Srivastava codes. J. Math. Cryptol., 6(2),149-169, 2012.

Additional Files



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.