logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 3: 032111(2016) https://doi.org/10.1007/s11432-015-5447-y

Cryptanalysis of an MOR cryptosystem based on a finite associative algebra

More info
  • ReceivedApr 24, 2015
  • AcceptedJul 24, 2015
  • PublishedJan 26, 2016

Abstract

The Shor algorithm is effective for public-key cryptosystems based on an abelian group. At CRYPTO 2001, paeng $(2001)$ presented a {MOR} cryptosystem using a non-abelian group, which can be considered as a candidate scheme for post-quantum attack. this paper analyses the security of a {MOR} cryptosystem based on a finite associative algebra using a quantum algorithm. specifically, let $L$ be a finite associative algebra over a finite field $F$. consider a homomorphism $\phi: \mathrm{Aut}(L)\rightarrow \mathrm{Aut}(H)\times \mathrm{Aut}(I)$, where $I$ is an ideal of $L$ and $H\cong L/I$. we compute $\dim \mathrm{Im}(\phi)$ and $\dim \mathrm{Ker}(\phi)$, and combine them by $\dim \mathrm{Aut}(L)=\dim \mathrm{Im}(\phi)+\dim \mathrm{Ker}(\phi)$. we prove that $\mathrm{Im}(\phi)=\mathrm{Stab}_{\mathrm{Comp}(H, I)}(\mu+B^{2}(H, I))$ and $\mathrm{Ker}(\phi)\cong Z^{1}(H, I)$. thus, we can obtain $\dim \mathrm{Im}(\phi)$, since the algorithm for the stabilizer is a standard algorithm among abelian hidden subgroup algorithms. in addition, $Z^{1}(H,I)$ is equivalent to the solution space of the linear equation group over the Galois fields $GF(p)$, and it is possible to obtain $\dim \mathrm{Ker}(\phi)$ by the enumeration theorem. furthermore, we can obtain the dimension of the automorphism group $\mathrm{Aut}(L)$. when the map $\varphi\in \mathrm{Aut}(L)$, it is possible to effectively compute the cyclic group $\langle\varphi\rangle$ and recover the private key $a$. therefore, the {MOR} scheme is insecure when based on a finite associative algebra in quantum computation.


Funded by

Fundamental Research Funds for the Central Universities(2012211020213)

national Natural Science Foundation of China(60970006)

foundation of Science and Technology on Information Assurance Laboratory(KJ-14-002)

national Natural Science Foundation of China(61003267)

national Natural Science Foundation of China(61332019)

major State Basic Research Development Program of China(2014CB340600)


References

[1] Deutsch D, Jozsa R. Proc Roy Soc A-Math Phys Eng, 1992, 439: 553-558 CrossRef Google Scholar

[2] Simon D R. SIAM J Comput, 1997, 26: 1474-1483 CrossRef Google Scholar

[3] Shor P W. SIAM Rev, 1999, 41: 303-332 CrossRef Google Scholar

[4] Grover L K. Phys Rev Lett, 1997, 79: 325-328 CrossRef Google Scholar

[5] Mosca M, Ekert A. The hidden subgroup problem and eigenvalue estimation on a quantum computer. Quantum Comput Quantum Commun, 1999: 174--188. Google Scholar

[6] Ko K H, Lee S J, Cheon J H, et al. New public-key cryptosystem using braid groups. In: Proceedings of 20th Annual International Cryptology Conference, Santa Barbara, 2000. 166--183. Google Scholar

[7] Paeng S H, Ha K C, Kim J H, et al. New public key cryptosystem using finite non Abelian groups. In: Proceedings of 21st Annual International Cryptology Conference, Santa Barbara, 2001. 470--485. Google Scholar

[8] Lempken W, van Tran T, Magliveras S S, et al. J Cryptol, 2009, 22: 62-74 CrossRef Google Scholar

[9] Mahalanobis A. Commun Algebra, 2012, 40: 3583-3596 CrossRef Google Scholar

[10] Paeng S H. Inf Process Lett, 2003, 88: 293-298 CrossRef Google Scholar

[11] Tobias C. Security analysis of the MOR cryptosystem. In: Proceedings of 6th International Workshop on Practice and Theory in Public Key Cryptography, Miami, 2002. 175--186. Google Scholar

[12] Lee I S, Kim W H, Kwon D, et al. On the security of MOR public key cryptosystem. In: Proceedings of 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, 2004. 387--400. Google Scholar

[13] Korsten A. Cryptanalysis of MOR and discrete logarithms in inner automorphism groups. In: Proceedings of 2nd Western European Workshop on Research in Cryptology, Bochum, 2008. 78--89. Google Scholar

[14] Mahalanobis A. Commun Algebra, 2006, 40: 3583-3596 Google Scholar

[15] Babai L, Beals R, Seress Á. Polynomial-time theory of matrix groups. In: Proceedings of 41st Annual ACM Symposium on Theory of Computing. New York: ACM, 2009. 55--64. Google Scholar

[16] Friedl K, Ivanyos G, Magniez F, et al. Hidden translation and orbit coset in quantum computing. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing. New York: ACM, 2003. 1--9. Google Scholar

[17] Hallgren S, Russell A, Ta-Shma A. SIAM J Comput, 2003, 32: 916-934 CrossRef Google Scholar

[18] Childs A M, van Dam W. Rev Mod Phys, 2010, 82: 1-52 CrossRef Google Scholar

[19] Wei H Z, Wang Y X. J Hebei Normal Univ, 1993, 17: 1-13 Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1