search

privacy-scaling-explorations / bfv-py

BFV implementation in Python
MIT License
3 stars 5 forks source link

Unable to perform public key encryption of BFV with CRT #6

Open Vishalkulkarni45 opened 4 months ago

Vishalkulkarni45 commented 4 months ago

@enricobottazzi I was testing the test_valid_public_key_decryption() of TestBFVWithCRT class with qi = [ 27424203952895201, 27424203952895203] , n = 4096 and t = 65537 in tests/test_bfv.py file , getting error as

 File "/home/vishal/.local/lib/python3.10/site-packages/galois/_ntt.py", line 259, in _ntt
    raise ValueError(f"Argument 'modulus' must be prime, {modulus} is not.")
ValueError: Argument 'modulus' must be prime, 27424203952895201 is not.

If i am not wrong the qis should be co-prime and not necessary prime , am i supplying the wrong inputs?

enricobottazzi commented 4 months ago

The reason is that to speed up polynomial multiplication we use Number Theoretic Transform (NTT) under the hood. And NTT only works with prime fields. As you correctly say, qis could only be co-prime and not necessarily primes. But for optimization reason we choose them to be prime as well (and enforce this constraint through the library API too)