short-paper

The duality principle in the theory of development generalized A-M knapsack cryptosystems

Authors:

Valeriy O. Osipyan,

Valeriy S. Tlusten,

Nina V. Laktionova,

Nadezhda V. VakhrushevaAuthors Info & Claims

SIN '17: Proceedings of the 10th International Conference on Security of Information and Networks

Pages 200 - 205

https://doi.org/10.1145/3136825.3136898

Published: 13 October 2017 Publication History

Abstract

We propose a method that extends the class of non-standard knapsack cryptosystem based on the principle of duality and provide a mechanism for such expansion on the example of super generalized additive knapsack problem. The generalized A-M knapsack is studied for the first time. The information protection system, based on the knapsack, can be developed both for additive and multiplicative knapsack. The necessary conditions under which a generalized A-M knapsack is dense and injective over Galois field GF(p) are established.

References

[1]

Shannon C. 1949. Communication theory of secrecy systems, Bell Syst Techn. J. 28, No. 4, 656--715.

[2]

W. Diffie, Hellman M. 1976. New directions in cryptography. IEEE Transactions on Information Theory. Vol. 22, 644--654.

Digital Library

[3]

Merkle R. Hellman M. 1978. Hiding information and signatures in knapsacks trapdoor. IEEE Transactions on Information Theory. Vol. IT-24, 525--530.

Digital Library

[4]

Chor B, Rivest R. 1988. A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory. Vol. 34, No. 5, 901--909.

Digital Library

[5]

Shamir, A. 1984. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Transactions on Information Theory. Vol. 30 No. 5, 699--704.

Digital Library

[6]

Lenstra Jr., H.W. 1983. Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research. Vol. 8, No. 4, 538--548.

Digital Library

[7]

Koblitz, N. 1987. A Course in Number Theory and Cryptography. Springer-Verlag, New York.

Digital Library

[8]

Vaudenay S. 1998. Cryptanalysis of the Chor-Rivest cryptosystem. LNCS 1462, Proceedings of Crypto'98, Springer-Verlag, 243--256.

Digital Library

[9]

Salomaa, A. 1995. Public key cryptography. Springer-Verlag Berlin Heidelberg, New York.

Digital Library

[10]

Alferov A.P., Zubov A., Cheremushkin A.S., Kuzmin A.V. 2002. Basics of cryptography. Helios ARV, Moscow.

[11]

Osipyan V.O. 2003. On one generalization of knapsack cryptosystems. Izv. vuzov. Northern-Caucasus area. Tech. science, Appendix No. 5, 18--25.

[12]

Osipyan V.O., Osipyan K.V. 2004. Cryptography in exercises and tasks. Helios ARV, Moscow.

[13]

Osipyan V.O. 2004. Information protection systems based on functional knapsack problem. Voprosi zachiti informatsi. No. 4, 16--19.

[14]

Osipyan V.O. 2006. On Information Protection System Based on the nonstandard Knapsack Problem. Izv. vuzov. Tomsk Polytechnical University. V. 309, No2, 209--212.

[15]

Osipyan V.O. 2007. Generalization of open key knapsack cryptosystems. Security of Information and Networks: Proceedings of the First International Conference on Security of Information and Networks (SIN'2007). Trafford, 58--63.

[16]

Osipyan V.O., Arutyunyan A.S., Spirina S.G. 2010. Modeling knapsack cryptosystems containing Diophantine difficulty. Chebyshev collection. T. XI, ed. 1, 209--217.

[17]

Osipyan V.O. 2011. Different models of information protection system, based on the functional knapsack. In Proceedings of the 4th international conference on Security of information and networks (SIN'11), ACM Press, New York, NY, 215--218.

Digital Library

[18]

Osipyan V.O. 2012. Modeling information protection systems containing Diophantine difficulties. Development of methods for multistage systems solutions of Diophantine equations. Development of nonstandard knapsack cryptosystems. LAP Lambert Academic Publishing.

[19]

Osipyan V.O. 2012. Building of alphabetic data protection cryptosystems on the base of equal power with knapsacks Diophantine problems. In Proceedings of the 5th International Conference on Security of Information and Networks (SIN'12), ACM Press, New York, NY, 124--129.

Digital Library

[20]

Osipyan V.O., Karpenko Yu.A., Zhuk A. S., Harutyunyan A. H. 2013. Diophantine difficulties attacks on non-standard back packs information protection systems. Izvestiya SFU. SCI, No. 12, 209--215.

[21]

Osipyan V. O. 2013. Information protection systems based on universal knapsack problem. In Proceedings of the 6th International Conference on Security of Information and Networks (SIN'13), ACM Press, New York, NY, 343--346.

Digital Library

[22]

Osipyan V. O., Zhuck A. S., Arutyunyan, A. H., Karpenko Y. A. 2013. Building of mathematical model of flow data processing system based on given the selection of elements of the set. In Proceedings of the 6th International Conference on Security of Information and Networks (SIN'13), ACM Press, New York, NY, 417--420.

Digital Library

[23]

Osipyan V.O. 2014. Mathematical model of the polyalphabetic information security system based on the generalized normal knapsack. In Proceedings of the 7th International Conference on Security of Information and Networks (SIN'14), ACM Press, New York, NY, 123--128.

Digital Library

[24]

Osipyan V.O. 2015. Mathematical modelling of cryptosystems based on Diophantine problem with gamma superposition method. In Proceedings of the 8th International Conference on Security of Information and Networks (SIN' 15), ACM Press, New York, NY, 338--341.

Digital Library

Cited By

Aleksandrov ATelny AFomich ASorokin I(2021)NIST Testing of a Knapsack Symmetric Cryptosystem on Hamlin Codes Using Source Block Injections2021 Dynamics of Systems, Mechanisms and Machines (Dynamics)10.1109/Dynamics52735.2021.9653724(1-5)Online publication date: 9-Nov-2021
https://doi.org/10.1109/Dynamics52735.2021.9653724

Index Terms

The duality principle in the theory of development generalized A-M knapsack cryptosystems
1. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

Generalized roof duality and bisubmodular functions

Consider a convex relaxation f of a pseudo-Boolean function f . We say that the relaxation is totally half-integral if f ( x ) is a polyhedral function with half-integral extreme points x , and this property is preserved after adding an arbitrary ...
On reduction of duality gap in quadratic knapsack problems

We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation. We characterize the duality gap by a distance measure from set {0, 1}^{n
...}
On generalized surrogate duality in mixed-integer nonlinear programming
Abstract
The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global $ϵ$ -optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SIN '17: Proceedings of the 10th International Conference on Security of Information and Networks

October 2017

321 pages

ISBN:9781450353038

DOI:10.1145/3136825

General Chairs:
Rajveer Singh Shekhawat
Manipal University Jaipur, India
,
M. S. Gaur
IIT Jammu, India
,
Atilla Elci
Aksaray University, Turkey
,
Jaideep Vaidya
Rutgers University
,
Oleg Makarevich
Southern Federal University, Russia
,
Ron Poet
University of Glasgow, UK
,
Mehmet Orgun
McQuarie Univ, Australia
,
Vijaypal S. Dhaka
Manipal University Jaipur, India
,
Manoj K. Bohra
Manipal University Jaipur, India
,
Virender Singh
IIT Bombay, India
,
Ludmila Babenko
Southern Federal University, Russia
,
Naghmeh M. Sheykhkanloo
Napier University, UK
,
Behnam Rahnama
Medis Inc., Iran

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

SIN '17

SIN '17: Security of Information and Networks

October 13 - 15, 2017

Jaipur, India

Acceptance Rates

Overall Acceptance Rate 102 of 289 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
28
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aleksandrov ATelny AFomich ASorokin I(2021)NIST Testing of a Knapsack Symmetric Cryptosystem on Hamlin Codes Using Source Block Injections2021 Dynamics of Systems, Mechanisms and Machines (Dynamics)10.1109/Dynamics52735.2021.9653724(1-5)Online publication date: 9-Nov-2021
https://doi.org/10.1109/Dynamics52735.2021.9653724

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents