Cryptanalysis of key exchange protocol based on tensor ergodic problem

Recently, Mao, Zhang, Wu et al. constructed two key exchange (KE) protocols based on tensor ergodic problem (TEP). Although they conjectured that these constructions can potentially resist quantum computing attack, they did not provide a rigorous security proof for their KE protocols. In this paper, applying the properties of ergodic matrix, we first present a polynomial time algorithm to solve the TEP problem using O(n6) arithmetic operations in the finite field, where n is the security parameter. Then, applying this polynomial time algorithm, we generate a common shared key for two TEP-based KE constructions, respectively. In addition, we also provide a polynomial time algorithm with O(n6) arithmetic operations that directly recovers the plaintext from a ciphertext for the KE-based encryption scheme. Thus, the TEP-based KE protocols and their corresponding encryption schemes are insecure.