Non-interactive and Output Expressive Private Comparison from Homomorphic Encryption

Wenjie Lu, Jun-Jie Zhou, Jun Sakuma

Abstract

Private comparison is about privately determining whether a > b, given two input integers a and b which are held as private information. Private comparison is an important building block for applications such as secure auction and privacy-preserving decision tree evaluation. In this paper, we consider a variant setting in which the inputs a and b as well as the result bit 1 {a > b} are encrypted. Using a ring variant of a fully homomorphic encryption scheme, our solution takes as input the ciphertexts of a and b and produces only one ciphertext which decrypts to the bit 1 {a > b} without any interaction with the secret key holder. Our approach does not encrypt the inputs bit-wisely and requires only a multiplicative depth of one, giving about 48 - 90 fold speed up over previous solutions.
BibTeX
@inproceedings{lu2018non,
  author = {Wenjie Lu and Jun-Jie Zhou and Jun Sakuma},
  title = {{Non-interactive and Output Expressive Private Comparison from Homomorphic Encryption}},
  booktitle = {AsiaCCS},
  year = {2018},
  doi = {10.1145/3196494.3196503},
}

Loading related content...

Figure