如何從 n 個 OT 中的 1 個實例生成 2 個 OT 中的 1 個的 logn 實例？
我正在閱讀論文改進的 OT 擴展。作者說，在半誠實模型中，單個實例 $ 1 $ n 個 OT 中的一個可用於生成 $ \log n $ 的實例 $ 1 $ 在……之外 $ 2 $ 舊約。更準確地說，成本 $ \text{OT}{l}^m $ 正好等於成本 $ 1 $ 出於n $ \text{OT}{l\log n}^{m/\log n} $ .
我想知道為什麼會這樣。有這方面的參考嗎？
案例中最容易理解 $ n=2^\ell $ . 假設我們有 $ \ell $ 有兩種長度消息選擇的實例 $ m/\ell $ . 我們寫 $ M_{e,i} $ 為了 $ e $ 消息的選擇 $ i $ 第一個實例（ $ e=0,1 $ 和 $ i=0,\ldots, \ell-1 $ ).
我們現在形成 $ n $ 通過連接消息 $ \ell $ 這些消息。如果位表示 $ j $ 是 $ b_{\ell-1}\cdots b_1b_0 $ 然後 $ j $ 我們的 $ n $ 新消息是 $ M_{b_\ell-1,\ell-1}|\cdots|M_{b_1,1}|M_{b_0,0} $ . 請注意，這些新消息的長度 $ m $ . 要求每個 $ \ell $ 原始 2 個 OT 實例中的 1 個，請求者將 $ \ell $ 數字的位選擇 $ j $ 在區間 $ [0,n) $ 並使用其中的 1 個 $ n $ OT 機制來檢索 $ j $ 我們的第 th 個新消息，它是所需的連接 $ \ell $ 消息。
你可以生成 $ \log n $ 1-of-2 OT 的實例使用一個 $ 1-of-n $ OT 通過執行以下操作。
讓我們修正一些符號。讓 $ x $ 是接收器的選擇指標和 $ r_1, \dots, r_n $ 是來自發送方的輸入，所以在協議結束時接收方得到 $ r_x $ . 注意 $ x $ 有 $ \log n $ 位。
此外，讓輸入為 $ \log n $ 1-of-2 OT 是 $ b_1, \dots, b_{\log n} $ 對於接收器和 $ (m_0^1, m_1^1), \dots, (m_0^{\log n}, m_1^{\log n}) $ 為發件人。
現在接收器只需編碼 $ \log n $ 選擇位 $ b_i $ 進入 $ x $ . 發件人對所有人進行編碼 $ i \in [n] $ , $ r_i = (m_{bit(1,i)}^1 || \dots || m_{bit(\log n,i)}^{\log n}) $ 在哪裡 $ bit(j,i) $ 是個 $ j $ 位分解的第 th 位 $ i $ .