# A Secure Median Implementation for the Federated Secure Computing Architecture
## 2 Preliminaries
### Protocol for the kth-Ranked Element  
[PERSON] et al. [10] propose a multiparty protocol for computing the exact median that requires only a logarithmic number of secure computations for the size \(M\) of the domain \(\mathbb{F}\) from which the data set \(D\) is drawn. Each party initializes the search range to the range of \(D\) and the candidate value to the midpoint of the range. Parties iteratively refine the search range based on securely aggregated counts of elements in their datasets less than or equal to the candidate value. This process continues until the range collapses to the true \(k\)th-ranked value. The protocol ensures data confidentiality and scalability in MPC scenarios and is presented in Algorithm 1.  
This minimizes the cryptographic overhead to just two comparisons and two secure summations per round. Achieving this is possible through widely applicable protocols, like additive secret sharing. Essentially, additive secret sharing divides shares of a secret among participants, enabling them to calculate sums without disclosing the actual values [22]. Consequently, they can obtain the desired result while safeguarding individual contributions. Algorithm 2 provides a concrete exemplary protocol demonstrating how parties collaboratively compute the sum of their private values while preserving privacy using random numbers.  
Figure 1: Illustration of Secure Multiparty Computation (MPC) —A set of two or more parties participate in an encrypted peer-to-peer network to jointly compute a function without revealing each party’s private input. This ensures that each party only receives the exact result of that function and nothing more.  
```
1:Input: Data \(D_{1},\ldots,D_{m}\) held by parties \(P_{1},\ldots,P_{m}\), rank \(k\), sizes of each \(D_{i}\), data range \([\alpha,\beta]\) Output:\(k\)th-ranked element in \(D_{1}\cup\cdots\cup D_{m}\).
2:Initialize \(a\leftarrow\alpha\), \(b\leftarrow\beta\), \(n\leftarrow\sum|D_{i}|\)
3:repeat
4: Each \(P_{i}\):
5:\(\mu\leftarrow\lceil\frac{(a+b)}{2}\rceil\)
6:\(l_{i}\leftarrow\lceil\{x\mid x\in D_{i},x<\mu\}\rfloor\), \(g_{i}\leftarrow\lfloor\{x\mid x\in D_{i},x>\mu\}\rfloor\)
7: Secure computation between parties:
8:if\(\sum_{i=1}^{m}l_{i}\leq k-1\) and \(\sum g_{i}\leq n-k\)then
9:done
10:endif
11:if\(\sum_{i=1}^{m}l_{i}\geq k\)then
12:\(b\leftarrow\mu-1\)
13:endif
14:endif
15:if\(\sum_{i=1}^{m}\mathcal{S}_{i}\geq n-k+1\)then
16:\(a\leftarrow\mu+1\)
17:endif
18:until done
```  
**Algorithm 1** Secure \(k\)th-Ranked Element ([PERSON] et al. [10], Protocol 3)  
```
1:Input: Values \(a_{i}\) held by parties \(P_{1},\ldots,P_{m}\) Output: Sum of the values \(\sum_{i=1}^{m}a_{i}\).
2:Distribute random numbers between parties:
3:for\(i=1\) to \(m\)do
4: Party \(P_{i}\) generates a random number \(r_{i}\).
5:if\(i=m\)then
6: Party \(P_{i}\) sends \(r_{i}\) to \(P_{1}\).
7:else
8: Party \(P_{i}\) sends \(r_{i}\) to \(P_{i+1}\).
9:endif
10:endfor
11:Add randomness:
12:for\(i=1\) to \(m\)do
13:if\(i=1\)then
14: Party \(P_{1}\) computes adjusted value \(a_{1}^{\prime}\gets a_{1}-r_{1}+r_{m}\).
15:else
16: Party \(P_{i}\) computes adjusted value \(a_{i}^{\prime}\gets a_{i}-r_{i}+r_{i-1}\).
17:endif
18:endfor
19:Parties share adjusted values \(a_{i}^{\prime}\) and calculate: \(sum\leftarrow\sum_{i=1}^{m}a_{i}^{\prime}\)
20:return\(sum\)
```  
**Algorithm 2** Secure summation protocol utilizing additive secret sharing