# BlackBox Protocols まとめ

https://arxiv.org/pdf/1907.03415.pdf を参照

- $\mathsf{Equality}([ x]^{\mathsf{A}},[ y ]^{\mathsf{A}})$
- $x=y$ の時 $z=1$ であり、それ以外の時 $z=0$ とした時、$[ z ]^{\mathsf{B}}$ を出力する
- $L$ - $\mathsf{OR}$ を用いる時
- 計算量は $O(2^L L)$
- 通信ラウンド数は、$N$ bit の整数を用いる時、$\frac{\lceil \log N \rceil}{\lfloor \log L \rceil}$ラウンドである。
- 通信ラウンド数が3回になるように$L(\leq 9)$ の値を変える
- $\mathsf{BX2A}([ b ]^{\mathsf{B}},[ x]^{\mathsf{A}})$
- $[ bx ]^{\mathsf{A}}$ を出力する。
- 計算量：$O(1)$
- 通信ラウンド：1 回
- $\mathsf{lessthan}([ x ]^{\mathsf{A}},[ y]^{\mathsf{A}})$
- $x<y$ の時 $z=1$ であり、それ以外の時 $z=0$ とした時、$[ z ]^{\mathsf{B}}$ を出力する
- $L$ - $\mathsf{OR}$ を用いる時
- 計算量は $O(2^L L)$
- 通信ラウンド数は、$N$ bit の整数を用いる時、$\frac{\lceil \log N \rceil}{\lfloor \log L \rceil}$ラウンドである。
- 通信ラウンド数が3回になるように$L(\leq 9)$ の値を変える