N=1024 or N=2048

[RasoulAM]

Is there any theoretical reason that N=1024, 2048 can not be used for this protocol? Or is it just a technical limitation in SEAL? If the limitation is theoretical, can you point me to any papers which discuss this limitation?

Thanks.

[sga001]

SealPIR depends on RLWE encryption (BFV cryptosystem in particular). This encryption has 3 parameters that all interact with each other in particular ways.

N = polynomial degree
q = coefficient modulus (i.e., modulus of coefficients in ciphertext polynomials)
t = plaintext modulus

For security, N and q need to have certain values based on t. For correctness (to get a valid result that's not corrupted by too much noise), they also need to have certain values based on the number of operations that you will be performing.

I'm not sure N = 1024 will work for large databases. Perhaps.

N = 2048 should work (indeed we used this in our prior implementation), but the current version of SEAL does not support certain operations we need (e.g., key switching, galois automorphisms) with N = 2048.

[RasoulAM]

So aside from choosing parameters which are secure and the noise does not corrupt the message, there is no limitation?

[sga001]

I think so.

[RasoulAM]

Thanks Sebastian for your answer.

I'm looking through the SEAL repository and the condition on which they allow galois automorphisms is captured in this line:
https://github.com/microsoft/SEAL/blob/206648d0e4634e5c61dcf9370676630268290b59/native/src/seal/context.cpp#L494

Tracing back the code, the reason that the condition on this line fails for N=1024 is that the coefficient modulus chain is of length one. Do you have insight as to why the developers of seal placed this limitation? Is a coeff mod chain of length 1 an actual limitation?

I should note that I am interested in PIR over a small database, which is why N=1024 might still be an option for me.