# On the Security of Offloading Post-Processing
## 3 Outsourcing Information Reconciliation
### Multiparty Computation-Based Outsourcing
The bit-flipping algorithm is a non-probabilistic hard-input hard-output decoding algorithm and works on the Tanner graph representation of the code. The messages passing back and forth are all binary. The main structure of the BF algorithm is similar for all variants. In the first step, the variable nodes send their current values to the check nodes. Then, the check nodes compute their values and feed back the results to the adjacent variable nodes, signaling if the check is valid. After each variable node receives the check bits from all connected check nodes, the current guess for the code word is updated. Different approaches exist to update the variable nodes, and to the best of our knowledge, no optimized codes or methods for the particular case of QKD have been studied or analyzed. Therefore, we selected one of the most prominent solutions--[PERSON]'s algorithm [35]--to demonstrate feasibility and applied it to (non-optimized) codes available for BP algorithms. We developed an MPC version for the bit flip-decoding algorithm which is shown in Figure 1, where \([[\cdot]]\) denotes variables which are processed in the encrypted domain and are therefore kept confidential. The implementation assures that the code word itself as well as related information is only kept in a secret shared form among the parties and never revealed during computation. On a high level, the algorithm performs message passing in a Tanner graph defined by the parity check matrix \(H\), with binary variables represented by public integers with values zero and one. We encoded the bits on integers because ITS-MPCs work on algebraic circuits, with additions being compared almost for free and multiplications requiring interactions between nodes. This allowed us to quickly count the number of ones in a vector of bits and also enabled exclusivity over vectors by reducing modulo two after summing them up. The algorithm comprises four major steps which are iteratively repeated until a valid code word is found or the maximum number of iterations is reached:  
* In the first step, the variable nodes pass their values to the check nodes, where they are combined to compute the check value, which is zero when the check is fulfilled and one if not. * In the second step, the values of the check nodes are passed back to the variable nodes, where they are aggregated (i.e., the number of check nodes not satisfied is counted for each variable node). * Thirdly, the algorithm terminates if all checknodes are zero. * Finally, the algorithm computes which variable nodes have to be flipped. Here, we used [PERSON]'s algorithm B Gallager (1976) in our implementation, which basically compares the counts computed in step two against a threshold value to decide which bits are flipped. Although the threshold value for comparison is public, this comparison has to be carried out obliviously to protect the variable node state as well as the bit flip information. From a performance point of view, all steps except the last one are extremely fast in MPCs, given that additions are only local operations and do not need any communication among the MPC peers, and the reductions in step one can be performed in parallel. The oblivious comparisons necessary to decide for each bit (if it has to be flipped or not) are the costly operations and limit the throughput in MPC implementation. However, modern highly optimized MPC systems such as MP-SPDZ ([[https://github.com/data61/MP-SPDZ](https://github.com/data61/MP-SPDZ)]([https://github.com/data61/MP-SPDZ](https://github.com/data61/MP-SPDZ)) (accessed on 23 January 2023)) are able to achieve good performance even for this task, as the results in Table 1 show. These results indicate that MPC-based real-time decoding for QKD is possible. Clearly, to achieve the best performance, optimized codes must be studied and designed in tandem with MPC protocols [PERSON] _et al._ (2018). In addition, BP-based alternatives to sum-product decoding should be studied to see how fast MPC versions of belief propagation methods can be pushed.