SoftSpokenOT
概要
立ち位置的にはOTの拡張だが、VOLE correlationをバッチしてセットアップすることができる。
SPVOLE->MPVOLEと拡張可能
公開鍵暗号などに頼らなくて良い
シンプルにt回のOTではt個のメッセージしかやりとりできないが、GGM treeと組み合わせると$ 2^t-1個のメッセージのやりとりが可能になる
https://scrapbox.io/files/6773dffe4f2b4c4430a1edee.png
前提知識・building blocks
検証者はどちらのメッセージが選択されたかを知ることなく、証明者から提供された2つのメッセージのうち1つを選択することができるプロトコル
LWEと同様の問題により安全性を提供する
correlationsの生成にかかるOTの線形コストをlogarithmicに削減するためにGGMを応用している
2PCプロトコルの一種。VOLE-based ZKで注目されている
SPVOLE(Single Point VOLE)
commitment protocolのsetup phaseにおける、Packing VOLEを構成する手法？
batchは関係なく、一つのvoleを作るためにランダムなNこのleafをおいている？
setupではrandomに生成することがキモでありPRFを土台にしている？OTに恣意性はないんだっけ？
ここで各vectorの長さはnとする
Prover
vector $ \vec{f}\in{F_2^{128}}
vector $ \vec{e}\in{F_2}
vector $ \vec{e}には1である要素が一つあり、他は全て0である
Verifer
global key $ \Delta\in{F_2^{128}}
vector $ \vec{s}\in{F_2^{128}}
これらは LPNの$ \vec{f} = \vec{s}-\Delta \cdot \vec{e}を満たす。
https://scrapbox.io/files/6773dab1dbb1864e0ff070ba.png
VOLEはOTによって相関数に線形なコストで直接実現できるが、後述するGGMの助けを借りれば、コストを相関数の対数に減らすことができる。
GGM treeとOTを組み合わせて、SPVOLEを構成していこう
https://scrapbox.io/files/6768b6c1a31985538c534247.png
評価点$ \Deltaを知られることなく、それ以外のfを知らせることができた
Pは$ \Deltaの位置は分かるがその値自体はわからない？
$ \alpha = 5を二進数に置き換えて反転させると、010になる。
これは目的のleaf($ \alpha = 5)までのpathを意味する。
first OT:
verifier constructs $ m_0=k_1and $ m_1=k_2
Prover choice bit$ \alpha[2]=0 and recive $ m_0=k_1
この時点でPrioverは緑の木に関して全て把握している
$ f[0] || f[1] || f[2] || f[3]
second OT:
verifier constructs $ m_0=k_3+k_5and$ m_1=k_4+k_6
Prover choice bit $ \alpha[1]=1 and recive $ m_1=k_4+k_6
Proverはすでに$ k_4について知っているので、$ k_6 = m_1 – k_4を得る。
この時点でPrioverは緑と黄色の部分に関して全て把握している。
$ f[0] || f[1] || f[2] || f[3] ||f[6]||f[7]]
final OT:
verifier constructs $ m_0= \vec{s}[0]+\vec{s}[2]+\vec{s}[4]+\vec{s}[6] and $ m_1= \vec{s}[1]+\vec{s}[3]+\vec{s}[5]+\vec{s}[7]
prover choce $ \alpha[0]=0 and recieve $ m_0= \vec{s}[0]+\vec{s}[2]+\vec{s}[4]+\vec{s}[6]
Proverはすでに$ f\lbrack0\rbrack,f[2] , f[6] について知っているので、$ \vec{f}[4] = \vec{f}[0]- \vec{f}[2]- \vec{f}[6] を得る。
最終的にProverは$ \alpha =5 以外の$ f[0] || f[1] || f[2] || f[3] ||f[4] || f[6]||f[7]] を得る
次にVerifier はProverに$ \vec{f}[a]=\vec{s}[a]+\Delta を$ \alphaを知らずに計算する必要がある。
Proverは$ \vec{s} 8個の要素をsum upし$ \Deltaを足し合わせれば良い。
結局全てのleafを知るのに、なんでこんなめんどいことやってんだっけ？
そこで、Verifierは$ c=\Delta+\sum_{j\in{\lbrack0,7\rbrack}} \vec{s}\lbrack{j}\rbrackを計算しProverに送る。
これを元に既知の要素をsubstructすることで$ \vec{f}[\alpha]= \vec{f}[5] = c-\sum_{j\neq5} \vec{f}[j] を得る
これでProver は$ \vec{f}を獲得したので、
Prover
vector $ \vec{f}\in{F_2^{128}}
vector $ \vec{e}\in{F_2}
vector $ \vec{e}には1である要素が一つあり、他は全て0である
Verifer
global key $ \Delta\in{F_2^{128}}
vector $ \vec{s}\in{F_2^{128}}
$ \vec{f} = \vec{s}-\Delta \cdot \vec{e}を満たす。
$ \vec{e}[i]= \dbinom{1,i=\alpha}{0, i\neq \alpha}
これにより、通常のVOLE constructionにおけるcommunication cost O(n)からO(log n)に落とすことができた。
これをどうやってVOLEにconvertするのか？
$ \vec{s}=\vec{f}+\Delta \cdot\vec{e}
MPVOLE(Multi Point VOLE) & LPM Bootstrapping
SPVOLEをt回 invokeすることで、N MPVOLEが構成される。
これにより、communication cost はO(log n)からO(t log N / t)に減少する。
Step1, Step2までのモチベーションはSetup phaseにおけるcommunication costを低減させることだった。
Step3ではvectorのlengthをh->Nに拡張することをモチxベとしている。
https://scrapbox.io/files/6773dffe4f2b4c4430a1edee.pnghttps://scrapbox.io/files/6775230a2bef1cad045d6c9b.png
VOLE設定におけるコストを低減することを目指しており、初回以降の拡張でOTを繰り返さなくても済むようにする。これにより計算コストと通信コストがさらに削減される。
制約: VOLEで扱える相関データの最大数 N は、システムの利用可能なメモリ量に制限される
プロセス:
1.ブートストラッピングの過程で、まず $ N’ = N + h の VOLE correlationデータを生成する
2.そのうちの h を次回の拡張用に保存し、新しいデータ（u や e）の生成に使用する
LPNをvectorのextentionとして使うのは違和感がある
右のLPNの関係から左のVOLEに変換すれば、相手に知られずにVOLE Correlationが作成できる。
Step1,Step2でProverとVeriferiが得た要素を元にそれぞれ$ \vec{y}と$ \vec{x}、$ \vec{z}を生成する。ここで$ AはPublicであり、$ \vec{v},\vec{u},\vec{w}はsecretとしてLPN仮定に基づいて保護される。
これらとVerifierの$ \DeltaでVOLE Correlationになる。
https://scrapbox.io/files/677539cbc5af69579aa1abac.png
$ A:N \times h
$ u,v,w: h
$ s,e,f: N
参考