Linkable Spontaneous Anonymous Group（LSAG）リング署名の仕組み

こないだ開催されてたMonero Conference 2019でPedro Moreno-Sanchez*1がMoneroでPayment Channel Networkを実現するためのプロトコルについて発表していた↓

ホワイトペーパーは↓

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

スクリプトもないMoneroでどうやってPayment Channel Networkを構成するのか？気になったので読み始めたら、このホワイトペーパーではMoneroのトランザクションの表現力およびスケーラビリティを向上させるために、新しいリンク可能なリング署名方式＝Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)を提案している。

このDLSAGはリング署名の署名スキームの話。Moneroでは送信者の匿名性を確保するのにリング署名を使っている。リング署名というのはユーザーグループのメンバーによって生成されるデジタル署名の一種で、別の言い方をすると、署名検証の際に単一の公開鍵ではなく、公開鍵のセットに対して署名が有効かどうかをチェックする署名スキームである。その署名が有効であった場合、それが公開鍵のセットの内どの公開鍵に対応した秘密鍵で作られた署名なのかは分からないという仕組みだ。Moneroはこのリングメンバー（公開鍵）を明らかにすることなく残高を証明するのにLSAG（Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups）のマトリクスバージョンであるMLSAGを使用している。

新しい提案のDLSAGの前に、今回はまず基本のLSAGについて理解する。LSAGの仕組みについては、↓のブログが参考になった。

https://joinmarket.me/blog/blog/ring-signatures/

リング署名

リング署名の概要は↑に書いた通りだけど、実際のアプリケーションでリング署名を使用するにあたっては以下の特性が求められる（LSAGのLとS）。

Linkability

最初にLinkabilityについて、一見リンク可能性という言葉は、匿名性を向上させるための仕組みと相反して署名者の特定ができるようなキーワードだが、ここでいうリンクというのはそういう意味ではない。リンク可能なリング署名というのは、ある公開鍵 ${P \in L}$ （Lは公開鍵のセット）があったとして、与えられたメッセージに対して１つのリング署名を作成することができる。そして同じ秘密鍵を使って別のリング署名を作成した場合、この2つのリング署名がリンク可能であるということだ。つまり、この特性を利用すると、各参加者は同じ秘密鍵を使った署名を１回しか作成できないようにすることができる。また、リンク可能であるがそれがどの秘密鍵であるかは分からないための、そのようなケースでも匿名性は維持できる。これはコインの二重使用を制限したり、投票システムにおいて同じ人間が複数回投票するのを防ぐのに適している。

Spontaneity

Spontaneityというのは自発性という意味だ。リング署名ではデコイとなる公開鍵のセットを用意するが、その際にそのデコイの秘密鍵の所有者などグループメンバーとの協力を必要とせずに、署名者自身のみでリング署名を作成できることが必要要件になる。コインを送金する際に誰と協力することもなくデコイのセットをピックアップして送金できる必要があるし、よくある例では、内部告発をする際にグループのメンバーであることだけを明かしたい場合、他のメンバーの協力が必要な署名スキームでは成立しないだろう。

上記のLinkabilityとSpontaneityを備えた署名スキームがLinkable Spontaneous Anonymous Group（LSAG）だ。LSAGはもともと暗号通貨などとは関係なく、2004年にJoseph K. Liu、Victor K. Wei、Duncan S. Wongらによって発表された署名スキームで、電子投票システムでの利用が想定されていた（各人の頭文字からLWWのLSAGと表記される）。

Abe-Ohkubo-Suzukiスキーム

LSAGの具体的なスキームの前に、NTT研究所が2002年に発表したAOS署名スキームについて理解した方が分かりやすい。↑のブログではAOS方式を単純化して説明している。

ここではSchnorr署名の式を利用する。鍵ペア P = xG、nonce R = kGで、Schnorr署名の s = k + H(m || R)x とした場合、署名の検証は

sG = R + H(m || R)P

が成立するか検証する。

このSchnorrの署名検証スキームを利用するにあたって、Rを計算する前にH(m || R)でRを含む値のハッシュ値を知る必要があるが、そのハッシュ値を計算する前にRが必要になるという構成を取る。鶏が先が卵が先か。

サンプルとしてN = 4人のメンバーによるリング署名を想定する。4人の公開鍵のセットを ${P_0, P_1, P_2, P_3}$ とし、そのうち秘密鍵を知っているのは ${P_2 = x_2G}$ のみと仮定する。

${s_0G = R_0 + H(m || R_3)P_0}$
${s_1G = R_1 + H(m || R_0)P_1}$
${s_2G = R_2 + H(m || R_1)P_2}$
${s_3G = R_3 + H(m || R_2)P_3}$

署名の生成

ハッシュを計算する際のRは１つ前のRを参照している。この内 ${P_2}$ の秘密鍵を知っている場合、以下の順序で計算すると、この式を満たす値を計算することができる。

まず ${R_2}$ の離散対数となる ${k_2}$ をランダムに選択する。 ${R_2 = k_2G}$
続いて、またランダムに ${s_3}$ の値を選択する。
${R_3 = s_3G - H(m || R_2)P_3}$ を計算し、 ${s_0}$ をランダムに選択する。
${R_0 = s_0G - H(m || R_3)P_0}$ を計算し、 ${s_1}$ をランダムに選択する。
${R_1 = s_1G - H(m || R_0)P_1}$ を計算する。
最後に ${s_2}$ をランダムではなく、 ${s_2 = k_2 + H(m || R_1)x_2}$ で計算する。

署名の検証

こうして出来た値 ${(e_0 = H(m || R_3), s_0, s_1, s_2, s_3)}$ が署名データとなり、どの秘密鍵を使ったのか明かすことなく、以下の検証ができる。

まず ${e_0, s_0}$ を使って、 ${R_0 = s_0G - e_0P_0}$ を計算する。
あとは順に、 ${e_1 = H(m || R_0), R_1 = s_1G - e_1P_1}$
${e_2 = H(m || R_1), R_2 = s_2G - e_1P_2}$
${e_3 = H(m || R_2), R_3 = s_3G - e_1P_3}$
最後に、 ${e_0 = H(m || R_3)}$ が成立するか検証する。

LWWのLSAG署名スキーム

↑を踏まえた上で、LSAGの署名スキームについて。

まず、署名者はn個の公開鍵のセット ${L = ｛P_0, ..., P_{n-1}｝}$ を選択する。この内、署名者が秘密鍵を持っている公開鍵のインデックスをπとする。続いて、キーイメージとして知られる、特別な新しい種類の曲線上の点を形成する。

${I = x_π ℍ(L)}$

ℍはスカラーではなく曲線上の点を出力するハッシュ関数。実装する方法としては、LのSHA-256ハッシュを取り、その256 bitの数値をsecp256k1のx座標として解釈し、xをインクリメントしながら有効な点(x, y)を見つける。

このキーイメージは署名に含まれるため、公開され誰もが知る値となる。しかし、それがどのインデックスの値で作られたのかは誰も知らない。

LSAGの署名生成

以下の手順で署名を生成する。

ランダムな値 ${k_π}$ を選択する。
πの次のインデックスのハッシュチャレンジを作成する。 ${e_{π+1} = H(m || L || k_πG || k_πℍ(L) || I)}$
ランダムな値 ${s_{π+1}}$ を選択する。
${R_{π+1} = s_{π+1}G - e_{π+1}P_{π+1}}$ および ${R_{π+1}^＊ = s_{π+1}ℍ(L) - e_{π+1}I}$ を計算する。
次のハッシュチャレンジ ${e_{π+2} = H(m || L || R_{π+1} || R_{π+1}^＊ || I)}$ を計算し、続くRおよびR*の計算を残りのインデックス分続ける。インデックス毎にsの値をランダムに選択するが、インデックスπの場合だけは ${s_π = k_π + e_πx_π}$ とする。
そして署名値 ${σ_L(m) = (s_0, ..., s_{n-1}, e_0, I)}$ ができあがる。

公開するハッシュチャレンジは１つのみで、他のチャレンジはそれから決定論的に生成されるのはLWWのスキームと変わらない。LSAGの場合、加えて、キーイメージIを署名の一部として公開する。

LSAGの署名検証

公開鍵のセットLと、メッセージmおよび署名 ${σ_L(m) = (s_0, ..., s_{n-1}, e_0, I)}$ が与えられると、以下の手順で署名を検証する。

${R_0 = s_0G - e_0P_0}$ および ${R^＊_0 = s_0ℍ(L) - e_0I}$ を計算し、それを使って、 ${e_1 = H(m || L || R_0 || R^＊_0 || I)}$ を計算する。
${e_0}$ を計算するまで、この計算を続けて、 ${e_0 = H(m || L || R_{n-1} || R^＊_{n-1} || I)}$ が成立するか検証し、成立したら有効な署名となる。

Adam Backが提案したLSAGの修正

LWWのLSAGではキーイメージは ${I = x_π ℍ(L)}$ と、保持する秘密鍵と公開鍵のセットから計算されていた。このためこのキーイメージを署名に添付してLinkabilityによりチェックできるのは、

同じ公開鍵セットを使った異なるLSAG署名が複数ある場合、それらが同じ秘密鍵により署名されているかどうか

である。つまり公開鍵セットが異なると、キーイメージも異なる。そのため、Moneroのような送信者が任意の公開鍵のセットを選択できるケースにおいては、二重使用をチェックできない。

2015年、Adam Backが提案したのはLWWのLSAGの以下の点を変更する↓

まずキーイメージを ${I = x_π ℍ(P_π)}$ とする。公開鍵のセットLではなく、秘密鍵 ${x_π}$ に対応する ${P_π}$ を使って生成する。
πの次のインデックスのハッシュチャレンジの作成はLの部分が ${P_π}$ になりIも含めなくなる→ ${e_{π+1} = H(m || L || k_πG || k_πℍ(P_π))}$
${R_{π+1} = s_{π+1}G - e_{π+1}P_{π+1}}$ の計算は変わらないが、 ${R_{π+1}^＊ = s_{π+1}ℍ(P_{π+1}) - e_{π+1}I}$ はLの部分が変わる。
次のハッシュチャレンジもLとIがなくなり、 ${e_{π+2} = H(m || R_{π+1} || R_{π+1}^＊ )}$ 。

他はLWWと同様。

↑のようにキーイメージが公開鍵のセットLに関係なく、使用するキーに固定されるので、Linkabilityのチェックの際に、公開鍵セットが異なる複数のリング署名が与えられても、署名に使った秘密鍵は同じであれば、それをチェックでき、Moneroのようなトランザクション毎に公開鍵セットが変わるようなケースにおける二重使用のチェックが可能になる。

実際にMoneroで使われているリング署名の仕組みはもう少し複雑で、Multilayered Linkable Spontaneous Anonymous Group Signatures（MLSAG）と呼ばれる署名スキームを使っている。これはMoneroがコインの量を秘匿するRing CTプロトコルを導入した際に一緒に導入された。MLSAGと他のリング署名の主な違いはMのマルチレイヤーの部分だ。n個の鍵のリング署名の代わりに、MLSAGはn個のキーベクトルのセットにリング署名を使用する。そのため2つのレイヤーというか次元ができ、そのためマルチレイヤーと呼ばれみたい。

とLSAGの仕組みが分かってきたので、次回はもともと読む予定だったDLSAGの内容を見ていきたい。

*1:2018年のScaling BitcoinではMulti Hop Locksの提案していた

Develop with pleasure!

福岡でCloudとかBlockchainとか。