# Generation and Distribution of Quantum Oblivious Keys for Secure Multiparty Computation
## 3 Results and Discussion
### Efficiency  
Complexity-wise, the main problem with public-key based OT protocols is that they require a public/private key generation, encryption, and decryption per transfer. In the case of RSA and ElGamal based algorithms, this has complexity \(O(n^{2.58})\) (where \(N=2^{n}\) is the size of the group), using Karatsuba multiplication and Berett reduction for Euclidian division [38]. Post-quantum protocols are still ongoing optimization, but recent results show RLWE key genereration and encryption in time \(O(n^{2}\log(n))\)[39]. To study the time complexity of the \(\pi_{HOK}\) protocol, consider first the complexity of \(\pi_{COMH}\). It requires two calls of \(H\) and one call of the universal hash family \(\mathbf{F}\), \(\hbar\) bit comparisons (if using the technique proposed in [29] to find the required \(f\)), and one additional evaluation of \(f\). Cryptographic hash functions are designed so that their time complexity is linear on the size of the input, which in this case is \(\ell=4k+2\bar{n}+4\). To compute the universal hashing, the construction in [29] requires \(\bar{n}k\) binary multiplications. Thus, the running time of \(\pi_{COMH}\) is linear on the security parameter \(k\). On the other hand, \(\pi_{QOT}\) has two security parameters: \(n\), associated to the size of the keys used to encrypt the transferred bits, and \(m\), associated to the security of the measurement test done by [PERSON]. The protocol requires \(n+m\) qubit preparations and measurements, \(n+m\) calls of the commitment scheme, and \(n\) bit comparisons. This leads to an overall time complexity of \(O(k(n+m))\) for the \(\pi_{HOK}\) protocol, which is linear in all of its security parameters. In realistic scenarios, however, error correction and privacy amplification must be implemented during the \(\pi_{OK\to OT}\). For the former, LDPC codes [40] or the cascade algorithm [41] can be used, and the latter can be done with universal hashing. For a given channel error parameter, these algorithms have time complexity linear in the size of the input string, which in our case is \(n\). Hence, \(\pi_{HOK}\) stays efficient when considering channel losses and preparation/measurement errors. One of the major bottlenecks in the GMW protocol for SMC is the number of instances of OT required (it is worth noting that GMW uses 1-out-of-4 OT, which can efficiently be obtained from two instances of the 1-out-of-2 OT presented here [42]). A single Advanced Encryption Standard (AES) circuit can be obtained with the order of \(10^{6}\) instances of OT. However, with current solutions, i.e., with computational implementations of OT based on asymmetric classical cryptography, one can generate \(\sim 10^{3}\) secure OTs per second in standard devices [43]. It is possible to use OT extension algorithms to increase its size up to rates of the order of \(10^{6}\) OT per second [3]. Several of such techniques are based on symmetric cryptography primitives [43], such as hash functions, and could also be used to extend the OTs generated by \(\pi_{HOK}\). Due to the popularity of crypto-currencies, fast and efficient hashing machines have recently become more accessible. Dedicated hashing devices are able to compute SHA-256 at rates of \(10^{12}\) hashes per second (see Bifury, Ebit, and WhatsMiner, for example). In addition, existent standard Quantum Key Distribution (QKD) setups can be adapted to implement OKD, since both protocols share the same requirements for the generation and measurement of photons. Notably, QKD setups have already demonstrated secret key rates of the order of \(10^{6}\) bits per second [44; 45; 46; 47; 48]. It is also worth mentioning that, as opposed to QKD, QKD is useful even in the case when [PERSON] and [PERSON] are at the same location. This is because in standard key distribution the parties trust each other and, if at the same location, they can just exchange hard drives with the shared key, whereas when sharing oblivious keys, the parties do not trust each other and need a protocol that enforces security.