亂碼電路和不經意傳輸之間的本質區別是什麼？
根據文獻（https://en.wikipedia.org/wiki/Garled_circuit），Oblivious Transfer 允許 A 方持有一個函式 $ f $ 與持有指數i的乙方共同計算價值 $ f(i) $ 在保護隱私的同時 $ f $ 和 $ i $ .
在我看來，OT 足以歸檔亂碼電路的加密功能：啟用兩方安全計算，其中兩個不信任方可以共同評估他們私人輸入的函式，比如函式 $ f(a,b) $ 帶輸入 $ a $ 和 $ b $ .
請注意 $ f(a,b) $ 可以被視為一個函式 $ f_a(b) $ , 因此使用 OT with function 立即對其進行評估 $ f_a() $ 和索引 $ b $ . 如果只想進行私有聯合計算，似乎沒有必要像在亂碼電路中那樣加密然後置換整個真值表。
我有什麼誤解嗎？ Garbled Circuit 與 Oblivious Transfer 相比有哪些本質區別（或優勢）？
感謝您的詳細回复@Mikero
在我之前的想法中，函式的聯合計算 $ f(a,b) $ 大輸入 $ b\in{1,…,2^k} $ 可以通過以下方式有效實施 $ k $ 使用 1-out-of-2 不經意轉移。
例如，Alice 和 Bob 兩百萬的錢 $ b\in{1,…,2^k} $ 想看看誰更富有。通過二分法的思想，200 萬人首先使用不經意的轉賬協議，根據他們的錢的大小進行粗略的比較。也就是說，他們使用 1-out-of-2 OT 來聯合評估一個簡單的函式 $ f_{2^{k-1}}\ (a, b) $ ，其中a（或b）=0表示Alice（或Bob）有錢 $ <2^{k-1} $ , a (或 b) =1 表示 Alice (或 Bob) 有錢 $ \geq2^{k-1} $ . 功能 $ f_{2^{k-1}\ }(a, b)=0,1,2,3 $ 對於的情況 $ a,b<2^{k-1} $ , $ a,b\geq2^{k-1} $ , $ a<2^{k-1}, b\geq2^{k-1} $ ， 和 $ a\geq2^{k-1}, b<2^{k-1} $ ， 分別。現在，如果他們的錢可以分開 $ 2^{k-1} $ ，則任務完成；否則，由 OT 對函式進行下一輪粗略比較 $ f_{2^{k-2} }\ $ 或者 $ f_{2^{k-1}\ + 2^{k-2}}\ $ 根據結果 $ {0,1,2,3} $ 最後的舊約。
但是，為了保持他們金錢數量的隱私（例如，< $ 2^{k-1} $ 或者 $ \geq2^{k-1} $ )，似乎有必要對每個 OT 的結果進行加密。也許這就是亂碼電路方法所做的。因此，在我的簡單理解中，“亂碼電路 = 不經意的傳輸 + 簡單邏輯電路的斷路功能”。亂碼電路相對於不經意傳輸的主要優勢不在於功能，而在於通信和計算的複雜性。
有沒有更詳細的參考比較OT和亂碼電路的複雜度
我在該頁面上沒有看到以您描述的方式描述不經意轉移的任何地方。
不經意轉移：
- 愛麗絲拿著兩根弦 $ x_0, x_1 $
- 鮑勃拿著一點 $ b $
- 鮑勃學習 $ x_b $ 但一無所知 $ x_{1-b} $
- 愛麗絲什麼都不知道 $ b $
亂碼電路：
- 當 Alice弄亂布爾電路時 $ f $ ，她獲得了大量密文 $ F $ (“the garbled circuit”) and she also learns two keys (labels) on each wire of the circuit. On wire # $ i $ she learns $ W_i^0 $ which represents false on that wire, and $ W_i^1 $ which represents true on that wire.
- If Bob knows the garbled circuit $ F $ and for each input wire $ i $ of the circuit he knows exactly one of $ { W_i^0, W_i^1} $ then he can evaluate the garbled circuit to learn exactly one label on each wire of the circuit (not just the input wires). He learns the “correct” wire label (i.e., the one corresponding to the behavior of $ f $ ) on each wire, according to which of the input labels he starts with.
- As Bob evaluates the garbled circuit, he does not learn whether he is holding $ W_i^0 $ or $ W_i^1 $ for any wire $ i $ . In other words, he doesn’t know whether any wire in the circuit carries true or false. He evaluates the circuit “blindly.”
If Alice & Bob want to evaluate a function using garbled circuits, then Alice garbles the circuit and sends the garbled circuit $ F $ to Bob. But Bob needs to also learn, for each input wire $ i $ in the circuit, exactly one of $ { W_i^0, W_i^1} $ . Both Alice & Bob have inputs to this computation.
- If wire # $ i $ is one of Alice’s input wires, then she can just send the “correct” one from $ {W_i^0, W_i^1} $ , since she knows both of these and she knows her input bit on that wire.
- If wire # $ i $ is one of Bob’s input wires, there must be a way for Bob to choose to learn exactly one of $ {W_i^0, W_i^1} $ . Since Bob chooses between these values according to his private input, Alice should not learn which one he chose. Oblivious transfer is used for exactly this step. For input wire # $ i $ belonging to Bob’s input, Alice provides $ W_i^0 $ and $ W_i^1 $ to an instance of oblivious transfer, and Bob chooses which of these to learn.
There are variants of oblivious transfer where Alice has $ N $ strings and Bob chooses one of them to learn. If Alice & Bob want to compute a very simple function $ f(a,b) $ , where there are only $ N $ possible inputs for Bob ( $ b \in {1, \ldots, N} $ ), then yes they can use oblivious transfer to compute the function directly like you suggest, without any garbled circuits. Alice uses $ f(a,1), f(a,2), \ldots, f(a,N) $ as inputs to oblivious transfer. Bob chooses to learn the $ b $ th of these, which is $ f(a,b) $ .
This only works when $ N $ is very small, because it requires communication and computation proportional to $ N $ . Remember that $ N $ is the number of possible inputs for Bob. If there is a circuit where Bob has $ k $ input wires, then he has $ N=2^k $ possible inputs. Hence, usually Bob has too many inputs to use this approach.
Response to edited post:
Your approach for the millionaire’s problem is not exactly clear, so I have to guess at a few things.
It doesn’t work to reveal partial information about the inputs during the protocol. If Alice has input 1, she shouldn’t be able to distinguish between Bob having input 2 vs input $ 2^{20} $ – but these two inputs would look very different if the outputs of the comparisons were revealed in the clear.
With this in mind, you suggest encrypting things somehow. But you are essentially proposing a binary search. A binary search requires you to know the result of the previous comparisons to decide which comparison to make next. If you are encrypting the result of the comparisons then it is not clear how to proceed in the next rounds.
A big problem with your proposal is that it is inherently sequential. The parties can’t know their inputs to the next round until receiving output from the previous round. So for $ k $ comparisons you need $ \Theta(k) $ rounds of communication. Compare this to a GC-based approach which always takes a constant number of communication rounds.
I think you are onto a good conceptual connection, though. Imagine the function $ f $ is very small, so that it’s possible to write down the entire truth table of $ f $ . Let’s say $ f : {1,2,3,4}^2 \to {0,1} $ . Alice chooses random encryption keys $ A_1, \ldots, A_4 $ and $ B_1, \ldots, B_4 $ . She also encrypts the truth table of $ f $ as $$ \textsf{Enc}( A_1 | B_1, f(1,1)), ~~ \textsf{Enc}( A_1 | B_2, f(1,2)), ~~\ldots, \textsf{Enc}( A_i | B_j, f(i,j)), ~~\ldots $$ To evaluate $ f $ on their private inputs, Alice can send all of these ciphertexts to Bob. She can send the correct $ A_i $ value, and they can use 1-out-of-4 OT to let Bob learn the correct $ B_j $ value. Now Bob can decrypt exactly one of these ciphertexts, which will contain the correct output of $ f $ .
Garbled circuits is just what you get when you take this simple construction, but instead of encrypting the final function output, you encrypt keys to another gadget of the same type.