A method for recovering linear block codes over an arbitrary finite field from sets of distorted code words

Authors

  • A.N. Alekseychuk Інститут спеціального зв'язку та захисту інформації Національного технічного університету України “Київський політехнічний інститут імені Ігоря Сікорського”, Ukraine
  • O.S. Shevchuk Інститут спеціального зв'язку та захисту інформації Національного технічного університету України “Київський політехнічний інститут імені Ігоря Сікорського”, Ukraine

DOI:

https://doi.org/10.30837/rt.2023.4.215.03

Keywords:

information security, learning of information, code-based cryptography, linear block code recovering, LPN problem

Abstract

The article is devoted to one of the practically important problems of information security and cryptanalysis, which consists in recovering an unknown linear block code over an arbitrary field from a set of distorted code words. This is a hard computational problem, and the known problem-solving methods are proposed only for codes over the field of two elements and are based on the algorithms for searching words of small weight in (undistorted) linear block codes.

The main result of the article is a method for solving the problem posed, which differs in essence from the known ones and consists in recovering the desired code by solving the LPN (Learning Parity with Noise) problem, namely, recovering the solutions of systems of linear equations with distorted right-hand sides and a random equally probable matrix of coefficients over specified field. The LPN problem is well known from the Theory of Computational Algorithms and Cryptanalysis. It is equivalent to the problem of random linear block code decoding, and the security of many modern post-quantum cryptosystems are based on its hardness.

The proposed method provides an opportunity to apply a wider class of algorithms for recovering linear block codes in comparison with the previously known methods, in particular, algorithms like BKW and also the low weight words search algorithms in co-sets of linear block codes. Moreover, in contrast to previously known ones, the complexity of the proposed method depends linearly on the length of the required code (and increases with increasing of its dimension according to which algorithm for the LPN problem-solving is applied).  Thus, the basic parameter determined the complexity of recovering a linear block code is its dimension (not its length), which, in principle, makes it possible to speed up known algorithms for recovering linear block codes from a set of corrupted code words.

References

Valembois A. Detection and recognition of a binary linear code // Discrete applied mathematics. 2001. Vol. 111, No. 1–2. P. 199–218. DOI: https://doi.org/10.1016/s0166-218x(00)00353-x.

Cluzeau M. Block code reconstruction using iterative decoding techniques // IEEE Conference ISIT’06. 2006. P. 2269–2273. DOI: https://doi.org/10.1109/isit.2006.261971.

Barbier J., Sicot G., Houcke S. Algebraic approach of the reconstruction of linear and convolutional error correcting codes // World Academy of Science, Engineering and Technology. 2006. Vol. 16. P. 66–71.

Sicot G., Houcke S. Blind detection of interleaver parameters // Signal Process. 2009. Vol. 89 (4). P. 450–462.

Cluzeau M., Finiasz M. Recovering a code's length and synchronization from a noisy intercepted bitstream // IEEE Conference ISIT’09. 2009. P. 2737–2731. DOI: https://doi.org/10.1109/isit.2009.5205843.

Karimian Y., Ziapuor S., Attari M.A. Parity-check matrix recognition from noisy codewords // ArXiv: 1205.4641v1 [cs.IT]. 2012. 22 p.

Carrier K., Tillich J.-P. Identifying an unknown code by partial Gaussian elimination // Designs, Codes and Cryptography. 2018. Vol. 87, No. 2–3. P. 685–713. DOI: https://doi.org/10.1007/s10623-018-00593-7.

Fast Blind Recovery of Linear Block Codes over Noisy Channels / P. Wang et al. // 2023 IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan, 25–30 June 2023. 2023. DOI: https://doi.org/10.1109/isit54713.2023.10206775.

Олексійчук А.М, Шевчук О. С. Оцінка ефективності атак на основі підібраних відкритих текстів на криптосистему Рао-Нама над скінченною абелевою групою // Радіотехніка. 2021. Т. 1, № 205. С. 22–31. DOI: https://doi.org/10.30837/rt.2021.2.205.02.

Шевчук О. С. Рандомізована симетрична криптосистема Мак-Еліса на основі узагальнених кодів Ріда-Соломона // Радіотехніка. 2020. Т. 1, № 200. С. 25–36. DOI: https://doi.org/10.30837/rt.2020.1.200.03.

Canteaut A., Chabaud F. A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511 // IEEE Transactions on Information Theory. 1998. Vol. 44, No.1. P. 367–378. DOI: https://doi.org/10.1109/18.651067.

Chose P., Joux A., Mitton M. Fast Correlation Attacks: An Algorithmic Point of View // Advances in Cryptology – EUROCRYPT 2002. Berlin, Heidelberg, 2002. P. 209–221. DOI: https://doi.org/10.1007/3-540-46035-7_14.

Dubiner M. Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem // IEEE Transactions on Information Theory. 2010. Vol. 56, No. 8. P. 4166–4179. DOI: https://doi.org/10.1109/tit.2010.2050814.

Cryptographic Primitives Based on Hard Learning Problems / A. Blum et al. // Advances in Cryptology – CRYPTO’ 93. Berlin, Heidelberg, 1994. P. 278–291. DOI: https://doi.org/10.1007/3-540-48329-2_24.

Pietrzak K. Cryptography from Learning Parity with Noise // SOFSEM 2012: Theory and Practice of Computer Science. Berlin, Heidelberg, 2012. P. 99–114. DOI: https://doi.org/10.1007/978-3-642-27660-6_9.

Bogos S. LPN in cryptography: an algorithmic study. PhD thesis. Ecole Polytechnique Federale de Lausanne. 2017. p.177. URL: https://infoscience.epfl.ch/record/228977/files/EPFL_TH7800.pdf.

Ігнатенко С. М. Методи розв’язання задачі LPN над скінченними кільцями для оцінювання стійкості симетричних постквантових шифросистем : дис. … канд. техн. наук : 05.13.21. Харків, 2021. 179 с. DOI: http://dspace.univer.kharkov.ua/handle/123456789/16047.

Blum A., Kalai A., Wasserman H. Noise-tolerant learning, the parity problem, and the statistical query model // Journal of the ACM. 2003. Vol. 50, No. 4. P. 506–519. DOI: https://doi.org/10.1145/792538.792543.

Bogos S., Tramer S., Vaudenay S. On solving LPN using BKW and variants. Implementation and analysis // Cryptology ePrint Archive, Report 2015/049. URL: http://eprint.iacr.org/2015/049.

Алексейчук А.Н., Грязнухин А.Ю. Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искаженной правой частью // Прикладная дискретная математика. 2013. Т. 20. С. 59–70.

Grigorescu E., Reyzin L., Vempala S. On Noise-Tolerant Learning of Sparse Parities and Related Problems // Lecture Notes in Computer Science. Berlin, Heidelberg, 2011. P. 413–424. DOI: https://doi.org/10.1007/978-3-642-24412-4_32.

Zhang B., Xu C., Meier W. Fast Correlation Attacks over Extension Fields, Large-Unit Linear Approximation and Cryptanalysis of SNOW 2.0 // Lecture Notes in Computer Science. Berlin, Heidelberg, 2015. P. 643–662. DOI: https://doi.org/10.1007/978-3-662-47989-6_31.

Regev O. On lattices, learning with errors, random linear codes, and cryptography // Journal of the ACM. 2009. Vol. 56, No. 6. P. 1–40. DOI: https://doi.org/10.1145/1568318.1568324.

Глухов М.М., Елизаров В.П, Нечаев А.А. Алгебра : учебник в 2-х т., Т. 1. Москва : Гелиос АРВ, 2003. 336 с.

Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables // Journal of the American Statistical Association. 1963. Vol. 58, No. 301. P. 13–30. DOI: https://doi.org/10.1080/01621459.1963.10500830.

Алексейчук А.Н., Грязнухин А.Ю. Метод восстановления систематических линейных кодов по наборам искаженных кодовых слов // Прикладная дискретная математика. 2013. Т. 12, № 2. С. 313–318.

Downloads

Published

2023-12-25

How to Cite

Alekseychuk, A., & Shevchuk, O. (2023). A method for recovering linear block codes over an arbitrary finite field from sets of distorted code words. Radiotekhnika, 4(215), 22–30. https://doi.org/10.30837/rt.2023.4.215.03

Issue

No. 215 (2023): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).