论文部分内容阅读
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 φ : Aut(L) → Aut(H) × Aut(I), where I is an ideal of L and H ■ L/I.We compute dim Im(φ) and dim Ker(φ), and combine them by dim Aut(L) = dim Im(φ) + dim Ker(φ). We prove that Im(φ) = Stab Comp(H,I)(μ + B~2(H, I)) and Ker(φ)■ Z~1(H, I). Thus, we can obtain dim Im(φ), 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 Ker(φ) by the enumeration theorem. Furthermore, we can obtain the dimension of the automorphism group Aut(L). When the map ? ∈ Aut(L), it is possible to effectively compute the cyclic group ? and recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.
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 Theor algorithm is effective for public-key cryptosystems based on an abelian group. paper analyzes 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 φ: Aut (L) → Aut (H) × Aut (I) where I is an ideal of L and H ■ L / I. We compute dim Im (φ) and dim Ker (φ) and combine them by dim Aut (L) = dim Im (φ) + dim Ker (φ). We prove that Im (φ) = Stab Comp (H, I) (μ + B ~ 2 (H, I)) and Ker Obtain dim Im (φ), 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 When the automorphism group Aut (L). When the map? ∈ Aut (L), it is possible to effectively find the cyclic group? And recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.