Paper 2022/622

Efficient and Accurate homomorphic comparisons

Olive Chakraborty and Martin Zuber

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Homomorphic EncryptionArgminTFHE Encryption SchemeBootstrappingPATE frameworkNearest-Neighbour
Contact author(s)
olive chakraborty @ cea fr
martin zuber @ cea fr
History
2022-05-23: received
Short URL
https://ia.cr/2022/622
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/622,
      author = {Olive Chakraborty and Martin Zuber},
      title = {Efficient and Accurate homomorphic comparisons},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/622},
      year = {2022},
      url = {https://eprint.iacr.org/2022/622}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.