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

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

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

１．アリスはランダムな秘密鍵aを選択して、A = aGを計算し、Aをボブに送付

２．ボブは、ランダムな値rを選択し、選択したビットbが、
○b == 0の場合、R = rGを計算し
○b == 1の場合、R = A + rGを計算し

３．ボブはRをアリスに送り、Kb=rAとする

４，アリスは、K0=aRとK1=a(R−A)を計算し、それぞれの鍵を使って２つのメッセージを暗号化する。つまり、c0=encrypt(K0,m0)、c1=encrpyt(K1,m1)。

５．アリスは、(c0,c1)をボブに送る。

６．ボブは、Kb=rAを使ってメッセージを復号する。
○b == 0の場合、4でアリスが暗号化に使ったK0=aR=arGは、3のボブのKb=rA=raGと一致するが。一方K1とは一致しない。
○b == 1の場合、4でアリスが暗号化に使ったK1=a(R−A)=a(A+rG−A)=arGは、3のボブのKb=rA=raGと一致する。一方、K0とは一致しない。

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

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

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

たとえば、アリスがベクトル a=[a1,a2,…,an]を保持し、ボブがスカラー値bを保持している場合、それらの積 a∗b=[a1∗b,a2∗b,…,an∗b]を ai∗b=ci+diとなるような加法的なシェアc=[c1,c2,…,cn],d=[d1,d2,….dn]に変換し、アリスが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）で

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

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

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

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

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

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

１．ボブが、ECDHの準備としてランダムな鍵ペアS=y0G,T=y1Gを用意し、アリスに送信

２．アリスは、ランダムなビットs∈{0,1}を選択し、ランダム値xを選択し、
○s == 0の場合は、R = xSとし、
○s == 1の場合は、R = xTとする。

３．アリスはRをボブに送信し、

４．ボブは、K0=y0R,K1=y1Rを計算する。

５．ボブは、ランダムな対象鍵k0,k1を生成し、K0=y0R,K1=y1Rを使って暗号化する。つまり、0=encrypt(H(K0),k0),c1=encrypt(H(K1),k1)を計算し、アリスに送る。

６．アリスは、k0,k1の内１つを復号する（つまり、基本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つめの鍵として、m0,m1
を暗号化するのに使う。

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

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

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

ブログの元記事はこちらから

当HPでは数式などが正しく表記されていない可能性がございます。
ぜひ元記事をご確認ください。
https://techmedia-think.hatenablog.com/entry/2025/06/17/231835

募集職種：

ブロックチェーンエンジニア
アプリケーションエンジニア
インフラ・保守エンジニア
プロジェクトマネージャー
フィールドセールス

Chaintopeで働く魅力：

最先端のブロックチェーン技術に触れる機会
リモートワークやフレックスタイム制による柔軟な働き方
専門性の高いチームとの協働
ブロックチェーン技術に情熱を持つあなたのスキルを、私たちのチームで活かしませんか？
詳細は、採用情報をご覧ください。

https://www.chaintope.com/recruit/