ВДОСКОНАЛЕНА ПОЛІНОМІАЛЬНО-СКЛАДНА АТАКА ВІДНОВЛЕННЯ ВІДКРИТОГО ТЕКСТУ НА РАНЦЕВИЙ ШИФР НА ОСНОВІ МАТРИЦЬ

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.