ブレイド群を利用した公開鍵暗号系の
実装と性能評価実験

日本大学 文理学部

情報システム解析学科

谷研究室 田中裕子

Search party over Wide Area

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果と今後の課題

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果と今後の課題

研究の目的

◆2000年に K.H.Ko , S.J.Lee らがブレイド群を

利用した公開鍵暗号系を提案

◆現在広く使われているRSAにかわる公開鍵

暗号系となるのか？処理速度や安全性は？

◆実装して性能評価実験を行う

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果と今後の課題

暗号系

当事者以外にはわからないように

鍵を使い決められた手順に従って文を変換する

暗号系

◆秘密鍵暗号系

当事者以外にはわからないように

鍵を使い決められた手順に従って文を変換する

暗号系

◆公開鍵暗号系

当事者以外にはわからないように

鍵を使い決められた手順に従って文を変換する

公開

暗号鍵から復号鍵を
求めることは難しい

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果

ブレイド群に関する定義

◆n-ブレイド

平行な2つの面に接続しているn本の組み紐

3-ブレイドの例

ブレイド群に関する定義

◆ブレイドの同値

紐が面に接続している点を固定したまま動かして

同じものにできる

赤い紐を動かせば同じ

ブレイド群に関する定義

◆ブレイドの積

AとBの積ABはAをBの上に置いたもの

A

B

AB

ブレイドは可換でない

◆逆元

紐が接続している面で折り返したもの

ブレイド群に関する定義

ブレイド群に関する定義

◆単位元

どの紐も交差しないもの

◆生成元

ブレイド群に関する定義

◆生成元

ブレイド群に関する定義

◆生成元

ブレイドは生成元の積で表される

ブレイド群に関する定義

◆生成元

ブレイドは生成元の積で表される

→ 一意に決まらない → 標準形

ブレイド群に関する定義

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果と今後の課題

ブレイド群を利用した公開鍵暗号系

◆公開鍵暗号系のしくみ

ブレイド群を利用した公開鍵暗号系

◆公開鍵暗号系が成立する条件

一方の鍵で暗号化したものはペアとなる
もう一方の鍵でしか復号化できない

公開鍵（暗号鍵）から秘密鍵（復号鍵）を
求めることができない → 一方向関数の利用

ブレイド群を利用した公開鍵暗号系

◆一方向関数

易しい

難しい

ブレイド群を利用した公開鍵暗号系

◆ブレイド群における一方向関数

ブレイド群を利用した公開鍵暗号系

◆ブレイド群における一方向関数

ブレイド群を利用した公開鍵暗号系

◆ブレイド群における一方向関数

ブレイド群を利用した公開鍵暗号系

◆ブレイド群における一方向関数

易しい

難しい

ブレイド群を利用した公開鍵暗号系

◆鍵の生成

公開鍵

公開鍵

秘密鍵

ブレイド群を利用した公開鍵暗号系

◆鍵の生成

公開鍵

秘密鍵

ブレイド群を利用した公開鍵暗号系

◆鍵の生成

公開鍵

xとyは共役

→ xとyからaは求められない

ブレイド群を利用した公開鍵暗号系

◆鍵の生成

公開鍵

標準形

ブレイド群を利用した公開鍵暗号系

◆暗号化

送信

送信

m：送信したい平文

公開鍵 x と y を受信

ブレイド群を利用した公開鍵暗号系

◆暗号化

xとcは共役

→ xとcからbは求められない

送信

ブレイド群を利用した公開鍵暗号系

◆暗号化

ハッシュ関数

原文を固定長のデータに要約

ハッシュ値から原文を再現することはできない

同じハッシュ値を持つ異なるデータを
作成することは困難

送信

m：送信したい平文

ブレイド群を利用した公開鍵暗号系

◆復号化

暗号文 c と d を受信

秘密鍵

ブレイド群を利用した公開鍵暗号系

◆復号化のしくみ

正しくもとの文に復号化できるのか??

ブレイドは可換で

ないのでは??

ブレイド群を利用した公開鍵暗号系

◆復号化のしくみ

ブレイド群を利用した公開鍵暗号系

◆復号化のしくみ

この暗号系においてaとbは可換である

ブレイド群を利用した公開鍵暗号系

◆復号化のしくみ

元の文に正しく

復号化されている

目次

研究の目的

暗号系

ブレイド群に関する定義

ブレイド群を利用した公開鍵暗号系

研究の成果と今後の課題

研究の成果と今後の課題

◆ブレイド群を利用した公開鍵暗号系を実装

◆性能評価実験

実行環境

《CPU》 Pentium 4(2.7GHz)

《OS》 Fedora Core 2 Linux

《搭載メモリ》 1GB

《コンパイラ》 g++ 3.3.3

研究の成果と今後の課題

◆ブレイド群を利用した公開鍵暗号系を実装

◆性能評価実験

実験方法

平文を固定して鍵の生成・暗号化・復号化に
要する時間を測定

鍵をランダムに生成して20回測定したときの
平均を求めた

研究の成果と今後の課題

◆実験結果

紐の本数とブレイドの長さ(生成元の個数)を変えた場合

（単位：秒）

◆問題点

現在紐の本数を6本以上にできない

現在使われているRSA暗号系と同程度にまで
安全性を高めるためには紐の本数を増やす必要あり

研究の成果と今後の課題

◆問題点

現在紐の本数を6本以上にできない

原因：

標準形を構成するアルゴリズムは基本的に
多項式時間であるが今回の実装では一部が
指数時間になっている

その部分の高速なアルゴリズムは知られている

研究の成果と今後の課題

◆今後の課題

標準形を構成するプログラムの改良

紐の本数を増やして暗号系の安全性を高める

RSA暗号系との処理速度比較実験

研究の成果と今後の課題

おわり

Search party over Wide Area

2005-02-06T00:44:40