# 不經意傳輸（Oblivious Transfer, OT）
不經意傳輸是一種兩方安全計算協議（Two-Party Computation）。發送者（Sender擁有一組數據，接收者（Receiver選擇其中一項進行接收。協議保證接收者能且僅能收到他選擇的那一項數據，同時發送者不知道接收者具體選擇了哪一項

OT想解決的問題：如何在保護接收者意圖（選擇了什麼）與保護發送者隱私（未被選擇的數據不洩漏）的前提下交換資訊

## OT的核心
OT通常以 $OT_k^N$ 表示，意即從$N$個輸入中選擇 $k$ 個。最基礎的模型為1-out-of-2 OT($OT_1^2$)。一個標準的 $OT_1^2$ 協議包含兩個參與者與以下階段：
1. 輸入（Inputs）：發送者$S$擁有兩個消息 $(m_0, m_1)$，接收者 $R$ 擁有一個選擇位元 $\sigma \in \{0, 1\}$
1. 傳輸（Transfer）：雙方執行交互協議
1. 輸出（Outputs）：接收者$R$得到 $m_\sigma$；發送者$S$什麼都沒得到（Output is $\bot$）

以$OT_1^2$為例的抽象流程：
1. 發送者 $S$ 生成公鑰或相關參數傳送給 $R$
1. 接收者 $R$ 根據選擇位元 $\sigma$ 生成加密的查詢$Q$傳送給 $S$。此查詢對於 $S$ 來說是盲（Blind）的
1. 發送者 $S$ 利用 $Q$ 對 $m_0$ 和 $m_1$ 分別進行處理，產生 $c_0, c_1$ 回傳給$R$
1. 接收者 $R$ 利用私鑰資訊解密 $c_\sigma$ 得到 $m_\sigma$

過程中 $R$ 無法解密 $m_{1-\sigma}$，且 $S$ 無法分辨 $R$ 到底選擇了0還是1

## OT的性質
**正確性（Correctness）**
如果發送者與接收者都誠實執行協議，對於任意的輸入 $(m_0, m_1)$ 和 $\sigma$，接收者最終輸出的結果必然是 $m_\sigma$。即 $Output_R = m_\sigma$ 恆成立

**安全性（Security）**
OT的安全性主要包含兩個面向（Privacy）：
1. 接收者隱私（Receiver Privacy）：
發送者無法從協議過程中區分接收者的選擇$\sigma$。即對於發送者而言，$\sigma=0$與$\sigma=1$的視圖（View）是計算上不可區分的（Computationally Indistinguishable）
1. 發送者隱私（Sender Privacy）：
接收者除了 $m_\sigma$ 之外，無法獲得關於 $m_{1-\sigma}$ 的任何資訊

**安全性模型分類**
1. 信息論安全（Information Theoretic Security）：
即使攻擊者擁有無限計算能力也無法破解。但在標準模型下這通常需要假設噪聲信道
1. 計算安全（Computational Security）：
基於密碼學困難假設（如 DDH, RSA, Factoring）。Naor-Pinkas 論文即是探討在此模型下的高效構建

## OT的運作機制
計算安全的OT協議通常建立在公鑰密碼學的困難問題上。以基於離散對數（Discrete Logarithm）的機制為例：
**密鑰盲化（Key Blinding）：**
* 機制：接收者生成兩個公鑰 $PK_0, PK_1$。其中一個是他知道私鑰的（對應 $\sigma$），另一個是他不知道私鑰的（隨機生成或由發送者參數推導，確保無法解密）
* 隱匿性：發送者看到的 $PK_0, PK_1$ 在分佈上看起來是一樣的，無法分辨哪一個是接收者真正持有的

**雙重加密傳輸：**
* 機制：發送者使用 $PK_0$ 加密 $m_0$，使用 $PK_1$ 加密 $m_1$
* 結果：接收者只能用手中的私鑰解密其中一個密文，另一個密文因為沒有對應私鑰，在計算上無法解密

**隨機預言機與優化（Random Oracle & Optimization）：**
* 為了提升效率，現代OT（如Naor-Pinkas）常結合對稱加密。使用公鑰操作交換種子（Seed），再用種子作為密鑰對大數據進行對稱加密，減少昂貴的公鑰運算

## OT的限制
OT是安全多方計算（MPC）的基礎（如用於Yao's Garbled Circuits），但存在以下成本與限制：
**計算成本（Computational Overhead）**
OT涉及公鑰密碼學操作（Exponentiation），運算速度遠慢於對稱加密。若是傳輸大量數據，直接使用公鑰 OT會非常慢

**通信開銷（Communication Complexity）**
即使接收者只想要其中1個，但發送者總需要傳送所有候選數據的密文（例如傳送$N$個密文），導致通信量至少是$O(N)$

**擴展性問題（OT Extension）**
基礎OT無法直接大量併發使用。解決方法是使用OT Extension技術，利用少量（如128次）基礎公鑰OT作為種子，配合快速的哈希函數與對稱加密，擴展出數百萬次OT

## 常見OT協議與分類
| 協議類型 | 定義 | 特點 | 適用場景 |
| -------- | -------- | -------- | -------- |
| 1-out-of-2 OT ($OT_1^2$) | 最基本的OT | 從兩個消息中選一個 | 混淆電路（Garbled Circuits）的輸入導線 |
| 1-out-of-N OT ($OT_1^N$) | 從N個中選一個 | 通信複雜度通常隨N線性增長 | 私有信息檢索（PIR）、資料庫查詢 |
| k-out-of-N OT ($OT_k^N$) | 從N個中選k個 | 允許批量選擇，Naor-Pinkas 提出了比重複k次更高效的解法 | 批量數據檢索 |
| Adaptive OT | 自適應 OT | 接收者可以分次進行查詢，後一次的選擇可以依賴前一次的結果 | 多輪交互式計算 |

## 參考資料
1. [OT（Oblivious Transfer，不经意传输）协议详解](https://zhuanlan.zhihu.com/p/424202269)
2. [Computationally Secure Oblivious Transfer](https://link.springer.com/content/pdf/10.1007/s00145-004-0102-6.pdf)
> 隨手筆記，有錯誤或需要補充的部分歡迎討論，~~還請鞭小力一點~~