日本応用数理学会2014年度年会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

Dickson 多項式を用いた暗号方式に対する秘密鍵が小さい場合の攻撃法
○尾西 昭彦 (首都大学東京), 内田 幸寛 (首都大学東京), 内山 成憲 (首都大学東京)

RSA暗号において、秘密鍵が小さい場合に有効な攻撃法として、Wienerによる攻撃法やBoneh-Durfeeによる攻撃法が知られている。これらは、連分数展開やLLLアルゴリズムなどを用いており、秘密鍵があるバウンドよりも小さければ、入力サイズの多項式時間で動くものである。本講演では、RSA 暗号や LUC暗号の一般化と言えるDickson多項式を用いた公開鍵暗号方式について、上記の攻撃法を適用し、その効果について考察する。

有限群作用を持つゴッパ符号の構成法
○河田 貴久 (名古屋工業大学大学院工学研究科)

関数体上に有限群Γの作用が与えられたとき、これを利用して誤り位置特定に関し効率がよくかつ符号長の大きいゴッパ符号を構成する。本構成の効果を見るため、通常の構成とのあいだで 符号パラメータ、符号化率、特定可能な誤り位置の数を比較する。本符号構成は、関数体上の自己同型を利用するという点でFolded AG 符号の構成と類似であるが、適用対象である復号法に由来する符号構成を行う点でFolded AG符号とは異なる。

群環を用いたNTRUの安全性解析
○安田 貴徳 (九州先端科学技術研究所), ダハン グザヴィエ (九州先端科学技術研究所), 櫻井 幸一 (九州大、九州先端科学技術研究所)

格子ベース暗号であるNTRUは巡回群に対する群環を用いた暗号方式である。一般に、群環はNTRUの復号化を成功させ易くする良い構造を持っており、様々な有限群に対する群環を用いたNTRUが構成できる。 この方式に対し問題となるのは群環の実現方法と構成されたNTRUの安全性である。この観点から、NTRUに適した良い群環が何であるかを考察する。

有限体上のロジスティック写像による生成系列に対する長周期を保証するための条件
○土屋 和由 (株式会社光電製作所), 野上 保之 (岡山大学)

有限体上の線形写像から再帰的に生成される系列の性質は良く知られている反面、非線形写像から生成される系列に対しては、その性質が充分知られている例は数多くは無い。本講演では、有限体上のロジスティック写像と呼ばれるある種の一次元二次写像から再帰的に生成される系列に対して、長周期を保証するためのパラメータ及び初期値の条件を述べる。本結果から、宮崎-荒木-上原-野上によって数値実験により得られていた結果が系として得られる。

疎な秘密鍵を用いた多変数多項式署名方式
○安田 貴徳 (九州先端科学技術研究所), 高木 剛 (九州大学), 櫻井 幸一 (九州大学、九州先端科学技術研究所)

多変数多項式公開鍵暗号は耐量子暗号の一候補である。その中のRainbowと呼ばれる署名方式は、RSA暗号などと比較して秘密鍵長が 膨大になることが課題となっている。これに関し、疎な秘密鍵を用いることで、秘密鍵長を削減し、さらに署名生成の効率性を向上できることが知られており、いくつかの変形方式が提案されている。我々は安全性を基に提案された２つの疎な秘密鍵を用いたRainbowの変形方式を融合し、さらなる秘密鍵長の削減、署名生成の効率性向上を達成した。

Diophantine method in determining problem of lattice points
○平田 典子 (日本大学理工学部), 伊藤 勝 (東京工業大学大学院)

整数格子の点の決定問題に対し，ディオファントス近似の方法を応用して得られた知見を報告する．本講演におけるディオファントス近似とは「ある数が整数になると結論づける」ための十分条件を 記述する数論的手法の一つを指すものとする．ここではSchneider methodと呼ばれるディオファントス近似を適用し，複素関数が整数格子に値を取るための条件を求めるポリアの問題に関する新しい考察を行う．

問い合わせ先

サイボウズ・ラボ株式会社 光成滋生
herumi[at]nifty.com