Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Authors: Guopeng Lin
Ruisheng Zhou
Shuyu Chen
Weili Han
Jin Tan
Wenjing Fang
Lei Wang
Tao Wei
Venue: ICML 2025 poster (2025)
Keywords: Privacy Preservation
K-Nearest Neighbors
Primary area: social_aspects->privacy

Abstract: K-nearest neighbors (KNN) classification plays a significant role in various applications due to its interpretability. The accuracy of KNN classification relies heavily on large amounts of high-quality data, which are often distributed among different parties and contain sensitive information. Dozens of privacy-preserving frameworks have been proposed for performing KNN classification with data from different parties while preserving data privacy. However, existing privacy-preserving frameworks for KNN classification demonstrate communication inefficiency in the online phase due to two main issues: (1) They suffer from huge communication size for secure Euclidean square distance computations. (2) They require numerous communication rounds to select the $k$ nearest neighbors.  In this paper, we present $\texttt{Kona}$, an efficient privacy-preserving framework for KNN classification. We resolve the above communication issues by (1) designing novel Euclidean triples, which eliminate the online communication for secure Euclidean square distance computations,  (2) proposing a divide-and-conquer bubble protocol, which significantly reduces communication rounds for selecting the $k$ nearest neighbors. Experimental results on eight real-world datasets demonstrate that $\texttt{Kona}$ significantly outperforms the state-of-the-art framework by  $1.1\times \sim 3121.2\times$ in communication size, $16.7\times \sim 5783.2\times$ in communication rounds, and $1.1\times \sim 232.6\times$ in runtime.

Kona: An Efficient
frame- Privacy-Preservatio Framework for KNN Classification by Communication Optimization
Guopeng Lin
Ruisheng Zhou'
Shuyu Chen
Weili Han
Jin Tan
Wenjing Fang? 2
Lei Wang? Tao Wei?
Abstract
Kataria & Singh, 2013) has drawn significant attention for its interpretability. The intuitive nature of KNN classifi- cation, which makes predictions based on the similarity of samples, allows users to easily understand and trust its outcomes, fostering its widespread adoption across diverse domains. For instance, in medical diagnosis, KNN can as- sist in identifying diseases based patient data (Ali et al., 2020; Wang et al., 2020), while in recommendation systems, it can tailor suggestions to user preferences (Adeniyi et al., 2016; Singh et al., 2020).
K-nearest neighbors (KNN) classification plays significant role in various applications due to its interpretability. The aceuracy of KNN classi- fication relies heavily on large amounts of high- quality data, which are often distributed among different parties and contain sensitive informa- tion. Dozens of privacy-preservinn frameworks have been proposed for performing KNN classifi- cation with data from different parties while pre- serving data privacy. However, existing privacy- preserving frameworks for KNN classification demonstrate communication inefficiency in the online phase due to two main issues: (1) They suffer from huge communication size for secure Euclidean square distance computations. (2) They require numerous communication rounds to se- lect the k nearest neighbors. In this paper, we present Kona, efficient framework for KNN classification. We resolve the above communication issues by (1) designing novel Euclidean triples, which eliminate the on- line communication for secure Euclidean square distance computations, (2) proposing a divide- and-conquer bubble protocol, which significantly reduces communication rounds for selecting the k nearest neighbors. Experimental results eight real-world datasets demonstrate that Kona sig- nificantly outperforms the state-of-the-art frame- work by 1.1x ~ 3121.2x in communication size, 16.7x ~ 5783.2x communication rounds, and 1.1x 232.6x runtime.
The accuracy of KNN classification heavily relies on large amounts high-quality data. However, in practical sce- narios, high-quality data are usually distributed across dif- ferent parties, and cannot be directly aggregated due to the sensitive nature of the data and regulatory restrictions. For instance, patient records are usually distributed across different hospitals or clinics and cannot be directly aggre- gated due to striet privacy regulations (e.g. GDPR (Voigt & Von dem Bussche, 2017)). As result, collecting suffi- cient high-quality data to obtain accurate KNN classification faces significant challenges.
To address the need for aggregating sufficient high-quality data to perform accurate KNN classification, numerous privacy-preserving frameworks (Sun & Yang. 2020; Li et al., 2023; Wu et al., 2019; Wong et al., 2009; Cui et al., 2020; Liu et al., 2019) for KNN classification have been proposed. These frameworks typically employ multi-party computa- tion (MPC) techniques, such secret sharing homomor- phic encryption, to keep the sensitive data private throughout KNN classification. Therefore, these frameworks can utilize data from different parties to improve the accuracy of KNN classification while preserving data privacy, which broadens the applicability of KNN in real-world scenarios.
1. Introduction
Despite the potential of these works for KNN classification, they still suffer from sig- nificant online communication inefficiency, which impedes their practical deployment. The online communication in- efficiency arises from two primary issues: (1) Existing frameworks suffer from huge communication size for se- cure Euclidean square distance computations. Euclidean square distance is commonly used metric to measure the similarity between samples in KNN classification. For
As fundamental machine-learning technique, K-nearest neighbors (KNN) classification (Mucherino al., 2009;
Fudan Univeristy, Shanghai, China Ant Group, Shanghai, China. Correspondence to: Weili Han <wIhan @ www.a..dd.cc. en?.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
dataset containing n samples, performing a KNN classifi- cation requires computing the Euclidean square distance n times. Existing frameworks, such (Li et al., 2023; Liu et al., 2019; Sun & Yang, 2020). necessitate communicat- ing secret shares or encrypted elements for each distance computation, which makes these frameworks inefficient, es- pecially for large-scale datasets. (2) Existing frameworks suffer from numerous communication rounds for k nearest neighbors selection. Selecting the k nearest neighbors is critical step during KNN classification. Existing frame- works, such as (Li et al., 2023; Liu et al., 2019), employ sequential bubble protocols to select the k nearest neigh- bors, which requires (kk) communication rounds. The numerous communication rounds make these frameworks extremely inefficient, especially in wide-area network envi- ronments.
O log These two optimizations significantly enhance the efficiency of Kona, making Kona a promising solution for large-scale and real-world applications.
We summarize the main contributions in Kona as follows:
We design novel Euclidean triples that enable secure Euclidean square distance computations without any online communication.
We present divide-anddconquee bubble protocol sig- nificantly reduce the communication rounds required for selecting the & nearest neighbors.
As is shown in Table 1, our proposed framework Kona sig- nificantly reduces both online communication size and com- munication rounds compared to the state-of-the frame- work, SecKNN (Li et al., 2023). Specifically, in terms of Euclidean square distance computation, Kona does not re- quire any online communication, while SecKNN requires (nm) communication size. In terms of k-nearest neigh- bor selection, Kona requires only O log n) communica- tion rounds, while SecKNN requires O(k)) communication rounds. In terms of total communication overhead for KNN classification, Kona achieves reductions in both communi- cation size and rounds compared to SecKNN.
Table 1. Online communication complexity comparison between Kona and the state-of the art framework ScCKNN (Li al., 2023). Here, is the number of samples, is the number of attributes, and & is the number of neighbors used the KNN classification.
Kona
SecKNN
Euclidean Square
Size
0(nm)
Distance Computation
Rounds
0(1)
K-nearest
Size
O(kn)
((kn)
Neighbor Selection
Rounds
O(klogn)
((km)
Total
Size
((kn)
O(nm + km)
To further demonstrate the efficiency of Kona ', we com- pare the performance of Kona against SecKNN with eight real-world datasets, which encompass various domains and data characteristics. The experimental results demonstrate that Kona significantly outperforms SecKNN by 1.1x ~ x in communication size, 16.7 ~ 5783.2 in com- munication rounds, and 1.1x ~ 232.6x in runtime. These results show that Kona is much more practical and scalable for real-world privacy-preseree KNN classification tasks.
Rounds
O(klogn)
O(kn)
In this paper, we present Kona, an efficient privacy- preserving framework for KNN classification. We resolve the aforementioned communication issues through two op- timizations: (I) We propose novel Euclidean triples that enable secure Fuclidean square distance computations with- out any online communication. We observe that although existing frameworks leverage random vectors (e.g. random pairs (Li et al., 2023)) generated in the offline phase to reduce the online communication size, these vectors are not fully compatible with Euclidean square distance com- putations. Inspired by the inpeeedndeennd but function- dependent technique (Ben-Efraim et al., 2019), we tailor our Euclidean triples specifically for Euclidean square distance computations. This design eliminates online communication and does not introduce additional offline communication overhead compared to the state-of-the et al., 2023). (2) We present a wwvide-and-conque bubble protocol to significantly reduce the communication rounds required to select the k nearest neighbors. We observe that the sequential bubble protocol incurs numerous communi- cation rounds because secure comparisons are performed one by one. However, secure comparisons are largely in- dependent of each other. Thus, our soride-and-conquee bubble protocol performs most secure comparisons in par- allel, reducing the communication rounds from (km) to
2. Preliminaries
2.1. K-Nearest Neighbors Classification
KNN classification is a non-pann non-parametric, instance- based learning method that infers the class of a new sample by examining its similarity to known samples. Specifically, as is shown in Algorithm 1, KNN classification inputs dataset of samples, each with m attributes and an asso- ciated class label, and new sample ă to be classified, an integer is representing the number of neighbors. To classify a, KNN classification first computes the distance between ă and every sample 7, in the dataset (Line 1-5). It then selects the samples closest to ă. known as its nearest neighbors (Line 6). Finally, it assigns the class label to ă based on the majority vote among these k neighbors (Line 7). This
framework (Li
We have open-sourced the implementation of Kona http://ghhncccmm///uaa//////////
2

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
straightforward approach makes KNN both conceptually simple and highly interpretable.
x + C.
Constant Multiplication: [>]] = [ * c, such that
In this paper, we measure the similarity between samples by employing the Euclidean square distance, which is widely used in previous studies (Sun & Yang, 2020; Li et al., 2023;
2 = x =r*c.
Share Addition: [=|- [ + [uv]succ
such that z = +
Liu et al., 2019) and is an intuitive metric that is easy to implement and interpret.
Share Multiplication: [z]] [ [v]. such that
2 = I y.
Share Comparison: [| [[æ]] [b]), such that
Algorithm 1 (WN-classff(((2.. k)
1 if a < y, otherwise 2 = 0.
Input: A dataset of n labeled samples (Zi, Mi W==0- where o; is
an m-dimensional attribute vector and y, is its class label: new attrihute vector á to be classified; and an integer k representing the number neighbors.
Share Equality Check: [=] ([=] [v]], such that = = 1
if x = y, otherwise 0.
Output: A predicted label 6 for C.
1: Initialize an empty array dis.
Masked Secret Sharing: A secret x is said to be shared to two computation parties Pa and P. by MSS if Pa holds pair (U, [wI[] and P. holds a pair (U, [ul]b), where x U [u] [u][-
2: for i = 0 to -1 de
3: Compute the Euclidean square distance d(d, d.).
4: Append (d(á, H.), ys) to dis.
5: end for
6: Select the & smallest entries from dis and their corresponding labels to form the l nearest neighbors.
Throughout this paper, we use the notation (z) to indicate that æ is shared to the two computation parties P. and P. by using MSS, i.e. (x) = (U, [u]).
7: Let b be the majority label among the nearest neighbors.
8: Return b.
3. Design of Kona
2.2. Multi-Party Computation
3.1. Overview
MPC enables multiple parties to cooperatively compute a function while keeping their input data private. There are several technical routes of MPC, which include homo- morphic encryption-based protocols (Dulek et al., 2016), garbled cireuit-based protocols (Ciampi et al., 2021), and secret sharing-basedd protocols (Ben-Or al., 2019). In this paper, we employ the two-party additive secret sharing (ASS) (Demmler et al., 2015) and the two-party masked secret sharing (MSS) (Ben-Efraim et al., 2019) as the foun- dational techniques of Kona.
Architecture. As is shown in Figure 1, the architecture of Kona consists of an arbitrary number of data owners (each one denoted as DO), an arbitrary number of users (each one denoted as UR), and two computation parties (denoted as Pa and Pb). Each DO (c.g. a hospital) holds a dataset, such as a small set of patient records, and would like to provide KNN classification services with its dataset. Besides, because an individual DO's dataset is often too limited to yield accurate KNN classification results, multiple DOs seek to collaborate while preserving the privacy of their dataset. Meanwhile, each UR holds its own sensitive data, such as an unlabeled medical record, and seeks a KNN classification result while keeping its data private. Pa and P. hold no sensitive data but provide computation resources. Note that the computation parties can also be played by DO or UR if DO UR has enough computation resources.
Additive Secret Sharing: To share a secret x to two com- putation parties (Pa. Pb)) by using ASS, two random values [=l]a and [æ]b are drawn from ring Eza of size 2 such that x = [x]lee + [ι<] o (mod 2*). Then [=]a is distributed to Pa, and [at]| is distributed to Ps. To reconstruct z to a user, each P. (i E {a, b)) sends [=]]s to the user. Then, the user computes x= = [x]a + [ (mod 2²).
Workflow. The workflow of Kona consists of a one-time dataset-share stage, and a KNN-classify stage. In the one- time shtaeet-share stage, each DO secret shares its dataset to Pa and P3 by using MSS. In the KNN-classify stage, each UR first secret shares its sensitive data to Pa and P, using MSS. And then P. and P, securely compute the classifica- tion result for the sensitive data with our proposed protocols, and send the ASS shares of the classification result to UR for reconstruction.
Throughout this paper, we use the notation [>] to indicate that & shared to the two computation parties by using ASS. Besides, we omit "(mod 2* in the following sections for simplicity, since all computations are performed on Ez,..
Let e be a constant value, [x]] and [v]] be two additive secret- shared values. In this paper, we leverage the following basic operations, whose implementation is detailed in the literature (Demmler et al., 2015), of ASS.
Security Model. Kona operates under a semi-honess secu- rity model with dishonest majority. In other words, both
Constant Addition: [>] = [>] + c, such that 2 =
3

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Protocol 1: DatasetShare
Input: DO imputs n samples (Fi, 31 M
Output: {(5)) = (U., [+.D[v
Data Owner
Dataset (
(a
Sensitive Data
User
1: DO shares {v. { by using ASS, so that the com-
putation parties hold [[==]]==0-
2: for i to n in parallel do
Secure Protocols
3: Pa randomly samples [ua]]. and P. randomly
Data Owner
Dutuset
Sensitive Data User
samples [[
4: P. sends [ DO, and P. sends [ū.] to DO.
())
8
5: DO computes U, E. + [4l + [0
6: DO sends U, to Pa and Po. such that Pa holds
Data Owner
Datasct
Sensitive Data User
(z))a (U,, [o] and P. holds (Z.))
Po
(U,, [T.][o).
7: end for
Figure 1. Architecture of Zona.
In the protocol, UR first shares the sample vector ā by MSS (Line 1-3). Then Pa and P. leverage the Euclidean triples to efficiently perform Euclidean square distance computation without incurring online communication overhead (Line 4- 6). Once all distances are computed, Pa and P', apply our proposed DQBubble protocol (shown in protocol 4) to select the k nearest neighbors, i.c. move the i nearest neighbors to the front of the vectors (Line 7-9). Finally, Pa and P. obtain the predicted label [6]] by calling the LabelCompute protocol (shown in Appendix B.1), and then send [b]a and [b] to UR for reconstructing b (Line 10-12).
computation parties will correctly execute our proposed pro- tocols, yet attempt to infer additional information about the URs' data or the DOs' data. Besides, the computation par- ties are assumed not to collude. Additionally, we assume each DO will correctly provide its dataset and each UR will correctly provide its sensitive data.
Data Representation. We assume the DOs hold horizon- tally distributed datasets, i.e. their datasets contain the same attributes but different samples. Each sample in the datasets is represented by an attribute vector 7 of size m and a label y. Besides, the sensitive data held by each UR is also repre- sented by an attribute vector size m. We further discuss how to handle vertically distributed datasets in Section 5.
Protocol 2: KNN-classify
Input: UR inputs sample a. P. and P. inputs [(Z.) (Ü: Ia.)), [vx]]]- and Euclidean triples
3.2. Dataset Share Stage
{1 [0], [[m, where we = (ih - -)
Output: UR obtains the predicted label b.
As is shown in Protocol 1, the DatasetShare protocol inputs DO's dataset ( 8: 3 and outputs secret-shared datasets to Pa and P.. DO first uses ASS to share each label yı to Pa and Po (Line 1). Then, for each feature vector T; DO uses MSS to share it (Line 2-7). Here, we use MSS to share the attribute vectors rather than ASS, because our proposed Euclidean square distance computation protocol relies on it.
1: Pa sends [+], to UR, and P. sends [5] to UR.
2: UR computes V ā + [7]. + [
3: UR sends V P. and Pb. such that P. holds (d),
(V, [.]) and Ps holds (ā), (V, (7)))
4: for = 0 n do
5: [d.] = Euclidean DistideenDDsttoe((aaa (a)).
6: end for
7: for j j= 0 to k do
For simplicity and readability, the DatasetShare protocol considers only one DO. Extending this protocol to support multiple DOs is straightforward: simply execute the pro- tocols independently for each additional DO. Then, let Pa and Ps merge secret-shared datasets from the DOs to get whole dataset.
8: [[d.I]= (v.
DQBubble
([dd))) (1.)))
9: end for
10: [[6] = LabeeComputed [
11: Pa sends [bb] to UR, and Po sends [b]. to UR..
12: UR computes b = [6] [b]a-
3.3. KNN Classify Stage
3.4. Euclidean Square Distance Computation Protocol
As is shown in Protocol 2, the KNN-classify protocol in- puts sample vector ē from UR, and inputs secret-shared attribute vectors, secret-shared labels, and Euclidean triples (introduced in Section 3.4) from Pa and P.. It outputs the predicted label b to UR.
Issue of Existing Methods. Existing methods incur large communication size during the online phase of secure Eu- clidean square distance computations, because they require communicating encrypted elements or secret shares for each

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
distance computation. For example, the method proposed by Sun and Yang (Sun& & Yang, 2020) employs homomorphic encryption to securely compute Euclidean square distance and requires communicating two encrypted vectors for each distance computation. Though the method proposed by Li et al. (Li et al., 2023) leverages ASS shares of random pairs (²) generated in the offline phase to reduce the online communication size, this method still requires communicat- ing secret-shared vector for each distance computation, because the random pairs are not fully compatible with Fuclidean square distance computations.
Protocol 3: EuclideanDistance
Input: (iT = (Ü, [u]]. (ā) = (V, [u]). and |w], where
W = (17 11)².
Output: [d]]. where d - d)².
1: Po computes Id]e = (Ú - v-² - 22( (V] [T].) + [[]]..
2: P. computes [d]e = -2(0 - V] [070) +
[w]s.
the baseline (Li et al., 2023) based homomorphic encryp- tion. We present the generation protocol in Appendix B.3 and the communication analysis in Appendix F.
Main Idea. To accelerate the online phase of secure Eu- clidean square distance computation, we introduce novel Fuclidean triple, which is inspired by the inpu-independent but dunction-dependen technique (Ben-Efrrim et al., 2019) specific function before
3.5.
Bubble Protocol
(generate randomness tailored actual inputs to the function are known). Specifically, an Eu- clidean triple consists of two secret-shared vectors [ and [[] and secret-shared scalar [w]] where each element of and is randomly sampled from Zza, and w = (ū d7? Leveraging this triple, we can compute the ASS shares of Euclidean square distance d (Ø ā)"² without online
Issue of Existing Methods. Existing methods (Li et al., 2023; Liu et al., 2019) require a large number of communi- cation rounds to select the nearest neighbors because they rely on sequential bubble protocols. In these protocols, the nearest neighbor is selected by comparing pairs of elements from the end of the distance list to the front, and swapping elements whenever smaller value appears behind larger one. Since these comparisons are performed sequentially, selecting the nearest neighbor in a list of size I demands (()) communication rounds. This high round complex- ity severely impacts performance, particularly in wide-area network environments.
communication. Let Ū = F + ūī and V = ā J. We have:
d= (o at² = ((Ū ú) (V - 8))²
(Ū 2)² - -2 V) σ) (ū-
= =(Ō 7)² -2ū - V>([.. - -
-2 ([ -b)))) [w] + [w]b
Protocol 4: DQBubble
Input: [[4D]= [[xI]] K-
Since 0 has been obtained in the dataset-share stage, [+] has been obtained from UR (Line in Protocol 2). and the Euclidean triples can be generated in the offline phase, Pa and Ps, can locally compute their ASS shares of d by [d]. (Ū- 12 2(U (I [T]a) + [w]a, and [d] 22 [IT], - (0),) + [w]s.
Output: {[d.]]= {IuD) where dp is the smallest
element in {d: and each y/ remains paired with its original d,.
while > 1 do
2: mid = L.
3: for g 0==10 00 to mid - 1 parallel do
4:
[dgl- mdg+ [Votmia]
As is shown in Protocol 3, the EuclideanDistance protocol inputs the masked secret-shared two vectors (z) (Ū, [T]] and (7) = (V, [.]]. ), as well additive secret-shared value [w] where
SempareeSaap(lue [1o. [dyymal [bo+mid]
5:
end for
6:
if is odd then
7:
[do]. [yo] [] Igc-1]] = Soap
(17- 2) and outputs an additive secret- shared value [d]. where d = (Ø d)2. By leveraging the Euclidean triples, both Pa and P, independently compute their respective shares of the distance, which significantly reduces communication overhead for secure computation for Euclidean square distance.
([do]. [vo], [di-1] [1r-1])
8:
end if
9:
[
10:
end while
Main Idea. To reduce the communication rounds needed to select the nearest neighbor, we present novel bubble protocol based on divide-and-conquer strategy. Rather than comparing adjacent elements one by one, our protocol partitions the list into pairs and performs secure comparisons in parallel. Specifically, at each iteration, the list is split into multiple pairs, and each pair of elements is compared and swapped if smaller value appears behind a larger
Generation of Euclidean Triples. The Euclidean triples can be generated in the offline phase either by trusted third party (e.g. trusted execution environment) or by using a generation protocol based on homomorphic encryp- tion. Note that the communication overhead for generating Euclidean triples based on homomorphic encryption is the same as the cost of generating ASS shares of random pairs in
5

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
one. This process then continues on the candidate minimum elements, until there is only one element. With our proposed bubble protocol, although the communication size remains unchanged, the communication rounds required to select the nearest neighbor are reduced to O(log!) I).
Table 2. Detailed information of employed datasets. "aaal
means the number of label types. Note that we remove the samples without labels from the original datasets.
Dataset
#Sample (n)
#Attribute (m)
#Label
Toxicity
120
1203
2
As is shown in Protocol 4, the DQBubble protocol inputs two additive secret-shared lists of size 1: [[ and {Iv=I]=>> It synchronously reorders both the distance list and the label list so that do becomes the smallest distance in {d meanwhile, each label remains paired with its orig- inal distance. The protocol proceeds in (log I) iterations, where each iteration "bubbles" the smallest distance and its corresponding label to the front half of the lists. At each it- eration, a CompareSwap protocol (shown in Appendix B.2) to swap the smaller distance and its associated label to the lower
Iris
150
4
3
Arcene
200
10000
2
PEMS-SF
440
137710
3
RNA-scq
800
20532
5
Sparbase
4601
57
2
Mnist
70000
784
10
Dota2 Games
102944
115
2
Dataset Split: We split each dataset in Table 2 into train- ing set and test set with ratio of 8 2.
performed for each pair of positions (g, g g +
Hyperparameter k: We set the hyperparameter k to 5, commonly used value in KNN-related literature (Li et al., 2023; Zhu et al., 2022; Xu & Klabjan, 2021).
index (Line 2-5). If I is odd, the last element [[]]1]] is also compared and potentially swapped with [do] (Line 6-8). After completing these pairwise comparisons, / is updated to _ (Line 9), and the above procedure repeats until < 1.
As is shown in Table 3, Kona achieves the same accuracy as sci k rn across all the datasets. This is because our proposed protocol merely transforms the computation from the plaintext domain to the ciphertext domain without altering the underlying computational semantics.
4. Evaluation
4.1. Experiment Setting
Implementation: We implement Kona in C++, and use function secret sharing (Boyle et al., 2015) to improve the secure comparison operations for fair comparison with the baseline (Li et al., 2023). Each computation party in Kona is simulated by a separate process with one thread. Besides, We perform the computation of Kona on the ring Z224..
Table 3. Accuracy of Kona vs. scikit-leat on eight real- world datascts.
Dataset
Kona
scikit-learn
Toxicity
0.5714
0.5714
Iris
0,9667
0.9667
Arcene
0,9250
0,9250
PEMS-SF
0,7386
0.7386
Experiment Environment: We conduct experiments on Linux server equipped with a 32-core 2.4 GHz Intel Xcon CPU and 128GB of RAM. Note that, since each computa- tion party in Kona is simulated by a separate process with one thread, Kona uses at most two cores during the classifi- cation process. As for the network setting, we apply the te t to simulate two network settings: one is the WAN set- ting with bandwidth of 40 megabit per second (Mbps) and 40ms round-trip trip time (RTT). The other is the LAN setting with 1024 Mbps and sub-millisecond RTT.
RNA-scq
1.0
1.0
Spambase
0,9011
0,9011
Mnist
0,9722
0,9722
Dota2 Games 0.5300
0.5300
4.3. Efficiency Evaluation
Baseline: For efficiency evaluation, we adopt SecKNN (Li et al., 2023) as the baseline. SecKNN is the most recent state-of-the-art secure KNN framework, which supports multiple data owners and relies function secret shar- ing (Boyle et al., 2015) to improve efficiency. As the code of SecKNN is not publicly available, we implement it in C++ and perform the computation on the ring Zz04.
Datasets: As is shown in Table 2, we use eight real-world datasets from UCI repository (Kelly et al., 2023).
4.2. Accuracy Evaluation
Dataset Split: We randomly select one sample from each dataset in Table as the query and use all the remaining samples the training set.
Baseline: For accuracy evaluation, we adopt the plain- text KNN algorithm in scikit-leal (Pedregosa et al., 2011), which is a famous open-sourced machine learning library implemented in Python, as the baseline.
Hyperparameter A: We first fix the hyperparameter k = 5 to demonstrate the efficiency improvement of Kona com- pared to SecKNN across all the datasets in Table 2. Sub- sequently, we evaluate the effect of varying on Kona's 's efficiency using the Arcene dataset.
Phttps://mant .org/ 1 Linux////a / htt///annnpaaaa caainn-aaas//aaaaaa 8 /tc.
8. html
6

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Table Online runtime (sccond), communication size (MB), and commumication rounds of Kona vs. SecKNN (Li al., 2023) with k 5.
Dataset
Framework
Toxicity
Iris
Arcene
PEMS-SF
RNA-seq
Spambase
Mnist
Dota2 Games
0.12
0.10
0.14
0.31
0.57
3,31
50.39
74.11
Communication Size
Kona
(28.25x)
(1.10x)
(228.07x)
(3121,25x)
(162.07x)
(2,26x)
(18.42x)
(3,55x)
SecKNN
3.39
0.11
31.93
967.59
263.38
7.50
928.46
263.53
88
88
88
98
108
138
178
178
Communication Round
Kona
(19.10x)
(16.72x)
(22.40x)
(44.61x)
(73.89x)
(333.19x)
(3932.42
(5783.21
SecKNN
1681
1471
1972
4372
7981
45981
699971
1029412
2.11
2.09
2.22
3,02
3,24
6.94
63.05
90.54
Runtime in WAN
Kona
(16.58x)
(14,36x)
(20,57x)
(79.16x)
(66.39 x)
(135,22x)
(229.31x)
(232.60xx
SecKNN
34.99
30,02
45,68
239.09
215.12
938,46
14458.60 60
21060,40
0.14
0.13
0.17
0,50
0,66
3,54
54,02
79.15
Runtime in LAN
Kona
(1.28x)
(1.15x)
(2.94x)
(11.36x)
(3.13x)
(1.21x)
(1.26x)
(1.18x)
BecKNN
0.18
0.15
0.50
5.68
2.07
4,29
68.54
94.04
As is shown in Table 4, we can conclude as follows:
Kona still achieves a 13.15x reduction in communication size, a 19.18x reduction in communication rounds, and a 16.02x speedup in WAN runtime. These results indicate that the optimizations employed by Kona remain robust and effective across varying is value settings.
terms of communication overhead, Kona significantly reduces both the communication size and communica- tion rounds. Specifically, Kona reduces communica- tion size by 1.10x (Iris) up 3121 x (PEMS-SF), and reduces communication rounds by 16.7x (Iris) to S7x (Dota2 Games). Notably, Kona provides greater benefits in reducing communication rounds as the number of samples increases, and greater benefits in reducing communication size as the number of attributes increases. These empirical results align with the analytical complexity results in Table 1, underscoring the effective- ness of the two communication optimization strategies employed by Kona.
4.4. Ablation Evaluation
In order to further show the effectiveness of the two op- timizations in Kona, we implement the two optimiza- tions of Kona into SecKNN (Li et al., 2023). We name SeCKNN with the optimization based on Euclidean triples as SecKNN-Trin Triples and SeCKNN with the optimization based on the DQBubble protocol as SecKNN-DGRubb e. We compare the communication size, communication rounds, and online runtime, of these two frameworks and the original SeCKNN with le 5.
In terms of runtime in the WAN setting, Kona achieves 14.36x to 232.60x speedups compared to SecKNN, where the performance bottleneck lies in communica- tion, with particularly large gains on large datasets like Mnist (229.31x) and Dota2 Games (232.60x). Espe- cially, Kona requires only about 90s obtain classi- fication result with the dataset Dota2 Games, which is moderate- sized dataset in the real world. These results confirm that Kona should be well-suited for real-world scenarios, where network bandwidth is usually limited and RTT is usually long.
As is shown in Figure 2, we can conclude as follows:
GecKNN-Triples significantly reduces the communi- cation size across all datasets (1.10x to 3064.94x) ) and significantly reduces runtime in both WAN and LAN set- tings (1.00x to 10.16x), especially for high-dimension datasets (e.g. PEMS-ST (FF.. These results confirm that the optimization with Euclidean triples can significantly en- hance efficiency over diverse network settings, and should be much more useful for high-dimensional datasets.
Even in the LAN setting, where the performance bottle- neck lies in both computation and communication, Kona remains up 11. 1..6x faster on PEMS-SF. These results demonstrate that the optimizations of Kona should also be useful for scenarios featuring high bandwidth and low latency.
SeCKNN-DDBubblle significantly reduces communica- tion rounds (16.165 (16.16x to 5688.51 x) without introducing additional communication size, and significantly reduces runtime in the WAN setting (1.62x to 164.56x). These results confirm that the optimization with the DQBubble protocol can effectively accelerate secure k--N selection in the WAN settings.
As is shown in Table 5, we can conclude as follows: Al- though the performance gains of Kona gradually decrease as & increases, the performance gains remain consistently significant even large values. For example, at = 100,
Note that we do not include accuracy comparisons in the ablation evaluation because both of our optimizations have no impact on the classification accuracy. As is shown in
7

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Table 5. Online runtime (sccond), communication size (MB), and communication rounds of Kona vs. SecKNN (Li et al., 2023) for varying & on the Arcene dataset.
Framework
10
20
40
60
80
100
0,03
0.06
0.14
0.28
0.56
1.12
1,64
2.14
2.62
Communication Size
Kona
(1062.00x)
(531 x0x)
(228.07 x)
(114.71x)
(67,58x)
(29. x1x
(20,10x)
(15,87x)
(13.15x)
SeCKNN
31,86
31.88
31.93
32.12
32,40
32,94
33.46
33.98
34.46
19
37
88
171
333
655
975
1279
1559
Communication Round
Kona
(21,05x)
x)
(22.40x)
(22.76x)
(22.76x)
(21.92x)
(20,86x)
(19.95x
(19.18x)
SCCKNN
400
796
1972
3892
7582
14362
20342
25522
29902
0.43
0.87
2.22
4,13
8,08
15.97
23.81
31,44
38.58
Runtime in WAN
Kona
(31.32x)
(24.90x)
(20.57x)
(20.51x)
(20,80x)
(18. x
(18.02x)
(17.03
(16.02x)
SecKYN
13:47
21.67
45.68
84.85
168.07
299.14
429.06
535.71
618.31
0,04
0.07
0.17
0.33
0.65
1.34
2.12
2.94
3.78
Runtime in LAN
Kona
(8,5x)
(5,28x)
(2,94x)
(2,06x)
(1.66x)
(1.43x)
(1.35x)
(1.29%)
(1.26x)
SecKVN
0.34
0.37
0.50
0.68
1,08
1.92
2.87
3.79
4.76
Table 3, Kona consistently achieves identical accuracy to scikit-lese across all datasets when both optimiza- tions are applied. Since the two optimizations are inde- pendent of each other, the frameworks with only one opti- mization (SecKNN-Tril Triples and MAccKNNDDQubblee should still achieve identical accuracy to seikit-learn.
for other distance metries. Concretely, first, our proposed divide-and-conquer bubble protocol makes no assumption on the distance metries. Thus, it can be applied to any distance metric. Besides, our proposed Euclidean triple opti- mization can be applied to other distance metrics with minor adaptations. That because the core idea of our optimiza- tion is to use the input-independent but function-dependenn technique (correlated randomness) to reduce online com- munication, and this idea can apply to any distance metric. e-ã For example, for cosine similarity | ) whose main communication bottleneck lies in secure dot product com- putations (T C, o E in | and 7 i in [[ā]], we can adapt our Euclidean triple to be a dot triple, which comprises two secret-shared vectors and their dot products. By leveraging the dot triple, all secure dot product computations in cosine similarity can be executed without online communication. For Hamming distance, which is usually used in binary data, the Euclidean triple can be directly applied in the binary domain because (x a)² equals the mismatch indicator. Thus, the sum of squared differences immediately gives the Hamming distance for binary vectors.
5. Discussion
Security Issue of Existing Top-k Protocol. We note that the existing shuffle-based top-k protocol (Hou et al., 2023) can be employed to select the & nearest neighbors. How- ever, this protocol may leak private information because it cannot always produce indistinguishable execution views for different distance lists. This security issue is discussed in detail in Appendix D.
Vertical Distributed Datasets. Kona can be extended to support vertically distribated datasets by performing private set intersection (Chen et al., 2017; Kolesnikov et al., 2017) among the DOs. Specifically, if the DOs have vertically par- titioned datasets, they first use a private set intersection to identify the intersection samples of their datasets. Each DO then shares the attributes of these intersection samples with Pa and Po. Finally, Pa and Po combine secret-shared at- tributes into a complete dataset. With this complete dataset, KNN
Future work: In the future, we will extend Kona to support more security models, such as the security model that de- fends against malicious parties, and more distance metrics.
Pa and Po can directly apply the classification protocols presented in this paper.
6. Related Work
Over the last decade, many privacy-preserving frame- works (Li et al., 2023; Liu et al., 2019; Sun & Yang, 2020; Rong et al., 2016; Wu et al., 2019; Li et al., 2015; Saman- thula et al., 2015; Elmehdwi et al., 2014) for KNN classifica- tion or query have been proposed. These frameworks can be broadly divided into two categories, based on whether they reveal private information during the classification or query process. The first category (Sun & Yang, 2020; Rong et al., 2016; Wu et al., 2019) reveals some private information to speed up the KNN protocols. For example, the framework proposed by Sun and Yang (Sun & Yang, 2020) reveals
Extension to More Computation Parties. Kona can be extended to support more computation parties. Specifically, the divide-and-conquee bubble protocol relies on a secure compare-and-swap operation, which can be realized under multi-party ASS protocols such as those in (Damgård et al., 2012). Furthermore, our Euclidean square distance compu- tation protocol can also be adapted to multi-party settings, which is shown in Appendix C.
Adaptation to Other Distance Metries. The optimizations in Kona can be adapted to save communication overhead
8

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
10'
SecKMN
SocKeN
Sire/MB
10a
SecKMN--riipees
Round
SecKVN- Triples
10
DOBubileee
BacckuN-DDBBbbe
10
10a
Tedicity
Iris
Arcene
PEMS-SF
RNA-
Spamtnase
Mnist
Dets2 Games
Texicity
Ints
Arcone
PEMS
RNA-seq
Spambase
Minist Dola2 Games
Data
Dataset
(a) Communication Size
(b) Communication Round
Runšime/s
10
SecKNN
Runtimels
102
SecKNN-Triples
SecKNN-Triiples
SecKNi-DDQubblee
10
10
Texkily
Inis
Arcene
PEMS-SF
RNA-sKq
Spambase
Mnist Dotaz Games
Toxicity
tris
Arcene
PEMS-SF
RNA-seq
Spambase
Mrest Data2 Games
Dataset
Dataset
(c) Runtime in WAN
(d) Runtime in LAN
Figure 2. Online Runtime (seconds), communication size (MBs), and communication rounds of SeCKNN (Li al., 2023).
BecKNN-Triples and BOCKNN-DDBubbll with k 5.
which samples are the & nearest neighbors to the data owner, and the framework proposed by Rong et al. (Rong et al., 2016) reveals the indices of the nearest neighbors. Al- though the revealed information accelerates the neighbor selection procedure, the information may be exploited to infer the sensitive data. Consequently, frameworks in this category should not be suitable for scenarios where the data owners' and users' data must be strictly protected.
Liu et al. (Liu et al., 2019) use secret sharing to improve efficiency over homomorphic encryption-basee methods, and Li al.(Li et al., 2023) further reduce communication rounds by integrating function secret sharing. However, these two frameworks require communicating secret shares for each distance computation and incur substantial com- munication rounds to perform k-nearest neighbor selection, which leads to huge communication overhead.
The second category of frameworks (Liu et al., 2019; Cui al., 2020; Li et al., 2015; 2023; Elmehdwi et al., 2014; Samanthula et al., 2015; Zheng et al., 2024), on the other hand, does not reveal private information during the clas- sification query process and can be further divided into two subtypes based on how many data owners they can sup- port. (1) Single data owner: Some frameworks (Elmehdwi et al., 2014; Samanthula et al., 2015; Zheng et al., 2024; Cui et al., 2020) can support only one data owner. For example, Elmehdwi al. (Elmehdwi al., 2014) employ Paillier homomorphic encryption to realize KNN queries with only one data owner, while Samanthula al. (Samanthula al., 2015) extend this approach to support KNN classification. Since these frameworks can only support one data owner, they cannot improve the accuracy of KNN classification by leveraging the data from different data owners. (2) Multi- ple data owners: The other frameworks (Li et al.. 2015; Liu al., 2019; Li al., 2023) can support multiple data owners. However, these frameworks usually suffer from computa- tion communication inefficiency. Specifically, Li et al. (Li et al., 2015) propose an outsourcing framework, which can support multiple data owners. However, this framework suf- fers from huge computation overhead since it requires O(n) homomorphic operations to compute distance. In contrast,
Our Advantages. Our proposed framework, Kona, does not reveal private information beyond what can be inferred from the classification result. Besides, Kona supports lever- aging data from multiple data owners improve the ac- curacy of KNN classification, and meanwhile significantly reduces the communication overhead compared to the state- of-the-art framework.
7. Conclusion
In this paper, propose Kona, efficient privacy- preservation framework for KNN classification, and op- timize the communication overhead from two-fold: (1) We design novel Euclidean triples to eliminate the online com- munication for secure Euclidean square distance computa- tions. (2) We propose a wwride-and-conquer bubble protocol to significantly reduce communication rounds for selecting the nearest neighbors. Experimental results on eight real- world datasets demonstrate that Kona significantly outper- forms the state-of-the-ar framework by 1.1x ~ 3121 22x in communication size, 16.7x ~ 5783.2 2x in communication rounds, and 1.1x 232.6x x in runtime.

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Acknowledgments
International Conference on the Theory and Applications of Cryptographic Techniques, pp. 64 14-93. Springer, 2021.
This paper supported by National Cryptologic Science Fund of China (2025NCSF01010), Natural Science Foun- dation of China (92370120, 62172100), and Ant Group
Cui, N., Yang, X., Wang, B., Li, J., and Wang, G. Svknn: Efficient secure and verifiable k-nearest neighbor query the cloud platform. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 253-200 264-264. IEEE, 2020.
Research Fund.
Impact Statement
This paper presents work whose goal is to advance the field of privacy-preservine machine learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Damgärd, I., Pastro, V., Smart, N. P., and Zakarias. S. Mul- tiparty computation from somewhat homomorphic en- cryption. In Annual International Cryptology Conference (CRYPTO), pp. 643-662. Springer, 2012.
Demmler, D., Schneider, T., and Zohner, M. Aby-a frame- work for efficient mixed-protocol secure two-party com- putation, In NDSS, 2015.
References
Adeniyi, D. A., Wei, Z.., and Yongquan, Y. Automated web usage data mining and recommendation system using k- nearest neighbor (knn) classification method. Applied Computing and Informatics, 12(1):90-108, 2016.
Dulek, Y., Schaffner, C., and Speelman, F. Quantum ho- momorphic encryption for polynomial-szeed circuits. In Annual International Cryptology Conference, pp. 3-32. Springer, 2016.
Ali, A., Alrubei, M. A., Hassan, L. F. M., Al-J'afari, M. A., and Abdulwahed, S. H. Diabetes diagnosis based knn. Tium engineering journal, 21(1):175- 181, 2020.
Elmehdwi, Y., Samanthula, B. K., and Jiang, W. Secure k- nearest neighbor query encrypted data in outsourced environments. In 2014 IEEE 30th International Confer- ence on Data Engineering, pp. 664-675. IEEE, 2014.
Ben-Efraim, A., Nielsen, M., and Omri, E. Turbospeedz: Double your online spdz! improving spdz using function dependent preprocessing. In Applied Cryptography and Network Security: 17th International Conference, ACNS 2019, Bogota, Colombia, June 5-7, 2019, Proceedings 17, pp. 330.549. Springer, 2019.
Hou, X., Liu, J., Li, J., Li, Y., Lu, W., Hong, C., and Ren, K. Ciphergpt: Secure two voo-party GPT inference. IACR Cryptol. ePrint Arch., pp. 1147, 2023. URL https: //eprint. ficr org/ 2023/1147
Ben-Or, M., Goldwasser, S., and Wigderson, A. Com- pleteness theorems for von-cryptographi fault-tolerant distributed computation. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 351-371.20 2019.
Kataria, A. and Singh. M. A review of data classification using k-nearest neighbour algorithm. International Jour- nal of Emerging Technology and Advanced Engineering, 3(6):354 360, 2013.
Boyle, E., Gilboa, N., and Ishai, Y. Function secret sharing. In Annual international conference on the theory and applications of cryptographic techniques, pp. 337-367. Springer, 2015.
Kelly, M., Longjohn, R., and Nottingham, K. The uci machine learning repository, 2023. URL https:// archive. uci. edu.
Chase, M., Ghosh, E., and Poburinnaya, O. Secret-shared shuffle. In Advances in Crypooloy-ASIACRYPY) 2020: 26th International Conference on the Theory and Appli- cation of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372 Springer, 2020.
Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., and Trieu, N. Practical multi-party private set intersection from symmetric-key techniques. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Com- munications Security, pp. 1257-1272, 2017.
Li, F., Shin, R., and Paxson, V. Exploring privacy preserva- tion in outsourced k-nearest neighbors with multiple data owners. arXiv, Jul 2015.
Chen, H., Laine, K., and Rindal, P. Fast private set inter- section from homomorphic encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1243-1255, 2017.
Li, Z., Wang, H., Zhang, S., Zhang, W., and Lu, R. Secknn: Fss-based secure multi-party knn classification under gen- eral distance functions. IEEE Transactions on Informa- tion Forensics and Security 01113266-341 2023.
Ciampi, M., Goyal, V., and Ostrovsky. R. Threshold gar- bled circuits and ad hoc secure computation. In Annual
10

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Liu, L., Su, J., Liu, X., Chen, R., Huang, K., Deng, R. H., and Wang, X. Toward highly secure yet efficient knn classification scheme outsourced cloud data. IEEE Internet of Things Journal,
Wu, W., Parampalli, U., Liu, J., and Xian, M. Privacy pre- serving k-nearest neighbor classification over encrypted database in outsourced cloud environments. World Wide Web, 22:101-123, 2019.
2019.
Mucherino, A., Papajorgji, P. J., Pardalos, M.,. Mucherino, A., Papajorgji, P. J., and Pardalos, P. M. K-nearest neigh- bor classification. Data mining in agriculture, pp. 83-106, 2009.
Xu, Y. and Klabjan, D. k-nearest neighbors by means of sequence sequence deep neural networks and memory networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Monireal, Canada, 19-27 August 2021, pp. 3214-3220. ijcai.org, 2021. doi: 10.24963/JJCA1220011
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V.,
Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P.,
442. URL https: /tt///do..// org/ 24 24963/ijcai. 2021/452 /442
Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, pp. 2825 2830, 2011.
Zheng. Y., Lu, R., Zhang, S., Shao, J., and Zhu, H. Achiev- ing practical and crypted data. IEEE Trans. Dependable Secur. Comput., 21 (6):5479-549) 2024. doi: 10.1109/DDCC:224437666.4 1ttp:/10..199////// 2024.
knn query over en-
Rong. H., Wang, H., Liu, J.. Wu, W. Hao, J., and Xian, M. Secure collaborative outsourced k-nearest neighbor clas- sification with multiple owners cloud environment. Information Security and Cryptology- 12th International Conference, Inscrypt 2016, Beijing, China, November 4-6, 2016, Revised Selected Papers, volume 10143 of Lecture Notes in Computer Science, pp. 451-471 Springer, 2016. doi: 10.11007797883-319--476---33 28. URL https: //
URL 3376084.
Zhu, S., Xie, L., Zhang, M., Gao, R., and Xie, Y. Distribu- tionally robust weighted k- k-nearest neighbors. Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28. December 9, 2022, 2022.
doi. ora..rrg111 http://111111////910 3 31 54705 - 3_28..
Samanthula, B., Elmehdwi, Y., and Jiang, W. K-nearest neighbor classification over semantically secure en- crypted relational data. International Journal of Ad- vance Engineering and Research Development, 2(11), Nov 2015. doi: 10.211900rjaarr..221 137. URL https: //doi. wwg.o/gg//oooooo 10. 21 21090/ ijaerd. 021137.
Singh, R. H., Maurya, S., Tripathi, T., Narula, T., and Sri- vastav, G. Movie recommendation system using cosine similarity and knn. International Journal of Engineering and Advanced Technology, 95):556-555, 2020.
Sun, M. and Yang, R. An efficient secure k nearest neighbor classification protocol with high-dimensional features. International Journal of Intelligent Systems, 35(11)::77 1813, 2020.
Voigt, and Von dem Bussche, A.
The eu general data protection regulation (gdpr). Practical Guide, 1st Ed., Cham: Springer International Publishing, 2017.
Wang, Z., Na, J., and Zheng, B. An improved knn classifier for epilepsy diagnosis. IEEE Access, 8: 1000000000000,, 2020.
Wong, W. K., Cheung, D. W.-., Kao, B., and Mamoulis, N. Secure knn computation on encrypted databases. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 139-152, 2009.

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
A. Notations
B.2. Compare and Swap
We show the notations used in this paper in Table 6.
As is shown in Protocol 6, the CompareSwap protocol in- puts four additive secret-shared values [ [6o]. [a,] [b1]] and outputs four updated additive shcret-shared values [o.1. (1]. [a'l. [b] If [ao] < [[1]] the outputs remain in the same order; otherwise, the protocol swaps them. First, Pa and Po perform a secure comparison [comp] = ([aol < [ai]] to determine which of the two values smaller (Line 1). Next, Pa and P. update the shares of and based on [comp]] If [comp]
Table 6. Notations used in this paper
Notation
Description
Number of samples in the dataset
Number of attributes per sample
k
Number of nearest neighbors
1, indicating [ < [ai]. then [a]] [ and [ [ai]; otherwise, the two are swapped (Line 2-3). The same logic applies to [ioo] and [b1]] (Line 4-5).
Attribute vector of the i-th sample Class label of the i-th sample A sample vector
y:
Additive secret share of x [=]]]
(x)
Masked secret share of æ
Protocol 6: CompareSwap
DO
A data owner
UR
A query user
Input: [ [bu] [as] |ba].
Pa and P.
The computation parties
Output: [06]. [6]] [o]] [B]]] such that dó op.
6/- bo, dj d1 and B1 bj if as al, else ab al.
8/- b1, aj = do and bj bo.
[comp] = [[0]] <[a1]
B. Remain Protocols for KNN Classification
2: [ag] = [ao] * +ccomp + (1 [compl) [[a]]
3: [a]] = [ao] + [[a]]
[o6]]
B.1. Label Computation
4: [b [bo] [compl
+ (1 [comp]) [bi]-
5: [6] [6o]
+b,] [6]
We follow the method proposed by Li et al, (Li et al., 2023)
to compute the most common label among the k-nearest neighbors.
B.3. Euclidean Triples Generation
As shown in Protocol 5, the LabelCompute protocol inputs list of additive secret-shared labels [[v]]]= and outputs single additive secret-shared label [b]]. where b is the most common label among [we)o In this protocol, Pa and P. first compute the occurrence times for each label (Line 1-6). which results in a counter [ent:]] for each [y:]. Pa and Po then apply the DQBubble' protocol to reorder both the counters {[nnt,]] and their associated labels {[v:]) } so that the label with the highest count moved index (Line
Note that Pa and Ps have obtained { {[u in the dataset- share stage. As long as DO's dataset remains unchanged, these values do not need to be regenerated. Consequently, producing new Euclidean triples only requires generating an additive secret-shared vector [e]] and computing the cor- responding {[w:]]= This approach reduces computa- tion and communication overhead for generating Euclidean triples, especially for scenarios where the dataset is stable.
7). Note that DQBubble' is variant of DQBublle to move the maximum value (instead of the minimum value) to the front. Finally, Pa and Ps set [b] [Bo]] (Line 8).
As is shown in Protocol 7, the EuclideanTTriles protocol inputs additive secret-shared vectors {["]]]=- and out- puts additive secret-shared Euclidean triples [[7.1)=- 1 [+]. and { {[m:]]=>] where w, = (17, - - To begin, Pa and P, each sample their share of σ (Line 1). Since wy = (i,, U)² = [[u=] [ula) + ([u.]o
Protocol 5: LabelCompute
[w],)]
Input: {[g [[=-)>)
the computation expands into three terms: ([uI. [e],a) [[u]]-Io]o]] [0] and the cross term 2[[u. [e] ([u]=
Output: [b]. where b is the most common label in
(m 1--3
[p]6). Here, ([u,]a - [[olaa) can be locally computed by Pa- and ([v.Jo - [o]]b)² can be locally computed by Pr. The primary challenge is securely compute the cross term. To achieve this, Pa encrypts ([u.J - [v]a) and sends the ciphertext to P. (Line 3-4). Then P. uses homomorphic operations to compute 2([ [v]] ([ - [T]])) un- der encryption, adds random mask rı, and returns the masked result to P. (Line 5-6). After decrypting, P. obtains the masked cross term and computes [we] = [[us]a [v]]a]] + 2[[u]a [T]]a) - [o]b) + rs, while
1: for 0 h: 1 in parallel do
2: [ent.] = [o].
3:
for = to k- in parallel do
4: [ent,] = [cnt.] + [1y11 = [l]])
5: end for
6: end for
7: [[ent]]]=> {[< DQBubble'
([[ent:]) 10 (1
8: [b] [Bo]]
12

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Po computes [w,]b ([v.Jo [=]b,]= ry (Line 7-8).
Protocol 8: NPartyEuccidaanDiittance
Note that the communication overhead of this protocol is the same as the cost of generating ASS shares of random pairs in the baseline (Li et al., 2023) based on homomorphic encryption (see Appendix F)..
Input: (i) (Ü, [u]]) (ā) = (V, [v]]. and | where
w (7 U)
Output: [d]] where d = (œ - क)²
computes [d]la (Ø 7) 2( <[
[+])] + [w]lo-
2: P3 computes [d]; = -2( V -+)
Protocol 7: Euclidean Triples
[w], for j E (1,N- 1].
Input: {[ [[
Output: Faclidean triples { [0]. [[o.])]
where w; (ū, - u
1: P. randomly samples [.] and P. randomly sam- ples |
clidean triples (1 1+]. and {[::]>=0 where wy = (ū, 2)2). Each party Pj first samples random
2: for i= 0 to n in parallel do
3: Pa locally computes tmp, = [ū, [o%a-
vector [ol, (Line 1). Then, for each g [0, n 1], party
4: Pa uses its private key to enerypt tmp, to get Enc(tmp;)) and sends Enc(tmp,) Pb.
Po computes local partial square [w.I [[ū]. [01,)²
(Line 3-5). The main challenge lies in securely computing the cross term 2 2[[u,
5: Po randomly samples ri and computes
Enc(tmp2) = 2 * ([u..
([. - -[epp) for all pairs
[+]]]] +
of parties (Pg. Pp) E [0, achieve this, P. locally computes tmp:g - [[ū.], 1 and encrypts it using its private key, obtaining Enc( tmp (Line 7-8). It then sends Enc( (tmp,,) to P.p. which homo- morphically computes 2 Enc(tmp ([T.pp [mpp) and adds random mask Tigp (Line 10-12). The result is then sent to Pq. and Pa decrypts it to obtain tmp? kgp and incor- porates fmp2 sqp into [wi]g (Line 13-14). And Pp updates [wi]p by subtracting Tegp (Line 15).
1). To
6: Ps sends Enc( (tre(tmp2,) P..
7: Pa decrypts Enc( (mp2.) to get tmp2
8: Pa computes [w:]]. = ([ū.]]a [0]a] tmp2,.
and Po computes [ux] = ([t [016)] Ti.
9: end for
C. Euclidean Square Distance Computation for More Computation Parties
In this section, we present the protocols to compute Eu- clidean square distance in multiple computation parties. Here, assume the number of computation parties is N. The computation parties are defined as Po to Px--1 [=]] represents I is additive secret shared among A computation parties, i.c. each P, holds [x] where x = E
Protocol 9: ErertyEEuclieeanTiipee.
Input: ([u.])]=o
Output: Euelidean triples {[ [[1]]=] [0]. ([w
where wy = (77, 8y
1: randomly samples 10l, for j [0. - 1].
2: for i = to - in parallel do
As is shown in Protocol 8, the NPartyEaclideannistnn protocol securely computes the Euclidean square distance in --party setting. This protocol inputs masked secret- shared vectors (ī7) (Ü, [all), (σ) [t]). and the additive secret-shared scalar [w]. where w = (ū it? and outputs the additive secret-shared square distance [[]] (d = (z (z--a) )) In this protocol, party Po locally computes [d]o (Ū - V) 20Ú - -V][o - -[]]oo + [w]o (Line
3: for to N 1 in parallel do
4: P, locally computes [w.], = ([ I. 101,)².
5: end for
6: for to N - in parallel do
7:
Pg locally computes tmp., [[ 17
8:
Pg uses its private key to encrypt tmp., to get Enn(ttp..)).
9:
for p q to No - in parallet do
10:
Pg sends (omp(ttmp))))))))))))))))) to Pp-
1), while each other party P3 for j E [1,W" 1] computes
11:
Pp randomly samples Tigp and computes Enc( pae(tmp22upp = 2 * Enc(tmpp,.. Enn(trp,,))(ii ([u.pp
[d] -2 -V) [1 ) + [[]]; (Line 2). Note that
[T]p) +rigp-
Σ [ (0- 2x V)(T (T)
12:
Pp sends Enc(tmp2..g. igp) to Pq.
(0 7) (V- 7)2 (5 2)2, thus completing the
13:
P. decrypts Enc(tmple kpp) to get tmp2.gn
14:
Pş computes [wi:] = [wi] + tmpp2 ipp
secure Euclidean square distance computation in multi- party setting.
15:
P. computes [шe]e [w.]pp p Figp-
16:
end for
As is shown in Protocol 9, the PParryEuclideanTriple protocol generates Euclidean triples in an --party set- ting. This protocol inputs additive secret-shareed vec- tors {[ and outputs additive secret-shared Fu-
17:
end for
18:
end for
13

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
D. Security Issue in Existing Top-K Protocol
Protocol 10: Top-K
In this section, we discuss the security issue in the existing shuffle-based top-k protocol (Hou et al., 2023).
Input: {[d.I
[ed]k=o minimum values of [d.).=0
Output: {[d]] 1--1 with {d. I 1-1 being the K
As is shown in Protocol 10, the T protocol inputs additive secret-shared list of distances Ji-0 a- and
1: {[d])= Shuffle(([d]])
2: {[d[]]= select [d]]== K).
k-1 outputs A additive secret-shared distances [[]]]=] N==0 that correspond to the k minimum values. To begin with, Pa and P. shuffles the input list {[d using a secure shuffle protocol (Chase et al., 2020) (Line 1). Then, Pa and Pb recursively partition the shuffled list into left subset Sy, and right subset S using pivot element [pivot] - [ (Line 2-12). For each [xx]]. a secure comparison [x,]] < [pivot]
3: Function se ( [= K):
4: [pivot] := [
5: Sr. : 0 SR = [[pivot]
6: For ;= 1
7:
[[b:]]] = [a.] < [pivot]
8:
Pa and Pb reveal [b.] and get b.
9:
if =0
10:
SL == Sy U [|..]}
is performed (Line 7). Then, Pa and P. reveal [6:]] (the comparison bit) to place [x:]] into either Sn or Sn (Line 9-13). The protocol proceeds recursively: if K" = |Sr.] equals K, St itself is returned (Line 16-17); if K' < K, then elements from Sn must also be included (Line 18-19); if K' > K, the algorithm recurses on S,, to select only K elements (Line 20-21).
11:
else
12:
Sn Sn U (+..}}
13:
end if
14:
End For
15:
K' sizeof(SL).
16:
if = K
17:
return S if K" K
18:
19:
return Sy U select(Sn. K K')
The T protocol is insecure because it cannot always produce the same views for different distance lists. Consider two distance lists: where all distances are identical versus where the distances vary. An adversary (such as Pa) observ- ing the protocol execution can distinguish between these two lists. Specifically, if all distances are identical, when comparing each d, with the pivot, the comparison always re- turns 'false'. Consequently, the subset SR is always empty. If the distances are not equal, the comparisons would yield mix of true and false results, thus splitting the elements into distinct subsets S₁, and SR at every pivot. The resulting par- tition pattern would differ significantly from the case where all distances are identical. Thus, by observing the partition pattern, the adversary can distinguish between these two lists.
20:
if K" >> K
21:
return scleel(Sr,,) K)
22:
End Function
capturing the inputs and outputs as follows.
F DDansetStare receives the dataset { y:) from DO and provides MSS shares of attributes and ASS shares of labels to Pa and Pb.
F FXNN-clasifty receives MSS shares of at- tributes, ASS shares of labels, Euclidean triples from Pa and Ph, and a sample from UR, and provides the classification label b UR.
FEBdlidsanDissanes FEuclideaDDistanee receives MSS shares of two vectors from Pa and P,, and provides ASS shares of their Euclidean square distance to Pa and Pa.
E. Security Analysis
We analyze the security of our protocols using the univer- sal composability (UC) theorem (UC-secure protocols can be composed arbitrarily without compromising overall se- curity) and the standard real/ideal world paradigm. We consider the two computation parties Pa and Po. the data owner (DO), and the user (UR) involved in Kona are semi- honest. Besides, we assume that Pa and P, will not collude with each other. In other words, we assume there exists an adversary who can corrupt DO, UR, and one of the two computation parties, and follows the protocols but attempts to learn additional information from the protocol transcripts. Our goal is to show that our proposed protocols reveal no information beyond what can be deduced from the intended outputs to the adversary.
FigBubble: FDQBablle receives ASS shares of a distance list and a label list from P. and P. and provides the ASS shares of an updated distance list and an updated label list to Pa and Po. where the smallest distance at the front and each label remains paired with its original distance
FhaheCComp FiabelCommute receives ASS shares of la- bels from Pa and Po, and provides the ASS shares of the label that occurs most frequently to Pa and Pb.
EoompareSwapi FCompaneSwap receives ASS shares of two pairs (ag, bo) and b,),b) from P., and Pa,, and pro- vides ASS shares of the new pairs (ob, b6) and (a), B)) to Pa and Po. where the output pairs are ordered
For each protocol, we first define an ideal functionality
14

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
such that if ag d1, then (d6: 16) (dg: by) and (a); 11) (a1, b1), otherwise, (d6: ()) (a1, b1) and
V = ā [o]a + [u]s, b. and sends V to Pa and Pa (Line 2-3). Finally, Pa sends [b] a to UR, and P. sends [b] 6 to UR (Line 11). Because the adversary can corrupt UR and one of Pa and P. in this protocol. We provide the simulations for the following three cases:
(a1, (1) (ao, bo).
Triplie Trilide receives ASS shares of [u, from Pa and Po. and provides ASS shares of 7 and (w:)== Pa and Pb, where w; (i, 7)
Case I: The adversary corrupts UR. S proceeds as follows:
We then prove the security of the protocols by using the UC theorem or constructing a simulator S that interacts with the ideal functionalities and produces a simulated view indistinguishable from the adversary's 's view in the real pro- tocol execution. In all descriptions below, unless otherwise specified, i ranges from 0
1. S receives the raw sample ă from F
S locally generates random values [v]a (as if receives from Pa) and [u]] (as if receives from Po).
S receives the final predicted label from FKNN-Classily. and local generated random values [b], n (as receives from Pa) and [[6] (as if receives from Po), where [b]]a + [b]|. b.
DatasetShare (Protocol 1). In this protocol, DO first sends l1 to Pa. and sends [uvlle to Pp- DO receives random shares [ and [ū from Pa and Po. and directly sends U, = x; + [ + [T7.]] to Pa and Pb. Because the adversary can corrupt DO and one of Pa and P% in this protocol. We provide the simulations for the following three cases:
Case 2: The adversary corrupts Pa. S proceeds as follows:
1. S locally generates random value V (as if receives from UR).
Case 1: The adversary corrupts DO. S proceeds as follows:
Case 3: The adversary corrupts UR and Pa: S proceeds as follows:
1. S receives the raw dataset ( 3 from DaunsetShare-
2. S locally generates random values [17]1 (as if receives from P.) and [7,,] la (as if receives from Ps).
S receives the raw sample ä from FKNN-Clasity-
2. S locally generates random values [v]s (as if receives from Po).
Case 2: The adversary corrupts Pa. S proceeds as follows:
1. S locally generates random values [vl and U3 (as if receives from DO).
3. S receives the final predicted label b from and local generated random values [b], and [b], (as if receives from Pt). where [6]] + [[6] = b.
Case 3: The adversary corrupts DO and Pa: S proceeds as follows:
In all the above cases, from the adversary's perspective, the values it receives in the real protocol are identical in distribution to the values it receives in the ideal world. Con- sequently, the KNN-classify protocol is secure against the adversary who can corrupt DO, UR, and one of Pa and Po.
1. S receives the raw dataset (7,, 3 from Datasethhare-
2. S locally generates random value [[7]] (as if receives from Pt).
FuclideanDistance (Protocol 3). In this protocol, Pa lo- cally computes [d]. - 20 ([ [++)+ [w]].s and P, computes [[]], = 22( - V [7)) + [w]]e- In the case of Pa being corrupted. S proceeds as follows:
Because the protocols are symmetric, the simulations for the cases where the adversary corrupts P, follow similarly.
In all the above cases, from the adversary's 's perspective, the values it receives in the real protocol are identical in distribution to the values receives the ideal world. Con- sequently, the DatasetShare protocol is secure against the adversary who can corrupt DO, UR, and one of P. and Ps.
1. S receives U, [u]l.. V. [v]a. and [w]] where w (u - 2) from FBuclideanDisance--
2. S locally computes [d]aa = (Ū
KNN-classify (Protocol 2). In this protocol, the steps shown in Line 4 to Line 10 totally rely on sub-protocols, which are proven secure below. Hence, these steps are secure under the UC thcorem. Except for these steps. Pa sends [[ to UR, and P, sends [u]s to UR (Line 1). Then, UR computes
([ [T],) + [w]la-
DQBubble (Protocol 4). This protocol totally relies on the composition of CompareSwap protocol, which is proven
15

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
secure below. Hence, this protocol is secure under the UC theorem.
the smallest element in list of size I in Olog () iterations. In each iteration, the size of the list is halved, and Pa and P. compare and swap each pair in parallel. Therefore, the communication overhead is O() communication size in O(log /) communication rounds.
LabelCompute (Protocol 5). This protocol totally relies on the composition of the secure equality test and DQBubble' protocol, which is proven secure. Hence, this protocol is secure under the UC theorem.
LabelCompute (Protocol 5) In this protocol, Pa and P. compute the occurrence count for each label through parallel comparisons and additions. Specifically, for each of the k labels, P. and Pa compare against all others, resulting in k2 operations that can be performed in paral- lel. This phase incurs an overall communication overhead of O(k²) communication size in O(1) communication rounds. Subsequently, Pa and P. invoke the DQBubble' protocol on the list of & counters and associated labels to reorder them such that the label with the highest count positioned at the front. The DQBubble' protocol requires (kk) communication size in Ollo k) rounds. Therefore, by combining both phases, the total communication over- head is O(k²) in O(log k) communication rounds.
CompareSwap (Protocol 6). This protocol totally relies on the composition of secure comparison and secure mul- tiplication. Hence, this protocol is secure under the UC theorem.
BuclideanTriples (Protocol 7). In this protocol, Pa sends Enc( (tmp;) to Po (Line 4), and Po sends Enc(tmp2, to Pa- In the case of Pa being corrupted. S randomly generate Ene( (mp22) ,) (as if received from Po). In the case of P. being corrupted. S randomly generate Enc(tmpy received from P.). In all the above cases, from the adver- sary's perspective, the values it receives in the real protocol are identical in distribution to the values it receives in the ideal world. Consequently, the EuclideanTriples protocol is secure against the adversary who can corrupt DO, UR, and
(as if
CompareSwap (Protocol 6): In this protocol, Pa and P. securely compare two additive secret-shared values [aoll and [aI]] and swap them if [aul > [an]] Hence, the communication overhead is O(1) communication size in O(1) communication rounds.
one of Pa and P..
F. Communication Analysis
In this section, we first analyze the communication overhead of each protocol in Kona, then compare the communication overhead for generating Euclidean triples and generating ASS shares of random pairs (Li al., 2023). We assume that each of the basic operations described in Section 2.2 has an (1) communication size and can be completed in O(1) communication rounds.
EuclideanTriple (Protocol 7): This protocol is executed in the offline phase to generate Fuclidean triples. In this protocol, Pa and P. communicate (nn) encrypted el- ements. Hence, the total communication overhead O (Anm)) communication size in 2 communication rounds, where À is the computation security parameter employed in homomorphic encryption.
DatasetShare (Protocol I): In this protocol, DO shares n samples of dimension m by MSS, and shares label by ASS. Hence, the total communication overhead is O(n m) communication size in O(1) communication rounds.
Protocol 11: RandomPair
Output: Random pair [F]] [r']. where PD] = -[.]².
1: P. randomly samples [r] and Po randomly samples [r
2: for j = t m 1 in parallel do
KNN-classify (Protocol 2): In this protocol, UR shares a new sample by MSS and then receives the final la- bel. Besides, the EuclideanDistance protocol involves no online communication, executing the DQBubble pro- tocol k times requires exchanging Onn) shared values in Ok log n.) communication rounds, and the La- belCompute protecol requires O(k2) communication size in O(log k) communication rounds. Therefore, the total communication overhead is (kk) communication size in Ok log n.) communication rounds.
3: Pa uses its private key to encrypt Fij] to get Enc((FFi]ll.) and sends Enc([FLi]) a a) to P..
4: P. randomly samples t, and computes
Enc(tmpp) = 2 Enc([F((i](a) [F]l]] +tz.
5: Po sends Enc(tmp,) ) to Pa-
6: Pa decrypts Enc( (fmp;) to get tmpp..
7: Pa computes [r] = [F]j] + tmps, and P.
computes [[ [i] [F[i]]] 155-tt1 t,.
8: end for
Euclidean Triples vs. Random Pairs (Li et al., 2023).: The communication overhead of EuclideurTriples is the same as the cost of generating ASS shares of random pairs in SeCKNN (Li et al., 2023) based on homomorphic encryp- tion. To securely compute the Euclidean square distance be- tween two vectors & and I each of dimension m, SecKNN
EuclideanDistance (Protocol 3): In this protocol, Pa and Ps compute locally. Hence, the communication overhead of this protocol is zero
DQBubble (Protocol 4): In this protocol, Pa and P, select
16

---

Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
requires generating ASS shares of pair of random vector (F,r), each of m dimension. As is shown in Proto- col 11, generating ASS shares of random pair based homomorphic encryption requires (Qm) communication size communication rounds. Hence, to generate ASS shares random pairs to perform one KNN classification, SecKNN also requires (Arm) communication size in 2 communication rounds.
17


Reviews:
[{"review_id": "JS5pukNcCe", "reviewer": "Reviewer_f4rX", "summary": "The paper introduces Kona, an efficient privacy-preserving framework for KNN classification, and optimizes communication overhead through two key methods: (1) It designs novel Euclidean triples to eliminate the need for online communication during secure computations of Euclidean squared distances. (2) It proposes a divide-and-conquer bubble protocol to reduce the number of communication rounds needed to select the k-nearest neighbors. Furthermore, the authors provide empirical results based on real data to support their findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. Below, we respond to your concerns:\n\n\n\n### 1. Can the proposed methods be applied using distance metrics other than Euclidean distance?\n\nYes, both of our proposed optimizations can be applied to other distance metrics.\n\nFirst, our proposed divide-and-conquer bubble protocol makes no assumption on the distance metrics. Thus, it can be applied to any distance metrics.\n\nBesides, our proposed Euclidean triple optimization can be applied to other distance metrics with minor adaptations. That is because the core idea of our optimization is to use the input-independent but function-depend technique (correlated randomness) to reduce online communication, and this idea can apply to any distance metrics. For example, for cosine similarity ( $\\frac{\\vec{x} \\cdot \\vec{a}}{\\|\\vec{x}\\|\\|\\vec{a}\\|}$), whose main communication bottleneck lies in secure dot product computations ($\\vec{x} \\cdot \\vec{a}$, $\\vec{x} \\cdot \\vec{x}$ in $\\|\\vec{x}\\|$, and $\\vec{a} \\cdot \\vec{a}$ in $\\|\\vec{a}\\|$), we can adapt our Euclidean triple to be a dot triple, which comprises two secret-shared vectors and their dot products.  By leveraging the dot triple, all secure dot product computations in cosine similarity can be executed without online communication. For Hamming distance, which is usually used in binary data, the Euclidean triple can directly apply in the binary domain because $(x - a)^2$ equals the mismatch indicator. Thus, the sum of squared differences immediately gives the Hamming distance for binary vectors.\n\nWe will discuss how our proposed methods can be applied to other distance metrics in detail in the final version.\n\n### 2. Is it possible to conduct experiments with larger ( k ) values (e.g., 100) for a larger sample size to compare with the baseline?\n\n\nYes, conducting experiments with larger values of $k$ is feasible. Our proposed framework, Kona, places no constraints on the value of $k$. Besides, the benefits of our optimizations become even more pronounced with increasing $k$. That is because the communication complexity in Kona is $O(k\\log n)$, while the communication complexity in  SecKNN is $O(kn)$. The performance gap widens significantly for larger $k$. For instance, preliminary experiments using $k = 100$ on the Mnist dataset yield substantial reductions: the runtime in the WAN setting decreases from 248124 seconds (about $68$ hours) to $1084.35$ seconds (a $265\\times$ reduction), the communication rounds decrease from $13989901$ (SecKNN) to $3417$ (Kona) (a $4094.20\\times$ reduction), and the communication size decreases from $942.91$ MB to $503.87$ MB (a $1.87\\times$ reduction).   We will include an evaluation of different $k$ in the final version to showcase Kona's scalability better.\n\n### 3. Is there a method for selecting an appropriate ($k$) value based on different data sizes for the proposed algorithm?\n\nYes, we can select an appropriate $k$ value based on different data sizes for our proposed algorithm, because our proposed algorithm directly accepts $k$ as an input parameter. We can employ standard selection methods, such as the method proposed by Maleki et al.[1], to select an optimal $k$, and then input the $k$ to our proposed algorithm. \n\n\n[1] Maleki et al. A novel simple method to select optimal k in k-nearest neighbor classifier[J]. International Journal of Computer Science and Information Security, 2017, 15(2): 464.\n\n\n###  4. However, there is one issue that needs to be addressed: in Figure 2 of Section 4.4, which focuses on Ablation Evaluation, only the runtime, communication size, and number of communication runs are compared. The accuracy comparison is notably absent.\n\nWe omitted accuracy comparisons in the ablation evaluation because both of our optimizations exclusively target communication efficiency, without affecting the classification accuracy. As is shown in Table 3 of our paper, Kona consistently achieves identical accuracy to scikit-learn across all datasets. This result demonstrates that our optimizations do not affect the classification accuracy. For completeness, we will include an accuracy comparison to the ablation evaluation in the final version.\n\n\n###  5. There is a lack of theoretical analysis and proof regarding the accuracy of the performance.\n\nIn the final version, we will include a theoretical analysis to clearly explain why the accuracy of our proposed protocols is equivalence with plaintext KNN classification. A brief explanation is that our secure KNN classification protocols fundamentally replicate the plaintext KNN classification exactly, and thus theoretically preserve identical accuracy. \n\n### 6. Some of the notations are not reader-friendly, and the subscripts can be confusing.\n\nWe will revise the notations to make them more reader-friendly in the final version.", "claims_and_evidence": "The authors offered clear empirical analyses to support all of their claims.", "methods_and_evaluation_criteria": "1. The proposed methods make sense for real-world k-NN applications, particularly in the area of privacy preservation within the nearest neighbor community.\n\n2. The evaluation criteria are appropriate for the problem. Both naive k-NN and state-of-the-art algorithms are presented and compared. The evaluations of accuracy and efficiency are relevant to the issue at hand.", "theoretical_claims": "This is not relevant to theoretical claims. The paper concentrated on designing algorithms.", "experimental_designs_or_analyses": "The experimental design effectively supports the claims regarding accuracy and efficiency. However, there is one issue that needs to be addressed: in Figure 2 of Section 4.4, which focuses on Ablation Evaluation, only the runtime, communication size, and number of communication runs are compared. The accuracy comparison is notably absent.", "relation_to_broader_scientific_literature": "This study provides comprehensive algorithm insights into privacy preservation issues for the k-NN method. The communication size and number of communication rounds have seen significant improvements compared to existing methods. This is beneficial for the nearest neighbor community.", "essential_references_not_discussed": "The literature review is comprehensive and essential for understanding the paper's contributions.", "other_strengths_and_weaknesses": "**Other Strengths:**\n\n1. The motivation and structure of the paper are clear and easy for readers to understand.\n\n2. The code is included in the supplementary materials, which is beneficial for practitioners.\n\n**Other Strengths:**\n\n1. The motivation and structure of the paper are clear and easy for readers to understand.\n\n2. The code is included in the supplementary materials, which is beneficial for practitioners.\n\n**Other Weaknesses:**\n\n1. The proposed algorithm is limited to Euclidean distance for k-nearest neighbor (kNN) calculations, making it unusable with other popular distance metrics.\n\n2. There is a lack of theoretical analysis and proof regarding the accuracy of the performance.\n\n3. Some of the notations are not reader-friendly, and the subscripts can be confusing.\n\n4. P3, right part, Share Comparison: [Z]=[x]<[y]. To be not ambiguous, it's better to add a parenthesis here: [Z]=([x]<[y])\n\n5. In the experiment section, k=5 is small for kNN in a large size data. Generally, it should scale with the data size.", "other_comments_or_suggestions": "1. Suggestion: Change the subscripts related to computation parts (e.g., P_0, P_1) to superscripts (P^0, P^1) to distinguish from users notation x_1, x_2.", "questions_for_authors": "1. Can the proposed methods be applied using distance metrics other than Euclidean distance?\n\n2. Is it possible to conduct experiments with larger \\( k \\) values (e.g., 100) for a larger sample size to compare with the baseline?\n\n3. Is there a method for selecting an appropriate \\( k \\) value based on different data sizes for the proposed algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nszUQWz30m", "reviewer": "Reviewer_CiRr", "summary": "This paper presents a systematic framework called Kona for privacy-preserving KNN classification, which addresses communication inefficiencies in existing approaches. The key innovations include Euclidean triples to eliminate online communication for Euclidean Square Distance computations and a divide-and-conquer bubble protocol to significantly reduce communication rounds. The authors provide detailed security and communication complexity analyses, and the experimental results validate substantial efficiency improvements over  baseline methods across multiple datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. Below, we respond to your concerns:\n\n### 1. How does the DQBubble protocol work under the encrypted distance, if all the encrypted distance use the same seed, will there be risk to leak seed such that disclose the original distance?\n\nOur proposed DQBubble protocol relies on secure comparison and multiplication protocols to `bubble' distances without leaking the original distance. Consider two additive secret-shared distances $[[x]]$ and $[[y]]$ with $x > y$. Our proposed DQBubble protocol first performs a secure comparison between $[[x]]$ and $[[y]]$ to obtain a secret-shared comparison result $[[comp]]$.  Then, the protocol securely swaps $[[x]]$ and $[[y]]$ based on $[[comp]]$ through:\n$ [[x']] = [[x]] * [[comp]] + [[y]] * (1 - [[comp]]), \\quad [[y']] = [[x]] + [[y]] - [[x']]$. After this secure swap, although  $x'$ and $y'$ are equal to $y$ and $x$ respectively, $[[x']]$ and $[[y']]$ bear no recognizable relationship to $[[y]]$ and $[[x]]$ (e.g. $[[x']]_0$ and $[[x']]_1$ maybe 100 and -50, while $[[y]]_0$ and $[[y]]_1$ maybe 21 and 29). This is because the secure multiplication protocol introduces fresh randomness to mask $[[x']]$ and $[[y']]$. \n\nRegarding the use of seed, it is a common and secure practice in MPC protocols to use a single seed in a single execution.  A secure pseudorandom number generator ensures unpredictability for the seed and generated randomness, eliminating the risk of leaking seed and disclosure of original distances.  However,  reusing the same seed across multiple independent protocol executions should be insecure, because it would result in identical randomness sequences. Therefore, secure deployment always ensures that each protocol execution uses distinct seeds.\n\n\n### 2. Most datasets contain a limited number of labels, which may not fully demonstrate the framework's performance in scenarios with many class labels. \n\nOur experimental datasets were selected primarily due to their wide use in KNN benchmarks, which typically do not encompass tasks with lots of labels. Moreover, the communication complexity of our proposed protocols is independent of the number of labels; thus, the efficiency advantages of our framework should consistently hold, irrespective of label number. In the final version, we will include datasets with more labels to validate this independence.\n\n\n### 3. While the paper evaluates performance with k=5, analysis with different k values would provide more insight into the scalability of the approach. \n \nPlease see Point 2 for Reviewer F4RX.\n\n\n### 4. The paper lacks clear discussion on how the number of attributes affects computation time specifically. \n\nWe will provide an analysis of how the number of attributes affects computation time in the final version.\n\n\n### 5. The protocol descriptions are complex and sometimes difficult to follow. A comprehensive pipeline diagram illustrating the data flow, encoding/decoding processes, and communications between parties would improve clarity.\n\n\nWe will add a comprehensive pipeline diagram to illustrate the data flow, encoding/decoding processes, and communications between parties in the final version.\n\n### 6. While the paper mentions extensions to multi-party settings and vertically distributed data, these extensions lack detailed implementation or evaluation.\n\nCurrently, our paper focuses on optimizing the communication overhead in the horizontal two-computation-party setting, which can support an arbitrary number of data owners and users and is foundational and widely applicable.  In the final version, we will elaborate on the necessary modifications for vertical data settings and multi-party settings. \n\n### 7. I would think this paper is more like an security paper style, which is more systematical and with complete security analysis but may lack the novelty since KNN is not a popular algorithm recently. \n\nWe believe our paper also holds significant novelty for premier AI conferences. Our paper systematically addresses the communication bottleneck of privacy-preserving KNN. Besides, our proposed optimizations—Euclidean triples and the divide-and-conquer bubble protocol—can benefit other privacy-preserving machine learning algorithms, such as K-Means and Approximate Nearest Neighbor (ANN), which also require Euclidean distance computation and neighbor selection. Additionally, KNN should be still a popular machine learning algorithm, particularly in medical diagnosis, finance, and natural language processing. A brief survey on DBLP identified more than 1,000 recent papers related to KNN (nearest neighbor) published within the past three years, including dozens appearing in premier AI conferences (e.g. ICML and NeurIPS) (references are available at https://gofile.io/d/TIx3Z2).", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "Most datasets contain a limited number of labels (10 or fewer), which may not fully demonstrate the framework's performance in scenarios with many class labels. Additionally, while the paper evaluates performance with k=5, analysis with different k values would provide more insight into the scalability of the approach.", "theoretical_claims": "Yes, I have checked and did not find the fault.", "experimental_designs_or_analyses": "The paper lacks clear discussion on how the number of attributes (dimension) affects computation time specifically. While Table 4 shows performance across datasets with different dimensions, a more explicit analysis of this relationship would strengthen the paper", "relation_to_broader_scientific_literature": "The paper adequately positions itself within the privacy-preserving machine learning literature and properly cites relevant work on secure KNN.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n1. The paper presents a complete and systematic protocol for privacy-preserving KNN classification.\n2. The security and communication analyses are thorough and well-executed.\n3. The experimental results convincingly demonstrate Kona's efficiency improvements.\n\nWeaknesses:\n1. The protocol descriptions are complex and sometimes difficult to follow. A comprehensive pipeline diagram illustrating the data flow, encoding/decoding processes, and communications between parties would improve clarity.\n2. While the paper mentions extensions to multi-party settings and vertically distributed data, these extensions lack detailed implementation or evaluation.", "other_comments_or_suggestions": "I would think this paper is more like an security paper style, which is more systematical and with complete security analysis but may lack the novelty since KNN is not a popular algorithm recently. I would recommend the paper to be submitted to the top security conference.", "questions_for_authors": "1. How does the DQBubble protocol work under the encrypted distance, if all the encrypted distance use the same seed, will there be risk to leak seed such that disclose the original distance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ar2rK0PHbt", "reviewer": "Reviewer_o6if", "summary": "This paper focuses on private KNN inference using multi-party computation techniques. Specifically, it introduces a new framework, Kona, for private KNN inference by designing new Euclidean triples. Additionally, the paper proposes a divide-and-conquer bubble protocol to achieve lower communication complexity. Finally, experiments are conducted to validate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. Below, we respond to your concerns:\n\n\n### 1. Can the proposed method support private KNN inference with other distance measures?\n\nPlease see Point 1 for Reviewer F4RX.\n\n\n\n### 2. Intuitively, how does the proposed Euclidean triple help reduce the previously large communication overhead during private distance computation? Could you provide a high-level explanation of its mechanism?\n\nAt a high level, the Euclidean triple reduces the communication overhead by shifting the heavy communication of secure distance computation from the online phase to the offline phase. Traditional secure computation methods require interactive communication during the online phase of distance computation. This becomes a bottleneck when computing distances to many data points in real time. Our Euclidean triple addresses this issue by precomputing randomness for each distance computation before the actual query is known. Each Euclidean triple includes three parts: two random vectors and one precomputed squared distance between them. When the real query arrives, these random components allow the computation of the true Euclidean distance using only local operations. In other words, we replace communication with computation by embedding the necessary randomness and structure for secure distance computation into the Euclidean triples.\n\n\n### 3. It is recommended to enhance the experimental results by reporting the mean and standard deviation of repeated experiments in the tables. \n\nThank you for this valuable suggestion. In the final version, we will use a t-test to report both the mean and standard deviation of the results.\n\n### 4. The paper only compares the proposed method with one state-of-the-art method, which is insufficient.\n\n We initially focused on comparing our proposed Kona with the most recent and representative state-of-the-art (SecKNN, Li et al.~2023). During the rebuttal period, We further compare Kona with Liu et al.'s framework [1], which, aside from SecKNN, is the most recent state-of-the-art secure KNN framework and supports multiple data owners without leaking private information. The experimental results (detailed in https://gofile.io/d/TIx3Z2) show that Kona significantly outperforms Liu et al.'s framework by $24.62\\times$ to $31.16\\times$ in runtime. We will include the experimental results in the final version.\n\n[1] Liu et al. Toward highly secure yet efficient knn\nclassification scheme on outsourced cloud data. IEEE\nInternet of Things Journal, 6(6):9841–9852, 2019.\n\n### 5. The contribution of the paper is somewhat limited. The divide-and-conquer bubble protocol appears to be a straightforward optimization, converting sequential comparisons into parallel comparisons. This protocol does not seem to have a direct relationship with the proposed Euclidean triple-based protocol, which raises questions about its novelty and integration.\n\nWe appreciate the reviewer’s perspective. Indeed, our proposed optimizations are complementary and independently valuable. Our proposed Euclidean triples focus on eliminating online communication during distance computation, addressing one major communication bottleneck. In parallel, our proposed divide-and-conquer bubble protocol targets the separate but equally critical bottleneck in secure neighbor selection by significantly reducing communication rounds through parallel comparisons and swaps. Although conceptually straightforward, this approach was previously unexplored in privacy-preserving KNN contexts. Previous studies either use an insecure method (discussed in Appendix D) or an inefficient sequential bubble protocol.   By combining these two optimizations, our proposed Kona achieves the first practical privacy-preserving KNN framework, which constitutes the novelty and practical contribution of our paper.\n\n\n\n### 6. The paper assumes that $k \\ll m \\ll n$. However, in the experiments, half of the datasets violate this assumption, as they exhibit $n \\ll m$. Additionally, for some datasets, $k \\approx m$, which further deviates from the assumed conditions. This raises concerns about the practicality of the assumptions for real-world applications, as they may not hold in many scenarios.\n\n\nThank you for highlighting this oversight. We acknowledge that our initial theoretical complexity analysis was presented under simplified assumptions ($k \\ll m \\ll n$). In the final version, we will carefully revise the theoretical complexity analysis to address more practical cases. Nevertheless, even without any assumption on the relationship among $k$, $n$ and $m$, the complexity of our proposed Kona remains favorable: the communication size is $O(kn)$ and the communication round is $O(k \\log n)$. While the communication size and communication round of the baseline SecKNN is $O(mn + kn)$ and $O(kn)$. Thus, our conclusions about Kona's communication advantages remain valid even when there is no assumption on the relationship among $k$, $n$ and $m$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "This paper does not have theoretical claims.", "experimental_designs_or_analyses": "It is recommended to enhance the experimental results by reporting the mean and standard deviation of repeated experiments in the tables. Conducting a statistical significance test, such as a t-test, to compare the proposed method with other methods would strengthen the empirical validation of the approach. Furthermore, the paper only compares the proposed method with one state-of-the-art method, which is insufficient.", "relation_to_broader_scientific_literature": "This paper proposes new Euclidean triples for private KNN inference based on the input-independent but function-dependent technique [1].\n\n[1] Ben-Efraim, Aner, Michael Nielsen, and Eran Omri. \"Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing.\" ACNS, 2019.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n-\tThe paper addresses the problem of private KNN inference and proposes a new inference protocol by designing Euclidean triples. Furthermore, the paper optimizes the KNN inference framework by performing secure comparisons in parallel using a divide-and-conquer bubble protocol.\n-\tThe paper conducts experiments on 8 datasets to validate the efficiency of the proposed method.\n\n\nWeaknesses:\n\n-\tThe contribution of the paper is somewhat limited. The divide-and-conquer bubble protocol appears to be a straightforward optimization, converting sequential comparisons into parallel comparisons. This protocol does not seem to have a direct relationship with the proposed Euclidean triple-based protocol, which raises questions about its novelty and integration.\n-\tAs highlighted in the “Experimental Designs or Analyses”, the paper only compares the proposed method with one state-of-the-art method. This is insufficient to demonstrate the effectiveness and superiority of the proposed approach. Comparisons with multiple state-of-the-art methods are necessary to provide a more comprehensive evaluation.\n-\tThe paper assumes that $k<<m<<n$. However, in the experiments, half of the datasets violate this assumption, as they exhibit $n<<m$. Additionally, for some datasets, $k\\approx m$, which further deviates from the assumed conditions. This raises concerns about the practicality of the assumptions for real-world applications, as they may not hold in many scenarios.", "other_comments_or_suggestions": "There is a typo error in line 58 (left): The k in “k nearest neighbors’ selection” should be formatted as $k$.", "questions_for_authors": "1.\tCan the proposed method support private KNN inference with other distance measures?\n2.\tIntuitively, how does the proposed Euclidean triple help reduce the previously large communication overhead during private distance computation? Could you provide a high-level explanation of its mechanism?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a communication-efficient privacy-preserving kNN classification framework based on (i) a novel Euclidean triples that enable secure Euclidean square distance computations without any online communication and (ii) a divide-and-conquer bubble protocol that reduces the communication rounds for selecting neighbors. Experimental results demonstrate superior efficiency of the proposed framework as compared with the existing framework. 

---

The paper is well-written and addresses a practical problem with significant improvements. A noted weakness is its lack of technical depth from a traditional machine learning perspective, but I think ICML has an open mind to diverse tastes and hence this should not undermine the value of the work. 

On the technical side, the proposed method seems reasonable and effective. Reviewer o6if points out a mismatch between the assumptions for complexity analysis (k<m) and experiment setting (k~m) and the lack of experimental comparisons with existing methods. Authors made a plausible effort of responding in rebuttal, and the reviewer raised score afterwards. 

--- 

Overall, I think the paper makes an acceptable contribution and could be accepted if there is room in the program. Authors are also encouraged to incorporate all reviews in the final version, especially align the assumptions and clarify the issues raised in the reviews.
Decision: Accept (poster)