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)
- 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
-
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} }