High variance in runtime

[RasoulAM]

Hi. I observe a very high variance in the runtime when I compute the intersection. Is there any reason for this? The high variance does not get fixed even with tens of runs. We also ran it over multiple different servers and observed the same behavior.

[karnseth]

Hi @RasoulAM

Probably the main reason you're getting a high variance is because the client generates a new Paillier keypair for each run, which involves sampling a new RSA modulus. This involves sampling primes, which is a process with inherent variance.

You can mitigate this by saving the client's Paillier Key to a file and loading it from there, rather than having it be generated in each run. Another option is to measure the time excluding the Paillier key generation (e.g. by inserting timing code in the right places).

Besides the Paillier key generation, the rest of the protocol should be very predictable.