秘密共有法 西関 隆夫 東北大学 大学院情報科学研究科 1

自己紹介 1969 東北大学工学部通信工学科 「 PCM パルス波形， FFT 」 1971 同 電気及通信工学修士修了 「集中定数回路網合成に関する研究」 1974 同 博士修了 「回路網接続の位相幾何学的研究」 1974 同 工学部通信工学科 助手 グラフ理論，アルゴリズム 1976 同 助教授 線形時間アルゴリズム，グラフ描画， VLSI レイア ウト Carnegie-Mellon 大学数学科客員数学者 Duffin 先生 1988 東北大学工学部通信工学科 教授 1993 同 情報科学研究科 教授 アルゴリズム，情報セキュ リティ 2005 同 副研究科長，教育研究評議員 2008 同 研究科長 2

Carnegie-Mellon Univ. 数学科 Richard J. DuffinRaoul Bott Bott-Duffin の回路合成法 幾何学 Elmor L. Peterson Clarence Zener Geometric programming John Nash Jr. 西関（ ) - メールがない - 電話代が高い - Gaurett Birkhoff がいた教授室 映画 “A Beautiful Mind” ノーベル 賞 推薦状 “This man is genius” 3 天国の１年 間

Top 10 GLOBECOM ‘87 グラフでない論文 は 1 つだけ 秘密共有法

1 2 GLOBECOM ‘87 6 秘密共有法

1 2 RSA 暗号 (k, n) しきい値法 ShamirRivestAdleman 7

契機 グラフ以外へ研究を展開 暗号 （ 1977 年に RSA 暗号発明， Allerton Conf. ‘77 で Rivest の講演を聞く） 修士 2 年生 上原輝昭君を NEC 研究所に派遣 岡本栄司氏（現 筑波大），中村勝洋氏（現 千葉大）が 指導 A. Shamir のしきい値法を一般化したらどうか？ 8

9 A. Shamir の (k, n) しきい値法 ・ k-1 次多項式の補間

本質 有限体上の行列の基底 ベースマトロイド 閾値法 ⇒ 一様マトロイド 極小アクセス集合の族（アクセス構造）が表現可能 な ベースマトロイドであればよい 10

修士 NEC 1986 年 11

問題点 日本語でしか発表しなかった 極小アクセス集合の要素数は一定 12

伊藤 充 （修士） 斉藤 明 （助手） 13 伊藤 充斉藤 明 東大（榎本彦衛先 生） グラフ理論

14 新しい秘密共有法の発明 各共有者に適当な複数個 の分散情報を配布してお く． n 人中の k 人のような特殊 なアクセス構造ばかりで なく，任意のアクセス構 造に対し秘密情報を復元 することができる． 複数割り当て法による復元

極大非アクセス集合の族 = { B 1, B 2, …, B j } 秘密情報を ( j, j ) 閾値法で j 個 w 1, w 2, …, w j に分割 各人 p に p ∈ B i ∈ なる w i を割り当てる 15 アクセス集合の族 A ∈, A ⊂ A’ ⇒ A’ ∈ W(p) = { w i | p ∈ B i ∈ } 任意のアクセス集合 A ∈ に対し， W(p) = { w 1, w 2, …, w j } ∪ p ∈ Ap ∈ A 任意の非アクセス集合 B に対し， W(p) ⊂ { w 1, w 2, …, w j } ∪ p ∈ Bp ∈ B

16

Globecom ’87 で R. S. A. が称賛 単調ブール関数の乗法標準形 一般アクセス構造を有する秘密共有法が， 情報セキュリティの一分野として発展 Globecom ’87 の実行委員の三木哲也氏（当 時 NTT ，現 電通大理事）が，投稿を勧める． 斉藤明さんが上手に発表 17 STOC 又は FOCS

絶対に安全な秘密鍵の共有法 情報科学研究科創設後 18 水木先生，静谷先生，学生と共同研究

Alice Bob ＡさんとＢさん遠くに離れているところに住ん でいて、ＡさんはＢさんにメッセージを伝えた いとしましょう。 今日、 会おう よ！ 19

Alice Bob ただし、メッセージの内容を他の人に知られたくありませ ん。 Eve 20 今日、 会おう よ！

Alice Bob 例えば、電話を掛ければ、メッセージを伝えられますね。あるいは、最近 では、電子メールを利用してメッセージを伝えるかもしれません。しかし、 電話にしても電子メールにしても、もしかしたら、途中に盗み聞きや盗み 見をしている悪い人がいるかもしれません。 Eve 電話・電子メール 21 今日、 会おう よ！

今日、 会おう よ！ Alice Bob そんなときには、「暗号」を使うと、ＡさんはＢさんに秘密にメッセージ を伝えることができます。Ａさんは、途中で盗み見されても大丈夫なよう に、メッセージを暗号化して、他の人にわからなくして、Ｂさんに送りま す。暗号文を受け取ったＢさんは元に戻してメッセージを得ます。 Eve カギ ？？？ 暗号 22

ところで、暗号は本当に安全なのでしょうか？つまり、どんな人にも本当 にメッセージの内容がバレないのでしょうか？実は、現在使われている暗 号のほとんどは、数学的な問題の難しさにその安全性の根拠を置いていま す。 Alice Bob c = m e mod pq c m = c d mod pq p, q → pq : easy pq → p, q : hard 23

小学校の算数の問題： 整数 35 を素因数分解しなさい 24

小学校の算数の問題： 整数 35 を素因数分解しなさい 35 ＝ 5×7 25

小学校の算数の問題： 整数 35 を素因数分解しなさい 35 ＝ 5×7 それでは、 2,795,519 では？ 26

2,795,519 を素因数分解しなさい 2 で割り切れない、 3 で割り切れない、 4 で割り切れない、 5 で割り切れない、 … 683 で … 割り切れた！ 2,795,519 ＝ 683×4,093 27

大きな数の素因数分解ができると、 現在使われている暗号は解読されてしまいます。 素因数 分解 × 28

したがって、もしそのような難しい数学の問題を解ける人がいたり、短時 間で解ける高性能なコンピュータがあったら、その暗号は破れてしまい、 メッセージの内容がバレてしまいます。 スーパーコンピュータ 29

本研究では、どんなに数学な得意な人でも、どんなに高性能なコンピュー タでも、絶対に解読できない暗号について研究し、どのような場合にその ような絶対に安全な暗号を作ることができるかどうか、について研究しま した。 Alice Bob Eve カギ 絶対に開け られない 30 今日、 会おう よ！ 暗号

31 小泉康一 （博士院生） 水木敬明 ２００８ 年

Alice Bob c = m k m = c k = (m k) k k ：秘密共有鍵 32

AliceBob Eve カードのランダム配布を考え る ０ １ 33

Alice Bob Eve ランダム配布 34

Alice Alice と Bob は “ 秘密鍵 ” を共有できる Alice のカードが大きい ⇒ “0” Alice のカードが小さい ⇒ “ １ ” Eve Bob （例 1 ） Alice ：「 と の中にあなたのカードありますか？」 Bob ：「はい，あります」4 3 Alice と Bob は， が Bob のカードで が Alice のカード であることを知る． しかし， Eve にはどっちがどっちのカードか全くわからない．4 3 35

Alice Eve Bob （例 2 ） Alice ：「 と の中にあなたのカードありますか？」 Bob ：「いいえ，ありません」4 1 Alice と Bob は と を捨てる． （実際には，捨てられたものであるとして以後振舞う．） Alice Eve Bob Alice ：「 と の中にあなたのカードありますか？」 Bob ：「はい，あります」 秘密鍵 を共有できる

AliceEve Bob ( 2, 1; 1) ○ ( 4, 3; 5) ○ ( 1, 1; 1)× ( a, b; e) ？？？ 秘密鍵が共有できるための条件は？ 37

改良 transformation プロトコル abeabe 分割 結合 38

This combining operation is repeated as long as there are two sets of almost same size. Final sets combining transformation No Eve's card 2 bits splitting transformation Alice Bob Eve d b a step 2: Combining transformation 39

d d The detail of combining operation d /3d /3 Alice randomly chooses d /3 cards from one of the two larger sets, 40

d d d /3d /3 and d /3 cards from the other larger set. 2d / 3 d /3d /3 The detail of combining operation Alice announces these card numbers Alice randomly chooses d /3 cards from one of the two larger sets, 41

d d d /3d /3 2d / 3 d /3d /3 The detail of combining operation Bob announces how many cards he has in the new set. ‘1 card’ Bob announces d d 2d / 3 New smaller set. Alice announces these card numbers. 42

d d The detail of combining operation d /3d /3 Alice randomly chooses d /3 cards from one of the sets, There are three cases. 43

d d Alice randomly chooses d /3 cards from one of the sets, and d /3 cards from the other larger set. 2d / 3 d /3d /3 The detail of combining operation There are three cases. ‘0 card’ Bob announces d /3d /3 44

d d The detail of combining operation There are three cases. 2d/3 2d/3 Alice can know that these cards are Eve’s cards. 2d/32d/3 Eve can know that this card is Alice’s. New smaller set. Alice announces the remaining set, as a new smaller set. 2d / 3 45

d d The detail of combining operation d /3d /3 Alice randomly chooses d /3 cards from one of the sets, There are three cases. 46

d d Alice randomly chooses d /3 cards from one of the sets, and d /3 cards from the other larger set. 2d / 3 d /3d /3 The detail of combining operation There are three cases. ‘2 cards’ Bob announces d /3d /3 47

d d The detail of combining operation There are three cases. Eve can know that one of these blue cards is Bob's card. Alice regards this smaller set, as a new smaller set. d/3d/3 d/3d/3 2d / 3 48

d d 2d/32d/3 2d/32d/3d/3d/3 The combining operation is a randomized one. The detail of combining operation There are three cases. 49

log 2 a+b a if e = 0 min a,b,if 0 < e < max{a,b} otherwise if s = 3, i = j = 1 otherwise if s > i+j ≧ 3 and i ≧ j (where r = s mod i) if s ≧ 4, i = j = 1 プロトコルにより n ビット共有できる ⇔ 定理 50

51

52 一般的なアクセス構造を有する秘密共有法の実 現 - 30 年～ 50 年生き延びる結果 - 秘密共有法という分野が形成されるきっかけとなった - 結果が単純ですぐ説明できる - 組合せ論の考え方 - 高等な数学の結果は一切使っていない 某 T 先生談 「そんな易しい数学（算数）だけで，よくそんなに論文 を書けるものですね」 「帰納法と背理法で証明できるのは，簡単で自明なことで ある」ともご託宣 むすび

53 ポテンシャル法，対角線論法 RSA 暗号だって，整数論の教科書の最初の 50 ペー ジに書いてある結果だけを用いている 誰でも理解できる易しい数学だけを用いてよい結 果を導けるならば，それにこしたことはない 上原君，伊藤君，小泉君，斉藤明さん，岡本さ ん，中村さん，水木先生，静谷先生との出会い 人との出会いが大事，大切 「 (k, n) 法が一般化できないか？」という岡本栄司 さんの直感が重要な役割 「回路理論的グラフ理論」博論亀山先生と高校で同級 (k, n) しきい値法は多項式補間にすぎない