| 講演名 | 2012-11-22 部分群判定問題とペアリング逆問題についての注意(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般) 金山 直樹, 内山 成憲, 岡本 栄司, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では、部分群判定問題(subgroup decision problem)と呼ばれる問題の困難性についての考察を行う。部分群判定問題の困難性を安全性の根拠とした暗号方式が2005年に初めてBonehら[1]によって提案され、その後もこの問題を利用した多くの暗号方式が提案されている。部分群判定問題とは、合成数の位数を持つ群に対して定義される問題で、群Gの元xがGの(非自明な)部分群Hに属しているか否かを判定する問題である。なお、Hの生成元も与えられていると仮定する。Bonehらは[1]にて、群Gの与え方の一例として、RSA合成数の位数を持つ楕円曲線を用いることを挙げている。楕円曲線のような群の場合は、群Gの位数|G|の素因数分解を知られると方式が破られるので、|G|は素因数分解の困難な合成数たとえばRSA型合成数でなければならない。また、多くの方式では、部分群判定問題の対象である群Gの上で双線型写像(ペアリング)が定義されていることを仮定している。実際、[1]で挙げられている楕円曲線もそうである。本研究では、ペアリングの定義できる群Gカリl_1l_2(l_1,l_2は秘密の素数)の時に、Gでの部分群判定問題がペアリング逆問題に帰着されることを示す。 |
| 抄録(英) | In the present paper, we treat hardness of the subgroup decision problem. In 2005, Boneh et al. proposed a homomorphic encryption scheme whose security is based on hardness of the subgroup decision problem. The subgroup decision problem is stated as follows. Given a group G of composite order N=l_1l_2, where l_1 and l_2 are distinct primes, and generators g of G and gl_1 of the subgroup of order l_1, distinguish between whether an element T is a random member of the subgroup or a random element of the full group G. They also proposed to use elliptic curves which have subgroups whose group orders are large composite integers. If the factorization of the group order is known, the subgroup decision problem on such elliptic curves are efficiently solved. Therefore, we must choose composite integers such as RSA-modulus to construct groups in which the subgroup decision problem is hard. In the present paper, we show that the subgroup decision problem on bilinear group is reduced to pairing inversion problem when the group order is of the form N=l_1l_2. |
| キーワード(和) | 楕円曲線 / 双線形群 / 部分群判定問題 / ペアリング逆問題 |
| キーワード(英) | elliptic curves / bilinear groups / subgroup decision problem / pairing inversion problem |
| 資料番号 | ISEC2012-70,LOIS2012-45 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2012/11/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 部分群判定問題とペアリング逆問題についての注意(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般) |
| サブタイトル（和） | |
| タイトル（英） | A note on subgroup decision problem and pairing inversion problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 楕円曲線 / elliptic curves |
| キーワード(2)（和/英） | 双線形群 / bilinear groups |
| キーワード(3)（和/英） | 部分群判定問題 / subgroup decision problem |
| キーワード(4)（和/英） | ペアリング逆問題 / pairing inversion problem |
| 第 1 著者 氏名（和/英） | 金山 直樹 / Naoki KANAYAMA |
| 第 1 著者 所属（和/英） | 筑波大学大学院システム情報系 Graduate School of Systems and Information Engineering, University of Tsukuba |
| 第 2 著者 氏名（和/英） | 内山 成憲 / Shigenori UCHIYAMA |
| 第 2 著者 所属（和/英） | 首都大学東京大学院理工学研究科 Graduate School of Science and Engineering, Tokyo Metropolitan University |
| 第 3 著者 氏名（和/英） | 岡本 栄司 / Eiji OKAMOTO |
| 第 3 著者 所属（和/英） | 筑波大学大学院システム情報系 Graduate School of Systems and Information Engineering, University of Tsukuba |
| 発表年月日 | 2012-11-22 |
| 資料番号 | ISEC2012-70,LOIS2012-45 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 305 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |