隨機 2 加 1 加 1 加 2 加 1
上週我在我的硬體中遇到了這個問題：
讓 $ OT^m $ 表示 1-out-of-2 不經意轉移 $ m $ 位輸入。
讓 $ RandOT^m $ 表示以下原語：
- 發送者的輸入由兩個 m 位字元串組成， $ x_0, x_1 $ .
- 接收器沒有輸入。
- 在協議結束時，接收方學習 $ (b,x_b) $ , 對於隨機選擇的 $ b $ 在 $ {0,1} $ , 並且一無所知 $ x_{1-b} $ . 發件人甚麼也學不到。（注意 $ b $ 必須隨機選擇，伺服器和伺服器都不能選擇 $ b $ ).
對於半誠實的情況，顯示以下兩個縮減。
- 可以構造 $ RandOT^1 $ 從 $ OT^2 $ .
- 可以構造 $ OT^1 $ 從 $ RandOT^1 $ .
我很容易解決了第一個問題，但我想不出解決第二個問題的方法。
我們建構 $ OT^1 $ 從 $ RandOT^1 $ 如下。說，發件人（S）有消息 $ m_0, m_1 $ 接收器 (R) 有選擇位 $ c $ . 即，R需要學習 $ m_c $ . 現在我們首先執行隨機 OT。S現在有隨機 $ x_0, x_1 $ R有 $ x_b,b $ . 現在的想法是讓 S 以某種方式 OTP $ m_c $ 和 $ x_b $ 和 $ m_{c \oplus 1} $ 和 $ x_{b \oplus 1} $ 並將這些值發送給 R。
為此，R 發送 $ d = b \oplus c $ 到 S（請注意，這會將 c 隱藏為 OTP）。S 然後發送 $ (y_0, y_1) = (x_{d} \oplus m_0, x_{d \oplus 1} \oplus m_1) $ 到 R。請注意，我們可以寫 $ y_i = x_{d \oplus i} \oplus m_i $ . R 然後發現 $ m_c = y_c \oplus x_b $ . 筆記， $ y_c = y_{d \oplus b} = x_{d \oplus d \oplus b} \oplus m_c = x_b \oplus m_c $ ，因此我們得到正確的結果。另請注意，R 不學習 $ m_{c \oplus 1} $ 因為它是 OTP 的 $ x_{b \oplus 1} $ .
我只是偶然發現了這個問題，發現它很有趣。由於沒有人發布答案，我想通過把我的想法扔在那裡來幫助讓事情順利進行。這不是一個答案。
- 發送方生成隨機的 1 位密鑰 $ K_0, K_1 $ 並將它們輸入 $ OT^1 $ .
- 接收者向發送者報告他是否收到了“正確”的密鑰（ $ K_0 $ 如果他想接收消息 0， $ K_1 $ 如果他想接收消息 1)。
- 如果否，則返回 1。
- 如果是，則發送方對兩條消息進行加密並將密文發送給接收方。 $ C_i = x_i \oplus K_i $ 為了 $ i \in {0, 1} $ .
- 接收方解密所需的消息： $ x_s = C_s \oplus K_s $ 在哪裡 $ s \in {0, 1} $ 是接收器的選擇輸入。
接收者無法了解有關未選擇字元串的任何資訊，因為 $ K_0 $ 和 $ K_1 $ 是獨立選擇的。
無法保證該算法會在有限的時間內停止。