Loading article…
デジタル署名は、デジタル情報を意図的な改ざんから保護し、デジタル情報の出所を認証する手段です。公開鍵暗号方式は、デジタル署名を作成するための多様な暗号アルゴリズムを提供します。しかし、現在使用されている主要な公開鍵署名（RSAおよび楕円曲線署名）は、 科学者が中規模の量子コンピュータを構築できた場合、完全に安全ではなくなります。[ 1 ]ポスト量子暗号は、量子暗号による攻撃に耐性を持つように設計された暗号アルゴリズムの一種です。格子における難問に基づくいくつかのポスト量子デジタル署名アルゴリズムが、一般的に使用されているRSAおよび楕円曲線署名に代わるものとして開発されています。これらの格子ベースのスキームの一部は、リング学習エラーと呼ばれる問題に基づいています。リング学習エラーに基づくデジタル署名は、ポスト量子署名の中でも公開鍵と署名サイズが最も小さいものの一つです。
過去 10 年間の量子コンピューティングの発展と、20 年以内に実際の量子コンピュータが実現するという楽観的な見通しにより、インターネットを保護する基本的な暗号化が脅かされ始めています。 [ 2 ] [ 3 ]わずか 1 万ビットの情報しか処理できない 比較的小さな量子コンピュータでも、インターネット上のプライバシーを保護し、情報をデジタル署名するために広く使用されている公開鍵暗号アルゴリズムをすべて簡単に破ることができます。[ 1 ] [ 4 ]
デジタル署名を作成するために最も広く使用されている公開鍵アルゴリズムの1つは、RSAとして知られています。そのセキュリティは、2つの大きく未知の素数の積を構成要素の素数に因数分解するという古典的な難しさに基づいています。素数がランダムに選択され、十分に大きい場合、整数因数分解問題は従来のコンピュータでは処理不可能であると考えられています。しかし、2つのnビット素数の積を因数分解するには、約6nビットの論理量子ビットメモリを持ち、ショアのアルゴリズムとして知られるプログラムを実行できる量子コンピュータであれば、このタスクを容易に実行できます。[ 5 ]ショアのアルゴリズムは、離散対数問題およびより難解な楕円曲線離散対数問題 として知られるものに基づいて、デジタル署名を迅速に解読することもできます。事実上、ショアのアルゴリズムを実行する比較的小さな量子コンピュータは、今日インターネット上の情報のプライバシーと完全性を確保するために使用されているすべてのデジタル署名を迅速に解読することができます。
RSAやその他のデジタル署名アルゴリズムを破る量子コンピュータがいつ出現するかはわかりませんが、攻撃者が量子コンピュータのリソースを自由に使える場合でも安全性を維持する暗号アルゴリズムを作成するための研究が過去 10 年間活発に行われてきました。[ 1 ] [ 6 ]この新しい暗号分野は、ポスト量子暗号または量子安全暗号と呼ばれています。[ 1 ] [ 6 ]この記事では、これらのアルゴリズムの 1 つのクラス、つまりリング学習エラー問題に基づくデジタル署名について説明しています。暗号における一般的な学習エラー問題 の使用は、2005 年に Oded Regev によって導入され、いくつかの暗号設計の源となっています。[ 7 ]
リングベースエラー学習（RLWE）暗号基盤の開発者は、リングエラー学習に基づくこれらのアルゴリズムの重要な特徴は、既知の困難な問題への証明可能な還元であると考えています。[ 8 ] [ 9 ] 以下に説明する署名は、理想的な格子における最短ベクトル問題への証明可能な還元を持ちます。[ 10 ]これは、リングLWE暗号システム に対する攻撃が見つかれば、想定される困難な計算問題のクラス全体に解が存在することを意味します。[ 11 ]
最初のRLWEベースの署名は、Lyubashevskyが論文「Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures」[ 12 ]で開発し、2011年に「Lattice Signatures Without Trapdoors」[ 13 ]で改良されました。その後、多くの改良と変種が生まれました。この記事では、RLWE署名の基本的な数学的構造を強調し、Lyubashevskyの元の研究とGuneysu、Lyubashevsky、Popplemann（ GLP ）の研究[ 10 ]に従います。このプレゼンテーションは、GLYPHと呼ばれるGLPスキームの2017年の更新に基づいています。[ 14 ]
RLWE-SIGは、奇素数qに対する有限体Zq（すなわち環Zq[x]/Φ(x)）の係数を持つ次数nの多項式Φ(x)を法とする多項式の商環で動作します。[ 13 ]多項式の乗算と加算は通常 の方法で行われ、乗算の結果はΦ(x)を法として簡約されます。この説明では、典型的な多項式は次のように表されます。
体 Z qの代表元は集合 { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 } にあります。n が 2 のべき乗の場合、多項式 Φ(x) は円分多項式x n + 1 になります。n の他の選択肢も可能ですが、対応する円分多項式はより複雑であったり、その安全性が十分に研究されていない場合があります。
RLWE署名では、「無限大ノルム」と呼ばれる尺度に関して「小さい」とみなされる多項式を使用します。多項式の無限大ノルムは、係数をZqではなくZの整数と見なしたときの、多項式の係数の絶対値の最大値です。 [ 10 ]署名 アルゴリズムは、特定の無限大ノルム境界に関して小さいランダムな多項式を作成します。これは、多項式のすべての係数(a0 , ..., an -1 )を、この境界以下になることが保証されているか、または非常に高い確率でそうなるようにランダムに生成することで簡単に実行できます。リング学習エラーに関する文献では、これを行う一般的な方法が2つあります。[ 13 ]
以下の例として使用されているRLWE署名GLYPHでは、「小さい」多項式の係数は一様サンプリング法を使用し、値bは値qよりもはるかに小さくなります。[ 10 ]
ほとんどのRLWE署名アルゴリズムは、任意のビット列を何らかの分布に従って小さな多項式に暗号学的にハッシュ化する機能も必要とします。以下の例では、ビット列ωを入力として受け取り、n個の係数を持つ多項式を出力するハッシュ関数POLYHASH(ω)を使用しています。この多項式では、係数のうちちょうどk個の絶対値が0より大きく、整数境界b（上記参照）より小さくなります。
RLWE署名アルゴリズムの重要な特徴は、拒否サンプリングと呼ばれる手法の使用です。[ 13 ] [ 12 ]この手法では、署名多項式の無限大ノルムが固定境界βを超えた場合、その多項式は破棄され、署名プロセスが再び開始されます。このプロセスは、署名多項式の無限大ノルムが境界以下になるまで繰り返されます。拒否サンプリングにより、出力署名が署名者の秘密鍵の値と悪用可能な相関関係を持たないことが保証されます。
次の例では、境界βは(b - k)となり、bは上述の均一サンプリングの範囲、kは「許容される」多項式で許容される非ゼロ係数の数となる[ 10 ] 。
GLYPH に従い、上記のとおり、多項式の最大次数は n-1 となり、したがって係数は n 個になります。[ 10 ] n の典型的な値は 512 と 1024 です。[ 10 ]これらの多項式の係数は、体 F qから取得されます。ここで q は 4 を法として 1 に合同な奇素数です。n=1024 の場合、GLYPH は q = 59393、b=16383 と設定し、Polyhash の出力における非ゼロ係数の数 k を 16 に設定します。[ 14 ] ハッシュ関数によって生成される非ゼロ係数の数 k は、どちらの場合も 32 になります。[ 10 ] 署名スキームのセキュリティは、n、q、b、k の相対的なサイズに密接に関係しています。これらのパラメータの設定の詳細については、以下の参考文献 5 および 6 を参照してください。[ 13 ] [ 10 ] [ 14 ]
上記のとおり、使用する多項式の環を定義する多項式 Φ(x) は x n + 1 となります。最後に、a(x) は、{ -(q-1)/2 から (q-1)/2 } の係数を持つ、ランダムに選択された固定の多項式となります。多項式 a(x) は、真のノイズ乱数発生器 (TRNG) の出力を一方向ハッシュ化したり、π や e などのよく知られた数学定数のデジタル展開を使用したりするなど、「秘密裏に」選択する必要があります。署名者と署名の検証者は全員、n、q、b、k、Φ(x)、a(x) およびβ = bk を知っています。
メッセージに署名したいエンティティは、以下の手順で公開鍵を生成します。
多項式 s(x) と e(x) は秘密鍵として機能し、t(x) は対応する公開鍵です。この署名方式のセキュリティは、次の問題に基づいています。多項式 t(x) が与えられたとき、次の条件を満たす小さな多項式 f 1 (x) と f 2 (x) を見つけます。 a(x)·f 1 (x) + f 2 (x) = t(x)
この問題を解決するのが難しい場合、署名方式を偽造することも難しくなります。[この問題の理論的な難しさに関する詳細は、Wikipediaの「誤差のあるリング学習」または「理想格子暗号」の記事を参照してください]
GLYPH [ 14 ]に従って、ビット列として表現されたメッセージ m に署名するために、署名主体は次のことを行います。
GLYPH [ 14 ]に従って、ビット列として表現されたメッセージ m を検証するには、検証エンティティは署名者の公開鍵 (t(x))、署名 (c(x)、z 1 (x)、z 2 (x))、およびメッセージ m を所有している必要があります。検証者は次のことを行います。
以下の点にご注目ください。
a(x)·z 1 (x) + z 2 (x) - t(x)c(x) = a(x)·[s(x)·c(x) + y 1 (x)] + z 2 (x) - [a(x)·s(x) + e(x)]c(x)
= a(x)·y 1 (x) + z 2 (x) - e(x)·c(x)
= a(x)y 1 (x) + e(x)·c(x) + y 2 (x) - e(x)·c(x)
= a(x)y 1 (x) + y 2 (x) = w(x) (上記で定義)
この簡単な導出により、署名が改ざんされていない場合、検証プロセスでは c'(x) = c(x) となることが示されます。
本書で説明するGLYPH署名方式は、Lyubashevsky、Gunesyu、Popplemenによる2011年と2012年の研究にほぼ準拠しています。彼らの研究には他にもいくつかのバリエーションがあります。それらには以下が含まれます。
リング上の格子に基づく署名の別のアプローチとして、特許取得済みのNTRUファミリーの格子ベース暗号方式の変種があります。このアプローチの主な例は、バイモーダル格子署名方式（BLISS）として知られる署名です。これは、Ducas、Durmas、Lepoint、Lyubashevskyによって開発され、彼らの論文「格子署名とバイモーダルガウス分布」に記載されています。[ 17 ] BLISS署名方式を参照してください。
{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)