If I have 4 kilobytes of Paillier encrypted data, how can I know the time needed to decrypt it?

  • 1
    $\begingroup$ Simple tining is the time command in Linux\Unix and see Chrono for C++ $\endgroup$
    – kelalaka
    Commented Jan 25, 2021 at 18:31
  • 2
    $\begingroup$ I’m voting to close this question because has nothing to do with Cryptography.SE $\endgroup$
    – kelalaka
    Commented Jan 25, 2021 at 18:31
  • $\begingroup$ I know time commands but i was hoping to see if someone has a answer referenced by a research paper. I found some work on this but with bigger data sizes. $\endgroup$
    – Mimi
    Commented Jan 25, 2021 at 21:03
  • $\begingroup$ Do you want to compare it to something else? $\endgroup$
    – kelalaka
    Commented Jan 25, 2021 at 21:59
  • $\begingroup$ I am comparing my algorithm that uses Paillier for encryption/decryption to another algorithm. So I am not comparing it to another encryption scheme. $\endgroup$
    – Mimi
    Commented Jan 25, 2021 at 22:30

1 Answer 1


You need to know

  • The size $s$ of the public modulus $n$ in bits.
  • The number $c$ of cryptograms.
  • If the code uses the CRT, or not; and in the affirmative, the number $k$ of prime factors in $n$ (usually $k=2$ for $n=p\,q$, with $p$ and $q$ distinct primes).
  • And of course, some benchmark of the code and hardware!

Each cryptogram is $2s$-bit, thus for 4kbyte ciphertext (at most 2kbyte plaintext) $c\,s\le2^{14}$. The largest range/safer/slower for 4kbyte ciphertext is $c=1$, $s=2^{14}$ (that is 16384-bit $n$, which is rather large).

As a rough approximation, using the same computation means and $k=2$, Paillier decryption with CRT for $s$-bit public modulus $n$ ($2s$-bit cryptogram) is about as fast as RSA decryption with CRT for $2s$-bit modulus. Using CRT in Paillier decryption gives a speedup comparable to RSA (a factor like 3). Time is proportional to $c$, and often normalized for $c=1$ in RSA benchmarks.

Extremely roughly, Paillier decryption for $c=1$ is like 5 times slower than RSA decryption at equal size of $n$ and other stuff.

Large savings are possible by increasing $k$, like in multiprime-RSA.

  • $\begingroup$ @fgrieu- Thanks, will try to work it out using your hints. $\endgroup$
    – Mimi
    Commented Jan 27, 2021 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.