Lightweight Secure Integer Comparison

Thijs Veugen

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 problem homomorphic encryption quadratic residues secure comparison
Contact author(s): thijs veugen @ tno nl
History: 2022-01-20: received
Short URL: https://ia.cr/2022/079
License: 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},
      url = {https://eprint.iacr.org/2022/079}
}