Paper 2023/1155

Secure Function Extensions to Additively Homomorphic Cryptosystems

Mounika Pratapa, Western University
Aleksander Essex, Western University

The number-theoretic literature has long studied the question of distributions of sequences of quadratic residue symbols modulo a prime number. In this paper, we present an efficient algorithm for generating primes containing chosen sequences of quadratic residue symbols and use it as the basis of a method extending the functionality of additively homomorphic cryptosystems. We present an algorithm for encoding a chosen Boolean function into the public key and an efficient two-party protocol for evaluating this function on an encrypted sum. We demonstrate concrete parameters for secure function evaluation on encrypted sums up to eight bits at standard key sizes in the integer factorization setting. Although the approach is limited to applications involving small sums, it is a practical way to extend the functionality of existing secure protocols built on partially homomorphic encryption schemes.

Note: This version of the paper contains Algorithm #1, which is omitted from the original publication in Selected Areas in Cryptography 2023 owing to space constraints

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Selected Areas in Cryptography 2023
Secure computationAdditive homomorphic encryptionQuadratic residuesResidue symbol sequences
Contact author(s)
mpratapa @ uwo ca
aessex @ uwo ca
2023-10-07: last of 2 revisions
2023-07-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mounika Pratapa and Aleksander Essex},
      title = {Secure Function Extensions to Additively Homomorphic Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1155},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.