| 講演名 | 2022-07-20 3次ツイストを持つペアリングフレンドリ曲線における効率的な疎乗算計算アルゴリズム 林田 大輝(三菱電機), 早坂 健一郎(三菱電機), 照屋 唯紀(産総研), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ペアリング計算は関数型暗号や電子署名をはじめ，多様な高機能暗号で用いられる基本的な演算であり，Miller loopと最終べき計算の二つの演算からなる．本論文では，Miller loopで出現する疎乗算に注目し，3次ツイストを持つ楕円曲線に適用可能なToom-Cook法をベースとする効率的な3次拡大体上の疎乗算アルゴリズムを提案する．本論文で提案する乗算アルゴリズムは，素体上の定数倍の回数を増加させる代わりに中間体上の加算回数を削減させることで計算コストの低減を図る．また，疎乗算を実行する元のどの係数が疎であっても疎乗算アルゴリズムを適用可能とする新たなテクニックを提案する．各埋め込み次数$k$に対して，今回の疎乗算アルゴリズムが有効となる条件を評価し，特に$k = 21,27$の3次ツイストを持つ楕円曲線においては素体の乗算加算コスト比に関わらず，今回の疎乗算アルゴリズムが最も効率的であることを示す． |
| 抄録(英) | In this paper, we propose an efficient sparse multiplication algorithm on elliptic curves with cubic twist based on the Toom-Cook method. The multiplication algorithm we propose reduces the complexity by reducing the number of addition operations on the extension field to the number of constant multiplication on the prime field. We give a new technique that enables the application of the sparse multiplication algorithm regardless of which coefficient is sparse in the Miller loop. |
| キーワード(和) | ペアリング暗号 / Miller loop / 疎乗算 / Toom-Cook法 |
| キーワード(英) | Pairing-based cryptography / Miller loop / sparse multiplication / Toom-Cook method |
| 資料番号 | ISEC2022-26,SITE2022-30,BioX2022-51,HWS2022-26,ICSS2022-34,EMM2022-34 |
| 発行日 | 2022-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
| 研究会情報 | |
| 研究会 | EMM / BioX / ISEC / SITE / ICSS / HWS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| 開催期間 | 2022/7/19(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2022） |
| テーマ（英） | |
| 委員長氏名（和） | 西村 竜一(NICT) / 今岡 仁(NEC) / 國廣 昇(筑波大学) / 大谷 卓史(吉備国際大) / 吉岡 克成(横浜国大) / 永田 真(神戸大) |
| 委員長氏名（英） | Ryoichi Nishimura(NICT) / Hitoshi Imaoka(NEC) / Noboru Kunihiro(Tsukuba Univ.) / Takushi Otani(Kibi International Univ.) / Katsunari Yoshioka(Yokohama National Univ.) / Makoto Nagata(Kobe Univ.) |
| 副委員長氏名（和） | 薗田 光太郎(長崎大) / 市野 将嗣(電通大) / 奥井 宣広(KDDI総合研究所) / 高田 直幸(セコム) / 四方 順司(横浜国大) / 花岡 悟一郎(産総研) / 森下 壮一郎(サイバーエージェント) / 辰己 丈夫(放送大) / 笠間 貴弘(NICT) / 林 優一(奈良先端大) / 鈴木 大輔(三菱電機) |
| 副委員長氏名（英） | Kotaro Sonoda(Nagasaki Univ.) / Masatsugu Ichino(Univ. of Electro-Comm.) / Norihiko Okui(KDDI Research) / Naoyuki Takada(SECOM) / Junji Shikata(Yokohama National Univ.) / Goichiro Hanaoka(AIST) / Soichiro Morishita(Cyber Agent) / Takeo Tatsumi(Open Univ. of Japan) / Takahiro Kasama(NICT) / Yuichi Hayashi(NAIST) / Daisuke Suzuki(Mitsubishi Electric) |
| 幹事氏名（和） | 高嶋 洋一(開志専門職大) / 今泉 祥子(千葉大) / 早坂 昭裕(NEC) / 佐野 恵美子(三菱電機) / 松田 隆宏(産総研) / 米山 一樹(茨城大) / 藤井 秀之(NRIセキュアテクノロジー) / 鈴木 大助(北陸大) / 山田 明(KDDI labs.) / 山内 利宏(岡山大) / 山本 弘毅(ソニーセミコンダクタソリューションズ) / 藤本 大介(奈良先端大) |
| 幹事氏名（英） | Youichi Takashima(Kaishi Professional Univ.) / Shoko Imaizumi(Chiba Univ.) / Akihiro Hayasaka(NEC) / Emiko Sano(MitsubishiElectric) / Takahiro Matsuda(AIST) / Kazuki Yoneyama(Ibaraki Univ.) / Hideyuki Fujii(NRI-Secure) / Daisuke Suzuki(Hokuriku Univ.) / Akira Yamada(KDDI labs.) / Toshihiro Yamauchi(Okayama Univ.) / Hirotake Yamamotoi(SSS) / Daisuke Fujimotoi(NAIST) |
| 幹事補佐氏名（和） | 梶山 朋子(広島市大) / 酒澤 茂之(大阪工大) / 鈴木 裕之(群馬大) / 白川 真一(横浜国大) / 花谷 嘉一(東芝) / 橘 雄介(福岡工業大) / 木藤 圭亮(三菱電機) / 菅原 健(電通大) / 鐘本 楊(NTT) |
| 幹事補佐氏名（英） | Tomoko Kajiyama(Hiroshima City Univ.) / Shieyuki Sakazawa(Osaka Inst. of Tech.) / Hiroyuki Suzuki(Gunma Univ) / Shinichi Shirakawa(Yokohama National Univ.) / Yoshikazu Hanatani(Toshiba) / Yusuke Tachibana(Fukuoka Inst. of Tech.) / Keisuke Kito(Mitsubishi Electric) / Takeshi Sugawara(Univ. of Electro-Comm.) / Yo Kanemoto(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Biometrics / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Technical Committee on Hardware Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 3次ツイストを持つペアリングフレンドリ曲線における効率的な疎乗算計算アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Efficient Sparse Multiplication Algorithm For Pairing-Friendly Elliptic Curves With Cubic Twist |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペアリング暗号 / Pairing-based cryptography |
| キーワード(2)（和/英） | Miller loop / Miller loop |
| キーワード(3)（和/英） | 疎乗算 / sparse multiplication |
| キーワード(4)（和/英） | Toom-Cook法 / Toom-Cook method |
| 第 1 著者 氏名（和/英） | 林田 大輝 / Daiki Hayashida |
| 第 1 著者 所属（和/英） | 三菱電機株式会社(略称：三菱電機) Mitsubishi Electric Corporation(略称：Mitsubishi Electric Corp.) |
| 第 2 著者 氏名（和/英） | 早坂 健一郎 / Kenichiro Hayasaka |
| 第 2 著者 所属（和/英） | 三菱電機株式会社(略称：三菱電機) Mitsubishi Electric Corporation(略称：Mitsubishi Electric Corp.) |
| 第 3 著者 氏名（和/英） | 照屋 唯紀 / Tadanori Teruya |
| 第 3 著者 所属（和/英） | 産業技術総合研究所(略称：産総研) National Institute of Advanced Industrial Science and Technology(略称：AIST) |
| 発表年月日 | 2022-07-20 |
| 資料番号 | ISEC2022-26,SITE2022-30,BioX2022-51,HWS2022-26,ICSS2022-34,EMM2022-34 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | ISEC-122,SITE-123,BioX-124,HWS-125,ICSS-126,EMM-127 |
| ページ範囲 | pp.110-117(ISEC), pp.110-117(SITE), pp.110-117(BioX), pp.110-117(HWS), pp.110-117(ICSS), pp.110-117(EMM), |
| ページ数 | 8 |
| 発行日 | 2022-07-12 (ISEC, SITE, BioX, HWS, ICSS, EMM) |