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...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(n^6) 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(n^6) 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.展开更多
基金supported by the National Natural Science Foundation of China(No.61672270,61602216,61702236)the Qing Lan Project for Young Researchers of Jiangsu Province of China(No.KYQ14004)+1 种基金the Open Fund of State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences(No.2015-MSB-10)Jiangsu Overseas Research&Training Program for University Prominent Young&Middle-aged Teachers and Presidents,Changzhou Sci&Tech Program,(Grant No.CJ20179027)
文摘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(n^6) 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(n^6) 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.
