# Sillcom: A Communication-Efficient Privacy-Preserving Scheme for Indoor Localization
## 5 Sillcom\({}_{3R}\): Basic Design with Three Online Rounds
### Round-Efficient Secure Top-\(k\) Ranking via FSS \(\Pi_{Rank}\)  
An important contribution to the high overhead of nonlinear modules in secure computation is the high round complexity. In particular, when performing a comparison between two \(l\)-bit values, the computation typically involves bit decomposition followed by bitwise comparisons, resulting in \(O(l)\) communication rounds [27; 47]. Although some works use optimized circuits to reduce the number of communication rounds to \(\log l\)[28; 48], the network latency introduced by communication rounds remains significantly higher than the computation time. Additionally, selecting the top-k from \(m\) values requires an efficient organization of comparisons, such as the commonly used binary tree structure for top-1 selection. When communication rounds are the bottleneck, increasing parallelism at the cost of additional computation is a viable optimization strategy. This section focuses on designing a secure ranking protocol that requires only one round of communication to determine the rank of each value in a set, while Section 6.1 will discuss the tradeoff of reducing computation by increasing communication rounds when computation becomes the bottleneck, allowing for adaptation to different application scenarios. [PERSON] et al. proposed a novel approach for secure comparison in the preprocessing model using FSS [44; 45]. Unlike the symmetric structure used for RSS computation in Figures 2 and 3 provides an intuitive illustration of its asymmetric computation structure in a three-party setting: \(P_{2}\) is responsible for generating DDCF keys (a simple variant of DCF keys) during the offline phase and distributing them to \(P_{0}\) and \(P_{1}\). In the online phase, \(P_{0}\) and \(P_{1}\) only require a single round of communication, where each party sends a single message to complete the secure comparison. Building on this foundation, a naive approach is to compare all \(m\) values pairwise, where each value computes its rank by summing the results of the \(m-1\) comparisons involving itself. Figures 4 and 5 provide an intuitive illustration of this process. Taking \(d_{1}\) as an example, it is compared with the other \(m-1\) distance values, and the sum of these comparison results determines its rank in the distance set. Figure 3: FSS-based top-k.  
Figure 2: RSS-based SED. **Discussion. ** The above naive approach requires \(O(m^{2})\) secure comparisons, with a computational cost of \(O(m^{2})\) DDCF key evaluations, which translates to \(O(m^{2}\cdot l)\) PRG invocations. Although the online communication still consists of a single round, since each pairwise DDCF key evaluation requires exchanging one value, both \(P_{0}\) and \(P_{1}\) need to send \(O(m^{2})\) values of length \(l\) bits to each other during the online phase. Reducing Communication to \(\mathcal{O}(n)\)  
To reduce this quadratic communication cost, we adopt optimization from [49]: as illustrated in Figure 5, taking the comparison between \(d_{i}\) and all remaining points as an example, Instead of randomly generating DDCF keys for each comparison, i.e., \(d_{i}\) and \(d_{s}\) where \(s\
eq i\), we first assign a fixed random mask to each distance and then generate the DDCF keys based on the difference between the random masks of each pair of distances \(d_{i}\) and \(d_{s}\). This optimization eliminates the need for sending one element per comparison and reduces communication to just one element for each distance involved in the ranking process. While the resulting pairwise comparisons still require \(O(m^{2})\) DDCF computation, the online communication is significantly reduced from \(O(m^{2})\) to \(O(m)\). Algorithm 2 provides details on secure ranking via FSS. Figure 4: Pairwise comparison. Figure 5: Ranking. ```
0: 2P-ASS shared \(d_{iq}\), \(P_{b}\) holds \(\langle d_{iq}\rangle_{b}\), \(b\in\{0,1\}\), \(i\in[m]\). 0: \(P_{b}\) gets 2P-ASS shared \((\langle rank_{1q}\rangle_{b},\ldots,\langle rank_{mq}\rangle_{b})\), \(rank_{iq}\) denotes rank of \(d_{iq}\).