現在主流となっている暗号が、
量子コンピューターによって破られるという危機感から、
次世代の暗号が求められています。
そんな、暗号の中で注目されているのが「格子暗号」
と呼ばれる暗号です。
格子の名前の通り、網目を使って暗号化を行うのですが、
中身を見てみると多項式が出てきたり、何だ複雑に見えます。
この記事では、そんな格子暗号のしくみを
なるべく視覚的に分かりやすく見ていくことにしましょう。
格子暗号ってどんな暗号？
初めに、ざっくりと格子暗号がどんなものかを見てみましょう。
格子暗号は公開鍵暗号の一つで、暗号化は公開された鍵で誰でも簡単にできるけど、
暗号の解読は別の特別な鍵を知っている人しかできないという特徴があるものです。
clean-copy-of-onenote.hatenablog.com
格子暗号では、その名前の通り、暗号化に格子を使います。
例えば、「右」という情報を暗号化するときに、
次のような歪んだ格子上でランダムな点をピックアップして、
そこから右方向に少しだけずれた点を使います。
今の場合、左下の原点から、
オレンジの方向に2つ、黄色の方向に1つ進んだ格子点を選んで、
そこから右にずれた点を取り出しました。
この青の点が格子点から右にずれているということが
「右」というメッセージになっています。
この絵だと、「右」にずれてることがバレバレですが、
暗号化を行っていない人からすると、
下のような情報から、青の点がどの格子点に近くて、
その格子点からどちらにずれているかを読み解かなければいけません。
この問題は、最近傍格子点問題と呼ばれていて、
格子の次元が増えてくると、短時間で解くことが難しい問題として知られています。
格子暗号では、この最近傍格子点問題の難しさを利用して、
暗号の安全性を担保しようという暗号です。
多項式で格子点を表す
格子暗号のより詳しい仕組みの説明に入る前に、
格子暗号の舞台となっている「格子」について説明します。
格子は、多項式で表現されることが多いです。
例えば、 の係数を見ると
なので、
横に2個、上に1個動いた点を表していると見なすことができます。
このような多項式で格子点を表すと何が嬉しいのでしょう？
多項式は数式なので、足したり、引いたり、掛けたりと、
様々な演算を行うことができます。
多項式の演算によって、格子点を別の場所に移す操作が表せそうですね。
多項式の足し算は位置ベクトルの足し算
上でみた、とは、
と
を足したものです。
多項式のは
の点を表し、
多項式のは
の点を表しているので、
多項式の足し算が、
それぞれの点に向かうベクトルを足したベクトルが向かう点に対応しています。
当たり前のようではありますが、
多項式での足し算が、格子点の位置ベクトルの足し算に対応しているのが分かります、
スカラー倍は位置ベクトルのスカラー倍
次に、多項式をまとめて2倍するというスカラー倍はどうなるでしょうか。
を2倍すると、
ですが、
これは、格子点のを表します。
つまり、元の格子点の位置ベクトルを2倍した格子点に移っています。
このように、多項式のスカラー倍が、格子点の位置ベクトルのスカラー倍に対応しています。
を掛けると軸の回転
多項式に数字をかけるとベクトルがそのまま伸びましたが、
変数をかけるとどうなるでしょうか。
に
をかけると
になり、
の点？となり、2次元をはみ出てしまいます。
次元が変わるのが面倒なので、はみ出た分を一番下の次元に戻すことにしましょう。
これはどうすればいいかと言うと、多項式をで割った余りを考えればいいのです。
（次元の場合は、
で割った余りを考えます)
すると、を
で割った余りは、
となり、はみ出た部分
が下の次元に戻ってきました。
この場合、格子上のを表していますが、
これは、元の格子点で軸を回転させた操作に対応します。
整数剰余で格子の大きさが決まる
そのままだと、格子は無限に広がりますが、
格子に大きさの制限をつけることはできるでしょうか？
例えば格子の大きさをにしたい場合は、
多項式をで割った余りを考えます。
こうすると、のように、格子からはみ出た部分は、
あたかも逆側からループしてきたようになり、
と格子点
に移ります。
図のように、右側を超えると、
左側に戻るような形で、
の格子の上をぐるぐるまわり続けます。
つまり、格子の大きさを一辺がに制限したい場合は、
で割った余りを取ればいいということになります。
暗号化の手順
上の多項式を使った格子点の表現と操作が分かれば、
暗号化の手順を理解することは簡単です。
暗号化では、事前に公開されている多項式が一つ必要です。
これがいわゆる公開鍵です。
この公開鍵をと書くことにしましょう。
また、格子の大きさも公開された情報となります。
歪んだ格子を作る
格子暗号では、歪んだ格子を使うのでした。
公開鍵は1つの多項式だけですが、
ここからどのように、歪んだ格子を作るのでしょうか？
ここで、をかけると、
軸を回転させる操作に対応していたことを思い出しましょう。
は
を回転させた点を表します。
これで、2本の歪んだ矢印が得られました。
後は、この矢印に沿って点を取れば、歪んだ格子の完成です。
3次元、4次元のように次元が増えた場合も、
同様に、 で矢印を次元の本数分作って歪んだ格子を作ります。
歪んだ格子の点を選ぶ
格子が作れると、あとはランダムに点を選ぶだけです。
例えば、オレンジの方向に2つ、黄色の方向に1つ進んだ点のように、
どちらの方向にいくつ進むかをランダムで決めればOKです。
この場合、対応する多項式は、 ですが、
まとめると、となり、
に多項式
を掛けたものとなります。
つまり、ランダムに格子上の点を選ぶには、
ランダムに係数を指定した多項式を、
基準となる多項式にかけることで得られます。
格子からのずれとしてメッセージを埋め込む
格子暗号による暗号化は、
最後にメッセージを格子からのずれとして入れれば完了です。
点をある方向にずらすのは、多項式の足し算で表現できるので、
メッセージを表す多項式を先ほどの格子点に足せばOKです。
メッセージを表す多項式は、
例えば、右向きのずれを表す
などになります。
暗号化の手順をまとめておくと、
ランダムに係数を決めた多項式と、
公開鍵を使って、
メッセージを
で暗号化するということになります。
非常にシンプルに書けました。
暗号文の復号化
メッセージから暗号文を作る手順は分かりましたが、
これをどうやって元のメッセージに戻せばよいのでしょうか？
素直に考えると、歪んだ格子からどのくらいずれているかを計算すればよいのですが、
これは、多次元になると容易に計算できないと述べました。
実は、公開鍵に秘密があったのです。
公開鍵は、暗号文を受け取る人が作るのですが、
そこに、その人だけが簡単に解読できるような仕掛けを仕組んでおきます。
その仕掛けとは、簡単に言ってしまうと、
歪んだ格子上の点を、小さな格子の世界の原点と対応させてしまうのです。
原点、つまりゼロは、その小さな格子の世界では消えてしまうので、
メッセージに付け加えられた歪んだ格子点の情報は小さな格子の世界ではなくなり、
メッセージの情報だけが見えるようになります。
小さな格子の世界と、元の格子がどのように対応しているかは、
公開鍵を作った本人だけの秘密にしておくことで、
他の人は、このトリックを使えず、計算時間が膨大にかかる方法を取らざるを得ないのです。
公開鍵の作り方
では、どのように、公開鍵に小さい格子の世界の原点の情報を埋め込んでおくのでしょうか。
まず、原点は簡単に作ることができます。
例えば、大きさが2の格子の原点は、
係数が小さい適当な多項式を2倍すれば得られます。
このままだと、対応がバレバレなので、
逆変換可能な適当な変換をかけておきます。
これは、多項式を掛けることで行います。
これは暗号化でも見たように、軸を回したり、何倍かに伸ばしたり、
それぞれを足したりする変換に対応しています。
これによって、小さい格子の世界の原点は
大きい格子の世界のどこかに移り、
その対応はで決まっています。
この小さな格子の世界と大きな格子の世界の対応は、
他の人には漏らさずに内緒にしておき、
移った格子点だけを公開します。
復号の方法
暗号文を受け取って、元のメッセージに直すときは、
先ほどの大きい格子の世界と小さい格子の世界の対応を使います。
公開鍵は、原点と対応していましたが、
その公開鍵を使って作られた格子上の点も全て原点と対応しています。
そのため、逆変換をかけると、
歪んだ格子上の点は小さい格子の原点に移り、
小さい格子の世界では、メッセージの情報を含んだ
だけが残ります。
メッセージにも変換がかかるので、
得られるのは、変換のかかったですが、
これを、小さな格子の世界で再び逆変換をかけることで、
元のメッセージが取り出せます。
このようにして、公開鍵を作った人だけが、
内緒にしている小さい格子の世界と大きい格子の世界の対応を使って、
簡単に元のメッセージを取り出すことができるのです。
まとめ
量子コンピューター時代に注目されている格子暗号について、
その暗号化および復号化、公開鍵の生成などの仕組みと、
そこで使われている多項式と格子の考え方を紹介しました。
式も出てきますが、格子という視覚的なイメージもあり、
仕組み自体は分かりやすい暗号だと思います。
仕組みが分かりやすいのに、解読が難しいというのは、
暗号として非常に優れた性質ですので、期待されているのも頷けますね。
