If I have 4 kilobytes of Paillier encrypted data, how can I know the time needed to decrypt it?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Simple tining is the time command in Linux\Unix and see Chrono for C++ $\endgroup$– kelalakaJan 25, 2021 at 18:31
-
2$\begingroup$ I’m voting to close this question because has nothing to do with Cryptography.SE $\endgroup$– kelalakaJan 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$– MimiJan 25, 2021 at 21:03
-
$\begingroup$ Do you want to compare it to something else? $\endgroup$– kelalakaJan 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$– MimiJan 25, 2021 at 22:30
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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$– MimiJan 27, 2021 at 20:44