RADIOELECTRONIC AND COMPUTER SYSTEMS

Asymmetric ciphers are widely used to ensure the confidentiality of data transmission via insecure channels. These cryptosystems allow the interacting parties to create a shared secret key for a symmetric cipher in such a way that an eavesdropper gets no information useful for cryptanalysis. Network security protocols that use asymmetric ciphers include TLS, S/MIME, OpenPGP, Tor, and many others. Some of the asymmetric encryption schemes are homomorphic, that is, that they allow calculations on encrypted data to be performed without preliminary decryption. The aforesaid property makes possible using these cryptosystems not only for symmetric key establishment but also in several areas of application, in particular in secret voting protocols and cloud computing. The matrix-based knapsack cipher is a new additively homomorphic asymmetric encryption scheme, which is based on the properties of isomorphic transformations of the inner direct product of diagonal subgroups of a general linear group over a Galois field. Unlike classic knapsack encryption schemes, the cryptographic strength of this cipher depends on the computational complexity of the multidimensional discrete logarithm problem. Despite some useful properties, further research into the cryptographic strength of the matrix-based knapsack cipher has found serious drawbacks inherent in this cryptographic scheme. In the given paper an improved polynomial-time plaintext-recovery attack on the matrix-based knapsack cipher is proposed. Applying this cryptanalytic method requires only public information and has time complexity O(t1.34), where t denotes the decryption time of the attacked cryptosystem. The aforementioned attack is more productive and easier to implement in software in comparison with the original one. The advantages of the proposed method are due to using in its algorithm the simple and relatively fast matrix trace operation instead of more complex and slower transformations.

matrix-based knapsack cipher; cryptanalysis; computational complexity; an asymmetric cipher; homomorphic encryption; plaintext-recovery attack

Schneier, B. Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th edn. John Wiley & Sons Publ., 2015. 540 p.

Van Tilborg, H., Jajodia, S. Encyclopedia of Cryptography and Security, 2nd edn. Springer Publ., 2011. 1416 p.

Li, Y., Schäge, S., Yang, Z., Kohlar, F., Schwenk, J. 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.

Schillinger, F., Schindelhauer, C. 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.

Maury, F., Reinhard, J.-R., Levillain, O., Gilbert, H. 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.

Ghosh, S., Kate, A. 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.

Campagna, M. 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.

Damgård, I., Groth, J., Salomonsen, G. The Theory and Implementation of an Electronic Voting System, Editor(s): D. Gritzalis. Secure Electronic Voting, Springer Publ., 2003, pp. 77-99.

Liu, J., Chen, L., Mesnage, S. 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.

Vambol, A. 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, A., Zyulyarkina, N., Kostygina, Yu. Modifikatsiya kriptosistemy s otkrytym klyuchom na osnove «zadachi o ryukzake» [Modification of the cryptosystem with public key on the basis of knapsack problem]. Vestnik UrFO. Bezopasnost' v informatsionnoi sfere [UrFR Newsletter. Information Security], 2014, no. 1(11), pp. 16-20. (In Russian).

Vambol, A. 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.

Vambol, A. Polynomial-Time Plaintext-Recovery Attack on the Matrix-Based Knapsack Cipher. International Journal of Computing, 2020. (Accepted for publication).

Roman, S. Advanced Linear Algebra, 2nd edn. Springer Publ., 2005. 482 p.

Menezes, A., van Oorschot, P., Vanstone, S. Handbook of Applied Cryptography. CRC Press Publ., 1996. 816 p.

Pohlig, S., Hellman, M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 1978, vol. 24, no. 1, pp. 106-110.