NIST PQC 標準化プロセスに関連した知識の体系化①（【いま、ブロックチェーンが危ない：⑥】）

METEORASYSTEM
2021/03/18 02:28

METEORA SYSTEM Co., Ltd. は,渡邊の[非可換algorithmによるBlockchain耐量子化技術] について, License partner の募集を開始しました. Cryptography の歴史を変えてくださる方との出会いを心待ちにするとともに, 候補者の方との積極的な discussion を歓迎しております.

ブロックチェーンの量子耐性化を実現する渡邊の 非可換アルゴリズム について、その独特なはたらきを紹介しました。

ここからは、この非可換アルゴリズムへの理解の一助とすべく、永らく信奉されてきた可換アルゴリズムとの関係を2編にわたって整理し、知識の体系化を試みます。

1976年に戻って未来へ

Abstract

1976年、 Diffie-Hellman-Markle は鍵配送のジレンマを解決しました。

それ以前に鍵配送の現実的なシナリオはあるにはありましたが、そのシナリオは「DES に二重に鍵をかけたら、逆順に鍵を外さねばならない」という逆順のルールに邪魔され情報技術として実現しませんでした。

しかし、Diffie-Hellman- Markle は DES の逆順のルールに縛られませんでした。この数学は可換アルゴリズムです。そして RSA も可換アルゴリズムであることが容易に判ります。可換アルゴリズムは逆順のルールに邪魔されない、これは画期的な発明でした。が、Shannon の数学は量子耐性を保証しません。このシステムを量子耐性にしたいなら鍵生成が「うそ」をつかねばならないからです。

2014~18 年筆者(渡邊)は、逆順のルールに潜んでいる AES の Shannon エントロピーから、一方向関数を創ることに成功しました(実装もしました)。これが非可換アルゴリズムの誕生です。

非可換アルゴリズムは可換ではないため公開鍵に互換ではない、しかしその安全性は現実の習慣に寄り添う。

NIST の Post-quantum cryptosystem(PQC)は可換アルゴリズムに属するもので決着するでしょう。本稿では非可換アルゴリズムの光に照らして見たところの PQC の着地点を議論します。

本論はここから 1976 年にさかのぼります。

1. 可換アルゴリズム

1.1 Diffie-Hellman-Markle

Fig,1 は D-H プロトコルが可換アルゴリズムであることを示そうとしています。Yα(mod P)という形式の一方向関数が活躍します。αは内部変数です。

アリスは α1 を手元に置き、ボブは α2 を手元に置き、外部変数 Y と P の値をアリスとボブが取り決めます。取り決めに際し、大声を出しても問題はありません。

第三者から見ると α1 と α2 は確率変数であるので、計算 Yα1 (mod P) と Yα2 (mod P) を関数の形で下記のように表現します。

Fig.1 の S2 と S1 は各々次のように関数形で与えられます。

結局、Diffie-Hellman-Markle 鍵配送は次のように要約されます。

ここで F2(F1(Y))と F1(F2(Y)は Y に関する各々多重暗号である。多重暗号の差分(S1 - S2)をエントロピー常数と定義する。

(S1 - S2)≡エントロピー常数-----------(2)

なる式が可換アルゴリズムです。可換アルゴリズムがあれば、アリスとボブは秘密の共有関係を創れます。これには認証機能が欠落していて、秘密の共有関係を任意の二人に保証するのは難しい。

エントロピー常数ゼロは二者間に Shannon エントロピーの壁が無いことを意味します。エントロピーの壁が無いことは当然、秘密の共有関係を危機に陥れる原因となります。

1.2 RSA

1975 年の夏、Diffie は非対称鍵の構想を発表しました。リヴエストの思考回路はそこに止まります。「Diffie の言う非対称鍵は実際に有るのだろうか?」と。今、受信者アリスが持つ特別の情報(鍵)を K1 と表し、送信者ボブが持つ鍵を K2 と表します。

鍵配送の現実的なシナリオでは、ボブが最初に、乱数 x1 を振り出し、これに K2 で鍵かけをしてから暗号をアリスに送ります。さらに受信者アリスがその暗号に K1 で鍵をかけて下記の(3)をボブに返送します。二重に鍵の掛かった暗号を確率変数 P で表すと、

P2=K1(K2(x1)) -----------(3)

これは確率変数 P で二重に鍵の掛かった暗号を表します。ここから鍵配送のシナリオは鍵を外すプロトコルに入ります。

もし、DES なら「逆順に鍵を外さねばならない」というルールに邪魔されてボブは(3) の鍵 K2 を外せません。

もう一つのやり方は、アリスが送信者になり、乱数 x1 を振り出し、これに鍵 K1 を掛けてボブに送る場合です。今度は受信者ボブが鍵 K2 を掛けてアリスに返送します。

そうするとアリスもまた「逆順に鍵を外さねばならない」ルールに邪魔されて(4)の鍵 K1 を外せません。

P1=K2(K1(x1)) -----------(4)

ここでもアリスは鍵 K1 を(4)から外せません。このように逆順のルールに邪魔されて(3)/(4)を復号するアルゴリズムが無いわけです。

リヴエストはなお考えました。「受信者が特別な情報を持っている時に限り、一方向関数の逆向き計算が可能になる、そのようなアルゴリズムが見つかるだろうか?」と。これが見つかった時、「受信者アリスはボブに P2 を返送する必要が無い」。なぜなら、特別な情報としての鍵 K1 を掛けた時点で、アリスはボブの乱数 x1 を手に入れるからです。次の通りです。

2=K1(K2(x1)) =x1-----------(5)

ボブも特別な情報としての鍵 K2 を掛けた時点で P1 を返送する必要が無く、アリスの乱数 x1 を手に入れることができます。

P1=K2(K1(x1)) =x1-----------(6)

上記の通りであれば、D-H プロトコルと同じ成り行きになります。

P1 - P2 = K2(K1(x1)) - K2(K1(x1)) = x1 – x1 = 0-----------(7)

ここでもエントロピー常数はゼロになり、関数 K1() と K2 () は可換になります。アリスとボブは秘密を共有する関係を創ることができます。

しかし、アリスとボブの間に Shannon エントロピーの壁はなく、壁の欠落はシステムを危機に陥れる原因になります。

このように可換アルゴリズムは鍵を公開する技術ではなく、鍵を配送する技術です。それゆえPost-quantum cryptosystem(PQC)が公開鍵に互換であろうとするなら、PQC は当然、可換アルゴリズムのルールに従うことになる。

そうすると、鍵 k1 と k2 のどちらかをネットに公開するためには鍵生成は「ウソ」をつかねばなりません。