1994 年、コンピューター科学者のピーター・ショールは 発見 量子コンピューターが発明された場合、オンラインで共有される情報を保護するために使用されるインフラストラクチャの多くが破壊されると考えられています。 その恐ろしい可能性により、研究者は新しい「ポスト量子」暗号化スキームを作成して、量子ハッカーの手に渡らないようにできる限り多くの情報を保存しようと奮闘しています。

今年初め、国立標準技術研究所は 明らかになった ポスト量子暗号標準の検索で XNUMX つのファイナリストが選ばれました。 そのうちの XNUMX つは「格子暗号」を使用しています。これは、空間内のドットの規則的な配置である格子に着想を得たスキームです。

格子暗号やその他のポスト量子の可能性は、現在の標準とは決定的に異なっています。 しかし、それらはすべて数学的非対称性に依存しています。 現在の多くの暗号化システムのセキュリティは、掛け算と因数分解に基づいています。どのコンピューターでも XNUMX つの数をすばやく掛けることができますが、暗号的に大きな数を素因数分解するには何世紀もかかる可能性があります。 この非対称性により、シークレットをエンコードするのは簡単ですが、デコードするのは難しくなります。

Shor が 1994 年のアルゴリズムで明らかにしたことは、素因数分解の癖が量子コンピューターによる攻撃に対して脆弱になるということでした。 「量子コンピューターができることは、非常に具体的で特別なことです。 キャサリン・スタンジ、コロラド大学ボルダー校の数学者。 そのため、Shor の後、暗号学者は新しい仕事を得ました。それは、実行は簡単だが元に戻すのはほとんど不可能な、斬新な数学的操作のセットを見つけることです。

格子暗号は、これまでで最も成功した試みの 1990 つです。 もともとは XNUMX 年代に開発されたもので、ポイントの合計をリバース エンジニアリングする難しさに依存しています。

ラティス暗号を説明する 10 つの方法を次に示します。友人がラティスを持っていると想像してください。ラティスは、平面全体で規則的に繰り返されるパターンのポイントの集まりです。 あなたの友人は、これらのポイントのうち XNUMX 個の名前を挙げてほしいと言っています。 しかし、彼は難しく、格子全体を描くことはありません。 代わりに、彼は XNUMX つのポイントだけを挙げています。 x-101 の値と y-値は 19、もう一方は座標 [235, 44] です。

幸いなことに、ラティス上の新しいポイントを見つけるのは簡単です。ラティス上の任意の XNUMX つのポイントを加算および減算すると、同じラティス内に XNUMX 番目のポイントが得られるからです。 したがって、あなたがしなければならないのは、あなたの友人があなたに与えたポイントを合計するか、それらに整数を掛けてから合計するか、またはXNUMXつの組み合わせです. これを XNUMX つの異なる方法で行うと、友達の質問に答えることができます。

しかし、あなたの友人はまだ満足していません。 彼は同じ 0 つの開始点を示し、同じ格子上で [0, 101] に近い点を見つけることができるかどうかを尋ねます。 この質問に正しく答えるには、[19, 235] に近づく [44, 0] と [0, XNUMX] の組み合わせを見つける必要があります。 この問題は最初の問題よりもはるかに難しく、答えを得るために推測と確認を行うだけで終わる可能性があります。 その非対称性が、格子暗号の根底にあるものです。

実際に格子暗号を使用して情報を共有したい場合は、次のようにします。 友人 (より良い友人) があなたに安全なメッセージを送信したいと考えているとします。 数字の正方形のグリッドから始めます。 XNUMX つの行と XNUMX つの列があり、次のようになっているとします。

これで、自分だけが知っている秘密の「鍵」を思いつきます。 この例では、あなたの秘密鍵が 3 と -2 の 3 つの秘密の数字であるとします。 最初の列の数字に 2 を掛け、XNUMX 番目の列の数字に -XNUMX を掛けます。 各行の結果を合計して、XNUMX つのエントリを含む XNUMX 番目の列を取得します。

新しい列をグリッドの端に貼り付けます。 この新しい XNUMX 列のグリッドが公開鍵です。 自由に共有してください！

(実際のシナリオはもう少し複雑になります。ハッカーが秘密鍵を解読できないようにするには、最後の列にランダム ノイズを少し追加する必要があります。ただし、ここでは簡単にするためにその手順を無視します。 )

これで、友人は公開鍵を使用してメッセージを送信します。 彼女は自分の 2 つの秘密の数字を考えます: 0 と 2. 最初の行の数字に 0 を掛け、XNUMX 番目の行の数字に XNUMX を掛けます。次に、各列の結果を合計して XNUMX 番目の行を取得します。

彼女は新しい行をグリッドの一番下に追加し、あなたに送り返します。 (繰り返しになりますが、実際のシステムでは、列にノイズを追加する必要があります。)

これで、メッセージを読むことができます。 これを行うには、友達の最後の行が正しいかどうかを確認します。 彼女の行の最初の XNUMX つのエントリに独自の秘密鍵を適用します。 結果は最後のエントリと一致する必要があります。

友達は、最後の列の番号が間違っている行を送信することもできます。 彼女は、この数があなたの計算と一致しないことを知っています。

友人が最後の数字が正しい行を送信した場合、これを 0 と解釈します。数字が正しくない行を友人が送信した場合、あなたはそれを 1 と解釈します。したがって、行は単一のビット: 0 または 1 のいずれか。

外部の攻撃者は、あなたの秘密鍵にも友人の秘密鍵にもアクセスできないことに注意してください。 それらがなければ、攻撃者は最終的な数字が正しいかどうかわかりません。

実際には、100 ビットよりも長いメッセージを送信したいと考えています。 したがって、たとえば 100 ビットのメッセージを受信したい人は、100 つではなく 0 の新しい列を生成します。 次に、メッセージの送信者は単一の新しい行を作成し、最後の 1 エントリを変更して各エントリを XNUMX または XNUMX にエンコードします。

格子暗号が実際に実装された場合、このシナリオでカバーされていない無数のニュアンスが含まれます。 たとえば、メッセージを詮索好きな目から完全に保護したい場合、マトリックスには考えられない数のエントリが必要であり、全体が非常に扱いにくくなり、使用する価値がなくなります。 これを回避するために、研究者はパラメーターの数を削減できる便利な対称性を持つ行列を使用します。 それを超えて、問題自体、エラーの組み込み方法などに適用できる一連の微調整があります。

もちろん、Shor が因数分解で見つけたように、誰かが格子暗号に致命的な欠陥を見つける可能性は常にあります。 特定の暗号化スキームが、考えられるあらゆる攻撃に直面しても機能するという保証はありません。 暗号化は解読されるまで機能します。 確かに、今年の夏の初めに 有望なポスト量子暗号スキームの XNUMX つが解読されました 量子コンピューターではなく、通常のラップトップを使用します。 スタンジにとって、このプロジェクト全体は不快なパラドックスを生み出しています。 「とても後ろ向きです。」

訂正： 2022 年 11 月 9 日
この記事の元のバージョンでは、格子暗号で解決するのが難しい問題は、原点近くの格子上の特定の点を見つけることであると述べました。 実際、特定のポイントを見つけるのは比較的簡単です。 難しい問題は、原点の近くにある未知の点を見つけることです。 この事実を反映するために記事が変更されました。