Efficient and accurate homomorphic comparisons

Olive Chakraborty (1) , Martin Zuber (1)

1 LCYL - Laboratoire pour la Confiance des sYstèmes de calcuL

We design and implement a new efficient and accurate fully homomorphic argmin/min or argmax/max comparison operator, which finds its application in numerous real-world use cases as a classifier. In particular we propose two versions of our algorithms using different tools from TFHE's functional bootstrapping toolkit. Our algorithm scales to any number of input data points with linear time complexity and logarithmic noise-propagation. Our algorithm is the fastest on the market for non-parallel comparisons with a high degree of accuracy and precision. For MNIST and SVHN datasets, which work under the PATE framework, using our algorithm, we achieve an accuracy of around 99.95% for both.

Domaines: Cryptographie et sécurité [cs.CR]

Olive Chakraborty, Martin Zuber. Efficient and accurate homomorphic comparisons. WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2022, ACM, pp.35-46, 2022, WAHC'22 - Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 978-1-4503-9877-0. ⟨10.1145/3560827.3563375⟩. ⟨cea-03983178⟩