Cryptology ePrint Archive: Report 2018/224

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

Rhys Carlton and Aleksander Essex and Krzysztof Kapulkin

Abstract: We present a semantically secure somewhat homomorphic public-key cryptosystem working in sub-groups of $\mathbb{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\r{a}rd et al.~we present results showing this approach to be both several times faster in computation and lower in communication complexity.

Category / Keywords: public-key cryptography / RSA,homomorphic encryption, homomorphic threshold, secure integer comparison

Original Publication (in the same form): RSA Conference Cryptographers’ Track 2018

Date: received 23 Feb 2018

Contact author: kkapulki at uwo ca

Available format(s): PDF | BibTeX Citation

Version: 20180301:163818 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]