Paper 2022/079

Lightweight Secure Integer Comparison

Thijs Veugen

Abstract

We solve the millionaires problem in the semi-trusted model with homomorphic encryption without using intermediate decryptions. This leads to the computationally least expensive solution with homomorphic encryption so far, with a low bandwidth and very low storage complexity. The number of modular multiplications needed is less than the number of modular multiplications needed for one Pallier encryption. The output of the protocol can be either publicly known, encrypted, or secret-shared. The private input of the first player is computationally secure towards the second player, and the private input of the second player is even unconditionally secure towards the first player. We also introduce an efficient client-server solution for the millionaires problem with similar security properties

Note: Special Issue Computational Aspects of Quadratic and High-Order Residues with Applications in Cryptography

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MDPI Mathematics
DOI
10.3390/math10030305
Keywords
Millionaires problemhomomorphic encryptionquadratic residuessecure comparison
Contact author(s)
thijs veugen @ tno nl
History
2022-01-20: received
Short URL
https://ia.cr/2022/079
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/079,
      author = {Thijs Veugen},
      title = {Lightweight Secure Integer Comparison},
      howpublished = {Cryptology ePrint Archive, Paper 2022/079},
      year = {2022},
      doi = {10.3390/math10030305},
      note = {\url{https://eprint.iacr.org/2022/079}},
      url = {https://eprint.iacr.org/2022/079}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.