Develop with pleasure!

福岡でCloudとかBlockchainとか。

BLS署名を利用した検証可能なwitness encryption

BLS DLC Cryptography

検証可能なwitness encryptionという新しい暗号プリミティブを利用してDLCを構成する新しい提案のペーパーが発表されてたので↓

https://eprint.iacr.org/2022/499.pdf

「II. TECHNICAL OVERVIEW」の内容を見てみた（まだ一部よく分かってない）。

BLS署名

ペーパーではBLS署名を利用したwitness encryptionスキームが提案されているので、まず前提となるBLS署名について。

ペアリング

BLS署名が利用しているペアリングは、同じ素数qを位数とした、2つの加法巡回群 {G_1, G_2} *1と乗法巡回群 {G_T} *2という３つの巡回群について、

{e:G_1 \times G_2 \rightarrow G_T}

という関係が成立する写像のことを指す。つまり {G_1}と {G_2}の各要素を入力として、 {G_T}の要素を出力できることを意味する。

{G_1, G_2}については楕円曲線を利用するため、入力は {G_1, G_2}に対応する楕円曲線上の2つの点で、有限体 {G_T}の要素を出力することになる。このことから楕円ペアリングとも呼ばれる。

また、この時、 {G_1}の楕円曲線の生成元をP、 {G_2}の楕円曲線の生成元をQとした場合、任意の数値a, bが与えられた場合に、

{e(aP, bQ) = e(bP, aQ) = e(P, Q)^{ab}}

が成立することを双線形性と呼ぶ。

BLS署名

ECDSAやSchnorr署名が１つの群、楕円曲線を使ったデジタル署名方式であるのに対し、BLS署名は↑の３つの群の関係を利用したデジタル署名方式になる。

{G_1}の曲線の生成点をP、 {G_1}の曲線の生成点をQとした場合、BLS署名は以下のように作成される。

  • ランダムな数値 {x \in \mathbb Z_q}を選択し、これを秘密鍵とする。対応する公開鍵は {G_2}上の点Y = xQ
  • 署名対象のメッセージをmとした場合、 {\sigma = xH_1(m)}を計算する。ここで、 {H_1}は {G_1}の曲線の要素を出力するハッシュ関数。この {\sigma}が署名で、かつ {G_1}の曲線上の点になる。

※ 署名方式によって公開鍵と署名に使用する際の {G_1, G_2}が逆になる場合もある。

署名の検証は、

  • {e(\sigma, Q) = e(H_1(m), Y)}が成立するか検証する。

{e(\sigma, Q)}は、ペアリングの双線型性から {e(xH_{1}(m), Q) = e(H_{1}(m), Q)^{x} = e(H_{1}(m), xQ) = e(H_{1}(m), Y)}と展開できる。右辺と左辺のペアリング関数の出力結果である有限体 {G_T}の要素が同じであれば検証をパスする。

つまりBLS署名はペアリングの双線形写像の特性を利用して秘密鍵の知識を証明する署名方式であることが分かる。また、ECDSAやSchnorr署名と違って署名の作成に乱数（nonce）を必要としない、決定論的な署名方式。

BLSベースのwitness encryption

検証可能なwitness encryptionに行く前に、前提となるBLSベースのwitness encryptionについて。BLSベースのwitness encryptionというのは、BLS署名を利用した暗号化スキームで、ある公開鍵とメッセージに対応するBLS署名が公開されたら、その署名を使って暗号化されたデータを復号できるというもの。

表記については以下を前提とする。

  • 暗号化対象のメッセージをmとする。
  • 署名に利用する公開鍵の鍵ペアをV = vQとする。vが秘密鍵で、Qは↑の {G_2}の楕円曲線の生成点。
  • 署名対象のメッセージを {\tilde{m}}とする（これは暗号化対象のメッセージではない）。
  • {H_1}を {G_1}の要素（点）を出力するハッシュ関数
  • {H_T}を {G_T}の要素のハッシュ値を計算するハッシュ関数

公開鍵Vとメッセージ {\tilde{m}}に対して有効なBLS署名が提供されたら、メッセージmを復号できる暗号スキーム。

暗号化

以下の手順でメッセージmを暗号化する。

  1. ランダムな値 {r_1 \in \mathbb Z_q}を選択する。
  2. ランダムな値 {r_2 \in G_T}を選択する。
  3. {c_1 = r_1P}とする。
  4. {h = H_T(r_2)}とする。
  5. {c_2 = e(V, H_1(\tilde{m}))^{r_1} \cdot r_2}とする。
  6. {c_3 = h + m}とする。
  7. {c = (c_1, c_2, c_3)}を暗号文とする。

復号化

上記の暗号文は、Vとメッセージ {\tilde{m}}に対するBLS署名 {\tilde{\sigma}(= vH_1(\tilde{m}))}が公開されると、以下の手順で復号できる。

  1. {c = (c_1, c_2, c_3)}をパースする。
  2. {r = c_2 \cdot e(c_1, \tilde{\sigma})^{-1}}を計算する。
  3. {h = H_T(r)}を計算する。
  4. {m = c_3 - h}が復号したメッセージとなる。

↑では、 {\tilde{\sigma} = vH_1(\tilde{m})}であるため、rの計算に出てくる {e(c_1, \tilde{\sigma})^{-1}}は、ペアリング関数の双線形性により、 {e(r_1P, vH_1(\tilde{m}))^{-1} = e(V, H_1(\tilde{m}))^{-r_1}}となる。

そして、 {c_2 = e(V, H_1(\tilde{m}))^{r_1} \cdot r_2}であるため {r = r_2}となり、 {h = H_T(r) = H_T(r_2)}であるため、 {c_3 - h}でメッセージmが入手できると。

復号のためには、h（つまり {r_2}）の値が必要になり、それを算出するためには、 {c_2}内のペアリング関数部分を打ち消す必要があり、それをBLSの双線形性と乱数使ってワークするようにしてるの面白いな。

ということで、このスキームを利用すると、（オラクルなどの）ある公開鍵とあるメッセージに対応した署名を入手すると復号可能な暗号文を作成することができる。

条件付きの支払い

DLCが扱うのは、オラクルが証明可能なイベントの結果を条件に支払いを行う条件付き支払いをサポートするユースケース。

ここでは、アリスがイベントの結果にコミットし、結果がコミットした値と同じ場合に、ボブに対して支払いをす条件付き支払いを考える。DLCでは、アダプター署名を利用して、署名を完成させるために必要なシークレットを復元するアプローチを採っている。

このような条件付き支払いを成立させるためには、

  • イベントの結果がコミットした内容である場合、ボブは必ず署名を入手することができる。
  • イベントの結果がコミットした内容でない場合、ボブが署名を入手することはできない。

ことを保証する必要がある。さらに追加で、オラクルを分散させて一定数のオラクルによる証明が提供された場合に、署名の入手を可能にする（閾値性）を考慮する必要があるが、今回はシンプルにオラクル１人のケースで考える。

検証可能なwitness encryption

↑の新しいソリューションとして提案されているのが検証可能なwitness encryptionという新しい暗号プリミティブを利用する方法。プロトコルの参加者（アリスとボブ）＝ブロックチェーンレイヤーが使用する署名方式はSchnorr署名（もしくはECDSA）で、オラクルの署名方式はBLS署名。まず、前提として、

  • アリスの鍵ペアを {P_A = x_AG}とする。ここで、Gはsecp256k1などの楕円曲線の生成点。
  • オラクルであるオリビアの鍵ペアを {P_O = x_OQ}とする。ここで、Qは上記のペアリングの {G_2}の楕円曲線の生成点。
  • アリスがボブに条件付き支払いをするメッセージ（トランザクション）をmとする。

アリスは秘密鍵 {x_A}を使ってメッセージに署名する。通常のSchnorr署名であれば、

  1. ランダムなnonce kを選択
  2. R = kGとする。
  3. {s = k + H(P_A||R||m)x_A}を計算する。
  4. (R.x, s)が署名

この署名があれば、ボブは資金を手に入れられる。ただ、条件付き支払いなので、アリスは、 {T = tG}を使って、メッセージmに対する事前署名s'を生成する。

  • {s' = k + t + H(m)x_A}

ボブには、(R, s)の代わりにアダプター署名 {(R, s', T)}を送る。アダプター署名を入手したボブは、tさえ分かれば、有効な署名sを導出できる。

その後は、

  1. アリスはtを暗号化した暗号文cをボブに送信する。この暗号化に↑のwitness encryptionを利用する。
  2. オリビアがイベントeをメッセージとして、秘密鍵 {x_O}を使ってBLS署名を作成し、公開する。
  3. ボブはこの署名とcからtを抽出し、s = s' - tをして署名sを手に入れる。

というプロセスを実行するが*3、ここで問題になるのが、ボブがアリスからアダプター署名と暗号文cを受け取った際に、cが暗号化されているので、tが確かに暗号化されているのか検証する術がない点。この検証ができなければ、単にアリスを信頼するしかないということになるのでよろしくない。

そこで、Cut&Chooseという手法を使って、暗号化されたデータが有効なデータ形式であることを検証できるようにしたのが検証可能なwitness encryption。具体的には、アリスが暗号文cを生成する際に、単一のtの暗号文を作るのではなく、以下の手順でλ個の暗号文を作成する（λはセキュリティパラメーター）。

暗号化

t単体を暗号化するのではなく、λ個の乱数 {r_i}（i = 0..λ-1）を生成し、この各 {r_i}を↑のBLSベースのwitness encryptionで暗号化する。そして、このλ個の暗号文とは別に、

  1. 各 {r_i}について {s_i = r_i + t}を計算する（sym-cipherと呼ばれる）。
  2. 各 {r_i}について {R_i = r_iG}を計算する。

アリスは、λ個の暗号文と {R_i}とアダプター署名をボブに送信する。

Cut & Choose

その後、

  1. ボブは受け取ったλ個の暗号文と {R_i}からλ/2個のペアを選択して、選択したペアをアリスに伝える。
  2. アリスは、
    • ボブから受け取ったデータに対応する {r_i}の値とwitness encryptionで暗号化に使用した乱数値をボブに送信する。
    • 選択されなかった残りのλ/2個のペアについて、 {s_i}をボブに送信する。
  3. ボブは、
    • 選択したペアについて、 {r_i}をアリスから受け取り、前に受け取った {R_i}について {r_iG = R_i}が成立するか検証する。さらに、オラクルの公開鍵Vとメッセージ {\tilde{m}}およびアリスから受け取った乱数値を使って {r_i}の暗号化計算を行い、それがアリスが送ってきたものと一致するか検証する。これにより、アリスが送ってきた暗号文はすべて {r_i}が暗号化されているだろうことが検証できる。
    • 選択しなかったペアについて、前に受け取った {R_i}とTに対して、 {s_iG = R_i + T}が成立するか検証する。これによりアリスが作成したデータはすべて {s_i = r_i + t}の形式のデータだろうということが検証できる。

そして、オラクルが署名を公開すれば、アリスが開示しなかった {r_i}も復号できるので、 {t = s_i - r_i}を計算して、witness tを入手できるということみたい。

この辺りが、ペーパーの「II. TECHNICAL OVERVIEW」で説明されてるんだけど、これアリスが {r_i}を開示した方のパターンだと、ボブはsym-cipherもらってないからどうやってt計算するんだろう？この辺り、まだよく理解できてない。

ちなみにペーパーの方は、

  • Fiat-Shamir変換した非対話型への変換
  • Cut&Chooseのバッチ化
  • 分散オラクルの閾値化

など、実用的な課題に対するプロトコルの拡張が続く。

*1:加法巡回群は、群の元がすべて生成元の整数倍で表現できる群

*2:乗法巡回群は、群の元がすべて生成元の冪乗で表現できる群

*3:イベントの結果に両者が合意していれば、tをそのまま渡して終了