I'm looking for a Additive Homomorphic Encryption scheme which can allow a ciphertext of size smaller than 128 bit.

I started studying this topic very recently so I don't have much knowledge, but I checked on Paillier and RSA and found out for 2048-bit RSA the ciphertext size is 2048 bit and for equivalent Paillier scheme it is 4096 bit.

Is there any way to make the ciphertext be small but make the security level be the same?

  • 1
    $\begingroup$ You can do ElGamal with the message on the exponent but the message space needs to be small since you need to find the discrete log (see crypto.stackexchange.com/questions/9000/…). The ciphertext is two point elements, it's smaller than RSA but still not 128 bits. $\endgroup$
    – lamba
    Jul 4 at 10:23
  • 1
    $\begingroup$ Adding on the above: for $k$-bit security using standard Elliptic Curve Group of size $2k$-bit, ciphertext would be in the order of $4k$-bit, thus 128-bit ciphertext would be less than secure. Also deciphering final result $n$ (with the private key) would have cost growing as $\mathcal O(\sqrt n\,)$; that's tolerable, or not, depending on how large $n$ is in the application. Some tradeofs between performance and ciphertext size are possible, thought; so if say 448-bit ciphertext or so is still OK for standard security level, please edit the question to loosen the 128-bit requirement. $\endgroup$
    – fgrieu
    Jul 4 at 16:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.