エラー署名付きリング学習

デジタル署名は、デジタル情報を意図的な変更から保護し、デジタル情報のソースを認証する手段です。公開鍵暗号は、デジタル署名を作成するためのさまざまな暗号化アルゴリズムの豊富なセットを提供します。しかし、現在使用されている主要な公開鍵署名（RSA署名と楕円曲線署名）は、科学者が中規模の量子コンピュータ を構築できれば、完全に安全ではなくなります。[ 1 ]ポスト量子暗号は、量子暗号による攻撃に耐えられるように設計された暗号化アルゴリズムの一種です。格子の難しい問題に基づくいくつかのポスト量子デジタル署名アルゴリズムが、一般的に使用されているRSA署名と楕円曲線署名に取って代わるものとして作成されています。これらの格子ベースのスキームのサブセットは、エラー付きリング学習と呼ばれる問題に基づいています。エラー付きリング学習に基づくデジタル署名は、公開鍵と署名のサイズが最も小さいポスト量子署名の1つです。

背景

過去10年間の量子コンピューティングの発展と、20年以内に真の量子コンピュータが実現するという楽観的な見通しは、インターネットを保護する基本的な暗号技術を脅かし始めています。 [ 2 ] [ 3 ]わずか1万ビットの情報しか処理できない 比較的小型の量子コンピュータは、インターネット上のプライバシー保護や情報へのデジタル署名に使用されている、広く使用されている公開鍵暗号アルゴリズムをすべて簡単に破ってしまうでしょう。[ 1 ] [ 4 ]

デジタル署名を作成するために使用される最も広く使用されている公開鍵アルゴリズムの1つは、RSAとして知られています。そのセキュリティは、2つの大きな未知の素数の積を、構成する素数に因数分解することの古典的な困難さに基づいています。素数がランダムに選択され、十分に大きい場合、整数の因数分解問題は、従来のコンピュータでは解決不可能であると考えられています。しかし、2つのnビットの素数の積を因数分解するには、約6nビットの論理量子ビットメモリを持ち、ショアのアルゴリズムと呼ばれるプログラムを実行できる量子コンピュータは、このタスクを簡単に達成します。[ 5 ]ショアのアルゴリズムは、離散対数問題や、より難解な楕円曲線離散対数問題 として知られる問題に基づくデジタル署名を迅速に解読することもできます。実際、ショアのアルゴリズムを実行する比較的小さな量子コンピュータは、今日インターネット上の情報のプライバシーと整合性を保証するために使用されているすべてのデジタル署名を迅速に解読できます。

RSAやその他のデジタル署名アルゴリズムを破る量子コンピュータがいつ登場するかは不明ですが、過去10年間、攻撃者が量子コンピュータのリソースを自由に使える場合でも安全な暗号アルゴリズムを作成するための研究が活発に行われてきました。[ 1 ] [ 6 ]この新しい暗号分野は、耐量子暗号または量子安全暗号と呼ばれています。[ 1 ] [ 6 ]本稿では、これらのアルゴリズムの一種である、リング学習エラー問題に基づくデジタル署名について考察します。暗号における一般的な学習エラー問題 の応用は、2005年にOded Regevによって導入され、多くの暗号設計の源泉となっています。[ 7 ]

リングベース誤り学習（RLWE）暗号基盤の考案者は、この誤り学習に基づくアルゴリズムの重要な特徴は、既知の難問への証明可能な還元であると考えている。[ 8 ] [ 9 ]以下に説明する署名は、理想的な格子における最短ベクトル問題 への証明可能な還元を持つ。[ 10 ] これは、リングLWE暗号システムへの攻撃が発見されれば、想定される一連の計算難問の全てが解決されることを意味する。[ 11 ]

最初のRLWEベースの署名は、リュバシェフスキーの論文「アボート付きフィアット・シャミール：格子および因数分解ベース署名への応用」[ 12 ]で開発され、2011年に「トラップドアなしの格子署名」 [ 13 ]で改良されました。その後、多くの改良と派生が行われました。本稿では、RLWE署名の基本的な数学的構造に焦点を当て、リュバシェフスキーのオリジナルの研究と、グネイシュ、リュバシェフスキー、ポップルマン（GLP）の研究を踏襲します。[ 10 ]本発表は、2017年にGLPスキームが更新されたGLYPHに基づいています。[ 14 ]

RLWE-SIGは、奇素数qに対する有限体Zqを係数とするn次多項式Φ(x)を法とする商環（すなわち、環Zq [ x]/Φ(x)）において作用する。[ 13 ] 多項式の乗算と加算は、乗算結果をmod Φ(x)で簡約したものを用いて、通常の方法で行われる。この説明では、典型的な多項式は次のように表される。

あ（×）＝あ0＋あ1×＋あ2×2＋…＋あん−3×ん−3＋あん−2×ん−2＋あん−1×ん−1{\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}

体 Z q は、{ -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 } の集合に代表元を持ちます。n が 2 のべき乗の場合、多項式 Φ(x) は円分多項式x n + 1 となります。n は他の値を取ることも可能ですが、対応する円分多項式はより複雑になるか、その安全性が十分に研究されていません。

「小さい」多項式の生成

RLWE署名は、「無限大ノルム」と呼ばれる尺度に関して「小さい」と見なされる多項式を使用します。多項式の無限大ノルムとは、多項式の係数をZ qではなくZの整数と見なした場合の、係数の絶対値の最大値です。[ 10 ] 署名アルゴリズムは、特定の無限大ノルムの境界に関して小さいランダムな多項式を作成します。これは、多項式のすべての係数（a 0、…、a n-1 ）を、この境界以下になることが保証されるか、非常に高い確率でランダムに生成することで簡単に実行できます。エラー付きリング学習に関する文献では、これを行うための一般的な方法が2つあります。[ 13 ]

  • 一様サンプリングの使用- 小さな多項式の係数は、小さな係数の集合から一様にサンプリングされます。bはqよりはるかに小さい整数とします。集合{-b, -b+1, -b+2, ... -2, -1, 0, 1, 2, ... , b-2, b-1, b}から多項式の係数をランダムに選択すると、多項式の無限大ノルムは≤ (b)になります。
  • 離散ガウス分布サンプリング法を用いる - 奇数qに対して、係数は平均0、分布パラメータσの離散ガウス分布に従って、{-(q-1)/2から(q-1)/2}の範囲からランダムにサンプリングされます。この手法の詳細については、参考文献を参照してください。

以下の例で使用されるRLWEシグネチャGLYPHでは、「小さな」多項式の係数には均一サンプリング法が使用され、値bは値qよりもはるかに小さくなります。[ 10 ]

「小さな」多項式へのハッシュ

ほとんどのRLWE署名アルゴリズムでは、任意のビット文字列を何らかの分布に従って小さな多項式に暗号的にハッシュする機能も必要です。以下の例では、ハッシュ関数POLYHASH(ω)を使用しています。この関数は、ビット文字列ωを入力として受け取り、n個の係数を持つ多項式を出力します。これらの係数のうち、k個の係数の絶対値は0より大きく、かつ整数境界bより小さい値を持ちます（上記参照）。

拒絶サンプリング

RLWE署名アルゴリズムの重要な特徴は、拒絶サンプリングと呼ばれる手法の使用です。[ 13 ] [ 12 ]この手法では、署名多項式の無限大ノルムが固定の境界βを超える場合、その多項式は破棄され、署名プロセスが再開されます。このプロセスは、署名多項式の無限大ノルムが境界以下になるまで繰り返されます。拒絶サンプリングにより、出力署名が署名者の秘密鍵の値と悪用可能な相関関係を持たないことが保証されます

以下の例では、境界βは（b - k）となる。ここで、bは前述の均一サンプリングの範囲であり、kは「受け入れられる」多項式で許容される非ゼロ係数の数である[ 10 ]。

その他のパラメータ

GLYPH に従い、前述のとおり、多項式の最大次数は n-1 なので、係数は n 個になります。[ 10 ] n の一般的な値は 512 と 1024 です。[ 10 ]これらの多項式の係数は、体 F qから取得されます。ここで、q は 1 mod 4 に合同な奇数の素数です。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を知っています。

公開鍵生成

メッセージに署名したい主体は、以下の手順で公開鍵を生成します

  1. 集合{-b,...-1, 0, 1, ..., b}から一様に選択された係数を持つ2つの小さな多項式s(x)とe(x)を生成する。
  2. t(x) = a(x)·s(x) + e(x)を計算します。
  3. t(x)をエンティティの公開鍵として配布する

多項式s(x)とe(x)は秘密鍵として機能し、t(x)は対応する公開鍵です。この署名方式の安全性は、次の問題に基づいています。多項式t(x)が与えられたとき、a(x)·f 1 (x) + f 2 (x) = t(x)を満たす小さな多項式f 1 (x)とf 2 (x)を求めます。

この問題を解決するのが困難であれば、署名方式の偽造も困難になります。[この問題の理論的な難しさに関する詳細は、 Wikipediaの「エラー付きリング学習」または「理想格子暗号」の記事を参照してください。]

署名生成

GLYPH [ 14 ]に従って、ビット文字列として表現されたメッセージmに署名するために、署名エンティティは次のことを行います

  1. 集合{-b, ..., 0, ...., b}の係数を持つ2つの小さな多項式y 1 (x)とy 2 (x)を生成する。
  2. w(x) = a(x)·y 1 (x) + y 2 (x)を計算します。
  3. w(x)をビット列ωに写像する
  4. c(x) = POLYHASH(ω | m) を計算します（これは k 個の非ゼロ係数を持つ多項式です。「|」は文字列の連結を表します）。
  5. z 1 (x) = s(x)·c(x) + y 1 (x)を計算します。
  6. z 2 (x) = e(x)·c(x) + y 2 (x)を計算します。
  7. z 1 (x)とz 2 (x)の無限大ノルム≤β = ( B - k)になるまでステップ1に進みます。（これは上記の棄却サンプリングステップです）
  8. 署名は多項式c(x)、z 1 (x)、z 2 (x)の3つ組である。
  9. メッセージとc(x)、z 1 (x)、z 2 (x)を検証者に送信します。

署名検証

GLYPH [ 14 ]に従って、ビット列として表現されたメッセージmを検証するには、検証者は署名者の公開鍵(t(x))、署名(c(x), z1(x), z2(x))、およびメッセージmを所有している必要があります。検証者は以下のことを行います

  1. z 1 (x) と z 2 (x)の無限大ノルムが≤ βであることを確認します。そうでない場合は署名を拒否します。
  2. w'(x) = a(x)·z 1 (x) + z 2 (x) - t(x)c(x)を計算します。
  3. w'(x)をビット列ω'に写像する
  4. c'(x) = POLYHASH(ω' | m) を計算します。
  5. c'(x) ≠ c(x) の場合は署名を拒否し、それ以外の場合は署名を有効なものとして受け入れます。

次のことに注意してください。

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署名スキームは、2011年と2012年のLyubashevsky、Gunesyu、Popplemenの研究に密接に従っています。彼らの研究には他にも多くのバリエーションがあります。これらには以下が含まれます

  • バイとガルブレイスによる短い署名に関する研究はここに記載されています。[ 15 ]
  • Akleylek、Bindel、Buchmann、Kramer、Marsonによる、より少ないセキュリティ仮定による署名のセキュリティ証明に関する研究は、ここで文書化されています。[ 16 ]

リング上の格子に基づく署名へのもう一つのアプローチは、特許取得済みの格子ベース暗号NTRUファミリーの派生です。このアプローチの代表的な例は、二峰性格子署名方式（BLISS）と呼ばれる署名です。これはDucas、Durmas、Lepoint、Lyubashevskyによって開発され、論文「格子署名と二峰性ガウス分布」に記載されています。[ 17 ] BLISS署名方式を参照

参考文献

  1. ^ a b c d Dahmen-Lhuissier, Sabine. 「ETSI - 耐量子暗号」 . ETSI . 2015年7月5日閲覧
  2. ^ Shah, Agam. 「IBMによる量子コンピューティングのブレークスルーに関する主張」 。 2015年9月23日時点のオリジナルよりアーカイブ。 2015年6月1日閲覧。
  3. ^ Markoff, John (2015年3月4日). 「研究者、量子コンピュータ開発におけるマイルストーンを報告」 .ニューヨーク・タイムズ. ISSN 0362-4331 . 2015年7月5日閲覧。 
  4. ^ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). 「量子因数分解のための効率的なネットワーク」. Physical Review A. 54 ( 2): 1034– 1063. arXiv : quant-ph/9602016 . Bibcode : 1996PhRvA..54.1034B . doi : 10.1103/PhysRevA.54.1034 . ISSN 1050-2947 . PMID 9913575. S2CID 2231795 .   
  5. ^ Smolin, John A.; Smith, Graeme; Vargo, Alexander (2013年7月11日). 「量子因数分解の過度な単純化」. Nature . 499 ( 7457): 163– 165. arXiv : 1301.7007 . Bibcode : 2013Natur.499..163S . doi : 10.1038/nature12290 . ISSN 0028-0836 . PMID 23846653. S2CID 4422110 .   
  6. ^ a b「はじめに」 . pqcrypto.org . 2015年7月5日閲覧。
  7. ^ 「エラーを伴う学習の問題」（PDF） www.cims.nyu.edu 2015年5月24日閲覧。
  8. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). 「理想格子と環上のエラー学習について」. Gilbert, Henri (編).暗号学の進歩 – EUROCRYPT 2010 . コンピュータサイエンス講義ノート. 第6110巻. pp.  1– 23. CiteSeerX 10.1.1.297.6108 . doi : 10.1007/978-3-642-13190-5_1 . ISBN  978-3-642-13189-9.
  9. ^ 「GCHQの『教訓』は格子暗号にとって何を意味するのか？」 www.cc.gatech.edu 。 2015年7月6日時点のオリジナルからアーカイブ。2015年7月5日閲覧
  10. ^ a b c d e f g h i Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). 「実用的な格子ベース暗号：組み込みシステム向け署名方式」 Prouff, Emmanuel; Schaumont, Patrick (編).暗号ハードウェアと組み込みシステム – CHES 2012 . コンピュータサイエンス講義ノート. 第7428巻. Springer Berlin Heidelberg. pp.  530– 547. doi : 10.1007/978-3-642-33027-8_31 . ISBN 978-3-642-33026-1.
  11. ^ミッチアンチョ、ダニエレ (1998). 「格子内の最短ベクトルをある定数内で近似することは困難である」第39回コンピュータサイエンス基礎シンポジウム論文集: 92–98
  12. ^ a b Lyubashevsky, Vadim (2009-01-01). 「Fiat-Shamir with Aborts: Application to Lattice and Factoring-Based Signatures」. 松井充編著. Advances in Cryptology – ASIACRYPT 2009 . Lecture Notes in Computer Science. Vol. 5912. Springer Berlin Heidelberg. pp.  598– 616. doi : 10.1007/978-3-642-10366-7_35 . ISBN 978-3-642-10365-0.
  13. ^ a b c d eリュバシェフスキー、ヴァディム (2011). 「落とし戸のない格子署名」 .暗号学eプリントアーカイブ
  14. ^ a b c d e Chopra, Arjun (2017). 「GLYPH: GLPデジタル署名方式の新たな例」(PDF) .国際暗号研究協会 eprint アーカイブ. 2017年8月28日時点のオリジナルよりアーカイブ。 2017年8月26日閲覧。{{cite web}}: CS1 maint: bot: 元のURLステータス不明（リンク）
  15. ^ 「Cryptology ePrint Archive: Report 2013/838」 . eprint.iacr.org . 2016年1月17日閲覧。
  16. ^ 「Cryptology ePrint Archive: Report 2015/755」 . eprint.iacr.org . 2016年1月17日閲覧。
  17. ^ 「Cryptology ePrint Archive: Report 2013/383」 . eprint.iacr.org . 2016年1月17日閲覧。
「 https://en.wikipedia.org/w/index.php?title=Ring_learning_with_errors_signature&oldid=1310099703」より取得