Threshold Properties of Prime Power Subgroups with Application to Secure Integer Comparisons

摘要

We present a semantically secure somewhat homomorphic public-key cryptosystem working in sub-groups of Z_n~* of prime power order. Our scheme introduces a novel threshold homomorphic property, which we use to build a two-party protocol for secure integer comparison. In contrast to related work which encrypts and acts on each bit of the input separately, our protocol compares multiple input bits simultaneously within a single ciphertext. Compared to the related protocol of Damgârd et al. [9,10] we present results showing this approach to be both several times faster in computation and lower in communication complexity.