TOKYO TECH CYBERSECURITY

田中研究室の研究テーマ

田中研究室では，暗号の理論について研究しています。

田中研究室では，暗号の理論について研究しています。

内容

暗号というと，秘密に通信する手段を想像する人が多いと思いますが，ここでいう暗号とは広義の意味の暗号のことで，多くの話題を含む分野を指します。主な話題としては，公開鍵暗号，ディジタル署名，ゼロ知識証明，マルチパーティ・プロトコル，秘密分散，ハッシュ関数，疑似乱数生成，共通鍵暗号，量子暗号などがあります・暗号はそのもの自体おもしろいのですが，さらに興味深いことに計算複雑さの理論，情報理論，あるいは数論と密接に関わっています。例えば，一方向性関数が存在するか，すなわち x から f(x) を計算するの は簡単だが f(x) から x を求めるは難しいような f が存在するかという問題は計算複雑さの本質的な部分に関わってきます。

特色

暗号理論の分野は上記のような多くの話題からなる上に，それぞれの話題についても安全性の証明といった理論的な内容から高速な計算機実装といった応用的な内容まで幅広い内容を含みます。現在，暗号の分野は論文の数も研究者の人口も多いです。研究の進め方の一例としては，対象とする話題を一つ決め ( 例えば公開鍵 暗号 )，さらにその話題の中で対象を一つ決め ( 例えば安全性の関係 )，そこを調べていくことです。また，研究を進めていくうえで役立つと思われる知識としては， 代数系， アルゴリズムとデータ構造， 計算複雑さの理論， 確率と統計の基礎， 情報理論などがあります。

研究テーマの具体例

以下では，本研究室で主に取り組んでいるテーマのいくつかを紹介します。

公開鍵暗号の安全性

公開鍵暗号は 1976 年に Diffie，Hellman によって概念が提案され， 1978 年に Rivest, Shamir, Adleman によって具体的実現方式が初めて提案されたシステムです。この公開鍵暗号の概念について簡単に説明します。公開鍵暗号とは，公開鍵と秘密鍵の二つの鍵を使ってデータの暗号化，復号化を行なう方式です。公開鍵は暗号化専用の鍵であり，復号化を行うことはできません．また，公開鍵で暗号化したデータはそれに対応する秘密鍵でしか復号することができません。まず受信者 Bob は公開鍵と秘密鍵のペアを用意し，公開鍵をだれでも見られるところに置きます。送信者 Alice が Bob にデータを送りたい場合は，Bob が公開している公開鍵をつかって暗号化を行ない，これを Bob に送信します。そして Bob は自分の秘密鍵で復号化を行ないます。このとき，誰かが盗聴していたとしても，秘密鍵をもっている Bob 以外は暗号を解読できないというわけです。
次に安全性です。安全性といっても，いろいろな観点があります。例えば，暗号は通信内容を隠して送ることが目的です。したがって，暗号文から平文がわからないということが重要です。また，暗号文から平文の内容を知ることができなくても，暗号文をうまく改ざんすることで，送ろうとした内容と違ったことが送られてしまうのも困ります。公開鍵暗号の安全性の分野は，どのような公開鍵暗号が，どのような安全性を満たすのか，ということについて研究する分野です。

ディジタル署名の安全性

電子化されたデータに承認印を押したい場合を考えます。例えば，印鑑パターンの画像をデータに添付するのはどうでしょうか．これは問題が起こります。なぜなら，一度印鑑パターンを受信した人は，その後自由に他の文書にその印鑑のパターンの画像をつけることができてしまうからです。つまり，承認印付きの文書をいくらでも偽造できてしまうのです。よって，電子化された世界では新たな技術が必要となります。それがディジタル署名です。ディジタル署名の実現には，公開鍵暗号が有効です。簡単にいうと，公開鍵暗号の秘密鍵を使って署名をし，公開鍵を使って正当性を検証することになります。一般的に，文書に対して署名が偽造できないとき，ディジタル署名が安全であると言います。ディジタル署名の安全性の分野は，どのようなディジタル署名が，どのような安全性を満たすのか，ということについて研究する分野です。

公開鍵暗号系と情報漏洩

公開鍵暗号を使う場合，受信者が復号するための秘密鍵や暗号化のための乱数は攻撃者にはまったく漏れない秘密情報として扱われてきました。しかしながら，近年の研究においてこれらの秘密情報を漏洩させる攻撃方法が数多く提案されてきています。したがって，上で述べた公開鍵暗号の安全性においても，これらの情報漏洩を考慮した上で定義する必要があります。ディジタル署名においても同様で，攻撃者が署名を偽造する際に秘密鍵の部分情報や過去の署名に使われた乱数情報が役に立つかもしれません。
本研究室では，このような秘密情報の漏洩を考慮した場合の安全性や，情報漏洩が起きても安全な方式の構成法などについて研究しています。

LLL アルゴリズム

LLL アルゴリズムは 1982 年に Lenstra, Lenstra, Lovasz によって提案されたもので，格子の基底縮小を行なうアルゴリズムです。このアルゴリズムは近似の精度と実行時間 ( 多項式時間 ) が理論的に証明されています。現実には理論で提示されている結果より，近似の精度がよくなることが実験により示されています。
この LLL アルゴリズムに関連する研究としては，格子に含まれる最短ベクトルの長さの上界・下界についての研究，格子に関する他の様々な問題の計算量に関する研究，格子基底縮小アルゴリズムの改良に関する研究，暗号の解読等のための LLL アルゴリズムの応用などがあります。本研究室では特に，ナップザック問題と呼ばれる組合せ問題を基礎とする公開鍵暗号方式に対する攻撃方法と，その攻撃方法に強い具体的なナップザック暗号方式について研究しています。

ゼロ知識証明

ゼロ知識対話証明とは，1985 年に Goldwasser, Micali, Rackoff によって示された概念で，「ゼロ知識」という概念と「対話証明」という概念の複合です。
「対話証明」とは，証明者が検証者にある事実を対話的に（質疑応答を繰り返して）納得させるようなプロトコルのことです。これは証明したいある事実が正しければ，検証者は高い確率で納得し，ある事実が間違っていれば，検証者が納得する確率は低いという性質を満たします。また，「ゼロ知識」とはある情報を隠してある目的を実行するものです。
「ゼロ知識対話証明」では，ある情報がある性質を満たしているということを，それ以外の余計な情報を一切漏らさずに対話的に証明します。例えば，自分のパスワードを隠して，そのパスワードを自分が知っているということを他人に示したいときにゼロ知識対話証明は役に立ちます。

量子計算暗号と量子暗号プロトコル

量子コンピュータは，1985 年に Deutsch により提案・定式化された，量子力学の基本原理に基づく新しい計算モデルです。ちなみに現在のコンピュータはニュートン力学に基づく計算モデルだと考えられます。1994 年には Shor により，この量子コンピュータを用いると素因数分解や離散対数の計算がが多項式時間でできることが示されました．このことから，量子コンピュータが実現されれば， RSA 方式をはじめとする現在広く使われているほとんどすべての公開鍵暗号は破られてしまうことになります。
よって，量子コンピュータが実現されても安全である公開鍵暗号についての研究は重要だと思われます。また，量子原理を用いた暗号プロトコルや情報理論についても研究されています。量子計算・通信では，量子力学の基本原理がとても単純な形でモデル化されていますので，研究をしていく上で量子力学の知識は特には必要とされません。ただし量子の世界の感覚はある程度必要となってきますが，これは研究を行なっていくなかで自然と身に着いてくるものだと思います。