RLWE Parameters

Parameters for Ring Based Learning with Errors Cryptography


Definitions:


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 Fq

  • Φ(x) = a cyclotomic polynomial. When n is a power of two Φ(x) = (xn + 1)

  • a(x) = a known fixed polynomial of degree less than n and with coefficients in Fq

  • ​s(x) a secret polynomial of degree less than, with coefficients in Fq chosen according to a probability distribution

  • e(x) a secret polynomial of degree less than n, with coefficients being in Fq 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.


Table of Parameters for Ring Learning with Errors


>
n q PK Size in Bytes Distribution Security Claim Source Year Algorithm
1024 30-bit Prime 3840 Gaussian    ≈ 2160 Zhang 2014   Key Exchange
1024 232 - 1 4096 Gaussian    > 2128 Bos 2014   Key Exchange
1024 40961 2048 Uniform    > 2256 Singh 2015   Key Exchange
1024 12289 1792 Binomial   > 2128 Alkim 2015   Key Exchange
432 35507 864 Uniform 2128 Singh 2015   Key Exchange
1024 5767169 5888 Gaussian    > 2135 Chopra 2016   Signature
512 39960489 3328 Gaussian    ≈ 2128 Akleylek 2016   Signature
1024 59393 2048 Uniform ≈ 2137 Chopra 2017   Signature