A Linear Algebra Attack on the Non-commuting Cryptography Class Based on Matrix Power Function

详细信息    查看全文

• 关键词：Cryptography ; Post ; quantum computational cryptography ; Cryptanalysis ; Asymmetric cipher ; Matrix power function
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10143
• 期：1
• 页码：343-354
• 丛书名：Information Security and Cryptology
• ISBN：978-3-319-54705-3
• 卷排序：10143

文摘

Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. Under this background, a non-commuting cryptography class based on matrix power function has been given. In this paper we show that the non-commuting cryptography class based on MPF is vulnerable to a linear algebra attack which only requires polynomial time to achieve the equivalent keys respectively. In addition, we conduct an analysis on the flaws in this schemes and propose an improved scheme that remedies the weakness of their schemes.