Basic NTRU workings

✍️ → Written on 2020-07-15 in 240 words. Part of cs IT-security pqcrypto

Key Generation:

f, g ← sample polynomials of degree ≤ N-1 with coefficients in {-1, 0, 1}
f⁻¹ =: f_p such that f*f_p = 1 mod p
f⁻¹ =: f_q such that f*f_q = 1 mod q
h := p * f_q * g mod q
return pk = (h)
    sk = (f, f_p, g)

Encryption(μ)

m := polynomial with coefficients in {-1, 0, 1} representing μ
r ← sample polynomial with coefficients close to 0
e := r * h + m mod q
return e

Decryption(e)

a := f * e mod q
b := a mod p
c := f_p * b mod p
return c

c = f_p * b = f_p * a = f_p * (f * e mod q) = f_p * (f * r * h + f*m mod q) = f_p * (f * r * p * f_q * g + f * m mod q) = f_p * (r * p * g mod q) + f_p * (f * m mod q) mod p = f_p * (r * p * g mod p) + f_p * (f * m mod p) mod p = f_p * 0 + 1 * m mod p = m mod p