紛失通信とVOLE - Develop with pleasure!

3ラウンドECDSA閾値署名プロトコルDKLS23について調べてたいたら、そこで登場する構成要素についてまず理解しておく必要があったので、署名プロトコルにいく前に、まず紛失通信（Oblivious Transfer）とVOLE（Vector Oblivious Linear Evaluation）について理解する。

紛失通信

紛失通信（Oblivious Transfer＝OT）は、送信者が送った情報の内、受信者はその一部の情報しか受信できず、受信したデータがどのデータかを送信者が知ることができないという暗号プロトコル。

たとえば、基本的な1-out-of-2 OTでは、送信者が2つのメッセージ ${m_0, m_1}$ を送信し、受信者はビット ${ b \in \lbrace 0, 1 \rbrace}$ を選択した場合、送信者はbを知らず、受信者は ${m_{b}}$ を知るが ${m_{1 - b}}$ を知らないという状態になる。

この実装方法はいろいろある。たとえばDDHベースのNaor-Pinkas OTだと、送信者をアリス、受信者をボブとした場合、

アリスはランダムな秘密鍵aを選択して、A = aGを計算し、Aをボブに送付
ボブは、ランダムな値rを選択し、選択したビットbが、
- b == 0の場合、R = rGを計算し
- b == 1の場合、R = A + rGを計算し
ボブはRをアリスに送り、 ${K_b = rA}$ とする
アリスは、 ${K_0 = aR}$ と ${K_1 = a (R - A)}$ を計算し、それぞれの鍵を使って２つのメッセージを暗号化する。つまり、 ${c_0 = encrypt(K_0, m_0)}$ 、 ${c_1 = encrpyt(K_1, m_1)}$ 。
アリスは、 ${(c_0, c_1)}$ をボブに送る。
ボブは、を使ってメッセージを復号する。
- b == 0の場合、4でアリスが暗号化に使った ${K_0 = aR = arG}$ は、3のボブの ${K_b = rA = raG}$ と一致するが。一方 ${K_1}$ とは一致しない。
- b == 1の場合、4でアリスが暗号化に使った ${K_1 = a(R - A) = a(A + rG - A) = arG}$ は、3のボブの ${K_b = rA = raG}$ と一致する。一方、 ${K_0}$ とは一致しない。

ボブはECDHにより同じ鍵（ ${K_0 or K_1}$ ）を導出できた場合のみ、共有シークレットを用いて対応するメッセージが復号でき、もう一方のメッセージは復号できない。そしてアリスはbの値を知らないので、ボブがどちらを復号できたかを知ることはできない。

その他のDDHベースの方式だったり、RSAベースだったり、格子暗号ベースなど実装方法はさまざま。

VOLE

続いて、VOLE（Vector Oblivious Linear Evaluation）について。OLEは、二者間でお互いのデータを秘密にしたまま、それらの値の線形演算を行う仕組みで、そのデータがベクトルなのがVOLE。そしてこのVOLEで先程のOTが使われている。

たとえば、アリスがベクトル ${\mathbf{a} = \lbrack a_1, a_2, ..., a_n \rbrack}$ を保持し、ボブがスカラー値bを保持している場合、それらの積 $\mathbf{a} * b = {\lbrack a_1 * b, a_2 * b, ..., a_n * b \rbrack}$ を ${a_i * b = c_i + d_i}$ となるような加法的なシェア ${\mathbf{c} = \lbrack c_1, c_2, ..., c_n \rbrack, \mathbf{d} = \lbrack d_1, d_2, .... d_n \rbrack}$ に変換し、アリスがc、ボブがdをそれぞれ保持するように出力する。

たとえば、a = [5, 7, 3]、b = 13（2進表記だと1101）とすると、

5 * 13 = 65 = c[0] + d[0]
7 * 13 = 91 = c[1] + d[1]
3 * 13 = 39 = c[2] + d[2]

となるように、アリスがcをボブがdを保持するようにする。基本的なVOLEは、

アリスは各要素とビット*1ごとにランダムな値rを準備する。
- 要素5用に、r[0, 0] = 17, r[0,1] = 42, r[0,2] = 31, r[0,3] = 28
- 要素7用に、r[1,0] = 23, r[1,1] = 56, r[1,2] = 14, r[1,3] = 45
- 要素3用に、r[2,0] = 38, r[2,1] = 19, r[2,2] = 62, r[2,3] = 11
アリスは各要素とビット毎にOTメッセージを構築し、各m0, 01をボブに送信
- a[0] = 5のOT
  - ビット0: m0[0,0] = 17, m1[0,0] = 17 + 5*1 = 22
  - ビット1: m0[0,1] = 42, m1[0,1] = 42 + 5*2 = 52
  - ビット2: m0[0,2] = 31, m1[0,2] = 31 + 5*4 = 51
  - ビット3: m0[0,3] = 28, m1[0,3] = 28 + 5*8 = 68
- a[1] = 7のOT
  - ビット0: m0[1,0] = 23, m1[1,0] = 23 + 7*1 = 30
  - ビット1: m0[1,1] = 56, m1[1,1] = 56 + 7*2 = 70
  - ビット2: m0[1,2] = 14, m1[1,2] = 14 + 7*4 = 42
  - ビット3: m0[1,3] = 45, m1[1,3] = 45 + 7*8 = 101
- a[2] = 3のOT
  - ビット0: m0[2,0] = 38, m1[2,0] = 38 + 3*1 = 41
  - ビット1: m0[2,1] = 19, m1[2,1] = 19 + 3*2 = 25
  - ビット2: m0[2,2] = 62, m1[2,2] = 62 + 3*4 = 74
  - ビット3: m0[2,3] = 11, m1[2,3] = 11 + 3*8 = 35
ボブは、ビット[1, 1, 0, 1]に従ってメッセージを選択
- 要素0については
  - ビット0(1): 22を選択
  - ビット1(0): 42を選択
  - ビット2(1): 51を選択
  - ビット3(1): 68を選択
- 要素1については、
  - ビット0(1): 30を選択
  - ビット1(0): 56を選択
  - ビット2(1): 42を選択
  - ビット3(1): 101を選択
- 要素2については、
  - ビット0(1): 41を選択
  - ビット1(0): 19を選択
  - ビット2(1): 74を選択
  - ビット3(1): 35を選択
アリスは以下を最終的なシェアcとする
- c[0] = -(17 + 42 + 31 + 28) = -118
- c[1] = -(23 + 56 + 14 + 45) = -138
- c[2] = -(38 + 19 + 62 + 11) = -130
ボブは以下を最終的なシェアdとする
- d[0] = 22 + 42 + 51 + 68 = 183
- d[1] = 30 + 56 + 42 + 101 = 229
- d[2] = 41 + 19 + 74 + 35 = 169

をそれぞれ得る。実際に

c[0] + d[0] = -118 + 183 = 65 = 5 * 13
c[1] + d[1] = -138 + 229 = 91 = 7 * 13
c[2] + d[2] = -130 + 169 = 39 = 3 * 13

となっている。どうしてこういう結果になるかというと、例えば要素0について考えるた場合、ボブが実際に受け取ったメッセージは、（22, 42, 51, 68）で

d[0] = 22 + 42 + 51 + 68
     = (17+5) + 42 + (31+20) + (28+40)
     = (17+42+31+28) + (5+0+20+40)
     = 118 + (5 * 2^1 + 0 + 5 * 2^2 + 5 * 2^3)
     = 118 + 65
     = 118 + 5 * 13

そしてアリスの加法シェアは

c[0] = -118

アリスが送信するメッセージm0, m1について、m0はアリスがランダムに選択した値、m1はそれにアリスが保持する値×2ⁱが加算された値になっている。
アリスの加法シェアは、アリスがランダムに選択した値を打ち消すための合算値になっている
ボブが選択した値のビットが立っている値のみ、アリスが保持する値×2ⁱが加算されている。
以上から、c[0] + d[0]を計算するとランダム値が相殺され、両者が保持する値の積が得られる。

↑のような仕組みで、乗算を加法シェアに変換することができる。これによりGG18/20でPaillier暗号を使って行っていたMultiplicative to Additive（MtA）と同じ結果が得られる。

OT拡張

VOLEでは要素数×ビットサイズ分のOTが行われることになるが、DDHベースのOTでそれだけの楕円曲線の演算を行うととてもコスト高になる。それを解消するための仕組みがOT拡張。

通常のOT（基本OTと呼ぶ）をシードとして用意しておき、そこから何百万個でも効率的に生成可能な拡張OTを生成することで、OTの演算コストを削減する。

OT拡張では、さきほどの送信者と受信者の役割を逆転させた基本OTを行う*2。

ボブが、ECDHの準備としてランダムな鍵ペア ${S = y_0G, T = y_1G}$ を用意し、アリスに送信
アリスは、ランダムなビットを選択し、ランダム値xを選択し、
- s == 0の場合は、R = xSとし、
- s == 1の場合は、R = xTとする。
アリスはRをボブに送信し、
ボブは、 ${K_0 = y_0 R}, K_1 = y_1 R$ を計算する。
ボブは、ランダムな対象鍵 ${k_0, k_1}$ を生成し、 ${K_0 = y_0 R}, K_1 = y_1 R$ を使って暗号化する。つまり、 ${c_0 = encrypt(H(K_0), k_0), c_1 = encrypt(H(K_1), k_1)}$ を計算し、アリスに送る。
アリスは、 ${k_0, k_1}$ の内１つを復号する（つまり、基本OTで暗号化されているのは対象鍵）。

この基本OTが終わると必要なbit数分の対象鍵が共有されている状態になる。ボブは両方の対象鍵を持っていて、アリスは片方の対象鍵のみを持っている状態。大事なのはボブがアリスがどっちを持ってるのか知らないこと。

実際には↑の基本OTを必要なbit数（セキュリティパラメーター、論文だと128 bit分）分行う。

基本OTが生成できたら続いて、アリスとボブは、それぞれが保持する鍵をシードとして使って必要なOTの数分、擬似ランダム関数（PRF）を実行する。必要なOTの数が416である場合、

アリスは、セキュリティパラメーター＝128×416のPRFを実行して、128×416の大きな行列を作る。
ボブは各ビットに応じて2つ分鍵を持ってるので、2つの128×416の大きな行列を作ることになる。

続いてアリスは、マスク値としてランダムなビットベクトル（128 bit分）を生成し、↑で生成した各列にマスク値をXORしてマスキングし、マスキングした列をボブに送信する。

そしてアリスは、その後の各OT拡張において、マスク値そのものを1つめの鍵として使い、マスク値を自分の選択ビット列でXORしたものを2つめの鍵として、 ${m_0, m_1}$ を暗号化するのに使う。

このように鍵を導出することで、基本OTでは従来どおりの楕円曲線を使った演算が必要になるけど、OT拡張の計算はPRF、XORおよびハッシュ関数の演算のみで行える。

*1:13は4 bitで表せるため簡易的に書いてるけど実際は256 bitなどの固定長

*2:以下の手順はMasny-Rindal OT