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

A.V. Aleksandrov

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

research article Pages: 71-77

¹ Ph. D. (Phys.-Math.), Associate Professor, Department «Informatics and Information Security», Vladimir State University named after A.&N. Stoletovs

Keywords: common memory problem of packing a backpack sparse backpacks density stacking Coster-Odlyzko block cipher mode of engagement in blocks

Abstract

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.

How to cite

Александров А.В. Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи // Динамика сложных систем - XXI век. 2016. № 4. С. 71–77.

References

Diffie R. Merkle, Hellman M. Hiding information and signatures in trapdoor knapsacks // IEEE Transactions on Information Theory. 1978. P. 525−530.
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.
Coster M.J., Joux A., LaMacchia B.A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. № 2. P. 111−128.
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.
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.
Hamlin N., Krishnamoorthy B., Webb W. A Knapsack-Like Code Using Recurrence Sequence Representations // Fibonacci Quarterly. 2015. 1 (53). 24−33.
Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward. Recurrence sequences. 2003. AMS, Mathematical Surv. and monographs. V104.
Dolev D., Yao A. On the Security of Public Key Protocols // IEEE Transact. on Inform. Theory. 1983. V. 29. № 2. P. 198−208.
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.

[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.