Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


About rarefied class in the problem of laying backpack backpack and some of its applications in secret communication


A.V. Aleksandrov – Ph. D. (Phys.-Math.), Associate Professor, Department «Informatics and Information Security», Vladimir State University named after A.&N. Stoletovs E-mail:

In this paper of the bases for the return of the final order of the sequences and their respective signatures to the generalized problem of packing a backpack proved necessary conditions sparse backpacks, providing density stacking Coster - Odlyzko outside the interval (0.1); obtained their asymptotic and algorithmic properties. Construction of backpacks used to construct a block cipher mode of engagement in blocks. Shows some comparison speed and the statistical properties of the encryption algorithm, in comparison with known block encryption standards.


  1. Diffie R. Merkle, Hellman M. Hiding information and signatures in trapdoor knapsacks // IEEE Transactions on Information Theory. 1978. P. 525−530.
  2. Shamir A. A polynomial time algorithm for breaking the basis Merkle–Hellman cryptosystem // Proc. 23-rd IEEE Symp. Found. Computer Science. 1982. P. 145−152.
  3. Coster M.J., Joux A., LaMacchia B.A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. № 2. P. 111−128.
  4. Murin D.M. Modifikacija metoda Lagariasa–Odlyzhko dlja reshenija obobshhennojj zadachi o rjukzake i sistem zadach o rjukzakakh // Prikladnaja diskretnaja matematika. 2013. № 2(20). S. 91−100.
  5. Aleksandrov A.V., Metlinov A.D. Simmetrichnaja rjukzachnaja kriptosistema s obshhejj pamjatju i plotnostju ukladki bolshe edinicy // Problemy informacionnojj bezopasnosti. Kompjuternye sistemy. 2014. № 4. S. 58−65.
  6. Hamlin N., Krishnamoorthy B., Webb W. A Knapsack-Like Code Using Recurrence Sequence Representations // Fibonacci Quarterly. 2015. 1 (53). 24−33.
  7. Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward. Recurrence sequences. 2003. AMS, Mathematical Surv. and monographs. V104.
  8. Dolev D., Yao A. On the Security of Public Key Protocols // IEEE Transact. on Inform. Theory. 1983. V. 29. № 2. P. 198−208.
  9. Aleksandrov A.V. O semejjstve rjukzachnykh blochnykh shifrov s obshhejj pamjatju i razrezhennojj plotnostju ukladki // Sb. nauchnykh trudov III Mezhdunar. nauchno-prakticheskojj konf. «Informacionnaja bezopasnost v svete Strategii Kazakhstan‑2050». 2015. S. 26−30.


May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio