Complexity of The Systems of Linear Restrictions over a Finite Field
Вантажиться...
Дата
2023
Автори
Kurinnyi, Oleh
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Igor Sikorsky Kyiv Polytechnic Institute
Анотація
This paper continues the results obtained in [1]. In the previous paper, we formulated the problem of the unknown vector recovering from linear dependencies with this vector, which act as constraints on it. The next step, after finding out some algebraic and combinatorial properties, is to give basic estimates of complexity for the main problem as well as for related problems. Such related problems can be obtained by fixing some parameters of the main problem or applying constraints on the number of restrictions in the system. Such an analysis makes possible to arrange the problem of recovering an unknown vector based on partial information into the general computational complexity framework in order to approach existing theoretical results to its solution. The obtained theoretical results can be used in algebraic cryptanalysis of stream ciphers and cryptosystems based on linear codes.
Опис
Ключові слова
system of linear restrictions, finite field, computational complexity, SLR problem
Бібліографічний опис
Kurinnyi, O. Complexity of The Systems of Linear Restrictions over a Finite Field / Oleh Kurinnyi // Theoretical and Applied Cybersecurity : scientific journal. – 2023. – Vol. 5, Iss. 2. – Pp. 47–55. – Bibliogr. 4 ref.