FPGA-Based Acceleration of K-Nearest Neighbor Algorithm on Fully Homomorphic Encrypted Data

Abstract

The suggested solution in this work makes use of the parallel processing capability of FPGA to enhance the efficiency of the K-Nearest Neighbor (KNN) algorithm on encrypted data. The suggested technique was assessed utilizing the breast cancer datasets and the findings indicate that the FPGA-based acceleration method provides significant performance improvements over software implementation. The Cheon–Kim–Kim–Song (CKKS) homomorphic encryption scheme is used for the computation of ciphertext. After extensive simulation in Python and implementation in FPGA, it was found that the proposed architecture brings down the computational time of KNN on ciphertext to a realistic value in the order of the KNN classification algorithm over plaintext. For the FPGA implementation, we used the Intel Agilex7 FPGA (AGFB014R24B2E2V) development board and validated the speed of computation, latency, throughput, and logic utilization. It was observed that the KNN on encrypted data has a computational time of 41.72 ms which is 80 times slower than the KNN on plaintext whose computational time is of 0.518 ms. The main computation time for CKKS FHE schemes is 41.72 ms. With our architecture, we were able to reduce the calculation time of the CKKS-based KNN to 0.85 ms by using 32 parallel encryption hardware and reaching 300 MHz speed.

Keywords

• field-programmable gate array (FPGA)
• K-Nearest Neighbor (KNN) algorithm
• Cheon–Kim–Kim–Song (CKKS) encryption scheme
• fully homomorphic encryption (FHE) scheme
• cloud computing