Solving a Modified Syndrome Decoding Problem using Integer Programming

Abstract

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.

References

[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.
https://doi.org/10.1007/11554868_6

[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.
https://doi.org/10.1109/ISIT.2007.4557609

[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.
https://doi.org/10.1007/978-3-319-29360-8_9

[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.
https://doi.org/10.1007/978-3-319-31517-1_18

[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.
https://doi.org/10.1007/s10623-003-6151-2

[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.
https://doi.org/10.1109/TIT.1978.1055873

[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.
https://doi.org/10.1007/978-3-642-19574-7_10

[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.
https://doi.org/10.1007/978-3-642-25405-5_16

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

[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.
https://doi.org/10.1007/978-3-642-10868-6_9

[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.
https://doi.org/10.1515/dma-2014-0024

[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.
https://doi.org/10.1007/3-540-45682-1_10

[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.
https://doi.org/10.1007/s10623-014-9967-z

[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.
https://doi.org/10.1109/ISIT.2014.6875072

[15] Couvreur, A.; Otmani, A.; Tillich, J.-P.(2013). New identities relating wild Goppa codes. Finite Fields Appl., 29,178-197, 2014.
https://doi.org/10.1016/j.ffa.2014.04.007

[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.
https://doi.org/10.1007/978-3-642-55220-5_2

[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.
https://doi.org/10.1109/LCOMM.2017.2779449

[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.
https://doi.org/10.1007/978-3-030-12942-2_29

[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.
https://doi.org/10.1109/TIT.2015.2493539

[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.
https://doi.org/10.3390/a12120248

[22] B.Gou (2008). Generalized integer linear programming formulation for optimal pmu placement. IEEE transactions on Power Systems, 23(3),1099-1104, 2008.
https://doi.org/10.1109/TPWRS.2008.926475

[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.
https://doi.org/10.1109/ISCISC.2014.6994031

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

[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.
https://doi.org/10.1287/ijoc.12.1.2.11900

[27] Karp, R.M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, 85-103. Springer, 1972.
https://doi.org/10.1007/978-1-4684-2001-2_9

[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.
https://doi.org/10.1007/978-3-642-38616-9_7

[29] Lenstra Jr, H.W.(1983). Integer programming with a fixed number of variables. Mathematics of operations research, 8(4),538-548, 1983.
https://doi.org/10.1287/moor.8.4.538

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

[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.
https://doi.org/10.1007/978-3-642-34129-8_45

[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.
https://doi.org/10.1007/978-3-540-72540-4_20

[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.
https://doi.org/10.1109/ISIT.2013.6620590

[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.
https://doi.org/10.1080/10556788.2016.1208748

[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.
https://doi.org/10.1109/ISIT.2000.866513

[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.
https://doi.org/10.1109/LCOMM.2016.2640271

[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.
https://doi.org/10.1007/978-3-642-34704-7_5

[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.
https://doi.org/10.1007/3-540-39805-8_4

[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.
https://doi.org/10.1007/978-3-319-18681-8_14

[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.
https://doi.org/10.1515/jmc-2011-0099
Published
2020-08-30
How to Cite
DRAGOI, Vlad-Florin et al. Solving a Modified Syndrome Decoding Problem using Integer Programming. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 15, n. 5, aug. 2020. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/3920>. Date accessed: 28 sep. 2020. doi: https://doi.org/10.15837/ijccc.2020.5.3920.

Keywords

Syndrome decoding, integer linear programming, simplex algorithm