Develop with pleasure!

福岡でCloudとかBlockchainとか。

準同型多項式公開鍵暗号ベースのデジタル署名スキーム

PQC Cryptography

準同型多項式公開鍵（Homomorphic polynomial public key ＝ HPPK）暗号は、量子耐性を持つ新しい暗号方式で、もともとは鍵カプセル化方式（KEM）として提案されたものが、その後デジタル署名に拡張されたもの↓

www.academia.edu

HPPK DS

HPPK DSでは、内部でバレット還元アルゴリズムを利用してデジタル署名スキームを構築しているので、まず前提となるアルゴリズムについて理解する↓

バレット還元アルゴリズム

このバレット還元アルゴリズムは、1986年にPaul Barretによって開発されたアルゴリズム。

z = a mod n

のような剰余演算において、任意の数値に対する除算は高コストなので、乗算と2の冪乗での除算（ビットシフト）に置き換えることで計算を高速化する。 {a \mod n = a - \lfloor a / n \rfloor * n} *1なので、商 {q = \lfloor a/n \rfloor}の部分が効率的に計算できればいい。

まず事前に {k \ge \lceil \log_2 n \rceil} *2として、 {R = 2^{k}}と {\mu = \lfloor R^{2} / n \rfloor}を計算する。

これらの事前計算値を使って商の近似値 {q' = \lfloor a \mu / R^{2} \rfloor}を計算する。q'は近似値でqと一致しない場合もあるので、 {z = a - q'n}を計算し、zがnより大きい場合は、nより小さくなるまでz -= nを繰り返す（この場合、最大2回）。

{\mu}については除算コストが発生するけど、これは実際にmod計算をするaとは無関係のパラメーターであるため、事前計算して固定値とすれば、mod計算時のコストにはならない（逆に毎回計算すると、このアルゴリズムの恩恵を受けられない）。残りの除算はビットシフトで計算できる。

このアルゴリズム自体は、剰余演算の高速化のためのものだけど、 {\mu = \lfloor R^{2} / n \rfloor}の値が分かれば {q' = \lfloor a \mu / R^{2} \rfloor}の計算時にnについて知らなくても近似値を計算できるようになることに注目して、HPPK DSスキームでは剰余演算の法を秘匿した状態での計算を署名検証に組み入れている。詳しくは後述。

鍵生成

素体 {\mathbb F_{p}}（pはセキュリティパラメーター）上のHPPKについて、まず最初に以下の秘密の値を生成する。

  1. 単変量多項式*3f(x)とh(x)を生成し（多項式の各係数は {\mathbb F_{p}}内からランダムに選択）、
  2. 2つの大きな整数 {S_1, S_2}を選択
    攻撃者が公開情報からこれらを推測するのを困難にするため、各値はpのビット長の2倍以上となることが推奨されている
  3. 2つの秘密の値 {R_1, R_2}を選択
    この2つはそれぞれは {S_1, S_2}より小さい数で {S_1, S_2}と互いに素である（逆元が存在するようにする）必要がある。

HPPKではこれらの {f(x), h(x), S_1, S_2, R_1, R_2}が秘密鍵になる。

次に秘密鍵から公開鍵を計算する手順が↓

  1. ランダムな多変量基底多項式*4 {B(x, u_1, ..., u_m)}を生成し、
  2. 1をそれぞれf(x)とh(x)に乗算して積多項式P、Qを計算する：
    • {P(x, u_1, ..., u_m) = f(x) B(x, u_1, ..., u_m) \mod p}
    • {Q(x, u_1, ..., u_m) = h(x) B(x, u_1, ..., u_m) \mod p}
      なお多項式の性質上、 {f(x) Q(x, u_1, ..., u_m) = h(x) P(x, u_1, ..., u_m) \mod p}が成立し、この等式が署名方式の正しさを支える根本的な要素。
  3. 多項式PとQの各係数を {(R_1, S_1), (R_2, S_2)}を使って暗号化する（各係数 × R mod Sを計算する）
    • 多項式Pについては、 {P(x, u_1, ..., u_m)R_1 \mod S_1}を計算する。元の多項式の各係数を {p_{i,j}}とした場合*5、暗号化後の各係数は {P_{i, j} = R_1 \cdot p_{i, j} \mod S_1}
    • 多項式Qについては、 {Q(x, u_1, ..., u_m)R_2 \mod S_2}を計算する。元の多項式の各係数を {q_{i,j}}とした場合、暗号化後の各係数は {Q_{i, j} = R_2 \cdot q_{i, j} \mod S_2}
  4. {\mathbb F_{p}}内からランダムな値βを選択し、
  5. {S_1, S_2}をβでマスクした {s_1, s_2}を計算する。
    • {s_1 = \beta \cdot S_1 \mod p}
    • {s_2 = \beta \cdot S_2 \mod p}
  6. 3で暗号化した各係数 {P_{i, j}, Q_{i, j}}をβでマスクした {p'_{i, j}, q'_{i, j}}を計算する。
    • {p'_{i,j} = \beta \cdot P_{i, j} \mod p}
    • {q'_{i,j} = \beta \cdot Q_{i, j} \mod p}
  7. バレット変換のアイディアを基に、バレットパラメーターR（公開パラメーター）を使って、 {\mu_{i,j}, \nu_{i,j}}を計算する。
    • {\displaystyle \mu_{i, j} = \lfloor \frac{R \cdot P_{i, j}}{S_1} \rfloor}
    • {\displaystyle \nu_{i, j} = \lfloor \frac{R \cdot Q_{i, j}}{S_2} \rfloor}

これらの結果、 {s_1, s_2, p'_{i,j}, q'_{i,j}, \mu_{i,j}, \nu_{i,j}}が公開鍵となる。

{\mu_{i,j}, \nu_{i,j}}を公開することで、その値を使って {x \cdot P_{i,j} \mod S_1}のような秘密の剰余演算の近似値を計算できるようになる。つまり、検証者は {S_1, S_2}の値を直接知らなくても検証式の計算が可能になる。

※ ステップ3の準同型な暗号化要素が、署名スキームの名前に準同型と付いている理由。

署名の生成

署名の生成プロセスは↓

  1. 署名対象のメッセージMのハッシュ値x = Hash(M)を計算する。
  2. {\mathbb F_{p}}内からランダムな値αを選択し、
  3. xで多項式f(x)、h(x)を評価し、以下の証明要素を計算する*6
    • {F = R_2^{-1} \cdot \lbrack \alpha \cdot f(x) \mod p \rbrack \mod S_2}
    • {H = R_1^{-1} \cdot \lbrack \alpha \cdot h(x) \mod p \rbrack \mod S_1}
  4. 署名データは {\lbrace F, H \rbrace}

※ αは多項式に対するブラインドファクターとして機能する。これがないと多数の署名が揃うと秘密鍵の漏洩に繋がってしまう。

署名の検証

  1. メッセージMのハッシュ値x = Hash(M)を計算する。
  2. ランダムなノイズ変数 {u_1, ..., u_m \in \mathbb F_p}を選択し*7、
  3. 署名データF, Hおよび公開鍵を使って多項式U、Vの各係数 {U_{i, j}, V_{i,j}}を計算する。
    • {\displaystyle U_{ij}(H) = H \cdot p'_{i,j} - s_1 \cdot \lfloor \frac{H \cdot \mu_{i, j}}{R} \rfloor \mod p}
    • {\displaystyle V_{ij}(F) = F \cdot q'_{i,j} - s_2 \cdot \lfloor \frac{F \cdot \nu_{i, j}}{R} \rfloor \mod p}
  4. 3の係数を使って多項式UとVを構築し、1で計算したxの値と2の変数を使って多項式 {U(H, x, u_1, ..., u_m)}と {V(F, x, u_1, ..., u_m)}を評価する。
  5. 4で評価した2つの多項式の結果が一致すれば署名検証は成功、一致しなければ失敗。

つまり、ここでは、秘密の多項式の等式 {f(x) Q(x, u_1, ..., u_m) = h(x) P(x, u_1, ..., u_m) \mod p}を何重にもマスキングした状態で間接的に検証している。

検証者は秘密の値を知らないため、これらの等式はバレット変換による以下の変換形式での検証になる。

  • {f(x) Q(x, u_1, ..., u_m)}については、 {\displaystyle V_{ij}(F) = F \cdot q'_{i,j} - s_2 \cdot \lfloor \frac{F \cdot \nu_{i, j}}{R} \rfloor \mod p}
  • {h(x) P(x, u_1, ..., u_m)}については、 {\displaystyle U_{ij}(H) = H \cdot p'_{i,j} - s_1 \cdot \lfloor \frac{H \cdot \mu_{i, j}}{R} \rfloor \mod p}

バレット変換の本来の目的は剰余計算なので近似値の補正が必要になるものの、上記の等式にはそれぞれ同じ近似値が適用されており、厳密な剰余計算がされていなくても署名の正当性は安全に確認できる。

※ もともと先行研究としてMPPK DSという署名スキームが提案されていたものの、その方式では秘密鍵と公開鍵の関係に線形性があり、それを悪用して署名の偽造ができてしまうという脆弱性があった。それを解消するためにHPPK DSではバレット変換で床関数を導入することで、秘密鍵と公開鍵が非線形になるように改良したらしい。

パラメーターとデータ長

素体pのサイズによるデータ長とセキュリティレベルは、論文の表1より↓

セキュリティレベル エントロピー フィールドサイズlog(p) 公開鍵 秘密鍵 署名
NIST Level I 144 bit 64 bit 196 byte 104 byte 144 byte
NIST Level III 208 bit 96 bit 276 byte 152 byte 208 byte
NIST Level V 272 bit 128 bit 356 byte 200 byte 272 byte

既存の耐量子デジタル署名スキームと比べるとかなりデータサイズが小さくて良い。また署名の生成/検証速度も非常に高速。ネックはまだ研究段階という点。

*1: {\lfloor \rfloor}は床関数

*2: {\lceil \rceil}は天井関数

*3:変数が1つのみの多項式

*4:変数を複数もつ多項式

*5:iはxの次数のインデックス、jはノイズ変数 {u_j}のインデックス

*6: {R_1^{-1}, R_2^{-1}}について、鍵生成時に互いに素なRとSを選択しているため、この逆元の存在が保証される。

*7:攻撃者が事前に特定の条件下でのみ通用する偽造署名を作成する攻撃を防止するため