TUMSAT-OACIS Repository - Tokyo
University of Marine Science and Technology(東京海洋大学)
ブレイド群を利用した公開鍵暗号系の実装
メタデータ

言語: Japanese
出版者:
公開日: 2022-02-14
キーワード (Ja):
キーワード (En):作成者: 前田, 有宏
メールアドレス:所属:

URL

https://oacis.repo.nii.ac.jp/records/2282

修士学位論文

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

平成１９年度（２００８ ３月）

東京海洋大学大学院
海洋科学技術研究科
海運ロジスティクス専攻
０６５５００５

前田 有宏

2

目次
第 1 章 はじめに

4

第 2 章 ブレイド群
6
2.1 ブレイド群に関する諸定義 . . . . . . . . . . . . . . . . . . 6
2.1.1 ブレイドとは . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 ブレイドの積 . . . . . . . . . . . . . . . . . . . . . 6
2.1.3 Artin generator . . . . . . . . . . . . . . . . . . . . 7
2.1.4 正ブレイド . . . . . . . . . . . . . . . . . . . . . . 8
2.1.5 半順序 . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.6 Band Generator . . . . . . . . . . . . . . . . . . . 9
2.2 ブレイドの標準形 . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 left canonical form の定義 . . . . . . . . . . . . . . 11
2.2.2 left canonical form 構成アルゴリズム . . . . . . . . 11
第 3 章 ブレイド群を利用した公開鍵暗号
3.1 共役とは . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 共役問題 . . . . . . . . . . . . . . . . . . . . . . . .
3.2 一方向関数 . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 鍵共有 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 公開鍵暗号 . . . . . . . . . . . . . . . . . . . . . . . . . .

15
15
15
16
17
18

第 4 章 Lawrence-Krammer 表現を用いた公開鍵暗号に対する攻撃
19
4.1 ブレイド群の線形表現 . . . . . . . . . . . . . . . . . . . . 19
4.1.1 Burau 表現 . . . . . . . . . . . . . . . . . . . . . . 19
4.1.2 Lawrence-Krammer 表現 . . . . . . . . . . . . . . . 20
4.2 攻撃アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 ρ−1
k を計算するアルゴリズム . . . . . . . . . . . . . . . . . 22
4.4 暗号への攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . 25
第 5 章 プログラムの仕様
27
5.1 Python パッケージの使用方法 . . . . . . . . . . . . . . . . 27
5.2 Python パッケージ . . . . . . . . . . . . . . . . . . . . . . 27

3
5.3

Mathematica パッケージ . . . . . . . . . . . . . . . . . . . 32

第 6 章 考察，及び結論

33

Appendix

34

参考文献

65

4

第 1 章 はじめに
ネットワーク化が進んだ今日において，情報を隠蔽するための暗号技
術は情報セキュリティ技術の中核をなすものの一つとしてとらえられ，非常に活発に研究がなされている．暗号とは，送信者がメッセージを別の形にすることにより，第三者に対して秘匿し，意図した特定の受信者だけがメッセージを理解できるようにする通信手段のことである．現在，軍事，
外交，商業などの幅広い分野で利用されている．
現在最も広く使われている公開鍵暗号は素因数分解の困難性を利用した「RSA 暗号」である．その後，「楕円曲線暗号」や「ElGamal 暗号」などの新しい公開鍵暗号が開発されるなど，現在に至るまで多くの公開鍵暗号が研究されてきている [15]．
RSA 暗号や楕円曲線暗号は離散対数問題の困難性に基づいた暗号であるが，2000 年に Ko 達はブレイド群の共役問題の困難性を利用した新たな公開鍵暗号 [10] を提案した．ここでブレイド群とは組み紐群のことであり，x と axa−1 から a を求めることを共役問題という．離散対数問題や共役問題はどちらも「群上の関数であって逆問題を解くことが困難なもの」であるから，この点でさらなる一般化が期待されている．Ko 達の暗号が発表されて以来，暗号に対する攻撃の研究も活発に行われ，2003 年に Cheon 達は [7] で上記の暗号に対して攻撃を行う初の多項式時間アルゴ
リズムを提案した．この攻撃において，Cheon らはブレイド群の線形表
現である Lawrence-Krammer 表現 [12] を用いることにより，共役問題を直接解くことなく暗号に対して攻撃を行うことができることを示した．しかし，上記のアルゴリズムには幾つかの誤りがあったため，本論文においては Lukkarila の修正したアルゴリズム [13] を用いることにした．上記の攻撃において，共役問題は解かれておらず，現在においてもブレイド群の共役問題を解くことは難しい．
本論文ではまず，ブレイド群の定義，及び上記の公開鍵暗号に関する総合報告を行う．次にブレイド群の線形表現と暗号に対する攻撃アルゴリ
ズムを示す．実装に関しては Python を用いて暗号を構成するのに必要なアルゴリズムを実装し，Mathematica を用いて攻撃アルゴリズムを実装
する．
本論文の構成は以下の通りである．第 2 章でブレイド群に関する諸定義

5とブレイドの標準形について述べ，第 3 章で暗号に使われているブレイド
群の共役問題，及びブレイド群を利用した公開鍵暗号について述べる．第4 章ではブレイド群の線形表現と暗号に対する攻撃について述べ，最後に第 5 章で作成したプログラムの構成について述べる．

6

第 2 章 ブレイド群

2.1

ブレイド群に関する諸定義

この節ではブレイドの積や同値関係といったブレイド群に関する諸定義について述べる [4],[16]．

2.1.1

ブレイドとはn− ブレイドとは平行な 2 つの面に接続している n 本の紐であり，上の面から出ている紐をたどると常に下へ向かい必ず下の面につくものをいう．n− ブレイド群のことを Bn と表し，n を braid index という．

B3 の例

2.1.2

ブレイドの積2 つの任意のブレイド a, b の積とは，a を b の上に置くことで得られる．

7

ab
a

b

2 つのブレイドの積

2.1.3

Artin generator

Bn , n = 1, 2, 3, . . . は n − 1 個の生成元 σ1 , σ2 . . . , σn−1 を持っている．生
成元 σi は 左から数えて i 番目と i + 1 番目の紐が交差しており，i 番目の紐が i + 1 番目の紐の下にきているブレイドを意味している．また，生成元σi−1 とは，
σi の紐の重なり方を上下反対にしたものをいい，どの紐も交差していないブレイドを単位元とし，e で表す．上記の生成元は Artin の生成元と呼ばれ，以下のような基本関係式が成り立つ．
σt σs = σ s σ t

if |t − s| > 1(2.1)

σ t σ s σt = σs σ t σ s

if |t − s| = 1(2.2)

また，2 つのブレイド a, b があり，a の端点を固定し，上下の平面によって囲まれた空間から紐を出さずに上下関係を維持したまま動かし，b に一致させることができるときを同値という．Bn に対して， σi2 = 1, i =1, 2, 3, . . . , n − 1 の関係を加えると，Bn は置換群Σn になる．つまり，BnからΣn への自然な全射準同型写像ρ : Bn → Σn が定義できる．ここで，σiは互換 (i, i + 1) に対応している．
例えば a ∈ B4 , π ∈ Σ4 とし，a = σ1 σ2 σ3 に対する置換はπ = 2341 である．
(
)
1234
π=
2341

8

単位元 e

...

1

...

i

...

n

i+1

...

生成元σi , σi−1

2.1.4

正ブレイド

生成元σi と関係式 (2.1)，(2.2) によって定義される半群を Bn+ とし，これを正ブレイドと呼ぶ．正ブレイドの中で，それぞれの紐の交差が高々1 回であるものを permutation braid と呼び，その集合をΣ̃n と表す．また permutation braid の中で，すべての紐がちょうど一回ずつ交差しているブレイドを fundamental braid と呼び，∆n で表す．

∆n : = σ1 σ2 · · · σn−1 ∆n−1
fundamental braid の例∆ 4 = σ 1 σ2 σ 3 σ1 σ2 σ1 = σ 1 σ2 σ 3 σ2 σ1 σ 2 = σ 1 σ3 σ2 σ3 σ1 σ 2

(2.3)

9

fundamental braid ∆4

2.1.5

半順序

Bn の元に対する半順序を次のように定義する．V ∈ Bn+ ，U = W V のとき，W ≤L U と表す．また，U = V W のとき，W ≤R U とする．最後に V1，V2 ∈ Bn+ ，U = V1 W V2 のとき，W ≤ U と表す．
2 つのブレイド U ，V が与えられたとき，W ≤L U ，W ≤L V を満たす最大の元 W を left meet と呼び，U ∧L V と表す．同様に，関係 ≤R を用
いて right meet も定義でき，U ∧R V と表す．また，U ≤L W ，V ≤L W を満たす最小の元 W を left join と呼び，U ∨L V と表す．またこれも同様に
right join を定義でき，U ∨R V で表す．ブレイド群において meet は最大
公約数，join は最小公倍数と同様の役割を果たす．

2.1.6

Band Generator

Birman らは Artin の生成元に対し，複数の紐をひとまとめにした band
generator [3],[9] と呼ばれる新しい生成元を提案した．1 ≤ s < t ≤ n のとき，band generator ats を−1−1 −1
ats = (σt−1 σt−2 · · · σs+1 )σs (σs+1· · · σt−2
σt−1 )(2.4)と定義する．これは t 番目の紐と s 番目の紐を他の紐の上で交差させたものである．例えば，a(i+1)i = σi である．

10
2

1

3

4

a41

band generator の例
band generator にも以下のような基本関係式がある．
if (t − r)(t − q)(s − r)(s − q) > 0(2.5)∀t, s, r (1 ≤ r < s < t ≤ n)

(2.6)

at(t+1) as(s+1) = as(s+1) at(t+1)

if |t − s| > 1(2.7)

at(t+1) as(s+1) at(t+1) = as(s+1) at(t+1) as(s+1)

if |t − s| = 1(2.8)

ats = arq ats

ats asr = atr ats = asr atr

また，band generator には次のような fundamental word δ と呼ばれるブレイドがある．

δ = an(n−1) a(n−1)(n−2) · · · a21 = σn−1 σn−2 · · · σ2 σ1

2.2

(2.9)

ブレイドの標準形

fundamental braid の例でもわかるように，ブレイドを生成元σi のワー
ドとして書く表し方は一意ではない．そこで，left canonical form という標準形を用いる．

11

2.2.1

left canonical form の定義

任意の正ブレイド P ∈ Bn+ に対して，以下の集合が定義される．
′′

S(P ) = {i | ある P ∈ Bn+ に対して，P = σi P }′F (P ) = {i | ある Q′
∈ Bn+ に対して，P = Q σi }(2.10)(2.11)

S(P ), F (P ) をそれぞれ Starting 集合，Finishing 集合という．また，任意の正ブレイドの積 AB が F (A) ⊇ S(B) を満たすとき left weighted という．
定理 １．任意のブレイド W ∈ Bn に対して，left canonical form と呼ばれる以下のような表現が一意に存在する．

W = ∆un A1 A2 . . . Ap ,u ∈ Z, Ai ∈ Σ̃n {e, ∆n }(2.12)

ただし，Ai Ai+1 (1 ≤ i < p) は left weighted である．また，上記の p を
canonical length，u を inﬁmum，u + p を supremum という [10]．

2.2.2left canonical form 構成アルゴリズム

Starting 集合に関して次の命題が成り立つ．
命題 １．P ∈ Σ̃n ならば ∀σj ∈ S(P ) に対して，

σj−1 P ∈ Σ̃n(2.13)

また，∆n は次のような性質を持っている．

(a) 1 ≤ i ≤ n − 1 に対して，∆n = σi Ai = Bi σi となるような Ai , Bi ∈ Σ̃nが存在する．
(b) 1 ≤ i ≤ n − 1 に対して，
σi ∆n = ∆n σn−i が成り立つ．
上の命題，及び (a), (b) を用いてleft canonical form を構成する．

1．生成元のワードの形で表された任意のブレイド W において，W がσi−1−1を含んでいる場合，(a) よりσi−1 = ∆−1
n Bi を用いてσi を置き換える．次′W = ∆un P ，P ∈ Bn+ を作る．に (b) を用いて左に∆−1
n を集め，

12
2-1．正ブレイド P を左から見ていって，permutation braid の積になるよ
うに分解する．
P = a1 a2 · · · al ， ai ∈ Σ̃n2-2-1. 1 ≤ ∀i < l に対して，S(ai+1 ) − F (ai ) ̸= ∅ ならば σj ∈ S(ai+1 ) −F (ai ) を用いて，
ai ← ai σj , ai+1 ← σj−1 ai+1と更新する．

-2. 上の 1 を S(ai+1 ) − F (ai ) = ∅ が全ての i について成り立つまで繰り
返す．
′

′

-3. a1 = ∆n のときは，u ← u + 1, a1 ← a2 と更新する．これを a1 ̸= ∆nとなるまで繰り返す．
-4. Ai ← ai を出力する．
2-2 に関するアルゴリズムの詳細については Appendix を参照のこと．
3．1，2 を組み合わせることにより，任意のブレイドを定理 1 の left canonical form に変形することができる．
left canonical form の例
n = 4，W = σ1 σ3−1 σ2 σ1 をleft canonical form に変形する．
1．σ3−1 を∆−1∆−1
4 B3 に置き換え，
4 を左に集める．
W= σ1 ∆−1
4 (σ3 σ2 σ1 σ3 σ2 )σ2 σ1= ∆−1
4 σ3 (σ3 σ2 σ1 σ3 σ2 )σ2 σ1
= ∆−1
4 P

2-1． 正ブレイド P = σ3 σ3 σ2 σ1 σ3 σ2 σ2 σ1 を permutation braid の元の積に分解する．
P= σ3 σ3 σ 2 σ1 σ 3 σ2 σ2 σ 1= (σ3 )(σ3 σ2 σ3 σ1 σ2 )(σ2 σ1 )= (a1 )(a2 )(a3 )(a1 , a2 , a3 ∈ Σ̃n )13
次に上記の (a1 a2 ), (a2 a3 ) が left weighted になるように分解する．

2-2
1. F (a1 ) = {3}, S(a2 ) = {2, 3} より，S(a2 ) − F (a1 ) = {2} であるので，
a1 ← (a1 )σ2 = σ3 σ2 , a2 ← σ2−1 (a2 ) = σ2−1 σ3 σ2 σ3 σ1 σ2 = σ3 σ2 σ1 σ22. F (a1 ) = {2}, S(a2 ) = {1, 3} より，S(a2 ) − F (a1 ) = {1, 3} であるので，
a1 ← (a1 )σ1 = σ3 σ2 σ1 , a2 ← σ1−1 (a2 ) = σ1−1 σ3 σ2 σ1 σ2 = σ3 σ2 σ1
3. F (a1 ) = {1}, S(a2 ) = {3} より，S(a2 ) − F (a1 ) = {3} であるので，
a1 ← (a1 )σ3 = σ3 σ2 σ1 σ3 , a2 ← σ3−1 (a2 ) = σ3−1 σ3 σ2 σ1 = σ2 σ1
4. F (a1 ) = {1, 3}, S(a2 ) = {2} より，S(a2 ) − F (a1 ) = {2} であるので，
a1 ← (a1 )σ2 = σ3 σ2 σ1 σ3 σ2 , a2 ← σ2−1 (a2 ) = σ2−1 σ2 σ1 = σ1
5. F (a1 ) = {1, 2}, S(a2 ) = {1} より，S(a2 ) − F (a1 ) = { } であるので，
F (a1 ) ⊇ S(a2 ) が成り立つので，a1 a2 は left weighted である．
6. F (a2 ) = {1}, S(a3 ) = {2} より，S(a3 ) − F (a2 ) = {2} であるので，
a2 ← (a2 )σ2 = σ1 σ2 , a3 ← σ2−1 (a3 ) = σ2−1 σ2 σ1 = σ1
7. F (a2 ) = {2}, S(a3 ) = {1} より，S(a3 ) − F (a2 ) = {1} であるので，
a2 ← (a2 )σ1 = σ1 σ2 σ1 , a3 ← σ1−1 (a3 ) = σ1−1 σ1 = e
8. F (a2 ) = {1, 2}, S(a3 ) = { } より，S(a3 ) − F (a2 ) = { } であるので，
F (a2 ) ⊇ S(a3 ) が成り立つので，a2 a3 は left weighted である．
9. F (a1 ) = {1, 2}, S(a2 ) = {1, 2} より，S(a2 ) − F (a1 ) = { } であるので，
F (a1 ) ⊇ S(a2 ) が成り立つので，a1 a2 は left weighted である．
上記より，

P

= (σ3 σ2 σ1 σ3 σ2 )(σ1 σ2 σ1 )(e)= (σ3 σ2 σ1 σ3 σ2 )(σ1 σ2 σ1 )= A1 A2となる．上記の A1 ，A2 において，F (A1 ) ⊇ S(A2 ) であり，A1 ，A2 は left
weighted である．よって，以下の left canonical form を得る．

W = ∆−1
4 (σ3 σ2 σ1 σ3 σ2 )(σ1 σ2 σ1 )14
上記の left canonical form と同様にして，right canonical form も定義できる．
W = A1 A2 . . . Ap ∆un u ∈ Z, Ai ∈ Σ̃n {e, ∆n }ここで，Ai , Ai+1 は F (Ai ) ⊆ S(Ai+1 ) が成り立ち，right weighted である．

15

第 3 章 ブレイド群を利用した公開鍵暗号
この章ではブレイド群の共役問題を紹介し，次にそれを利用した公開鍵
暗号について述べる [10]．

3.1

共役とは

ブレイド x，y が共役であるとは，y = axa−1 となるブレイド a が存在するときをいう．共役に関して，困難であると予想されている計算問題に以下のようなものがある．ここで，Bm を m < n に対して，
σ1 ，· · · ，
σm−1 で生成される Bn の部分群とする．

3.1.1

共役問題

1．共役決定問題
入力：(x, y) ∈ Bn × Bn
出力：x と y が共役であるかどうかを決定する．
2．共役探索問題
入力：(x, y) ∈ Bn × Bn (a ∈ Bn が存在して，y = axa−1 ．
)−1
出力：y = axa を満たす a ∈ Bn を見つけること．
3．一般共役探索問題
入力：(x, y) ∈ Bn × Bn (m ≤ n に対して，y = axa−1 ，a ∈ Bm )出力：y = axa−1 を満たす，a ∈ Bm を見つけること．
4．共役分解問題
入力：(x, y) ∈ Bn × Bn (m < n に対して，y = axa−1 ，a ∈ Bm )′′′′出力：y = a xa を満たす a ，a′′ ∈ Bm を見つけること．

16
次の節以降で具体的に上記の一般共役探索問題を用いた公開鍵暗号について説明する．

3.2

一方向関数

l, r ≤ n に対して，Bn の部分群 LBl ，RBr を次のように定める．LBl は n 本の紐の中で左側の l 本の紐を，RBr は右側の r 本の紐を編むことによって構成されるとする．すなわち，LBl は生成元σ1 , · · · , σl−1 ，RBr はσn−r+1，· · · , σn−1 から生成される部分群である．l +r ≤ n のとき，任意の a ∈ LBl，b ∈ RBr は可換である．以下 l + r = n とする．上記の LBl を用いて以下の一方向関数を定義する．
f : LBl × Bl+r → Bl+r × Bl+r ，

f (a, x) = (axa−1 , x)(a, x) が与えられたとき，axa−1 を計算するのは易しいが，(axa−1 , x) から a を計算する多項式時間アルゴリズムは知られていない [1]．また，上記の一方向関数は一般共役探索問題に基づている．
ブレイド群を利用した鍵共有，公開鍵暗号は以下の問題の計算量的困難性に基づいている．

[Base Problem]
入力：秘密である a ∈ LBl ，b ∈ RBr に対して，y1 = axa−1 ，y2 = bxb−1 を満たす Bl+r の元 (x, y1 , y2 )出力：by1 b−1 (= ay2 a−1 = abxa−1 b−1 )Base Problem を計算量的に困難にするためには，十分に複雑なブレ
イド x ∈ Bl+r を選ばなければならない．ここで，x が十分に複雑であるとは x1 ∈ LBl ，x2 ∈ RBr ，z ∈ Bl+r であって，「z は a, b, x1 , x2 と可換
かつ x が x = x1 x2 z と分解される」ものが存在しないことをいう．もし x = x1 x2 z と分解されたとしたら，
by1 b−1 = baxa−1 b−1= ab(x1 x2 z)a−1 b−1 (a, x1 ∈ LBl , b, x2 ∈ RBr )= abx1 x2 a−1 b−1 z= (ax1 a−1 )(bx2 b−1 )z

17
ここで，

y1 = axa−1= a(x1 x2 z)a−1= (ax1 x2 a−1 )z= (ax1 a−1 )x2 z
y2 = bxb−1= b(x1 x2 z)b−1= (bx1 x2 b−1 )z= x1 (bx2 b−1 )z−1 = x−1 y z −1 と分かるので，より，ax1 a−1 = y1 z −1 x−1
2
2 ， bx2 b
1

by1 b−1 = (ax1 a−1 )(bx2 b−1 )z−1−1= (y1 z −1 x−1
2 )(x1 y2 z )zとなる．これより，a，b を知らなくても by1 b−1 が分かってしまう．
Base Problem における x の役割は，g x と g y から g xy を求める DiﬃeHellman Problem [8] における g に相当していることから，上記の問題は
Diﬃe-Hellman-Like Conjugacy Problem(DHCP) と呼ばれている．

3.3

鍵共有

A(lice) と B(ob) との間において，以下の鍵共有を定義する．
1．前処理
適当な整数の組 (l, r)，及び十分に複雑なブレイド x ∈ Bl+r を選び公開する．
2．鍵共有(a) A はランダムに秘密鍵 a ∈ LBl を選び，B に対して y1 = axa−1 を送る．
(b) B はランダムに秘密鍵 b ∈ RBr を選び，A に対して y2 = bxb−1 を送る．
(c) A は y2 を受け取り，共有鍵 K = ay2 a−1 を計算する．

18(d) B は y1 を受け取り，共有鍵 K = by1 b−1 を計算する．
ここで，a ∈ LBl ，b ∈ RBr は ab = ba であるので，

ay2 a−1 = a(bxb−1 )a−1 = b(axa−1 )b−1 = by1 b−1
上記より，Alice と Bob は同じブレイドを得ることができる．

3.4

公開鍵暗号

3.3 の 鍵共有の原理を用いて，ブレイド群を利用した公開鍵暗号を定義する．H：Bl+r → {0, 1}k をブレイド群からメッセージ空間へのハッシュ関数とする．
1．鍵の生成：(a) 十分に複雑なブレイド u ∈ Bl+r を選ぶ．
(b) a ∈ LBl を選ぶ(c) v = aua−1 を計算し，(u, v) を公開鍵，a を秘密鍵とする．
2．暗号化：メッセージ m ∈ {0, 1}k と公開鍵 (u, v) が与えられているとする．
(a) b ∈ RBr をランダムに選ぶ．
(b) w = bub−1 と d = H(bvb−1 ) ⊕ m を計算し，暗号文を (w, d) とする．
3．復号化：暗号文 (w, d) と秘密鍵 a を用いて，m = H(awa−1 ) ⊕ d を計算する．
a と b は可換であるので，awa−1 = abub−1 a−1 = baua−1 b−1 = bvb−1 が成り立ち，H(awa−1 ) ⊕ d = H(awa−1 ) ⊕ H(bvb−1 ) ⊕ m = m となりメッセージを得ることができる．

19

第4章

Lawrence-Krammer 表現を用いた公開鍵暗号に対する攻撃

この章ではブレイド群の線形表現を示し，それを用いた暗号に対する攻撃について説明する．

4.1

ブレイド群の線形表現

ブレイド群の線形表現は幾つかあるが，本論文では Burau 表現 [2] とLawrence-Krammer [12] 表現の 2 つのみを紹介する．

4.1.1

Burau 表現

Burau 表現は次の写像 ρB：Bn → GLn (Z[t, t−1 ]) で定義される．


Ii−1
0
 0
1−t

σi → 
 0
1
0
0


0
0

t
0



0
0
0 In−i−1

n = 4 のとき，

1 − t t − t2 t2
 1
0
0

W = σ1 σ 2 → 
 0
1
0
0
0
0


0
0 


0 
1

Burau 表現は一般的に忠実ではない．また，与えられた Burau 行列に対応するブレイドを返す決定性アルゴリズムは現在のところ存在しない．
Burau 表現は n = 3 のとき忠実であり，n ≥ 5 のとき忠実ではない．n = 4のとき，Burau 表現が忠実であるかどうかという問題はまだ明らかでは
ない．

20

4.1.2

Lawrence-Krammer 表現

Lawrence-Krammer 表現は次の写像 ρK：Bn → GLn(n−1)/2 (V ) によって定義される．ここで，V = Z[t±1 , q ±1 ] である．{xi,j |1 ≤ i < j ≤ n} を
自由加群 V の標準基底とすると，生成元σk はLawrence-Krammer 表現のもとで次のように表される．

tq 2 xk,k+1(i = k, j = k + 1)





(1 − q)xi,k + qxi,k+1(j = k, i < k)





k−i+1 (q − 1)x(j = k + 1, i < k)
k,k+1
xi,k + tq
ρk (σk )xi,j = tq(q − 1)xk,k+1 + qxk+1,j(i = k, k + 1 < j)
xk,j + (1 − q)xk+1,j(i = k + 1, k + 1 < j)






xi,j
(i < j < k or k + 1 < i < j)




k−i
2
xi,j + tq (q − 1) xk,k+1(i < k < k + 1 < j)．
例えば n = 4 のとき，
ρK (σ2 σ3 ) は
1−q 1−q
1
0
0
0


0
0
0
0
0
 q



 0

q
0
0
0
0


ρK (σ2 σ3 ) = 0−q 2 t + q 3 t
0
q2t
0
 0



3
4
2
3
2
0
−q t + q t
0−q t + q t
q t
 0

3
4
5
2
2
3
4
2
3
0
0
−q t + 2q t − q t q −q t + 2q t − q t q t − q tとなる．Lawrence-Krammer 表現は任意の自然数 n に対して忠実である．次の節で上記の表現を用いた公開鍵暗号に対する攻撃について述べる．

4.2

攻撃アルゴリズムCheon と Jun は Lawrence-Krammer 表現を用いた暗号を攻撃する多項式時間アルゴリズムを提案した．このアルゴリズムでは暗号化と鍵共有に対して攻撃を行うが，直接的には共役問題を解かない．一般的に，現在においても共役問題を解く多項式時間アルゴリズムは知られていない．まず，アルゴリズムの大まかな流れを記述する [7],[11]．
上記の暗号ではブレイド群の共役問題の困難性を利用しており，与えられた u, v = aua−1 , w = bub−1 ∈ Bn (a ∈ LBn , b ∈ RBn ) から baua−1 b−1を見つけだせれば解読できる．
Cheon らは Lawrence-Krammer 表現を用いて，次のような暗号に対する攻撃を提案した．

21
まず，上記のアルゴリズムにおいて Lawrence-Krammer 表現はアルゴ
リズムの計算量を減らすために q = 1/2（q を 0 < q < 1 を満たす実数と′′してもLawrence-Krammer 表現は忠実である [12]．
）とし，ρk と表す．ρkにおける a, b, u, v, w の像をそれぞれ A, B, U, V, W とすると，V = AU A−1
から V A = AU となり，以下の A に関する連立方程式を得る．

V A = AU
′

(4.1)

′

(l + 1 ≤ i ≤ n − 1)Aρk (σi ) = ρk (σi )A
′

(4.2)

′

上記の連立方程式の正則な解を A とする．この A を用いて，次のよう′に ρk (baua−1 b−1 ) を計算する．
′

′

′

′

′

′

A W A −1 = A BU B −1 A −1 = BA U A −1 B −1′′

= BV B −1 = ρk (baua−1 b−1 ) ∈ ρk (Bn )
′

′

(4.3)

′

ここで，A ∈ ρk (Bn ) とは限らないが，A は暗号における秘密鍵 a と同じ役割をはたしている．暗号に対する攻撃アルゴリズムは次のようにまとめられる．

Algorithm 1: DHCP を解くアルゴリズム
Input: u, v = aua−1 , w = bub−1 ∈ Bn (a ∈ LBn , b ∈ RBn )Output: baua−1 b−1 .
′

′

′

′

1. q = 1/2 と選び，ρk とする．ρk (u), ρk (v), ρk (w) を計算する．
′′

2. 連立方程式 V A = AU, Aρk (σi ) = ρk (σi )A (l + 1 ≤ i ≤ n − 1) を解く．
3. A が正則行列であれば，A−1 を計算する．そうでなければ，上のステッ
プに戻って別の解を求める．
′′

4. Aρk (w)A−1 = ρk (baua−1 b−1 ) を計算する．
5. Lawrence-Krammer 表現に対応するブレイドを返す (ρ−1k ) アルゴリズ−1−1
ムを用いて baua b を出力する．

上記のアルゴリズムにおける連立方程式を解く際，Cheon らはさまざまな高速化を行っているが，本論文においては Mathematica の Solve 命令を使用したのみで，特別な高速化は行っていない．また，5 における ρ−1kを求めるアルゴリズムについては，次の節で述べる．

22

4.3

ρ−1
k を計算するアルゴリズム±1 ±1cheon らは [12] に基づいて逆写像 ρ−1
k : GLn(n−1)/2 (Z[t , q ]) → Bn
を求めるアルゴリズムを提案した．しかし，幾つかの誤りとあいまいな部分があっため，本論文においては Lukkarila の修正したアルゴリズム [13]について扱う．まずアルゴリズムについて述べる．

Algorithm 2: ρ−1
k を計算するアルゴリズム．
Input: Krammer 行列 ρk (W ) ∈ GLn(n−1)/2 (Z[t±1 , q ±1 ])．
Output: W の left canonical from．
1. dt ← 行列ρk (W ) における t の最小次数．
2. ρk (W ) ← ρk (∆n )−dt ρk (W )．
3. l ← 行列ρk (W ) における t の最大次数．
4. for k = 1 to l:
4.1. v ← ρk (W ) · (1)1×n(n−1)/2 ．
4.2. A ← {(i, j)| (v, xi,j ) ∈ tR[t])}．
4.3. Ak ← GB(A)．
4.4. ρk (W ) ← ρk (Ak )−1 ρk (W )．
5. return ∆ndt A1 · · · Al ．
上記のアルゴリズムにおける (v, xi,j ) は v と基底 xi,j の内積 をとることを意味しており，4.2 では定数項を持たない t の多項式になっている行のみを集めることを意味している．また，
4.3 の GB（Greatest Braid）は[12] から引用しており，以下の通りである．

sij ∈ Σn (1 ≤ i < j ≤ n) を i と j のみを交換し，残りは移動させない置換とする．例えば，
(
)
1234
s14 =
4231
¯
である．また，Ref で sij の集合 Ref = {sij ¯ 1 ≤ i < j ≤ n} を表す．
Ref
の部分集合
¯
{
}
HP = A ⊂ Ref ¯ sij , sjk ∈ A ⇒ sik ∈ A 1 ≤ i < j < k ≤ n
(4.4)

23
に対して，

GB = rL−1 Pro: HP → f ⊂ Bn+(4.5)

を次のように定義する．

}{ ¯
L:Σn → HP, L(x) = sij ¯ 1 ≤ i < j ≤ n, x−1 i > x−1 j , (x ∈ Σn )(4.6)
Pro : HP → HP

(4.7)

ただし，A ∈ HP に対して，B = Pro(A) は B ⊂ A かつ B ∈ L(Σn ) となる最大の集合である．

r: Σn → Bn+ , また f = r(Σn )

(4.8)

例えば，

r(s14 ) = σ1 σ2 σ3 σ2 σ1である．
上記より，L(x) ⊂ Ref ⊂ Σn の関係が成り立ち，GB は HP から Bn+ への写像である．

ρ−1k の計算例W = σ2 σ3 ∈ B4 とし，ρ−1k (W ) を計算する．

1−q 1−q
1
0
0
0


0
0
0
0
0
 q



 0

q
0
0
0
0


ρk (W ) = 0−q 2 t + q 3 t
0
q2t
0
 0



3
4
2
3
2
0
−q t + q t
0−q t + q t
q t
 0

0
0
−q 3 t + 2q 4 t − q 5 t q 2 −q 2 t + 2q 3 t − q 4 t q 2 t − q 3 t
1. dt ← 上記の行列の t の最小次数 0．
2. ρk (W ) ← ρk (∆4 )0 ρk (W ) = ρk (W )．
3. l ← 上記の行列の t の最大次数 1．

24
4. for ループ:
4.1. v ← ρk (W ) · (1)1×6

3 − 2q


q






q


=

3
q
t




q4t


2
4
5
q +q t−q t4.2. (v, xi,j )
3 − 2q






q




q
=

q3t






q4t




q 2 + q 4 t − q 5 t(i, j) = (1, 2)(i, j) = (1, 3)(i, j) = (1, 4)(i, j) = (2, 3)(i, j) = (2, 4)(i, j) = (3, 4)

A ← {(i, j)| (v, xi,j ) ∈ tR[t])} = {(2, 3), (2, 4)}．
4.3. A = {s23 , s24 } ∈ HP
(
)
1234
x=
∈ Σn
1342
とすると，L(x) = {s23 , s24 } j A∴ x = L−1 Pro(A)A1 ←− GB = r(x) = σ2 σ3 ．
4.4. ρk (W ) ← ρk (A1 )−1 ρk (W )
1 0 0 0 0
 0 1 0 0 0

 0 0 1 0 0= 0 0 0 1 0
 0 0 0 0 1
0 0 0 0 0


0

0 

0 

0 


0 
1

25
5. return ∆04 A1 = σ2 σ3 ．
上記より，ρ−1
上記のアルゴリズムは q = 1/2 とし
k (W ) = σ2 σ3 を得る．ても同様に動作する．

4.4

暗号への攻撃

この章では上記のアルゴリズムを用いて，暗号への攻撃例を示す．例えば，u = σ3 σ2 σ1 ，v = aua−1 = σ1 σ3 σ2 σ1 σ1−1 ，w = bub−1 = σ3 σ3 σ2 σ1 σ3−1を知っているとする．
′′′

1. ρk (u), ρk (v), ρk (w) を計算する．
′′

2. 連立方程式 V A = AU, Aρk (σ3 ) = ρk (σ3 )A を解く．ここで，
a11 a12 a13 a14 a15 a16
 a21 a22 a23 a24 a25 a26  a31 a32 a33 a34 a35 a36 


A=

a
a
a
a
a
a
 41 42 43 44 45 46 
 a51 a52 a53 a54 a55 a56 
a61 a62 a63 a64 a65 a66とする．

3. 上の連立方程式を解くと，
ttt
4 a35 − 4 a35 − 4 a35

0
0
 0

 0
0
0
A=
1
 0
a
0

2 35

1
0
 0
2 a35
0
0
0

0
a35
0
1
a
2 35
0
0


0
0

0
0 

a35
0 

0
0 


1
a
0

2 35
0
a35

を得る．この A は正則行列であるので，A−1 を計算する．

26
′

′

4. Aρk (w)A−1 = ρk (baua−1 b−1 )

3t
0
− 4t
4

1
3t
1
9t
+
−
 0
8
32
8 − 32
1
t3t
 0− 81 − 32
8 + 32
=
5
3t
5
9t
 3
 16
16 + 64 − 16 − 64
 1
5
t
5
3t
 16
16 + 64 − 16 − 64
2
2
3t
5t
t
− 128
− 64
128

0
1
3t
4 − 161t
4 − 1613t
8 − 321t
8 − 32
3t2
64

0
1
9t
− 4 + 163t
− 41 + 16
9t− 81 + 32
3t− 81 + 32
2
− 5t
64

0
2
t
2
t
1
t
1
t












0

を得る．
′

5. Algorithm 2 を用いて，4 で計算した ρk (baua−1 b−1 ) から baua−1 b−1を求める．
baua−1 b−1 = ∆−1
4 A1 A2 A3= ∆−1
4 (σ3 σ1 )(σ1 σ2 σ3 σ2 σ1 )(σ3 σ2 )．

上記より，暗号への攻撃が成功した．

27

第 5 章 プログラムの仕様
Lukkarila の Mathematica パッケージ [14] などをもとにブレイドの積，
left canonical form などの公開鍵暗号を構築するのに必要なアルゴリズム
を Python で実装し [4],[5],[6]，4 章で述べた Lawrence-Krammer 表現を用いた公開鍵暗号に対する攻撃を Mathematica で実装した [7],[13]．

5.1

Python パッケージの使用方法

Python がインストールされているとし，作成したプログラムの使用方
法について述べる．まず，Python を起動した後，>>> import Braid>>> Braid.Artin_Braid(4).Delta()[1, 2, 3, 1, 2, 1]と入力することで ∆4 を返すプログラムを起動することができる．Braid.Ar
tin_Braid(n). 関数において，任意の紐の本数を n に入力し，続いて関数を入力することでプログラムを起動することができる．関数については以
下を参照．

5.2

Python パッケージ

Python で実装したプログラムの仕様について述べる．プログラムにおいて引数が w のときは word を，p のときは置換を入力することを意味している．例えば n = 4 のとき，W = σ1 σ2 σ3−1 を引数 w では配列を用いて w = [1, 2, −3] と入力し，置換では同じく配列を用いて p = [2, 3, 4, 1] と入力する．
Word Operations• Braid_As_WordQ[w]: Braid_As_WordQ は w が word を表しているときに True を，そうでなければ False を返す．

28
• Positive_Braid_As_WordQ[w]: Positive_Braid_As_WordQ[w] は wが正ブレイド word を表しているときに True を，そうでなければFalse を返す．
• Freely_Reduce_Word[w]: Freely_Reduce_Word[w] は w = [a, · · · , i,
− i, · · · , b] のようなとなりあう要素が打ち消しあうことができる場
合 w = [a · · · b] を返す．打ち消しあう要素がない場合はそのまま w を返す．
• Delta[ ]： Delta[n] は word としての ∆n を返す．
• Word_To_Permutation[w]: Word_To_Permutation は w に対応す
る置換を返す．
• Product_Word[w1,w2]: Product_Word は w1∗w2 を返す．
• Inverse_Word[w]: Inverse_Word は w−1 を返す．
• Reverse_Word[w]: Reverse_Word は w の reverse である wr を返す．
• Negation_Word[w]: Negation_Word は wr−1 を返す．
• Half_Twist_Word[w]: Half_Twist_Word は τ (w) = ∆−1n w∆n を返す．
• Word_Left_Meet[p1,p2]: Word_Left_Meet は入力した置換 p1,p2 の
p1 ∧L p2 を word として返す．
• Word_Right_Meet[p1,p2]: Word_Right_Meet は入力した置換 p1,p2の p1 ∧R p2 を word として返す．
• Word_Left_Join[p1,p2]: Word_Left_Join は入力した置換 p1,p2 の
p1 ∨L p2 を word として返す．
• Word_Right_Join[p1,p2]: Word_Right_Join は入力した置換 p1,p2の p1 ∨R p2 を word として返す．
• Word_Random_Braid[ ]: Word_Random_Braid はランダムな w ∈Bn を返す．
• Word_To_Left_Canonical_Form[w]: Word_To_Left_Canonical_Fo
rm は w の left canonical form を返す．戻り値は [inﬁmum,W(wordWのリスト)] のリストとする．ここで，[inﬁmum,W] = ∆inﬁmum
ninﬁmumw1∗w2∗ · · · を表している．
= ∆n

29
• Word_To_Right_Canonical_Form[w]: Word_To_Right_Canonical_
Form は w の right canonical form を返す．戻り値は [W(word のリスト),inﬁmum] のリストとする．ここで，[W,inﬁmum]=W∆inﬁmum=
ninﬁmumw1∗w2∗ · · · ∆nを表している．
• Word_Braid_Comparison[w1,w2]: Word_Braid_Comparison は w1,
w2 が同じブレイドを表している場合は True，そうでなければ False
を返す．
• Word_Commute_Left[w,s,d]: Word_Commute_Left は w の s 番目の要素を群の同値関係を使って d 番目に移動させる．d 番目まで移動できない場合は，移動できるところまで要素を移動させる．最終的に [s 番目の要素の現在位置, 要素を移動させた後の w] のリストを返す．(1≤ s,d ≤ n かつ s ≥ d)
• Word_Commute_Right[w,s,d]: Word_Commute_Right は w の s 番
目の要素を群の同値関係を使って d 番目に移動させる．d 番目まで移動できない場合は，移動できるところまで要素を移動させる．最終的に [s 番目の要素の現在位置, 要素を移動させた後の w] のリストを返す．(1≤ s,d ≤ n かつ s ≤ d)
Permutation Operations• Identity_Permutation[ ]: Identity_Permutation は単位元 e に対応する置換を返す．
• Omega[ ]: Omega は ∆n に対応する置換Ωn を返す．
• Braid_As_PermutationQ[p]: Braid_As_PermutationQ は p が置換を表しているときに True を，そうでなければ False を返す．
• Half_Twist_Permutation[p]: Half_Twist_Permutation は p を Ωnで共役したものを返す．
• Transposition[i]: Transposition は互換 (i, i + 1) ∈ Σn を返す．
• Permutation_Product[p1,p2]: Permutation_Product は p1,p2 の置換の積を返す．
• Permutation_To_Word[p]: Permutation_To_Word は p に対応する
word を返す．
• Permutation_Inverse[p]: Permutation_Inverse は p の逆置換を返す．

30• Starting_Set_Permutation[p]: Starting_Set_Permutation は p の St
arting 集合を返す．ここで，p は正ブレイドを仮定している．
• Finishing_Set_Permutation[p]: Finishing_Set_Permutation は p のFinishing 集合を返す．ここで，p は正ブレイドを仮定している．
• Left_Weighted[P]: P=[p1,p2, · · · ] は置換 p1,p2 · · · のリストとする．Left_Weighted は p1,p2 · · · が left weighted である場合 True，
そうでなければ False を返す．
• Right_Weighted[P]: P=[p1,p2, · · · ] は置換 p1,p2 · · · のリストとする．Right_Weighted は p1,p2 · · · が Right weighted である場合
True，そうでなければ False を返す．
• Permutation_Length[p]: Permutation_Length は p に対応する生成元 σi の最少数を返す．
• Permutation_Left_Meet[p1,p2]: Permutation_Left_Meet は入力した置換 p1,p2 の p1 ∧L p2 を置換として返す．
• Permutation_Right_Meet[p1,p2]: Permutation_Right_Meet は入力した置換 p1,p2 の p1 ∧R p2 を置換として返す．
• Permutation_Left_Join[p1,p2]: Permutation_Left_Join は入力した
置換 p1,p2 の p1 ∨L p2 を置換として返す．
• Permutation_Right_Join[p1,p2]: Permutation_Right_Join は入力
した置換 p1,p2 の p1 ∨R p2 を置換として返す．
• Maximal_Head[p1,p2]: Maximal_Head は p1,p2 の maximal Headp1((Ωn p1−1 ) ∧L p2) を返す．
• Permutation_To_Left_Canonical_Form[inf,P]: Permutation_To_Le
inf
ft_Canonical_Form は ∆infn P= ∆n p1∗p2∗ · · · の left canonical form
を返す．戻り値は [inﬁmum,P] のリストとする．ここで，P=[p1,p2,· · · ]は置換のリストを表している．
• Permutation_To_Right_Canonical_Form[inf,P]: Permutation_To_
inf
Right_Canonical_Form は P∆inf
n = p1∗p2∗ · · · ∆n の Right canonical form を返す．戻り値は [P,inﬁmum] のリストとする．ここで，
P=[p1,p2,· · · ] は置換のリストを表している．
• Permutation_Left_Canonical_Form_Product[LCF1,LCF2]: Permutation_Left_Canonical_Form_Product は LCF1,LCF2 の積を返す．

31
ただし，LCF1,LCF2 には left canonical form(LCF=[inf,p1,p2,· · · ])を入力する．

• Permutation_Left_Canonical_Form_Inverse[LCF]: Permutation_
Left_Canonical_Form_Inverse は LCF−1 を返す．ただし，LCF には left canonical form(LCF=[inf,p1,p2,· · · ]) を入力する．
• Permutation_Braid_Comparison[P1,P2]: Permutation_Braid_Com
parison は入力された置換のリスト P1,P2 が同じブレイドを表している場合は True，そうでなければ False を返す．
• Permutation_Random_Braid[ ]: Permutation_Random_Braid はランダムな置換 p ∈ Σn を返す．
Braid Operations• Inﬁmum_Left_Canonical_Form[w]: Inﬁmum_Left_Canonical_For
m は w の left canonical form における inﬁmum を返す．
• Canonical_Length_Left_Canonical_Form[w]: Canonical_Length_
Left_Canonical_Form は w の left canonical form における canonicallength を返す．
• Supremum_Left_Canonical_Form[w]: Supremum_Left_Canonical_Form は w の left canonical form における supremum を返す．
• Inﬁmum_Right_Canonical_Form[w]: Inﬁmum_Right_Canonical_
Form は w の right canonical form における inﬁmum を返す．
• Canonical_Length_Right_Canonical_Form[w]: Canonical_Length_Right_Canonical_Form は w の right canonical form における canonical length を返す．
• Supremum_Right_Canonical_Form[w]: Supremum_Right_Canoni
cal_Form は w の right canonical form における supremum を返す．
• Cycling[W_LCF]: Cycling は W_LCF= ∆un x1 x2 · · · xk が left canonical form のとき，cycling c(W_LCF) = ∆un x2 · · · xk τ u (x1 ) を返す．
• Decycling[W_LCF]: Decycling は W_LCF= ∆un x1 x2 · · · xk が left
canonical form のとき，decycling d(W_LCF) = ∆un τ u (xk )x1 · · · xk−1
を返す．

32

5.3

Mathematica パッケージ

今回，実装した暗号系に対する攻撃のプログラムは Lukkarila の Mathematica パッケージ [14] の関数を利用して作成した．プログラムの詳細については以下を参照．

• LKRAttack[u,v,w,index,n]: LKRAttack は a ∈ LBn , b ∈ RBn , u ∈Bn のとき，u, v = aua−1 , w = bub−1 から baua−1 b−1 を計算し，′′戻り値とする．また，index は (4.2) の Aρk (σi ) = ρk (σi )A (l + 1 ≤i ≤ n − 1) の i に相当する．

33

第 6 章 考察，及び結論
本研究を通して，ブレイド群の定義や共役問題を用いた公開鍵暗号について整理し，まとめることができた．また，Python という無料かつ誰にでも簡単に習得できる言語でそれらを実装したことは価値が高い．一方，攻撃に関しては既存のアルゴリズムをまとめ，Mathematica ではあるが，実装することができた．
これらを通して得た一考察として，今回の公開鍵暗号における暗号化，及び復合化にはブレイド群からメッセージ空間へのハッシュ関数が使われているが，このハッシュ関数をブレイド群の忠実な表現である LawrenceKrammer 表現からメッセージ空間への関数に変更することにより，暗号プロトコルを高速化できるのではないかと思われる．
今後の課題としては，まず攻撃のプログラムを無料で使用できる言語で作成するということが挙げられる．その他としては，非常に難しい研究ではあるが，上記の暗号プロトコルにそのまま適用でき，かつ忠実な線形表
現を持たない新たな群を見つけることなどが挙げられる．
しかし，今回の暗号に対する攻撃は強力ではあるが，非常に大きな行列を扱うため，計算量や実装に関して幾分問題があり，まだ研究の余地は残っている．

謝辞
下野孝一 教授，竹縄知之 准教授には修士論文を作成するにあたり，多くの有意義な助言を頂きました．本論文を作成できたのも両先生の熱心な御指導があったからであると考えております．最後になりましたが，両先生に厚く御礼を申し上げます．

34

Appendix

Python Program# -*- coding: cp932 -*"""A python-package for braid groups.
start date:2007 7/5 (Thursday)

last update:2008 2/20 (Wednesday)

author:"""Arihiro_Maeda############################################################ This is a class for braid_groups. (Artin_Generator)############################################################
import random
import sys
class Artin_Braid:
def __init__(self,n):"""n is the braid index. (n > 0)
you must input natural number.
"""
if n <= 0:35
print "Braid_Index_Error"
while n <= 0:n = input("input: n = ")self.n = n"""
Word Operations"""
def Braid_As_WordQ(self,w):"""
You must input "Word" into w.
"""
for i in w:
if abs(i) >= self.n or i == 0:
return False
return Truedef Positive_Braid_As_WordQ(self,w):"""
You must input "Word" into w.
"""
for i in w:
if i <= 0 or i >= self.n:
return False
return True
def Freely_Reduce_Word(self,w):"""
You must input "Word" into w.
"""
if len(w) == 0:
return w
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)i = 0while (i >= 0 and i < len(w)-1):

36
if w[i] == -w[i+1]:
del w[i]del w[i]i = i-1i = i+1
return w
def Delta(self):a=[]n = self.n
i = 1
while n >= 1:
if i < n:a.append(i)i = i+1else:
i = 1
n = n-1
return adef Word_To_Permutation(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)a = self.Identity_Permutation()
i = 0
while i < len(w):j = w[i]if j < 0:
j = -jTemp(a,j-1,j)i = i+1
return a

37
def Product_Word(self,w1,w2):"""
You must input "Word" into w1 and w2.
"""
if (self.Braid_As_WordQ(w1) == False) or \(self.Braid_As_WordQ(w2) == False):
print "Word_Error"
sys.exit(0)#W = []#for i in w1:#
W.append(["σ",i])#for i in w2:
w1.append(i)#W.append(["σ",i])# print W
return w1
def Inverse_Word(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)i = len(w)-1#r = []
p = []
while i >= 0:
j = -w[i]p.append(j)#r.append(["σ",j])i = i-1#print r
return p
def Reverse_Word(self,w):"""

38
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)i = 0n = len(w)W = []
while i < n:W.append(w.pop())
i = i + 1
return W
def Negation_Word(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)i = 0while i < len(w):w[i] = -w[i]i = i+1
return w
def Half_Twist_Word(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)p = []
for i in w:
if i > 0:p.append(self.n-i)
else:

39
p.append(-self.n-i)
return p
def Word_Left_Meet(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
p3 = self.Permutation_Left_Meet(p1,p2)
w = self.Permutation_To_Word(p3)return w
def Word_Right_Meet(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
p3 = self.Permutation_Right_Meet(p1,p2)
w = self.Permutation_To_Word(p3)return w
def Word_Left_Join(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
p3 = self.Permutation_Left_Join(p1,p2)
w = self.Permutation_To_Word(p3)return w
def Word_Right_Join(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
p3 = self.Permutation_Right_Join(p1,p2)
w = self.Permutation_To_Word(p3)return w
def Word_Random_Braid(self):
p = self.Permutation_Random_Braid()w = self.Permutation_To_Word(p)

40
i = 0
while i < len(w):if (random.randint(1,2)%2) == 1:
w[i] = -w[i]i = i+1
return w
def Word_To_Left_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)pr = Word_To_Permutation_Representation(w,self.n)
W_LCF = Permutation_Representation_\
To_Left_Canonical_Form(pr,self.n)
i = 1
while i < len(W_LCF):
W_LCF[i] = self.Permutation_To_Word(W_LCF[i])i = i+1
return W_LCF
def Word_To_Right_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)pr = Word_To_Permutation_\
Representation(w,self.n)
lcf = Permutation_Representation_To_Left\_Canonical_Form(pr,self.n)
rcf = []
inf = lcf[0]del lcf[0]p = lcf41
if (inf % 2) == 1:i = 0while i < len(p):p[i] = self.Half_Twist_Permutation(p[i])i = i+1
p.reverse()
rev = []
i = 0
while i < len(p):rev.append(self.Permutation_Inverse(p[i]))i = i+1
rev.insert(0,0)
rev = Permutation_Representation_To_Left_\
Canonical_Form(rev,self.n)
del rev[0]rev.reverse()
i = 0
while i < len(rev):
rev[i] = self.Permutation_Inverse(rev[i])i = i+1
p = rev
p.append(inf)
W_LCF = pi = 0while i < len(W_LCF)-1:
W_LCF[i] = self.Permutation_To_Word(W_LCF[i])i = i+1
return W_LCF
def Word_Braid_Comparison(self,w1,w2):"""
You must input "Word" into w1 and w2.
"""
if (self.Braid_As_WordQ(w1) == False) or \(self.Braid_As_WordQ(w2) == False):
print "Word_Error"
sys.exit(0)pr = Word_To_Permutation_Representation(w1,self.n)

42
w1 = Permutation_Representation_To_Left_\
Canonical_Form(pr,self.n)
pr = Word_To_Permutation_Representation(w2,self.n)
w2 = Permutation_Representation_To_Left_\
Canonical_Form(pr,self.n)
if w1 == w2:
return True
else:
return False
def Word_Commute_Left(self,w,s,d):"""
You must input "Word" into w and"natural number" into s,d (s >= d).
"""if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)if (s < d) or (s > len(w)) or (d <= 0):
return w
if self.Positive_Braid_As_WordQ(w) == False:
return w
s = s-1
d = d-1
while s > d:k = sif w[s] == w[s-1]:
i = s+1
return [[i]]+w
if abs(w[s]-w[s-1]) > 1:
Temp(w,s-1,s)s = s-1else:
j = s+1
while j < len(w) and j-2 >= 0:
if w[j-2] == w[j]:if j != s+1:
w[j-2] = w[j-1]43w[j-1] = w[j]w[j] = w[j-2]s = s-1
breakelse:
w[s-1] = w[s]w[s] = w[s+1]w[s+1] = w[s-1]s = s-1
break
j = j-1
if j-(s+1) == -2:i = s+1
return [[i]]+w
j = j-1
if s == d:i = s+1
return [[i]]+w
if j-2 >= 0 and w[j-2] == w[j]:w[j-2] = w[j-1]w[j-1] = w[j]w[j] = w[j-2]s = s-1
if k == s:
breaki = s+1
return [[i]]+w
def Word_Commute_Right(self,w,s,d):"""
You must input "Word" into w and"natural number" into s,d (s <= d).
"""if self.Braid_As_WordQ(w) == False:
print "Word_Error"
sys.exit(0)if (s <= 0) or (d > len(w)) or (s > d):return w

44
if self.Positive_Braid_As_WordQ(w) == False:
return w
s = s-1
d = d-1
while s < d:k = s
if w[s] == w[s+1]:
i = s+1
return [[i]]+w
if abs(w[s]-w[s+1]) > 1:
Temp(w,s,s+1)
s = s+1else:
j = s-1
while j >= 0 and j+2 < len(w):if (w[j] == w[j+2]):
if j != s-1:
w[j] = w[j+1]w[j+1] = w[j+2]w[j+2] = w[j]s = s+1
breakelse:
w[s-1] = w[s]w[s] = w[s+1]w[s+1] = w[s-1]s = s+1
break
j = j+1
if j-(s-1) == 2:i = s+1
return [[i]]+w
j = j+1
if s == d:i = s+1
return [[i]]+w
if j+2 < len(w) and w[j] == w[j+2]:
w[j] = w[j+1]45
w[j+1] = w[j+2]w[j+2] = w[j]s = s+1
if k == s:
breaki = s+1
return [[i]]+w"""
Permutation Operations"""
def Identity_Permutation(self):
p = range(1,self.n+1)
return p
def Omega(self):
p = range(1,self.n+1)
p.reverse()
return p
def Braid_As_PermutationQ(self,p):"""
You must input "Permutation" into p.
"""
if len(p) != self.n:
return False
I = self.Identity_Permutation()
for i in p:
if (self.n-i) < 0 or (self.n-i) >= self.n:
return False
I[i-1] = 0
for i in I:
if i > 0:
return False
return Truedef Half_Twist_Permutation(self,p):

46"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)i = 0
P = []
while i < self.n:
P.append(0)i = i+1i = 0
while i < self.n:
P[i] = self.n - p[self.n-(i+1)] + 1
i = i+1
return P
def Transposition(self,i):"""
You must input "natural number" into i.
"""
if i <= 0 or i >= self.n:
print "Index_Error"
sys.exit(0)p = self.Identity_Permutation()
Temp(p,i-1,i)return p
def Permutation_Product(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
if (self.Braid_As_PermutationQ(p1) == False) or \(self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p3 = range(0,self.n)
i = 0

47
while i < self.n:t = p2[i]-1t = p1[t]p3[i] = ti = i + 1
return p3
def Permutation_To_Word(self,p):"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)w = []
q = self.Identity_Permutation()while p != q:i = 0
while i < len(p)-1:
if p[i] > p[i+1]:
w.append(i+1)
Temp(p,i,i+1)
continuei = i+1
w = self.Reverse_Word(w)return w
def Permutation_Inverse(self,p):"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)p.insert(0,0)
q = range(0,self.n+1)
i = 1
while i < self.n + 1:

48
q[p[i]] = i
i = i + 1
del p[0]del q[0]return q
def Starting_Set_Permutation(self,p):"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)S = self.Finishing_Set_Permutation\(self.Permutation_Inverse(p))
return S
def Finishing_Set_Permutation(self,p):"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)all_word = range(1,self.n)
S = []
for i in all_word:
if Is_LeftElement_Big(p,i-1) == True:
S.append(i)return S
def Left_Weighted(self,P):"""
You must input "Permutation List" into P.
"""
for i in P:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"

49
sys.exit(0)i = 0while i < len(P)-1:
S1 = self.Starting_Set_Permutation(P[i+1])S2 = self.Finishing_Set_Permutation(P[i])for j in S2:
k = 0
while (len(S1) > 0) and (k < len(S1)):
if S1[k] == j:del S1[k]k = k+1
if len(S1) != 0:
return False
i = i+1
return Truedef Right_Weighted(self,P):"""
You must input "Permutation List" into P.
"""
for i in P:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)i = 0while i < len(P)-1:
S1 = self.Starting_Set_Permutation(P[i+1])S2 = self.Finishing_Set_Permutation(P[i])for j in S1:
k = 0
while (len(S2) > 0) and (k < len(S2)):
if S2[k] == j:del S2[k]k = k+1
if len(S2) != 0:
return False
i = i+1
return True50

def Permutation_Length(self,p):"""
You must input "Permutation" into p.
"""
if self.Braid_As_PermutationQ(p) == False:
print "Permutation_Error"
sys.exit(0)n = len(self.Permutation_To_Word(p))
return n# The following algorithm is taken straight from# "Efficient implementation of braid groups"# (J.C.Cha et al) and "Braid group Cryptography# untangled" (A.Bolstad).
"""def Convert_Descending_To_Permutation(self,x):
a = range(0,(len(x)+1))
z = [0]*(self.n+1)
i = 1
i = 1
x.insert(0,0)
while i <= len(x)-1:
if z[x[i]] == 0:a[i] = ielse:
a[i] = a[z[x[i]]]a[z[x[i]]] = iz[x[i]] = ii += 1del a[0]del x[0]return a"""def Permutation_Right_Meet(self,p1,p2):"""

51
You must input "Permutation" into p1 and p2.
"""
if (self.Braid_As_PermutationQ(p1) == False) \or (self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p1.insert(0,0)
p2.insert(0,0)
self.c = range(0,self.n+1)
Meet_Sub(p1,p2,self.c,1,self.n,self.n)
i = 1
r = (self.n+1)*[0]while i < self.n+1:
r[self.c[i]] = i
i = i+1
del p1[0]del p2[0]del r[0]return r
def Permutation_Left_Meet(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
if (self.Braid_As_PermutationQ(p1) == False) or\(self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p1.insert(0,0)
p2.insert(0,0)
u = range(0,self.n+1)
v = range(0,self.n+1)
i = 1
while i < len(u):u[p1[i]] = iv[p2[i]] = i
i = i + 1
self.c = range(0,self.n+1)

52
Meet_Sub(u,v,self.c,1,self.n,self.n)
del p1[0]del p2[0]del self.c[0]return self.c
def Permutation_Left_Join(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
if (self.Braid_As_PermutationQ(p1) == False) or\(self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p = []
p.append(self.Permutation_Inverse(p1))
p.append(self.Permutation_Inverse(p2))
join = self.Permutation_Right_Join(p[0],p[1])return self.Permutation_Inverse(join)
def Permutation_Right_Join(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""
if (self.Braid_As_PermutationQ(p1) == False) or\(self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p = []
p.append(Right_Complement(p1,self.n))p.append(Right_Complement(p2,self.n))join = self.Permutation_Right_Meet(p[0],p[1])return Right_Complement(join,self.n)
def Maximal_Head(self,p1,p2):"""
You must input "Permutation" into p1 and p2.
"""

53
if (self.Braid_As_PermutationQ(p1) == False) or\(self.Braid_As_PermutationQ(p2) == False):
print "Permutation_Error"
sys.exit(0)p1_inv = self.Permutation_Inverse(p1)d = self.Omega()c = self.Permutation_Product(d,p1_inv)
c = self.Permutation_Left_Meet(c,p2)
M_H = self.Permutation_Product(p1,c)return M_H
def Permutation_To_Left_Canonical_Form(self,inf,P):"""
You must input "Infimum" into inf and"Permutation List" into P.
"""
if len(P) <= 0:
return [inf]+P
for i in P:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)i = 0w = []
while i < len(P):a = self.Permutation_To_Word(P[i])for j in a:w.append(j)i = i+1
pr = Word_To_Permutation_Representation(w,self.n)
P_LCF = Permutation_Representation_To_Left_\
Canonical_Form(pr,self.n)
P_LCF[0] = P_LCF[0]+inf
return P_LCF
def Permutation_To_Right_Canonical_Form(self,inf,P):"""
You must input "Infimum" into inf and54"Permutation List" into P.
"""
if len(P) <= 0:
return [inf]+P
for i in P:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)i = 0w = []
while i < len(P):a = self.Permutation_To_Word(P[i])for j in a:w.append(j)i = i+1
P_RCF = self.Word_To_Right_Canonical_Form(w)i = 0
while i < len(P_RCF)-1:
P_RCF[i] = self.Word_To_Permutation(P_RCF[i])i = i+1
P_RCF[-1] = P_RCF[-1]+inf
return P_RCF
def Permutation_Left_Canonical_Form_Product(self,LCF1,LCF2):"""
You must input Left Canonical Form
into LCF1 and LCF2.
(LCF = [inf,"Permutation List"])"""if (len(LCF1) or len(LCF2)) == 1:
sys.exit(0)p = LCF1[0]q = LCF2[0]inf = p+q
del LCF1[0]del LCF2[0]for i in LCF1:
if self.Braid_As_PermutationQ(i) == False:55
print "Permutation_Error"
sys.exit(0)for i in LCF2:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)LCF = []
for i in LCF1:
if q % 2 == 1:
LCF.append(self.Half_Twist_Permutation(i))
else:
LCF.append(i)LCF = LCF + LCF2
LCF = self.Permutation_To_Left_Canonical_Form(inf,LCF)
return LCF
def Permutation_Left_Canonical_Form_Inverse(self,LCF):"""
You must input Left Canonical Form
into LCF.
(LCF = [inf,"Permutation List"])"""q = LCF[0]l = len(LCF)-1
inf = -(q+l)
del LCF[0]for i in LCF:
if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)B = []
for i in LCF:
B.append(self.Permutation_Product(\self.Permutation_Inverse(i),self.Omega()))
B.reverse()
LCF = []
for i in B:
if -(q+l) % 2 == 1:
LCF.append(self.Half_Twist_Permutation(i))

56
else:
LCF.append(i)l = l-1
LCF = [inf] + LCF
return LCF
def Permutation_Braid_Comparison(self,P1,P2):"""
You must input [Infimum,["Permutation List"]]into P1 and P2.
"""
if (len(P1) < 2) or (len(P2) < 2):sys.exit(0)for i in P1[1]:if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)for i in P2[1]:if self.Braid_As_PermutationQ(i) == False:
print "Permutation_Error"
sys.exit(0)P1_inf = P1[0]P2_inf = P2[0]del P1[0]del P2[0]P1 = self.Permutation_To_Left_\
Canonical_Form(P1_inf,P1[0])P2 = self.Permutation_To_Left_\
Canonical_Form(P2_inf,P2[0])if P1 == P2:
return True
else:
return False
def Permutation_Random_Braid(self):
i = 0
I = self.Identity_Permutation()while i < self.n:

57
j = random.randint(0,self.n-1)
Temp(I,i,j)
i = i+1
return I"""
Braid Operations"""
def Infimum_Left_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
LCF = self.Word_To_Left_Canonical_Form(w)return LCF[0]def Canonical_Length_Left_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
LCF = self.Word_To_Left_Canonical_Form(w)return len(LCF)-1
def Supremum_Left_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
LCF = self.Word_To_Left_Canonical_Form(w)return (LCF[0]+len(LCF)-1)
def Infimum_Right_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
RCF = self.Word_To_Right_Canonical_Form(w)return RCF[-1]
def Canonical_Length_Right_Canonical_Form(self,w):

58"""
You must input "Word" into w.
"""
RCF = self.Word_To_Right_Canonical_Form(w)return len(RCF)-1
def Supremum_Right_Canonical_Form(self,w):"""
You must input "Word" into w.
"""
RCF = self.Word_To_Right_Canonical_Form(w)return (RCF[-1]+len(RCF)-1)
def Cycling(self,W_LCF):"""
You must input "Left Canonical Form(Word)"
into W_LCF.
"""
if len(W_LCF) <= 1:
return W_LCF
inf = W_LCF[0]x1 = W_LCF[1]del W_LCF[1]cyc = W_LCF
if inf % 2 == 1:
x1 = self.Half_Twist_Word(x1)cyc.append(x1)return cyc
def Decycling(self,W_LCF):"""
You must input "Left Canonical Form(Word)"
into W_LCF.
"""
if len(W_LCF) <= 1:
return W_LCF
inf = W_LCF[0]x1 = W_LCF[-1]59
del W_LCF[-1]cyc = W_LCF
if inf % 2 == 1:
x1 = self.Half_Twist_Word(x1)cyc.insert(1,x1)
return cyc# The end of this Artin_Braid class.

########################################################### Following functions is subfunction for main program ###########################################################
def Temp(a,i,j):
temp = a[i]a[i] = a[j]a[j] = temp
def Is_LeftElement_Big(p,i):if p[i] > p[i+1]:
return True
else:
return False
def Longest_Permutation_Braid_Word_From_Left(w,n):b = Artin_Braid(n)P = b.Identity_Permutation()
i = 0
while i < len(w):g = w[i]if Is_LeftElement_Big(P,g-1) == True:
W = []
j = 0
while j <= i-1:
W.append(w[j])60
j = j+1
return W
g = abs(g)Temp(P,g-1,g)i = i+1
return w
def Word_To_Permutation_Representation(w,n):b = Artin_Braid(n)seq = [0]W = []
X = []
i = len(w)-1
while i >= 0:
g = abs(w[i])if seq[0]%2 == 0:
g = g
else:
g = n-g
if w[i] < 0:
seq[0] = seq[0] - 1
pos = b.Omega()
Temp(pos,g-1,g)
W = b.Permutation_To_Word(pos)+W
else:
W.insert(0,g)
i = i-1
while W != []:X = []
for i in W:
X.append(i)pref = Longest_Permutation_Braid_\
Word_From_Left(X,n)
i = 0
while i < len(pref):del W[0]i = i+1
seq.append(b.Word_To_Permutation(pref))

61
del X
return seq
def Permutation_Representation_To_Left_Canonical_\Form(PR,n):b = Artin_Braid(n)if len(PR) == 1:
return PR
inf = PR[0]A = []
I = b.Identity_Permutation()D = b.Omega()i = 1
while i < len(PR):A.append(PR[i])i = i+1i = 0
while i < len(A):if A[i] == I:
del A[i]i = i+1i = 0
while i < len(A)-1:
ss = b.Starting_Set_Permutation(A[i+1])
if ss == []:del A[i+1]
continue
fs = b.Finishing_Set_Permutation(A[i])k = 0Complement(ss,fs)
if ss != []:j = ss[0]Temp(A[i],j-1,j)A[i+1] = \Multiply_From_LeftPriv(A[i+1],j-1,j,n)
if A[i+1] == I:
del A[i+1]
if i > 0:62
i = i-1else:
i = i + 1
while (len(A) > 0) and (A[0] == D):
inf = inf+1
del A[0]A.insert(0,inf)
return A
def Meet_Sub(a,b,c,s,t,n):u = (n+1)*[0]v = (n+1)*[0]w = (n+1)*[0]
if t <= s:returnm = (s+t)/2
Meet_Sub(a,b,c,s,m,n)
Meet_Sub(a,b,c,m+1,t,n)u[m] = a[c[m]]v[m] = b[c[m]]if s < m:
i = m-1
while i >= s:u[i] = min(a[c[i]],u[i+1])v[i] = min(b[c[i]],v[i+1])
i = i-1u[m+1] = a[c[m+1]]v[m+1] = b[c[m+1]]
if t > m+1:
i = m+2
while i <= t:u[i] = max(a[c[i]],u[i-1])v[i] = max(b[c[i]],v[i-1])
i = i+1
l = s
r = m+1i = swhile i <= t:63
if ((l > m) or ((r <= t) and \(u[l] > u[r]) and (v[l] > v[r]))):
w[i] = c[r]r = r+1
else:
w[i] = c[l]l = l+1i = i+1i = swhile i <= t:c[i] = w[i]i = i+1
def Complement(SS,FS):for i in FS:
k = 0
while (len(SS) > 0) and (k < len(SS)):
if SS[k] == i:del SS[k]k = k+1
if SS == []:break
def Multiply_From_LeftPriv(p,i,j,n):b = Artin_Braid(n)p = b.Permutation_Inverse(p)Temp(p,i,j)
p = b.Permutation_Inverse(p)return p
def Right_Complement(p,n):b = Artin_Braid(n)o = b.Omega()
return b.Permutation_Product(o,p)

64Mathematica Program
プログラム内で使われている関数，及び使用方法は Lukkarila の Mathematica パッケージを参照．

LKRAttack[u_, v_, w_, index_, n_] :=Module[{a, A, alist, ans, i, j, ki, KI, m, q, U, VV, W},
If[n/2 + index ≧ n || index ≦ 0, Return[False]];q = 1/2;
m = n(n - 1)/2;
U = Krammer[u, n, t, q];
VV = Krammer[v, n, t, q];
A = Normal[SparseArray[{m, m} -> 0]];alist = Normal[SparseArray[{m*m} -> 0]];For[i = 1; k = 1, i ≦ m, i += 1,
For[j = 1, j ≦ m, j += 1; k += 1, A[[i, j]] =StringExpression[a, ToString[i], ToString[j]];alist[[k]] = A[[i, j]]]];
i = n/2 + index;
ki = {i};KI = Krammer[ki, n, t, q];(*Solve VA = AU, AK’(σ i) = K’(σ i)A*)
ans = Solve[{A.U == VV.A, A.KI == KI.A}, alist];
A1 = A /. ans[[1]];W = Krammer[w, n, t, q];
A2 = Simplify[A1.W.Inverse[A1]];A2 = InvertKrammer[A2, t, q];
Return[A2];];

65

参考文献
[1] I. Anshel, M. Anshel, D. Goldfeld An algebraic method for publickey cryptography, Math. Res. Lett.6 287-291 (1999).
[2] S. Bigelow, The Burau representation is not faithful for n = 5,
Geometry and T opology, 3 397-404 (1999).
[3] J. S. Birman, K. H. Ko, S. J. Lee, A new approach to the word andconjugacy problems in the braid groups, Advances in Mathmatics,
139, 322-353, (1998).
[4] A. Bolstad, Braid Group Cryptography Untangled,
http://www.math.wisc.edu/˜boston/bolstad.doc, (2004).
[5] J. C. Cha, K. H. Ko, S. J. Lee, J. W. Han, J. H. Cheon, An efﬁcient implementation of braid groups, Advances in Cryptology:
Proceedings of ASIACRYPT 2001, Lecture Notes in Computer Science, Springer-Verlag, 2248 (2001) 144-156.
[6] J. C. Cha, CBraid: a C++ library for computation in braid groups,
http://knot.kaist.ac.kr/ jccha/cbraid/, (2001).
[7] J. H. Cheon, B. Jun, A polynomial time algorithm for the braid
Diﬃe-Hellman conjugacy problem, Advances in Cryptology: Proceedings of CRYPTO 2003, Lecture Notes in Computer Science,
Springer-Verlag, 2729 (2003) 212-225.
[8] W. Diﬃe, M. E. Hellman, New directions in Cryptography, IEEE
Transactions on Information Theory, 22 (1976), 644-654.
[9] H. Fuji, An implementation of the algorithm to construct the nomal
forms of band generator presentation for the braid group, 日本大学
文理学部応用数学科卒業研究報告書, (2003),
http://www.tani.cs.chs.nihon-u.ac.jp/g-2003/hanana/.
[10] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. S. Kang, C. S.
Park, New public-key cryptosystem using braid groups, Advances

66
in Cryptology: Proceedings of CRYPTO 2000, Lecture Notes in
Computer Science, Springer-Verlag, 1880 (2000) 166-183.
[11] K. H. Ko, S. J. Lee, T. Thomas, TOWARDS GENERATING SECURE KEYS FOR BRAID CRYPTOGRAPHY,
http://eprint.iacr.org/2007/149.pdf, (2007).
[12] D. Krammer, Braid groups are linear, Annals of Mathematics, 155(2002) 131-156.
[13] V. Lukkarila, A Mathematica-package for algebraic braid groups,
TUCS Technical Report, (2005),
http://www.tucs.ﬁ/publications/insight.php?id=tLukkarila05a.
[14] V. Lukkarila, AlgebraicBraids,
http://www.tucs.ﬁ/publications/attachments/TR689-Algebraic
Braids.m, (2005).
[15] D. R. Stinson 著, 櫻井 幸一監訳, 暗号理論の基礎, 共立出版, (1996)[16] Y. Tanaka, Experimental Performance Evaluations of Public-key
Cryptosystem Using Braid Groups, 日本大学文理学部情報システム
解析学科卒業研究報告書, (2005),
http://www.tani.cs.chs.nihon-u.ac.jp/g-2005/yuko/.