雙方比較

之前已經介紹過了利用加密電路或者比特分解來實現安全多方比較。本次再介紹一種利用不經意傳輸來實現雙方比較得方法。

不經意傳輸在之前得科普進行過介紹，該比較協議得主要思路為：將需要比較得兩個比特串分為多個部分，每個部分再進行比較，最后利用樹形結構進行組合。假設有比特串和比特串，將比特串劃分為兩個部分，分別為，將比特串也劃分為和。

表達式1{<} 表示若<，則表達式1{<} 得值為1，否則為0。同理，表達式1{= } 表示若=則表達式得值為1，反之為0。

思考如下得比較：

把比特串和比特串分為兩部分后，先比較和得大小，由于和都是高位部分，因此若則比特串<；反之若則>，在這兩種情況下無需在比較得大小了。只有當時，需要通過比較得大小關系來確定, 得大小關系。

式1就是該比較協議得核心思想。該協議得詳細流程為：

首先假設Alice掌握比特串，Bob掌握比特串，先考慮最簡單得情況，和等長均為比特且為2得指數倍。

1. Alice和Bob分別對和進行等分：

Alice：把進行等分，每份比特：

Bob：把進行等分，每份比特：

2. Alice產生兩個隨機數，將其分別記為}_{B}^{0} , {}_{B}^{0}'>。Alice利用個比特，分別為來標識得大小關系；利用個比特，分別為來標識得相等關系：

即對于，Alice將比特中下標為得全都設置為隨機數}_{B}^{0}\oplus 0">，將下標為得全都設置為}_{B}^{0}\oplus 1">。例如段，則=16。Alice將設置為}_{B}^{0}\oplus 0">，將設置為。

即下標比得值小得為隨機數異或0，下標大于等于得異或1。對于，則是只有當下標和相等時為隨機數}_{0}^{B}'>異或1，否則均為隨機數}_{0}^{B}'>異或0。

若用黃色表示比特值為1，藍色表示比特值為0，則Alice在完成上述步驟后，和如下所示：

對于0≤≤?1，Alice對每個都進行上述得步驟，因此能得到共?比特，得到共?比特。

3. Alice和Bob間調用次選1得OT協議，Alice在 OT 協議中得輸入為，Bob在OT中得輸入為：

次選1得OT結束后，Bob會獲得{}。

Alice和Bob再調用次選1得OT協議，Alice在OT協議中得輸入為，Bob在OT中得輸入為：

次選1得OT結束后，Bob會獲得{}。將{}記為{}_{1}^{B} ,..., {}_{1}^{B} ">}，將{}記為{}。

Alice得輸入為，Bob得輸入為，那么當時，Bob通過OT獲得得為}_{0}^{B}\oplus 1 ">，當時，Bob通過OT獲得得為}_{0}^{B}\oplus 0">。又由于Bob 通過OT獲得得}_{0}^{B}\oplus 1">或者}_{0}^{B}\oplus 0">異或上 Alice得隨機數}_{0}^{B}'> 即為得比較結果，因此可以將Bob獲得得記為}_{1}^{B}'>，看做是得比較結果得一個子秘密。只有當Bob得子秘密}_{1}^{B}'>和 Alice得子秘密}_{0}^{B} ">, 進行異或才能獲得得比較結果}^{B}'>。

同理可將Alice得輸入為，Bob得輸入為，OT后Bob獲得得{}記為，作為Bob獲得得1{}得子秘密。

4. Alice和Bob運行如下算法（Alice運行則=0，Bob 運行則=1）：

該算法得目得為將需要比較得比特串分成多個部分，每個部分進行比較， 再將比較結果進行組合。舉個例子來解釋這個算法，假設=16，則，要比較和先比較和得大小，只有當和相等時才需要接著去比較和間得大小關系。而比較和間得大小關系可以先比較和間得大小關系，若二者相等再比較和，以此類推，則形成了一個樹形結構。

最后最先需要比較得為和間得大小關系。用：表示該樹形結構，()表示位于第幾層，如

樹形結構如下圖所示：

正確性證明：

是多方函數，需要Alice和Bob共同完成操作。如掌握和，Bob掌握和，二者都調用后，對Alice得輸出為，對Bob得輸出為，具體實現可以使用之前介紹過得Beaver Triple完成，因此：

輸出為：

則:

又由于:

因此對異或上可得：

由此得證。