On Collisions Related to an Ideal Class of Order 3 in CSIDH

情報処理学会

書誌事項

タイトル別名
  • 同種写像暗号CSIDHにおける秘密鍵の衝突可能性について

抄録

CSIDHは同種写像問題を安全性の根拠とする鍵交換方式であり，耐量子暗号の候補の1つである. その計算においてイデアル類群の超特異楕円曲線の素体上の同型類への作用を用いる. 計算に用いるイデアル類は整数係数のベクトルとして表される. それらの間にはほぼ1対1の対応があることがヒューリスティックにより示されてはいるが, 正確な対応関係については知られていない. 整数ベクトルで表されるイデアル類の全体がCSIDHの鍵空間となるため, 整数ベクトルとイデアル類の対応を調べることは重要である. 我々はこの対応について研究し, 全ての係数が1であるベクトルは位数3のイデアル類と対応することを示した. この事実より, 現在提案されているCSIDHのイデアル類の表示方法には, 秘密鍵の衝突があることが従う. さらに我々はこの位数3のイデアル類が導く衝突を含まないような新しいイデアル類の表示方法を提案し, その表示方法によるイデアル類の作用を高速に計算するための公式を与えた.

CSIDH is an isogeny-based key exchange, which is a candidate for post quantum cryptography. It uses the action of an ideal class group on Fp-isomorphic classes of supersingular elliptic curves. In CSIDH, the ideal classes are represented by vectors with integer coefficients. The number of ideal classes represented by these vectors determines the security level of CSIDH. Therefore, it is important to investigate the correspondence between the vectors and the ideal classes. We investigate this correspondence and show that the vector (1, ..., 1) corresponds to an ideal class of order 3. Consequently, the integer vectors in CSIDH have collisions related to this ideal class. We further propose a new ideal representation in CSIDH that does not include these collisions and give formulae for efficiently computing the action of the new representation.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1050292572112089856
  • NII論文ID
    170000181030
  • Web Site
    http://id.nii.ac.jp/1001/00201259/
  • 本文言語コード
    en
  • 資料種別
    conference paper
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ