Let \(p = 4 \ell _1 \cdots \ell _n - 1\) be a CSIDH-type prime for distinct odd primes \(\ell _1, \dots , \ell _n\) . Let \(\mathcal {O} = \mathbb {Z}[\sqrt{-p}]\) , and let \(Ell_{\mathbb {F}_p}(\mathcal {O})\) denote the set of \(\mathbb {F}_p\) -isomorphism classes of supersingular elliptic curves defined over \(\mathbb {F}_p\) whose \(\mathbb {F}_p\) -endomorphism ring is isomorphic to \(\mathcal {O}\) . The action of the ideal class group of \(\mathcal {O}\) on \(Ell_{\mathbb {F}_p}(\mathcal {O})\) underlies the CSIDH scheme and its variants, whose security of key recovery relies on the computational hardness of the group action inverse problem (GAIP). In this work, we introduce a general framework for constructing class group orbits that enables an efficient meet-in-the-middle approach to the GAIP. Let L be the lattice in \(\mathbb {Z}^n\) spanned by vectors \(\boldsymbol{e} = (e_1, \dots , e_n) \in \mathbb {Z}^n\) such that the ideal class of \(\mathfrak {l}_1^{e_1} \cdots \mathfrak {l}_n^{e_n}\) acts trivially on \(Ell_{\mathbb {F}_p}(\mathcal {O})\) , where each \(\mathfrak {l}_i\) is a prime ideal of \(\mathcal {O}\) lying above \(\ell _i\) . If there exists a sub-lattice M of \(\mathbb {Z}^n\) such that \(L \subseteq M\) , we can construct class group orbits of size [M : L]. The typical lattice \(M = L + \mathbb {Z}\boldsymbol{e}_0\) with \(\boldsymbol{e}_0 = (1, \dots , 1) \in \mathbb {Z}^n\) yields efficiently computable orbits of size 3. We investigate the (non-)existence of other efficiently computable orbits by analyzing the structure of torsion sections on an elliptic surface whose fibers are Montgomery curves representing \(Ell_{\mathbb {F}_p}(\mathcal {O})\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the (Non-)Existence of Efficient Class Group Orbits for Collision Search in CSIDH

  • Ryo Negishi,
  • Kazuki Komine,
  • Akira Katayama,
  • Masaya Yasuda

摘要

Let \(p = 4 \ell _1 \cdots \ell _n - 1\) be a CSIDH-type prime for distinct odd primes \(\ell _1, \dots , \ell _n\) . Let \(\mathcal {O} = \mathbb {Z}[\sqrt{-p}]\) , and let \(Ell_{\mathbb {F}_p}(\mathcal {O})\) denote the set of \(\mathbb {F}_p\) -isomorphism classes of supersingular elliptic curves defined over \(\mathbb {F}_p\) whose \(\mathbb {F}_p\) -endomorphism ring is isomorphic to \(\mathcal {O}\) . The action of the ideal class group of \(\mathcal {O}\) on \(Ell_{\mathbb {F}_p}(\mathcal {O})\) underlies the CSIDH scheme and its variants, whose security of key recovery relies on the computational hardness of the group action inverse problem (GAIP). In this work, we introduce a general framework for constructing class group orbits that enables an efficient meet-in-the-middle approach to the GAIP. Let L be the lattice in \(\mathbb {Z}^n\) spanned by vectors \(\boldsymbol{e} = (e_1, \dots , e_n) \in \mathbb {Z}^n\) such that the ideal class of \(\mathfrak {l}_1^{e_1} \cdots \mathfrak {l}_n^{e_n}\) acts trivially on \(Ell_{\mathbb {F}_p}(\mathcal {O})\) , where each \(\mathfrak {l}_i\) is a prime ideal of \(\mathcal {O}\) lying above \(\ell _i\) . If there exists a sub-lattice M of \(\mathbb {Z}^n\) such that \(L \subseteq M\) , we can construct class group orbits of size [M : L]. The typical lattice \(M = L + \mathbb {Z}\boldsymbol{e}_0\) with \(\boldsymbol{e}_0 = (1, \dots , 1) \in \mathbb {Z}^n\) yields efficiently computable orbits of size 3. We investigate the (non-)existence of other efficiently computable orbits by analyzing the structure of torsion sections on an elliptic surface whose fibers are Montgomery curves representing \(Ell_{\mathbb {F}_p}(\mathcal {O})\) .