POLYNOMIAL-TIME PLAINTEXT-RECOVERY ATTACK ON THE MATRIX-BASED KNAPSACK CIPHER
DOI:
https://doi.org/10.47839/ijc.19.3.1896Keywords:
matrix-based knapsack cipher, plaintext-recovery attack, cryptanalysis, time complexity, computational complexity, asymmetric encryption, homomorphic encryption, knapsack cryptosystems, group-based knapsack ciphersAbstract
The aim of the present paper is to propose a polynomial-time plaintext-recovery attack on the matrix-based knapsack cipher. The aforesaid algorithm uses only public information and has time complexity O(t1.34), where t is the decryption time of the attacked cryptosystem. The matrix-based knapsack cipher is a novel additively homomorphic asymmetric encryption scheme, which is a representative of group-based knapsack ciphers. This cryptosystem is based on the isomorphic transformation’s properties of the inner direct product of diagonal subgroups of a general linear group over a Galois field. Unlike the classical knapsack cryptoschemes, the cryptographic strength of the aforesaid cipher depends on the computational complexity of the multidimensional discrete logarithm problem. Due to the attack proposed in the given paper, the matrix-based knapsack cipher can be considered broken and should not be used as a privacy tool. However, this cryptosystem is still suitable for educational purposes as an example of the application of linear and abstract algebras in asymmetric cryptography.
References
B. Schneier, Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th ed., John Wiley & Sons, 2015, 784 p.
H. van Tilborg, S. Jajodia, Encyclopedia of Cryptography and Security, 2nd ed., Springer, 2011, 1416 p.
Y. Li, S. Schäge, Z. Yang, F. Kohlar, J. Schwenk, “On the security of the pre-shared key ciphersuites of TLS,” Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2014), Buenos Aires, Argentina, March 26-28, 2014, pp. 669-684.
F. Schillinger, C. Schindelhauer, “End-to-end encryption schemes for online social networks,” Proceedings of the 12th International Conference on Security, Privacy, and Anonymity in Computation, Communication, and Storage (SpaCCS 2019), Atlanta, USA, July 14-17, 2019, pp. 133-146.
F. Maury, J.-R. Reinhard, O. Levillain, H. Gilbert, “Format Oracles on OpenPGP,” Proceedings of the Cryptographer's Track at the RSA Conference 2015 (CT-RSA 2015), San Francisco, USA, April 20-24, 2015, pp. 220-236.
S. Ghosh, A. Kate, “Post-quantum forward secure onion routing (future anonymity in today’s budget),” Proceedings of the 13th International Conference on Applied Cryptography and Network Security (ACNS 2015), New York, USA, June 2-5, 2015, pp. 263-286.
M. Campagna et al., ETSI White Paper No. 8. Quantum Safe Cryptography and Security: An introduction, benefits, enablers and challenges, European Telecommunications Standards Institute, 2015, 64 p.
I. Damgård, J. Groth, G. Salomonsen, “The theory and implementation of an electronic voting system,” in: D. A. Gritzalis (Eds.), Secure Electronic Voting, Springer, 2003, pp. 77-99.
J. Liu, L. Chen, S. Mesnage, “Partially homomorphic encryption schemes over finite fields,” Proceedings of the 6th International Conference on Security, Privacy and Applied Cryptography Engineering (SPACE 2016), Hyderabad, India, December 14-18, 2016, pp. 109-123.
A. Vambol, “The matrix-based knapsack cipher in the context of additively homomorphic encryption,” Proceedings of the 3rd International Conference on Computational Linguistics and Intelligent Systems (COLINS), Kharkiv, Ukraine, April 18-19, 2019, pp. 344-354.
А. Zhivotova, N. Ziuliarkina, Y. Kostygina, “Modification of the cryptosystem with public key on the basis of knapsack problem,” UrFR Newsletter. Information Security, issue 1 (11), pp. 16-20, 2014. (in Russian)
A. Vambol, “The prospects for group-based knapsack ciphers in the post-quantum era,” Proceedings of the 9th IEEE International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, May 24-27, 2018, pp. 271-275.
N. Smart, Cryptography Made Simple, Springer, 2015, 481 p.
S. Roman, Advanced Linear Algebra, 2nd ed., Springer, 2005, 482 p.
A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, 816 p.
H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993, 536 p.
M. Law, M. Monagan, “Computing characteristic polynomials of matrices of structured polynomials,” Proceedings of the 18th International Workshop on Computer Algebra in Scientific Computing (CASC 2016), Bucharest, Romania, September 19-23, 2016, pp. 336-348.
O. Vasilenko, Number-Theoretic Algorithms in Cryptography, American Mathematical Society, 2007, 243 p.
P. Bürgisser, “Permanent versus determinant, obstructions, and Kronecker coefficients,” Séminaire Lotharingien de Combinatoire, vol. 75, 2015, 19 p.
S. Pohlig, M. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,” IEEE Transactions on Information Theory, vol. 24, issue 1, pp. 106-110, 1978.
H. van Tilborg, Fundamentals of Cryptology: A Professional Reference and Interactive Tutorial, Springer, 2000, 506 p.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
