Secure Function Extensions to Additively Homomorphic Cryptosystems

Mounika Pratapa; Aleksander Essex

Paper 2023/1155

Secure Function Extensions to Additively Homomorphic Cryptosystems

Mounika Pratapa

, Western University

Aleksander Essex

, Western University

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. SAC 2023
Keywords: Secure computation Additive homomorphic encryption Quadratic residues Residue symbol sequences
Contact author(s): mpratapa @ uwo ca
aessex @ uwo ca
History: 2023-07-27: revised; 2023-07-26: received; See all versions
Short URL: https://ia.cr/2023/1155
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1155,
      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{https://eprint.iacr.org/2023/1155}},
      url = {https://eprint.iacr.org/2023/1155}
}