0
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ Simple tining is the time command in Linux\Unix and see Chrono for C++ $\endgroup$ – kelalaka Jan 25 at 18:31
  • 2
    $\begingroup$ I’m voting to close this question because has nothing to do with Cryptography.SE $\endgroup$ – kelalaka Jan 25 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 Jan 25 at 21:03
  • $\begingroup$ Do you want to compare it to something else? $\endgroup$ – kelalaka Jan 25 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 Jan 25 at 22:30
2
$\begingroup$

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$, Pailler 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. Not using CRT in Pailler causes a moderate slowdown (at most a factor of $2$), less than in RSA. Time is proportional to $c$, and often normalized for $c=1$ in RSA benchmarks.

Extremely roughly, Pailler 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.

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

Your Answer

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

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