## 4 Proposed Algorithm
### Oblivious Transfer  
OT is a cryptographic protocol in which a sender transfers one of multiple pieces of information to a receiver without knowing which piece is sent. [PERSON] and [PERSON] [7] introduced a 1-out-of-N OT protocol using a 1-out-of-2 OT as the building block, as shown in Algorithm 1.  
Our objective is to thwart M2 GA attacks, in which fake users deliberately select target keys (or sets of keys) to increase the frequency and mean value of those specific keys. To achieve this, we replace the 1-out-of-\(d\) random sampling of PrivKV with the 1-out-of-\(d\) OT protocol between the user (\(A\) in OT) with \(d\) key-value pairs and the server (\(B\)), which selects one element \(\langle k_{a},v_{a}\rangle\). However, the server cannot perform subsequent perturbation steps, as it must remain unaware of whether the user has key \(k_{a}\) or the private value \(v_{a}\in[0,1]\). Therefore, we rearrange the steps such that users perturb the keys and values before the server randomly selects a key-value pair via OT.  
Algorithm 2 outlines the proposed perturbation process using the OT protocol for sampling. The perturbed key-value pairs are used to estimate the frequency and mean for the keys. With the step reordering, users must perturb key-value pairs for all \(d\) keys, leading to an increased computational cost on the user side by a factor of \(d\). However, we consider this increase in the computational cost to be negligible because the perturbation is lightweight compared to the cryptographic cost of the 1-out-of-\(d\) OT. This algorithm proves robust against poisoning attacks.  
```
Suppose \(A\) has \(N\) messages \(m_{0},\ldots,m_{N}\in\{0,1\}^{n}\), where \(N=2^{\ell}-1\) \(A\) generates \(2\ell\) secret key pairs \((K_{1}^{0},K_{1}^{1}),\ldots,(K_{\ell}^{0},K_{\ell}^{1})\). \(A\) sends to \(B\) the ciphertexts \(C_{0},\ldots,C_{N}\), where \(C_{I}=m_{I}\oplus F_{K_{1}^{I_{1}}}(I)\oplus\cdots\oplus F_{K_{\ell}^{I_{\ell }}}(I)\) and \(I\) is the \(\ell\)-bit string \(I_{1}\ldots I_{\ell}\in\{0,1\}^{2}\) and \(F_{K}\) is a pseudo-random function. \(A\) and \(B\) perform \(\ell\) 1-out-of-2 OT \((K_{i}^{0},K_{i}^{1})\) so that \(B\) learns \(K_{1}^{I_{1}},\ldots,K_{\ell}^{I_{\ell}}\) where \(t\) is the index that \(B\) chooses from \(N\) messages such that \(t=1_{1}\ldots t_{i}\in\{0,1\}^{\ell}\). \(B\) decrypts \(C_{t}\) using \(K_{1}^{I_{1}},\ldots,K_{\ell}^{I_{\ell}}\) to obtain \(m_{t}\).
```  
**Algorithm 1** 1-out-of-\(N\) OT [7]  
**Proposition 1**.: _An M2 GA poisoning attack against the PrivKV scheme with 1-out-of-\(d\) OT for sampling key-value pairs has frequency and the mean gains as large as an RMA poisoning attack has._  
Proof of Proposition.: Using an OT protocol, the fake users in the M2 GA attack are not able to intentionally select the targeted keys. They may craft an arbitrary value but the server can detect invalid pairs other than the valid perturbed pairs \(\langle 0,0\rangle\), \(\langle 1,-1\rangle\), and \(\langle 1,1\rangle\). Therefore, they can prepare the valid perturbed pairs with arbitrary fractions, which is equivalent to an RMA attack. Therefore, the frequency and the mean gains will be less than or equal to those of an RMA attack.  
\begin{table}
\begin{tabular}{l c c} \hline \hline
**Step** & **PrivKV [2]** & **Our Work** \\ \hline
1 Pre-sampling & 1-out-of-\(d\) sampling & – \\ \hline \multirow{2}{*}{2 Perturbing} & Value \(VPP(v,\epsilon_{2})\) & \\  & Key \(RR(k,\epsilon_{1})\) & \\ \hline
3 Post-sampling & – & 1-out-of-\(d\) OT \\ \hline
4 Estimating & MLE & EM \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of defenses approaches.