The buildModChain function modification affect performance

[NanXiao]

I find f2717f0e564fb7e1fc8c3838819b03b853741755 will downgrade application performance. For example, my multi-thread program likes this:

......

#pragma omp parallel for
for (long i = 0; i < plaintext2DCoeffs.size(); i++) {
    ......
    for (long j = 0; j < degree; j++) {
        ......
        tempCtxtTwo.multByConstant(plaintext2DCoeffs[i][j]);
        ......
    }
    ....
}

#pragma omp parallel for
for (long j = 0; j < degree; j++) {
        resultCtxtVec[j].smartAutomorph(1L << j);
}

#pragma omp parallel for
......

The program which uses daa25ce46474dd8d35d07b40fddaac478b4c027e which before f2717f0e564fb7e1fc8c3838819b03b853741755 will consume ~7 seconds, but consumes ~11 seconds using f2717f0e564fb7e1fc8c3838819b03b853741755. I check f2717f0e564fb7e1fc8c3838819b03b853741755 and find buildModChain() function is changed. So is it reasonable for application performance downgrade?

Thanks very much in advance!

Best Regards Nan Xiao

[shaih]

It's possible that the sizes of 'digits' in the context would change, which could impact performance. What parameters were you using for the context (m, p, r) and for buildModChain (L, c)? Also, did you compile it with or without the NO_HALF_SIZE_PRIME compilation flag?

[NanXiao]

@shaih

m is 11119, p is 2 and r is 1 for context (m, p, r); L is 11 and c is 3 for buildModChain (L, c); compile without NO_HALF_SIZE_PRIME.

Thanks!

[fionser]

@NanXiao If you heavily use "rotation" (including replication, totalSum functionality), I strongly recommend you to use "good" combination of (m, p). By saying "good", I mean you should find such m and p that PlAlgebra::numGens() as small as possible and PlAlgebra::SameOrd is true for all generators.

[AlexanderViand]

@fionser Is there an easy way to do this? I'm using HElib as a non-crypto person and the setup/parameter choice is by far the hardest part to really understand, so I just rely on findM. Yet I can see that choosing the parameters more carefully can make dramatic performance differences, so I'd obviously like to choose "good" parameters, too.

Do I just write a brute-forcing loop that tries various m's against those criteria? It would be great if all the information about the parameters was consolidated in one place somewhere in the documentation :)

[fionser]

@AlexanderViand Hope this helps. I also do a BF search actually.

Using findM is the most easiest way. But, to achieve the optimal performance, you need to tune by yourself. Basically, we need to determine m, p and L.

The L determines the number of operations you can do on the ciphertexts. It depends on the complexity of the function you are going to evaluate.

The m and L together determine the security level. A large m and a small L gives a higher security. Of course, how much level of security also depends on your requirements.

Here is a trade-off between m and L. The larger m you use, the magnitude of noise inside the ciphertext can grow, as a result, you need a larger L to make sure you can decrypt the ciphertext after you complete your computation. However, when you use a new but larger L (with the m fixed), the security level decreases. What I want to say is that, you need to tune your parameter carefully.

:). Hope it helps.

To me, there are too much "know-how" of using HElib to be documented.

[shaih]

I (hopefully) fixed the performance-degradation issue that Nan Xiao pointed out. The current revision (8f972c2) should now deliver performance similar or better than daa25ce

[benjaminhmtan]

@fionser Do you have any references for why it is so? Any similar criteria for good m, p combinations for frobenius automorphisms?

[fionser]

@benjaminhmtan, I just read the source code and found out that. Sorry, I do not know the criteria for frobenius automorphisms, but I think it is similar.