# Generation and Distribution of Quantum Oblivious Keys for Secure Multiparty Computation
## 2 Methods
### Oblivious Key Distribution  
In order to make the quantum implementation of OT more practical during SMC we introduce the concept of oblivious keys. The protocol \(\pi_{QOT}\) can be separated in two phases: the _Oblivious Key Distribution phase_ which consists of steps 1 to 7 and forms the \(\pi_{QKD}\) subprotocol, and the Oblivious Transfer phase which takes steps 8 to 10 and we denote as the \(\pi_{OK\to OT}\) subprotocol. Note that after step 7 of \(\pi_{QOT}\) the subsets \(I_{0}\), \(I_{1}\) have not been revealed to [PERSON], so she has no information yet on how the correlated and uncorrelated bits between \(k\) and \(\tilde{k}\) are distributed (recall that \(k\) and \(\tilde{k}\) are the result of removing the tested bits from the strings \(s\) and \(\tilde{s}\) respectively). On the other hand, after receiving [PERSON]'s preparation bases, [PERSON] does know the distribution of correlated and uncorrelated bits between \(k\) and \(\tilde{k}\), which is recorded in the string \(x\) (\(x_{i}=0\) if \(a_{i}=\tilde{a}_{i}\), otherwise \(x_{i}=1\)). Note that until step 7 of the protocol all computation is independent of the input bits \(e_{0},e_{1},c\). Furthermore, from step 8, only the strings \(k,\tilde{k}\), and \(x\) are needed to finish the protocol (in addition to the input bits). We call these three strings collectively an oblivious key, depicted in Figure 3. Formally, let [PERSON] and [PERSON] be two agents. Oblivious Key Distribution (OKD) is a service that outputs to [PERSON] the string \(k=k_{1}k_{2}\ldots k_{\ell}\) and to [PERSON] the string \(\tilde{k}=\tilde{k}_{1}\tilde{k}_{2}\ldots\tilde{k}_{\ell}\) together with the bit string \(x=x_{1}x_{2}\ldots x_{\ell}\), such that \(k_{i}=\tilde{k}_{i}\) whenever \(x_{i}=0\) and \(\tilde{k}_{i}\) does not give any information about \(k\) whenever \(x_{i}=1\). All of the strings are chosen at random for every invocation of the service. A pair \((k,(\tilde{k},x))\) distributed as above is what we call an oblivious key pair. [PERSON], who knows \(k\), is referred to as the sender, and [PERSON], who holds \(\tilde{k}\) and \(x\), is the receiver. In other words, when two parties share an oblivious key, the sender holds a string \(k\), while the receiver has only approximately half of the bits of \(k\), but knows exactly which of those bits he has. When two parties have previously shared an oblivious key pair, they can securely produce OT by performing the steps \(\pi_{OK\to OT}\) of \(\pi_{QOT}\). This is significantly faster than current implementations of OT without any previous shared resource and does not require quantum communication during SMC. Note that the agents can perform, previously or concurrently, an OKD protocol to share a sufficiently large oblivious key, which can be then partitioned and used to perform as many instances of OT as needed for SMC. Fortunately, it is possible to achieve fast oblivious key exchange if the parties have access to fast and reliable quantum communications and classical commitments. In order to use this QOT protocol, the commitment scheme must be instantiated. Consider the commitment protocol \(\pi_{COMH}\) shown in Figure 4, first introduced by [PERSON] and [PERSON]. It uses a combination of universal and cryptographic hashing, the former to ensure statistical uniformity on the commitments, and the latter to hide the  
Figure 3: Oblivious keys. [PERSON] has the string \(k\) and [PERSON] the string \(\tilde{k}\). For each party, the boxes in the left and right represent the bits of their string associated to the indices \(i\) for which \(x_{i}\) equals 0 (**left box**) or 1 (**right box**). [PERSON] knows the entire key, [PERSON] only knows half of the key, but [PERSON] does not know which half [PERSON] knows. committed message.