Moneroに導入された新しいリング署名スキームCLSAG

MoneroでRingCT導入時に採用されたMLSAGについて書いた↓

techmedia-think.hatenablog.com

ので、続いて、2020年10月17日のアップグレードで新しく導入されたリング署名スキームCLSAGについて↓

https://eprint.iacr.org/2019/654.pdf

CLSAG

CLSAGはConcise Linkable Spontaneous Anonymous Groupの略で、機能としてはMLSAGと同じ機能を提供するが、署名サイズが小さくなり、署名検証も高速化する。

具体的には、インプット２つとアウトプット２つ持つ典型的なトランザクションについて、MLSAGを使ったトランザクションは約2.5KBだが、CLSAGを使うと1.9KBとなり約25%サイズが削減され、署名検証のスピードも20%の速度改善がみられるみたい。

署名の生成

↑のMLSAGの記事と同様に以下の表記を適用する（modの計算は省略）。

キーベクトルの個数をd
各キーベクトルのリングメンバーの数をn
n * d個の公開鍵のセットを ${L = P_{j, i}}$ 、 ${i \in 1, .., n}$ および ${j \in 1, ..., d}$
署名に使用するリング内の鍵（1..n）のインデックスをπとする。
楕円曲線上の点を出力するハッシュ関数を ${\mathbb H}$
署名対象のメッセージをm
Rをn * d個の全公開鍵の集約鍵

CLSAGで、d個のサイズnのキーベクトルを持つ場合（d ✕ nのマトリックスに対して）にd個の秘密鍵を使って有効な単一の署名を作る手順は↓

d個分対応する秘密鍵 ${x_{j, π}}$ を使ってキーイメージ ${I_j = x_{j, π} \mathbb H(P_{j, π})}$ を生成する（ ${j \in 1, ..., d}$ ）。
ランダムな数値αを生成する（MLSAGはd個生成したけどCLSAGでは１つのみ）。
${i \in 1, ..., n}$ からπを除いて（つまりデコイの数分）、ランダムな数値 ${r_i}$ を生成する（MLSAGはd✕(n-1)個生成していたけど、CLSAGではn-1個）。
n個の公開鍵（ ${i \in 1, ..., n}$ ）を使って集約公開鍵
${W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}$
を計算する（ ${T_j}$ はタグで、実際は”CLSAG_j”というデータのタグになる）。
ここで、 ${w_π = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * x_{j, π}}$ が ${W_π}$ に対応する集約秘密鍵となる。ｂ
d個のキーイメージを集約して集約キーイメージ
${\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}$
を計算する。
最初のチャレンジ ${e_{π+1} = H(T_c || R || m || αG || α \mathbb H(P_{1, π}))}$ を計算する（ ${T_c}$ はタグで、実際は”CLSAG_c”というデータ）。
${e_{π+1}}$ 以外のチャレンジとして、i = π+1, π+2, ..., n, 1, 2, ..., π-1について、それぞれチャレンジ ${e_{i+1} = H(T_c || R || m || r_iG + e_iW_i || r_i \mathbb H(P_{1, i} + e_i \tilde{W}))}$ を計算する。
${r_π = α - e_πw_π}$ を計算する。
署名値は ${σ(m) = e_1, r_1, ..., r_n}$

そしてプライマリキーイメージが ${I_1}$ で、補助イメージが ${(I_2, ..., I_d)}$ 。

署名の検証

キーイメージ ${I_1, ..., I_d}$ が楕円曲線のベースポイントの群内の点が検証する。
n個分、集約公開鍵と集約キーイメージを計算する。
- ${W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}$
- ${\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}$
${e_1}$ と各rの値を使って
${e'_{i+1} = H(T_c || R || m || r_iG + c_iW_i || r_i \mathbb H(P_{1, i} + c_i \tilde{W}))}$
を計算する。
最終的に計算した ${e'_1}$ が署名値の ${e_1}$ と一致すれば有効な署名。

MLSAGとの違い

↑のCLSAGの署名プロトコルとMLSAGの主な違いは、鍵の集約とLinkability。

鍵の集約

CLSAGでは、各チャレンジを生成する際にd個の鍵セットを単一の鍵として集約することで、元の鍵のマトリクスを一次元にしている。

MLSAGでは、チャレンジの入力値としてd個分 $(r_{j,i}G + e_iP_{j, i}, r_{j, i}\mathbb H(P_{j, i}) + e_iI_j)$ のペア計算する必要があり、dの数が増えるにつれて、計算量も線形増加する。

この部分がCLSAGでは集約鍵 ${W_i}$ と集約キーイメージ ${\tilde{W}}$ を使った単一の ${(r_iG + e_iW_i , r_i \mathbb H(P_{1, i} + e_i \tilde{W}))}$ のペアのみになっている（事前に鍵を集約するための計算はあるけど）。

Linkability

MLSAGの書名スキームではLinkabilityが全てのキーイメージに対して有効になるが、CLSAGの場合この部分に制限が入る。CLSAGではプライマリキーイメージと呼ばれる単一のキーイメージにのみLinkabilityが適用され、残りのキーイメージは補助キーという位置付けになる。

チャレンジの計算の部分で、 ${r_i \mathbb H(P_{1, i} + c_i \tilde{W})}$ と ${P_{1, i}}$ に固定されているのもこのためと思われる。

↑のMLSAGの記事にも書いたが、MoneroのRingCTでは、ワンタイムアドレスによる所有権の証明と、疑似コミットメントの正しさの証明のために２次元の公開鍵セットに対してMLSAGを提供しているが、二重使用に関係するのは前者のみで、前者のキーイメージだけ二重使用のチェックに使われる。そのため、それがプライマリキーイメージとなれば、他のキーイメージにLinkabilityは不要なので、CLSAGの制限は受容可能な条件になる。

なので、各インプット毎にMLSAGやCLSAGを適用してるけど、これをインプット跨いでやろうとすると、CLSAGでは無理になる。

データスペースと計算コストの削減に

d ✕ nのセットに対してMLSAGとCLSAGで署名を生成した場合、

MLSAGの書名データのサイズ：1 + n * dのデータ
CLSAGの書名データのサイズ：1 + nのデータ

nonceとなるrの個数が鍵の集約に伴い✕d必要なくなったので、その分データを削減することができる。また前述したように一度集約鍵の計算をすれば各チャレンジでdセット発生していた楕円曲線の演算をしなくて済むので、その分計算コストが小さくなる。

Develop with pleasure!

福岡でCloudとかBlockchainとか。