Polynomials with coefficients in a Finite Field are the basic building blocks of Ring Learning with Errors (RLWE) cryptosystems. These cryptosystems are defined by the following parameters:

- n = a prime number or power of 2. There will be n coefficients in the polynomials or n-1 is the
maximum degree of the polynomial
- q = a prime number. The coefficients of the polynomials will be integers mod q and the arithmetic will be in F
_{q} - Φ(x) = a cyclotomic polynomial. When n is a power of two Φ(x) = (x
^{n}+ 1) - a(x) = a known fixed polynomial of degree less than n and with coefficients in F
_{q} - s(x) a secret polynomial of degree less than, with coefficients in F
_{q}chosen according to a probability distribution - e(x) a secret polynomial of degree less than n, with coefficients being in F
_{q}and "small" in the integers and chosen according to a probability distribution - b(x) a public polynomial equal to b(x) = a(x)s(x) + e(x).

b(x) is a public key

s(x) and e(x) together constitute the private key

n, q, Φ(x) and a(x) along with the probability distributions for the coefficients of s(x) and e(x) are the system wide parameters.

The following table provides various sets of parameters found in the RLWE academic literature. There are links to the papers defining these parameter sets in the source column of the table. The name listed is the first author of the paper.

>

n | q | PK Size in Bytes | Distribution | Security Claim | Source | Year | Algorithm |
---|---|---|---|---|---|---|---|

1024 | 30-bit Prime | 3840 | Gaussian | ≈ 2^{160} |
Zhang | 2014 | Key Exchange |

1024 | 2^{32} - 1 |
4096 | Gaussian | > 2^{128} |
Bos | 2014 | Key Exchange |

1024 | 40961 | 2048 | Uniform | > 2^{256} |
Singh | 2015 | Key Exchange |

1024 | 12289 | 1792 | Binomial | > 2^{128} |
Alkim | 2015 | Key Exchange |

432 | 35507 | 864 | Uniform | 2^{128} |
Singh | 2015 | Key Exchange |

1024 | 5767169 | 5888 | Gaussian | > 2^{135} |
Chopra | 2016 | Signature |

512 | 39960489 | 3328 | Gaussian | ≈ 2^{128} |
Akleylek | 2016 | Signature |

1024 | 59393 | 2048 | Uniform | ≈ 2^{137} |
Chopra | 2017 | Signature |