POLYNOMIAL-TIME PLAINTEXT-RECOVERY ATTACK ON THE MATRIX-BASED KNAPSACK CIPHER

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.