Develop with pleasure!

福岡でCloudとかBlockchainとか。

量子耐性のある準同型コミットメントスキームBDLOPコミットメント

PQC Cryptography

Confidential Transactionなどの仕組みでは、送金額を秘匿するのに以下のようなPedersen commitmentを利用することが多い。

C = rG + vH
  • r：ブラインドファクター（ランダム値）
  • v：秘匿する総金額
  • G：楕円曲線のベースポイント
  • H：誰もその離散対数を知らないNUMSポイント。

このように構成されたコミットメント同士は加算・減算ができるため、取引の中で送金額を秘匿したまま、金額が不正に増やされていないことを検証でき、さまざまな暗号通貨で採用されている。

ただその安全性は離散対数問題の困難性（ECDLP）に依存しているため、量子耐性を得るためには別の数学的安全性に基づく準同型コミットメントに移行する必要がある。

BDLOPコミットメント

量子耐性を持つ準同型コミットメントの設計は、格子暗号を用いるのが主流になっている。これは格子上の演算は自然に加法準同型性を持つから。そしてその1つが、格子ベースの準同型コミットメントスキームであるBDLOPコミットメント。

BDLOPコミットメントは、多項式環 {R_q = \mathbb Z_q \lbrack x \rbrack / (x^{n} + 1)}上で作業する。一般的にn = 256、qは32bit前後の素数。

ランダムに生成された2つの行列を公開パラメーターとする：

  • {A_1 \in R_q^{k \times l}}：束縛用（Binding）
  • {A_2 \in R_q^{v \times l}}：秘匿用（Hiding）

この時、lはブラインドファクターrの次元、kはBinding部の出力次元、vはメッセージm（Pedersen commitmentのvに該当する部分）の次元。これらはPedersen commitmentのGやHのようなもので、一様にランダムに見える行列である必要がある。実際には公開シードなどからハッシュ関数などで行列の要素を生成するなど、決定論的に生成することになる。

実際のパラメーターは大きいけど、計算を追ってくのに以下のおもちゃのパラメーターで試してみる。

  • n = 2、q = 17とする。
  • 多項式環は {R_{17} = \mathbb Z_{17} \lbrack x \rbrack / (x^{2} + 1)}
  • 次元l = 2
  • 公開行列は以下の1×2の多項式の行列
 { A_{1} = \begin{pmatrix} 3 + 2x & 1 + 4x \end{pmatrix}}
 { A_{2} = \begin{pmatrix} 2 + 5x & 6 + x \end{pmatrix}}

コミット

値にコミットするには、まず小さな係数のブラインドファクター {r \in R_q^{l}}をランダムに選択する。小さいというのが格子ベース特有のポイントで、各係数は一様にランダムなものではなく、{-1, 0, 1}や離散ガウス分布から選択した短いベクトルになる。

コミットメントはこのブラインドファクターを使って以下のように計算する。

 \displaystyle C = \begin{pmatrix} t_1 \\ t_2 \end{pmatrix} = \begin{pmatrix} A_1 \cdot r \\ A_2 \cdot r + m \end{pmatrix}

上段の {t_1}はブラインドファクターrから計算され、値は含まれない。下段の {t_2}は値を {A_2 \cdot r}というマスクで隠している部分になる。Pedersen commitmentのrG + vHに対応してる。Pedersen commitmentではGとHという２つの生成元を用いて隠していたのに対し、BDLOPでは行列 {A_2}とブラインドファクターの乗算結果に対して値を直接加算する。

Pedersen commitmentでは「ECDLPの困難性」という単一の仮定がBindingとHidingの両方を担保していたけど、BDLOPではこの2つの性質をそれぞれ別々の格子問題に分離して帰着させている。

  • Bindingは上段で担保される。Bindingは一度コミットした値を、後から別の値として開示できないという性質。仮に同じCに対して2通りの開示(m, r),(m', r')を示せたとした場合、上段と下段の計算により { \displaystyle A_1 \cdot (r - r') = 0}、 {\displaystyle A_2 \cdot (r - r') = m' - m}が計算できることになる。ここでrもr'も小さいベクトルなので、その差r - r'も小さいベクトルになる。つまり、 {A_1}に対する短いゼロ解を見つけたことになるけど、これはModule-SIS問題を解いたことに相当する。Module-SISが困難である限り、こうした2通りの開示は作れない。
  • Hidingは下段で担保される。 {A_2}は公開ランダム行列で、rは小さな秘密のベクトル。この構造はModule-LWE問題そのものの構造になっており、Module-LWEが困難なら {A_2 \cdot r}は一様にランダム値と識別できない。

このように１つのコミットメントの中で、Module-SIS（上段）とModule-LWE（下段）という２つの困難な問題を使い分けている。

簡単な例として金額v = 5をコミットしてみよう。前述したようにメッセージ多項式の定数項にこの金額を埋め込む。

\displaystyle m = 5 \quad (\text{定数項のみ、} x \text{ の係数は } 0)

ブラインドファクターrは、係数の小さな多項式ベクトルを選択する。たとえば、

 \displaystyle r = \begin{pmatrix} 1 - x \\ -1 \end{pmatrix}

各係数が{-1, 0, 1}に収まっているので「短いベクトル」の条件を満たしている。

{t_1 = A_1 \cdot r} の計算は、

{\displaystyle t_1 = (3 + 2x)(1 - x) + (1 + 4x)(-1) = 3 - 3x + 2x -2x^{2} -1 - 4x = 2 - 5x - 2x^{2}}

となり、 {x^{2} = -1}であることから {t_1 = 4 - 5x}。また、 {\mathbb{Z}_{17}} では {-5 \equiv 12} なので、 {t_1 = 4 + 12x}。

続いて、 {t_2 = A_2 \cdot r + m}の計算は、

{\displaystyle t_2 = (2 + 5x)(1 - x) + (6 + x)(-1) + 5 = 2 - 2x + 5x - 5x^{2} - 6 - x + 5 = 1 + 2x - 5x^{2}}

で、 {x^{2} = -1}であることから {t_2 = 6 + 2x}。

結果、コミットメントは、

 {\displaystyle C = \begin{pmatrix} t_1 \\ t_2 \end{pmatrix} = \begin{pmatrix} 4 + 12x \\ 6 + 2x \end{pmatrix}}

このコミットメント内の {t_2} の定数項6を見ても金額が5であることは分からない。マスク {A_2 \cdot r} の定数項 1 が乗っているので、5 + 1 = 6 になっているけど、rを知らない人にとって、この1は完全にランダムに見える。

別の金額をコミット

別の金額v' = 3をコミットしてみよう。新しいブラインドファクターを

 {\displaystyle r' = \begin{pmatrix} 1 + x \\ -x \end{pmatrix}}

とする。さっきと同様の計算をすると、

{ \displaystyle t_1' = 5 + 4x, \quad t_2' = 1 + x}

となり、コミットメントは、

 {C' = \begin{pmatrix} 5 + 4x \\ 1 + x  \end{pmatrix}}

コミットメントの加算

2つのコミットメントを単純に加算すると、

 {\begin{pmatrix} (4 - 5x) + (5 + 4x) \\ (6 + 2x) + (1 + x) \end{pmatrix} = \begin{pmatrix} 9 - x \\ 7 + 3x \end{pmatrix}}

これが本当に金額5 + 3 = 8のコミットメントになっているか検証する。

合算後のブラインドファクターは

 {\displaystyle r + r' = \begin{pmatrix} (1 - x) + (1 + x) \\ (-1) + (-x) \end{pmatrix} = \begin{pmatrix} 2 \\ -1 - x \end{pmatrix}}

合算後のメッセージは {m + m' = 5 + 3 = 8}。

これで、 {C + C'} が {(m + m', r + r')} のコミットメントになっているか計算すると、

  • {\displaystyle A_1 \cdot (r + r') = (3 + 2x) \cdot 2 + (1 + 4x)(-1 - x) = 6 + 4x - 1 -x - 4x -4x^{2} = 5 - x - 4x^{2} = 9 - x}
  • {\displaystyle A_2 \cdot (r + r') + 8 = (2 + 5x) \cdot 2 + (6 + x)(-1 - x) + 8 = 4 + 10x - 6 - 6x -x - x^{2} + 8= 7 + 3x }

となり、一致する。コミットメントの加算の結果、対応する金額の和に対するコミットメントが得られている。

無制限に加算できない

ただ、Pedersen commitmentと違って、無制限に足し合わせることはできない点に注意する必要がある。r + r'のノルムは元のrより大きくなり、これを繰り返すとrが小さいとは言えなくなってしまう。たとえば、r + r' = (2, -1 -x)の係数のノルムは既に2で、元のrの1より大きくなっている。そしてある閾値を超えると、Module-SISの短解性が崩れる。したがって、加算回数の上限を事前に見積もった上で、パラメーターを設計する必要がある。

コミットメントの開示

コミットメントを開示する場合は、mとrをそれぞれ開示することで、検証者は、以下をチェックする。

  1. {A_1 \cdot r} を計算して {t_1}と一致するか
  2. {A_2 \cdot r + m} が {t_2} と一致するか
  3. rの係数が十分小さいか（ノルム上限βに対してrのノルム≦β）

サイズの課題

Pedersen commitmentの場合、コミットメントは楕円曲線上の点なのでsecp256k1などの曲線であれば33 byteのデータで表現できる。一方、BDLOPの場合は、これに比べるとコミットメントのサイズがとても大きくなる。

上記の金額5はわずか3 bitのデータであるものの、コミットメントは係数4個分（それぞれ {\mathbb{Z}_{17}} の元）のデータになる。たとえば以下のような実用的なパラメーターの場合、

  • n = 256
  • q ≈ 2^23
  • l = 4
  • k = 4
  • v=1

コミットメントは、k + v = 5個の {R_q}の元を持つことになり（上段 {t_1} が k = 4 個、下段 {t_2} が v = 1 個）、その1つあたりのサイズは、

  • {R_q}の元は次数255までの多項式であり、係数が256個
  • 各係数は {\mathbb Z_q}の元なので23 bit必要。
  • 結果、 {\displaystyle 256 \text{ 係数} \times 23 \text{ bit} = 5888 \text{ bit} = 736 \text{ byte}}

これが5個あるので、736×5＝3680 byte（約3.6KB）。Pedersen commitmentの33 byteと比べると110倍。

さらに、実際には金額が負でないことを保証するために別途範囲証明が必要になり、これが現状数KB〜数十KBとされている。

まぁサイズの問題はあるものの、格子暗号ベースで量子耐性および準同型性のあるコミットメントスキーム自体は実現できる。

⚡ Zap me!

Lightning QR

Lightning Address

techmedia_think@walletofsatoshi.com