# Evaluate the time of Paillier decryption

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

• Simple tining is the time command in Linux\Unix and see Chrono for C++ Commented Jan 25, 2021 at 18:31
• I’m voting to close this question because has nothing to do with Cryptography.SE Commented Jan 25, 2021 at 18:31
• 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.
– Mimi
Commented Jan 25, 2021 at 21:03
• Do you want to compare it to something else? Commented Jan 25, 2021 at 21:59
• I am comparing my algorithm that uses Paillier for encryption/decryption to another algorithm. So I am not comparing it to another encryption scheme.
– Mimi
Commented Jan 25, 2021 at 22:30

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.

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