BFV relinearization

This vignette follows the same structure as BFV multiply, but before decryption, instead of decrypting the terms C1, C2, and C3, this vignette implements relinearization of those terms to: C1hat and C2hat. The term C3 includes the terms s^2 (or s*s), by removing this exponential term, the whole of C is linear again (i.e. only including s^1 terms).

Load libraries that will be used.

library(polynom)
library(HomomorphicEncryption)

Set some parameters.

d  =      4     # n and d need to be renamed throughout the package
n  =      2^d
p  =      11
q  =  p * 15000
pm = GenPolyMod(n)

Set a working seed for random numbers

set.seed(123)

Create the secret key and the polynomials a and e, which will go into the public key

# generate a secret key
s = GenSecretKey(n)

# generate a
a = GenA(n, q)

# generate the error
e = GenError(n/10) # need to figure out how this division can be removed, by scaling q/p

Generate the public key.

# generate the public key
pk0 = GenPubKey0(a, s, e, pm, q)
pk1 = GenPubKey1(a)

Generate the evaluation key (EvalKey, EK).

ek0 = GenEvalKey0(a, s, e)
ek1 = a

Create polynomials for the encryption

# polynomials for encryption
e1 = GenError(n)
e2 = GenError(n)
u  = GenU(n)

Now create to messages to multiply.

m1 = polynomial(c(3, 2, 2))
m2 = polynomial(c(0, 2   ))

Encrypt the two messages (i.e. genete the ct0 and ct1 part for each m1 and m2).

m1_ct0 = EncryptPoly0(m1, pk0, u, e1, p, pm, q)
m1_ct1 = EncryptPoly1(    pk1, u, e2,    pm, q)
m2_ct0 = EncryptPoly0(m2, pk0, u, e1, p, pm, q)
m2_ct1 = EncryptPoly1(    pk1, u, e2,    pm, q)

Multiply the encrypted messages.

multi_ct0 = m1_ct0 * m2_ct0 * (p/q)
multi_ct0 = multi_ct0 %% pm
multi_ct0 = CoefMod(multi_ct0, q)
multi_ct0 = round(multi_ct0) # the rounding should come before the mod (both of the mods)

multi_ct1 = (m1_ct0 * m2_ct1 + m1_ct1 * m2_ct0) * (p/q)
multi_ct1 = multi_ct1 %% pm
multi_ct1 = CoefMod(multi_ct1, q)
multi_ct1 = round(multi_ct1)

multi_ct2 = (m1_ct1 * m2_ct1) * (p/q)
multi_ct2 = multi_ct2 %% pm
multi_ct2 = CoefMod(multi_ct2, q)
multi_ct2 = round(multi_ct2)

Relinearize:

ct0hat = CoefMod(multi_ct0 + ek0 * multi_ct2 %% pm, q)
ct1hat = CoefMod(multi_ct1 + ek1 * multi_ct2 %% pm, q)

Decrypt the multiple

decrypt = ct0hat + ct1hat * s
decrypt = decrypt %% pm
decrypt = CoefMod(decrypt, q)

# rescale
decrypt = decrypt * p/q

# round then mod p
decrypt = CoefMod(round(decrypt), p)
print(decrypt)
#> 6*x + 4*x^2 + 4*x^3