# Universally Composable Oblivious Transfer with Low Communication
## 4 UC-Secure 1-out-of-2 OT Protocol
### Random Oblivious Transfer
#### 4.1.2 The Privacy of the Receiver  
In the protocol, the R only sends \((B,\,c)\) to the S, but the S can get \((v_{1},v_{2},sk_{1},sk_{2})\) through \((B,c)\). Therefore, it is required that no information about \(\sigma\) can be obtained from \((B,c)\) and \((v_{1},v_{2},sk_{1},sk_{2})\) to ensure that the R's privacy is not compromised. The following theorem is used to prove the privacy security of the R.  
**Theorem 1**. : _Suppose no probabilistic polynomial time adversary can guess \(\sigma\) with non-negligible probability from \((B,c)\) and \((v_{1},v_{2},sk_{1},sk_{2})\). In that case, it means that the [PERSON]'s privacy is guaranteed during the execution. Then, it is necessary to prove the following three points:_  
1. \(B_{\sigma=0}\) _and_ \(B_{\sigma=1}\) _are indistinguishable._
2. \(c\) _and_ \(\sigma\) _are independent of each other._
3. \(v_{1}\) _and_ \(v_{2}\) _are indistinguishable._  
Proof of Theorem 1.:
1. Assuming that the adversary corrupts S, the corrupted sender is denoted as S\({}^{*}\). It follows that \(b^{\prime}=bits\big{(}a^{T}s^{\prime}+h,\in_{q},\in_{p}\big{)}\) and \(bits\big{(}u,\in_{q},\in_{p}\big{)}\) are indistinguishable because of the Mod-LWR assumption, where \(u\leftarrow\mathcal{U}\Big{(}R_{q}^{l\times 1}\Big{)}\). Besides, the difference between \(B_{\sigma=0}\) and \(B_{\sigma=1}\) is \(T\), where \(T\gets U\Big{(}R_{q}^{l\times 1}\Big{)}\). Hence, \(B_{\sigma=0}=b^{\prime}\) and \(B_{\sigma=1}=b^{\prime}+T\) are indistinguishable. 2. As \(c\) sent to the sender is computed by the receiver and the sender can obtain \(\sigma\) from \(c\). Assuming the S\({}^{*}\) can get \(s^{\prime}\) from \(c\), then the S\({}^{*}\) can distinguish between \(B_{\sigma=0}\) and \(B_{\sigma=1}\), and finally get \(\sigma\). Therefore, it is necessary to prove that \(c\) and \(\sigma\) are independent of each other by showing that the possibility of obtaining \(\sigma\) from \(c\) is negligible. \begin{table}
\begin{tabular}{l l} \hline \hline
**Alice** & \multicolumn{1}{c}{**Bob**} \\ \hline
**Parameter Generation:** & \\ \(seed_{a}\leftarrow(U\big{(}0,1)^{256}\big{)}\) & \(a\gets gen(seed_{a})\) \\ \(a\leftarrow gen(seed_{a})\) & \(s^{\prime}\leftarrow\beta_{\mu}\Big{(}R_{q}^{l\times 1}\Big{)}\) \\ \(s\leftarrow\beta_{\mu}\Big{(}R_{q}^{l\times 1}\Big{)}\) & \(\overset{seed_{a},\mathcal{A},T}{\rightarrow}\) & \(b^{\prime}=bits\big{(}a^{T}s^{\prime}+h,\in_{q},\in_{p}\big{)}\) \\ \(T\gets U\Big{(}R_{q}^{l\times 1}\Big{)}\) & & \(v^{\prime}=A^{T}bits\big{(}s^{\prime},\in_{p},\in_{p}\big{)}+h_{1}\) \\ \(A=bits\big{(}as+h,\in_{q},\in_{p}\big{)}\gets R_{q}^{l\times 1}\) & & \(c=bits\big{(}v^{\prime},\in_{p}-1,\in_{l}\big{)}\) \\ \hline
**Make a choice:** & \(\overset{B,c}{\leftarrow}\) & \(if(\sigma=0)\)\(B=b^{\prime}\) \\  & & \(if(\sigma=1)\)\(B=b^{\prime}+T\) \\ \hline
**Key derivation:** & \\ \(v_{1}=B^{T}bits\big{(}s,\in_{p},\in_{p}\big{)}+h_{1}\) & & \\ \(v_{2}=(B-T)^{T}bits\big{(}s,\in_{p},\in_{p}\big{)}+h_{1}\) & & \\ \(sk_{1}=bits\Big{(}v_{1}-2\epsilon^{\varepsilon_{p}-\varepsilon_{i}-1}c+h_{2}, \in_{p},1\big{)}\) & & \\ \(sk_{2}=bits\Big{(}v_{2}-2\epsilon^{\varepsilon_{p}-\varepsilon_{i}-1}c+h_{2}, \in_{p},1\big{)}\) & & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Random oblivious transfer protocol. The first step is to prove indistinguishability. It can be shown by the Mod-LWR problem that \(c\) is indistinguishable from uniformly distributed sampling; thus, \(\sigma\) cannot be obtained directly from \(c\). The second step is to prove independence. A series of games shown in Table 3 show that \(c\) cannot help the S\({}^{*}\) to distinguish \(B_{\sigma=0}\) from \(B_{\sigma=1}\). Let \(X_{i}\) denote the event that the S\({}^{*}\) guesses on \(n\) in the \(i-th\) game.