Ensuring Noise Immunity of a Communication Channel by Using a Method of Searching for Small-Weight Words in Linear Block Binary and Ternary Codes


Аuthors

Usatjuk V. S.1*, Egorov S. I.2**, Vatutin E. I.1***, Chernetskaya I. E.2****

1. ,
2. South-Western State University, 94, 50-let Oktyabrya str., Kursk, 305040, Russia

*e-mail: l@lcrypto.com
**e-mail: sie58@mail.ru
***e-mail: evatutin@rambler.ru
****e-mail: white731@yandex.ru

Abstract

The functionality and reliability of unmanned aerial vehicles is largely determined by the data transmission channel used. Data, including video, must be transmitted reliably in real time at high speed over the greatest possible distance. This requires the use of advanced error correction and encryption systems. In the context of the development of such systems, there is a need to construct error-resistant codes with specified properties, the most important of which is the minimum code distance.
For estimating the minimum code distance, the article proposes a new method for searching for words of small weight in linear block binary and ternary codes based on the geometry of numbers using a family of heuristics. The method involves the following steps: 1) embedding (Kannan) code into a lattice; 2) reduction of the lattice basis; 3) orthogonalization of the lattice basis using QR decomposition methods; 4) search for the shortest vector in the lattice using the Kannan-Finke-Post (KFP) method. The number of non-zero components of the found vector is equal to the desired codeword weight, which gives an estimate of the code distance.
The performance of the proposed method for searching for words of small weight is determined by the performance of the KFP method for searching for the shortest vector. The performance of the latter increases significantly with the use of heuristics. The following heuristics were used: Gaussian branch pruning; extreme branch cutting based on replacing the hypersphere of the Gaussian heuristic with the body of the intersection of cylinders; rounding heuristics based on reducing the problem of finding the shortest vector to the problem of finding the nearest vector using the Babai algorithm and lattice density heuristics.
The proposed method has high performance when solving problems of approximate estimation of the code distance. This method on the task of searching for a word of small weight 228 demonstrated 3172.9 times the speedup compared to the Brouwer-Zimmerman algorithm implemented in the MAGMA V2.22-3 package. The low weight codeword 212 was found based on the proposed method in 4 147 201 seconds using an Intel 7700K 64GB processor and a 1070 8GB graphics card. Finding this code word won first place in the international low-weight word search competition run by the French National Center for Scientific Research (CNRS), the National Institute for Research in Digital Sciences and Technologies (Inria Paris), and the National Research Institute for Mathematics and Informatics in the Netherlands (CWI).

Keywords:

Number Geometry, Error Correction Code, Hamming distance estimation, Shortest Vector Problem, Shortest Basis Problem, Extremal lattices, Kannan embedding

References

  1. Borodin V.V., Petrakov A.M., Shevtsov V.A. Trudy MAI, 2015, no. 81. URL: https://trudymai.ru/eng/published.php?ID=57894
  2. Anan'ev A.V., Ivannikov K.S., Filatov S.V. Trudy MAI, 2022, no. 125. URL: https://trudymai.ru/eng/published.php?ID=168188. DOI: 10.34759/trd-2022-125-16
  3. Titov K.D. Trudy MAI, 2022, no. 122. URL: https://trudymai.ru/eng/published.php?ID=164250. DOI: 10.34759/trd-2022-122-12
  4. Volkov A.S. Trudy MAI, 2023, no. 128. URL: https://trudymai.ru/eng/published.php?ID=171396. DOI: 10.34759/trd-2023-128-12
  5. Usatyuk V.S., Egorov S.I. Telekommunikatsii, 2016, no. 8, pp. 32-40.
  6. Aragon N., Lavauzelle J., Lequesne M. Low-weight codewords problem challenge, 2019. URL: https://decodingchallenge.org/low-weight
  7. Burg A., Wenk M., Zellweger M., Wegmueller M., Felber N., and Fichtner W. VLSI implementation of the sphere decoding algorithm, Proceedings of the 30th European Solid-State Circuits Conference, Leuven, Belgium, 2004, pp. 303-306.
  8. Usatyuk V.S. Obozrenie prikladnoi i promyshlennoi matematiki, 2015, no. 5 (22), pp. 600-602.
  9. Dumer I., Micciancio D., and Sudan M. Hardness of approximating the minimum distance of a linear code, IEEE Transactions on Information Theory, 2003, vol. 49, no. 1, pp. 22-37. DOI: 10.1109/SFFCS.1999.814620
  10. Konvei Dzh., Sloen N. Upakovki sharov, reshetki i gruppy (Sphere Pakings, Lattices and Groups. Vol. II.) Moscow, Mir, 1990, 367 p.
  11. Goldstein D., Mayer A. On the equidistribution of Hecke points, Forum Mathematicum, 2003, vol. 15, no 2, pp. 165–189. DOI: 10.1515/form.2003.009
  12. Korkine A., Zolotareff G. Sur les formes quadratiques, Mathematische Annalen, 1873, no. 6, pp. 366-389. DOI: 10.1007/BF01442912
  13. Lagarias J.C., Jr. Lenstra H.W., Schnorr C.P. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, 1990, vol. 10 (4), pp. 333-348. DOI: 10.1007/BF02128669
  14. Schnorr C-P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Fundamentals of Computation Theory, 1991, pp. 68-85.
  15. Lenstra A., Lenstra H., Lovász L. Factoring polynomials with rational coefficients, Mathematische Annalen, 1982, vol. 261 (4), pp. 515-534. DOI: 10.1007/BF01457454
  16. Kannan R. Minkowski’s convex body theorem and integer programming, Mathematics of operations research, 1987, vol. 12 (3), pp. 415-440. DOI: 10.1287/MOOR.12.3.415
  17. Betten A., Braun M., Fripertinger H. Error-Correcting Linear Codes Classification by Isometry and Applications, Berlin, Springer-Verlag, 2006, pp. 594-596.
  18. Usatyuk V.S. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie. 2015, no. 3 (16), pp. 76-85.
  19. Ivanova V.S. Lattice Basis Reduction in Infinity, Bachelor Thesis, Technische Universität Darmstadt, 2010, 31 p.
  20. MacKay J., Davey M. C. Evaluation of Gallager codes for short block length and high rate applications, IMA Workshop on Codes, System and Graphical Models, Springer-Verlag, 2001, pp. 113-130.
  21. Smarandashe R., Vontobel P.O. Quasi-cyclic LDPC codes: influence of proto- and Tanner-graph structure on minimum hamming distance upper bounds, IEEE Transactions on Information Theory, 2012, vol. 58, no 2, pp. 585-607. DOI: 10.1109/TIT.2011.2173244
  22. Butler B.K., Siegel P.H. Bounds on the minimum distance of punctured quasi-cyclic LDPC codes, IEEE Transactions on Information Theory, 2013, vol. 59, no 7, pp. 4584-4597. DOI: 10.1109/TIT.2013.2253152
  23. Fontein F., Schneider M., Wagner U. PotLLL: a polynomial time version of LLL with deep insertions, Designs Codes and Cryptographym, 2014, vol. 73, pp. 355–368. DOI: 10.1007/s10623-014-9918-8
  24. Yasuda M., Yamaguchi J. A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths, Designs Codes and Cryptographym, 2019, vol. 87, pp. 2489–2505. DOI: 10.1007/s10623-019-00634-9
  25. Oded R., Missiansio D. Kriptografiya na osnove reshetok (Lattice-based Post-Quantum Cryptography), 2010, 78 p. URL: https://www.researchgate.net/publication/331047955
  26. Micciancio D., Walter M. Practical predictable lattice basis reduction, Annual International Conference on Theory Applications of Cryptographic Techniques, Berlin, 2016, pp. 820–849. DOI: 10.1007/978-3-662-49890-3_31
  27. Neumaier A. Bounding basis reduction properties, Designs Codes and Cryptographym, 2017, vol. 84, pp. 237-259. DOI: 10.1007/s10623-016-0273-9
  28. Yamamura K., Wang Y. Fujisaki E. Improved lattice enumeration algorithms by primal and dual reordering methods, IET Information Security, 2023, vol. 17 (1), pp. 35-45. DOI: 10.1049/ise2.12083
  29. Schnorr C.P. Fast Factoring Integers by SVP Algorithms, Cryptology ePrint Archive, Paper 2021/933. URL: https://eprint.iacr.org/2021/933
  30. McGuire Gary, Robinson Oisin. A New Angle on Lattice Sieving for the Number Field Sieve, 2020. URL: https://arxiv.org/pdf/2001.10860
  31. Gabrielle de Micheli, Pierrick Gaudry, Cécile Pierrot. Lattice Enumeration for Tower NFS: a 521- bit Discrete Logarithm Computation, 27th Annual International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2021, pp.67-96. DOI: 10.1007/978-3-030-92062-3_3
  32. Robinson O. An Implementation of the Extended Tower Number Field Sieve using 4d Sieving in a Box and a Record Computation in Fp4, 2022. URL: https://arxiv.org/abs/2212.04999
  33. Schnorr C.P., Hörner H.H. Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction, Advances in Cryptology, LNCS, 1995, vol. 921, pp 1-12. DOI: 10.1007/3-540-49264-X_1
  34. Gamma N., Nguyen P. Q., Regev O. Lattice Enumeration Using Extreme Pruning, Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology – EUROCRYPT, 2010, pp. 257–278. DOI: 10.1007/978-3-642-13190-5_13
  35. Babai L. On lovasz lattice reduction and the nearest lattice point problem, Combinatorica, 1986, vol. 6, pp. 1-13. DOI: 10.1007/BF02579403
  36. Micciancio D. The shortest vector problem is NP-hard to approximate to within some constant, SIAM Journal on Computing, 2001, no. 30, pp. 2008-2035. DOI: 10.1137/S0097539700373039
  37. Usatyuk V.S. Veroyatnostnyi metod opredeleniya kodovogo rasstoyaniya lineinogo blochnogo koda, Proceedings of the III International conference "Engineering&Telecommunication - En&T 2016", Moscow, MIPT, 2016, pp. 43-46.
  38. Kuz'min O.V., Usatyuk V.S. Programmnye produkty i sistemy, 2015, no. 1 (109), pp. 55-62.
  39. Usatyuk V.S. Prikladnaya diskretnaya matematika. Prilozhenie, 2012, no. 5, pp. 120-122.
  40. Usatyuk V.S., Egorov S.I. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie. 2017, no. 4 (25), pp. 24-33.
  41. Bosma W., Cannon J.J., Fieker C., Steel A. Handbook of Magma functions, 2019, 6129 p.
  42. Hernando F., Igual F. D., Quintana-Orti G. Algorithm 994: Fast Implementations of the Brouwer-Zimmermann Algorithm for the Computation of the Minimum Distance of a Random Linear Code, ACM Transactions on Mathematical Software, 2019, vol. 45, no. 2, pp. 1-28. DOI: 10.1145/3302389
  43. Support material for Low weight codewords problem search method. URL: https://github.com/Lcrypto/Low-weight_Codeword_Problem V2.22-3


Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход