Research map / Federated learning and privacy / Privacy attacks and secure learning
Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Kona is a two-party MPC framework for privacy-preserving KNN classification that removes online communication for Euclidean distance computation via Euclidean triples and cuts neighbor-selection rounds with a divide-and-conquer bubble protocol.
Problem
Existing secure KNN classification frameworks incur large online communication size for secure Euclidean square distance computation and many communication rounds for selecting the k nearest neighbors, which hurts practicality especially over WANs.
Approach
Input-independent but function-dependent Euclidean triples (u, v, w=(u-v)^2) tailored to squared Euclidean distance so that distances are computed locally with no online communication, plus a divide-and-conquer compare-swap bubble protocol that reduces selection rounds from O(kn) to O(k log n).
Key results
- Kona reduces communication size by 1.10x to 3121.25x versus SecKNN across eight UCI datasets (k=5).
- Kona reduces communication rounds by 16.7x to 5783.21x versus SecKNN.
- Kona achieves 14.36x to 232.60x WAN runtime speedups over SecKNN and produces the same accuracy as scikit-learn on all datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Kona instead of SecKNN for privacy-preserving KNN | KNN classification · Eight UCI datasets | communication size: 1.10× to 3121.25× reduction | Helped |
| Use Kona instead of SecKNN for privacy-preserving KNN | KNN classification · Eight UCI datasets | communication rounds: 16.7× to 5783.21× reduction | Helped |
| Use Kona instead of SecKNN for privacy-preserving KNN | KNN classification · Eight UCI datasets, WAN | runtime: 14.36× to 232.60× speedups | Helped |
| Transform plaintext KNN computation to privacy-preserving computation with Kona | KNN classification · Eight UCI datasets | accuracy | No clear effect |
| Add Euclidean triples (ablation) | SecKNN · Eight UCI datasets | communication size: 1.10× to 3064.94× | Helped |
| Add Euclidean triples (ablation) | SecKNN · Eight UCI datasets, WAN and LAN | runtime: 1.00× to 10.16× | Helped |
| Add the DQBubble protocol (ablation) | SecKNN · Eight UCI datasets | communication rounds: 16.16× to 5688.51× | Helped |
| Add the DQBubble protocol (ablation) | SecKNN · Eight UCI datasets, WAN | runtime: 1.62× to 164.56× | Helped |
Limitations
- Semi-honest security model with dishonest majority only; malicious-party security is future work.
- Top-k shuffle-based protocol from prior work may leak information, so Kona uses its own selection protocol.
- Gains in efficiency shrink as k grows (e.g., 13.15x size reduction at k=100 on Arcene).
Experimental setup
Datasets: Toxicity Iris Arcene PEMS-SF RNA-seq Spambase Mnist Dota2 Games
Benchmarks: Toxicity Iris Arcene PEMS-SF RNA-seq Spambase Mnist Dota2 Games
Metrics: communication size communication rounds online runtime accuracy
Baselines: SecKNN scikit-learn KNN sun & yang homomorphic encryption KNN Liu et al. secret-sharing KNN
Builds on: SecKNN function secret sharing masked secret sharing additive secret sharing
Closest papers by meaning
- Private-kNN: Practical Differential Privacy for Computer Vision (CVPR 2020 · similarity 0.87)
- Training-Time Attacks against K-nearest Neighbors (AAAI 2023 · similarity 0.85)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.83)
- Practical Privacy-Preserving MLaaS: When Compressive Sensing Meets Generative Networks (AAAI 2024 · similarity 0.82)
- Private Truly-Everlasting Robust-Prediction (ICML 2024 · similarity 0.82)
- United We Stand: Accelerating Privacy-Preserving Neural Inference by Conjunctive Optimization with Interleaved Nexus (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.