| 講演名 | 2009-05-22 12個の事前計算点を用いた共同疎形式 桶屋 勝幸, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 楕円曲線暗号におけるマルチスカラー倍算の高速化手法として、スカラーの対を共同疎形式(Joint Sparse From,JSF)を用いて表現する方法が知られている。SolinasのJSF提案論文では、三つの拡張形式の構成が未解決問題として提示された。そのうちの二つは解決済みであるが、残りの一つが未解決として残されていた。その未解決問題とは、通常のJSFが0,±1によって定まる桁集合(digit set)を用いて整数対を表現するのに対して、±3などのより大きな値の桁集合を用いた場合への拡張表現の構成である。本稿では、この未解決となっていたJSFの拡張について考察する。事前計算する点の個数を12個とした場合、既存の結果では非ゼロ密度が0.3615が最小であった。本稿の結果では0.3577となることを示す。さらに、通常のJSFが満たすいくつかの性質について、拡張JSFも満足することを確認する。例えば、拡張JSFはいくつかのルールを満たす表現として定義できることや、存在性、一意性、(ハミング重みの)最小性などである。 |
| 抄録(英) | The joint sparse form (JSF) is a representation of a pair of integers, which is famous for accelerating a multi-scalar multiplication in elliptic curve cryptosystems. Solinas' original paper showed three unsolved problems on the enhancement of JSF. Whereas two of them have been solved, the other still remains to be done. The remaining unsolved problem is as follows: To design a represntation of a pair of integers using a larger digit set such as a set involves ±3, while the original JSF utilizes the digit set that consists of 0, ±1 for representing a pair of integers. This paper put an end to the problem. In the case with 12 precomputed points, whereas one of the best known results achieved 0.3615 of non-zero density, this paper improves it to 0.3577. In addition, the proposed enhancement satisfies some of properties, as the original does. For example, the enhanced represetation is defined as a representation that satisfies some rules. Some other properties are the existance, the uniquness of such a representation, and the optimality of the Hamming weight. |
| キーワード(和) | 楕円曲線暗号 / マルチスカラー倍算 / 共同疎形式(Joint Sparse Form,JSF) |
| キーワード(英) | elliptic curve cryptosystem / multi-scalar multiplication / joint sparse form (JSF) |
| 資料番号 | ISEC2009-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2009/5/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 12個の事前計算点を用いた共同疎形式 |
| サブタイトル（和） | |
| タイトル（英） | Joint Sparse Forms with Twelve Precomputed Points |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 楕円曲線暗号 / elliptic curve cryptosystem |
| キーワード(2)（和/英） | マルチスカラー倍算 / multi-scalar multiplication |
| キーワード(3)（和/英） | 共同疎形式(Joint Sparse Form,JSF) / joint sparse form (JSF) |
| 第 1 著者 氏名（和/英） | 桶屋 勝幸 / Katsuyuki OKEYA |
| 第 1 著者 所属（和/英） | (株)日立製作所システム開発研究所 Hitachi, Ltd., Systems Development Laboratory |
| 発表年月日 | 2009-05-22 |
| 資料番号 | ISEC2009-7 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 42 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |