2020, Kupriyashin, M. A., Slonkina, I. S., Borzunov, G. I., Куприяшин, Михаил Андреевич, Борзунов, Георгий Иванович

© 2020 IEEE.In this paper, we give a short introduction to the hard lattice problems and application of corresponding methods in cryptanalysis. We provide several examples of specialized lattices we may use to solve certain instances of the related tasks, such as the Knapsack Problem or the Learning with Errors Problem. In this study, we pay special attention to using lattice-based cryptanalysis with asymmetric Knapsack-based cipher systems.

2020, Kupriyashina, N. A., Kupriyashin, M. A., Slonkina, I. S., Borzunov, G. I., Куприяшин, Михаил Андреевич, Борзунов, Георгий Иванович

© 2020 IEEE.In this paper, we review and analyze the efficiency of several binary vector enumeration algorithms we have been using in our work on the Knapsack Problem. As we keep in mind the possibility of massively parallel computation, we are interested in algorithms that are able to start the search from any vector (identified by ordinal number). In this case, it is possible to implement static load balancing efficiently. Apart from the actual implementation performance, we study the load balancing diagrams for each of the algorithms. We assume that every bit of the binary vector is associated with some fixed amount of work a computer must do and examine the resulting complexity of subtasks obtained by splitting the vector sequences into subsequences.