WEKO3
アイテム
CSIDHにおける同値な秘密鍵の探索と秘密鍵空間の解析
https://ipsj.ixsq.nii.ac.jp/records/228757
https://ipsj.ixsq.nii.ac.jp/records/228757c6372a0b-2251-491d-82e1-54303b3f0cb6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-CSS2023144.pdf (307.9 kB)
2025年10月23日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, CSEC:会員：¥0, SPT:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Symposium(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-10-23 | |||||||||
| タイトル | ||||||||||
| タイトル | CSIDHにおける同値な秘密鍵の探索と秘密鍵空間の解析 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Searching for Equivalent Secret Keys and Analyzing the Secret Key Space of CSIDH | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 耐量子計算機暗号，同種写像暗号，ρ法，衝突探索 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 立教大学大学院理学研究科 | ||||||||||
| 著者所属 | ||||||||||
| 立教大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Science, Rikkyo University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Rikkyo University | ||||||||||
| 著者名 |
高橋, 康
× 高橋, 康
× 安田, 雅哉
|
|||||||||
| 著者名(英) |
Yasushi, Takahashi
× Yasushi, Takahashi
× Masaya, Yasuda
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 同種写像暗号は耐量子計算機暗号の候補の一つであり，同種写像問題の計算困難性を安全性の根拠としている．特にCSIDHは鍵共有方式であり，超特異楕円曲線の同型類に対するイデアル類群の作用を利用する．CSIDHの秘密鍵空間はベクトル空間の部分集合であり，与えられたベクトルに対応する作用が一意に定まる．しかし一方で，その対応関係は１対１でなく，与えられた作用に対応するベクトルは必ずしも一意でない．実際，自明な作用に対応するベクトルとして(3k,...,3k)（kは整数）があることが，2021年に小貫らとCastryckらによって同時に示されている．そこで本研究では，自明な作用に対応するベクトルを探索するためのρ法探索法を開発し，実際に30～40bit標数に対して探索実験を行った．さらに，実験により発見したベクトルを用いて格子簡約を行い，ベクトル空間全体から自明な作用への写像の核空間に対して，その線形空間としての次元を評価する．加えて，核空間内の一次独立なベクトルのノルムを評価し，自明な作用に対応するベクトルの中で秘密鍵空間に入るものがあるか調べる． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Isogeny-based cryptosystem is one of the candidates for post-quantum cryptography, relying on the computational complexity of the isogeny problem for its security. In particular, CSIDH is a key exchange method that uses the action of the ideal class group on isomorphism classes of supersingular elliptic curves. The secret key space of CSIDH is a subset of a vector space, and the action corresponding to a given vector is unique. However, on the other hand, this correspondence is not one-to-one, and a vector corresponding to a given action is not necessarily unique. In fact, it has been simultaneously discovered by Onuki et al. and Castryck et al. in 2021 that there exist vectors corresponding to trivial actions, such as (3k, . . . , 3k) (k is an integer). Therefore, in this paper, we develop a ρ-method search algorithm to search vectors corresponding to trivial actions and make search experiments for 20-40bit characteristics. Furthermore, using the discovered vectors from the experiments, we perform lattice reduction and evaluate the dimension of the kernel space of a map to the actions of the ideal class group from the vector space as a linear space. Additionally, we evaluate the L1-norms of linearly independent vectors in the kernel space and investigate whether there are vectors corresponding to trivial actions that belong to the secret key space. |
|||||||||
| 書誌情報 |
コンピュータセキュリティシンポジウム2023論文集 p. 1057-1061, 発行日 2023-10-23 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
