東北大学大学院情報科学研究科 教授 西関 隆夫 絶対に安全な秘密鍵の共有法 - 離散数学の考え方 - 東北大学大学院情報科学研究科 教授　西関　隆夫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ランダム配布 2 4 1 3 Alice Bob Eve

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

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

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

改良 transformation プロトコル b e 分割 結合

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

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

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

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

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

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

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

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

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

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

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

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

むすび ○ カードの配布による秘密鍵共有に関する未解決 　　問題の解決 ○ 離散数学，特に組合せ論の考え方