Modular Exponentiation algorithm on BGV

Library Questions
1

Hi there! I’m trying to implement a modular exponentiation algorithm for the BGV ciphertexts. The idea is to be able to extend this algorithm for computing Fermat’s Little Theorem.

I have successfully implemented the algorithm for Plaintext Modulus p=65537 for up to a multiplicative depth of 13 iterations. For Fermat’s Little Theorem I need to compute a^65536, but this implicitly needs a multiplicative depth of 16 or 17. However, if I try to increase the multipicative depth, the following error arises:

Please provide a primeModulus(q) and a cyclotomic number(m) satisfying the condition: (q-1)/m is an integer. The values of primeModulus = 65537 and m = 131072 do not satisfy this condition

Any ideas on how can I avoid this issue?

2

Set plaintext modulus p=786433 and let me know if it solves your issue.

3

Issue solved! The problem was of course about choosing the right prime number. Thanks for the answer!

4

Related to this, is there any ‘list of suitable prime numbers’ to use in OpenFHE? It would be great to have this list of primes with their maxDepth, for developers to know what prime to choose deoending on the operations to be done on the ciphertexts.

Looking forward to your answer!

5

You are using ultra-large parameters that we do not generally recommend. The default plaintext modulus used in the example should support reasonable ring dimensions.
Look at the last paragraph in this post. It should give you an idea about how to choose your prime modulus.

6

@Caesar is there any security issue raised when selecting such ultra-large parameters?

7

@dcousins - As long as the ring dimension is set appropriately (which is done automatically in OpenFHE), then there should be security issues. What I meant by not recommended settings above was merely based on the performance aspect.

1 Like