2010年度連合発表会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

前田 博之、小椋 直樹（首都大学東京）、金山 直樹（筑波大学）、内山 成憲（首都大学東京）、岡本 栄司（筑波大学）
Elliptic net を用いたペアリングの計算について

近年，ID ベース暗号等，楕円曲線上のペアリングの双線形性を用いた暗号方式への応用の観点から，ペアリングについて盛んに研究されている．
それに対し，2007 年に Stange により elliptic net と呼ばれる写像を用いたTate ペアリングの新しい計算方法が提案された．elliptic net とは，elliptic divisibility sequence と呼ばれる楕円曲線の等分多項式と同様の性質をもつ数列を一般化した写像である。
本講演では，elliptic net を用いたペアリングの計算について，その計算量評価及び実装の観点から考察を行う．また，ある高速化についても述べる．

和田 祐一、内山 成憲、徳永 浩雄（首都大学東京）
代数曲面暗号に対するグレブナー基底を用いた攻撃法の考察

量子計算機を用いた攻撃から安全であろうと考えられている「次数の高い連立方程式の解を求める問題」に安全性の根拠をおいた多変数公開鍵暗号について、現在盛んに研究がすすめられている。本講演では、その中の一つである秋山と後藤によって提案された代数曲面暗号への攻撃法であるリダクション攻撃と呼ばれるものの改良版について述べる。この攻撃法は、内山と徳永により提案され、岩見により改良が与えられたものであったが、この改良版には論理的飛躍がみられ、正しい攻撃法になっていなかった。ここでは、その論理的飛躍の部分について指摘し、正当化を与えたアルゴリズムについて説明する。

金子 元（京都大学）
Borel予想、特に代数的無理数の2進展開について

Borelは全ての代数的無理数が2進展開について正規数であることを予想した。しかし、正規数であると証明された代数的無理数は無く、また、反例も見つかっていない。本講演では代数的無理数の2進展開においてdigitの0、1が変化した回数について下からの評価を行う。

石黒 司、松尾 和人（情報セキュリティ大学院大学）
種数2の超楕円曲線の位数計算の高速実装

GaudryとSchostによって種数2の超楕円曲線一般に適用可能な位数計算アルゴリズムが提案されている。このアルゴリズムは$O(l^4)$次の一変数$l$-等分多項式から実際に$l$-等分点を求め、これに対するFrobenius写像の作用を観察することで、Frobenius写像の特性多項式を求めるアルゴリズムである。Gaudryらは、このアルゴリズムの計算量が定義体に依存することを利用し、高速な定義体を選択することで160ビットの位数計算に成功している。本講演では、位数計算に必要な等分多項式の因子の最大次数が$O(l^3)$と多項式の次数に比べて小さいことを利用した改良アルゴリズムを示す。また、実装結果からこの改良の有効性を示す。

小椋 直樹（首都大学東京）、山本 剛、小林 鉄太郎（NTT）、内山 成憲（首都大学東京）
イデアル格子に基づく準同型暗号のパラメータ生成法

準同型暗号とは, ある平文集合に演算を施した結果の暗号文を, 各々の平文の暗号文から構成できるという性質を持つ暗号で, 電子投票やクロス集計等, 様々な応用が期待されている。
従来, 準同型暗号といえば, 加法のみ, あるいは乗法のみといった一つの演算について, 準同型性を持つものがほとんどであったが, 2009 年 Gentry によって, イデアル格子を用いた任意の深さの回路について準同型とする画期的な構成法が示された。
しかし, 提案された論文では秘密鍵の生成法について具体的に述べられていなかった。 本発表では, 定数深さの回路について機能する準同型暗号の具体的なパラメータ生成法を提案する。

秋山 浩岐、満保 雅浩、岡本 栄司（筑波大学）
改良Hidden Vector Encryption Schemeの検討

サーバに保管された暗号文書に対して、検索内容を外部に秘匿してキーワード等による検索を実現する暗号方式を検索可能暗号という。
Iovinoらは素数位数のペアリングを用いて、連接キーワード検索や大小比較検索、部分集合検索を実現する検索可能暗号方式を提案している。しかし、彼らの方式は検索実行時に検索クエリから生成されるベクトルをサーバへ送るため、このベクトルから検索内容についての情報が漏洩する可能性があるという問題がある。
そこで、本発表では特にIovinoらの方式に注目し、擬似ランダム置換を用いて検索クエリベクトルを改変することで検索内容についての情報を秘匿する改良検索可能暗号方式を提案する。

問い合わせ先

松尾和人 (情報セキュリティ大学院大学)
matsuo(at)iisec.ac.jp