# FHE-PIR meeting notes

## Aug 25, 2022

Discuss items:
- ~~implement unoptimized version of SHECS-PIR~~
- Figuring out switching key stuff (Chengyu)
- refer to [Torus LWE paper](https://eprint.iacr.org/2017/430.pdf). Section 2.2, page 8-10. TLWE sample definition in page 5.

### Ciphertext packing
Polynomial ring: $Z_q[X]/(X^N+1)$
RLWE ciphertext, (a, a * s + e + M)
- non-packing: M <- Z_q
- coeff-packing: M(X) = \sum M_i * X^i (addition, mul -> conv)
- canonical packing: \sigma_i, M(\sigma_i) = M_i, (add, mul)
- \sigma_i satisfies that \sigma_i^N+1 = 0

[D_1, ..., D_n] n database ciphertexts/plaintexts log(n) CMUX.
n/N cts/pts log(n/N) = log(n) - log(N) CMUX

### Optimize upload cost

- Problem: h CMUX gates. h selection ciphertexts. compress to only 1 selection ciphertext.
- Solution 1: SealPIR/MulPIR

input ciphertext, M(X) = \sum M_i * X^i
[CT_1, ..., CT_N], CT_i encrypts M_i.

- Solution 2: SHECS-PIR
RLWE ciphertext: a(x), a(x) * s(x) + e(x) + M(x)
convert to LWE ciphertext: (a, <a, s> + e + M_i)
f(x)*g(x) % (x^N + 1)
f(x) = a_0x^0 + a_1x^1 + ... + a_Nx^N
g(x) = b_0x^0 + b_1x^1 + ... + b_Nx^N
h(x) = -(a_0*b_0 + a_1*b_N-1 + a_2*b_N-2 + ...)
x x^N-1

a(x) * s(x) ~= b(x)
\vec a = a_0, a_1, ..., a_N
b = (a_0*b_0 + a_1*b_N-1 + a_2*b_N-2 + ...)
b ~= \vec a * \vec s
(\vec a, b)

Multiplication in Z_q[X]/Q(X), f(X) * g(X) % Q(X) corresponds to

f(X) * g(X) = \sum g_i * (X^i * f(X)) % Q[X]
[f(X), f(X) * X, f(X) * X^2, ... f(X) * X^{N-1}] * [g(X)] = [f*g]

Q(X) = X^N+1.
f(X) * X^i % (X^N + 1) is an anti-cyclic rotation

RLWE: a(x), a(x) * s(x) + e(x) + M(x)
A, A \time s + e + M

RLWE->LWE ciphertext transformation
first row: A_0, <A_0, s> + e_0 + M_0

need to confirm

LWE -> Enc(m)
Let d_g = \ceil(log_B(q))
GSW -> Enc(m/B^0), Enc(m/B^1), ..., Enc(m/B^(d_g - 1))

RLWE, pack N Z_q elements
The first d_g coefficients
RLWE encrypt(m/B^0, m/B^1, ..., m/B^(d_g - 1))
If we perform d_g extraction,
d_g LWE cts, Enc(m/B^0), Enc(m/B^1), ..., Enc(m/B^(d_g - 1)) => GSW ciphertext
Keyswitching(LWE) -> RLWE
RGSW == d_g RLWE ciphertext

TODO:
- implement database packing
- documents conversion between LWE/RLWE/RGSW ct (Thomas)

-----------------------------------------------------------------

## RLWE to LWE:

If we have a RLWE ciphertext (a(x), b(x)) encrypting a polynomial m(x) it means that b(x) - a(x)s(x) ~= m(x) for some secret key s(x).

Therefore, we have m(x) = m_0 + m_1x + ... + m_(N-1)x^(N-1):
- m_0 = b_0 - (a_0s_0 - a_1s_(N-1) - a_2s_(N-2) ...)
- m_1 = b_1 - (a_0s_1 + a_1s_0 - a_2s_(N-1) ...)
- ...
- m_(N - 1) = b_(N-1) - (a_0s_(N-1) + a_1s_(N-2) + a_2s(N-3) ...)

Therefore, we just need to create N (a, b) ciphertexts such that as ~= b_i + m_i as above. Note that s is always (s_0, s_1, ..., s_(N-1)). Therefore, we can simply adjust the elements in a accordingly to satisfy what we need.

- Sample code: https://github.com/tfhe/tfhe/blob/master/src/libtfhe/lwe.cpp#L41
- I have a [sample code](https://gist.github.com/RaindropFamily/793d97f44af6eeef2a84db6e2f36e6a4) using PALISADE, but it's for CKKS ciphertext so it might not be very useful.

## LWE to RLWE:

If we have an LWE ciphertext (a, b), which means b - as ~= m for some plaintext m.

Then, if we simply let a(x) = a_0 + a_1x + ... + a_(N-1)x, s(x) = s_0 + s_(N-1)x + s_(N-2)x + ... + s_2x + s_1x, b(x) = b. Then, b(x) - a(x)s(x) ~= m(x) + c(x), where m(x) = m and c(x) is some random polynomial without a constant term.

This means the RLWE ciphertext (a(x), b(x)) is encrypting some polynomial m + c_1x + ... + c_Nx. If we can zero out c_1 to c_N, we can get a new RLWE ciphertext (a'(x), b'(x)) encrypting a constant polynomial m.

1. Zeroing out is not hard, b/c we can compute what c_1 to c_N is, as we know everything in a and in s. Therefore, we can simply zero out them by calculating c_1 ... c_N one by one homomophically using a and s. This is how [TFHE](https://eprint.iacr.org/2017/430.pdf) do this.
- One issue is that this process requires O(N) homomorphic operations.
- Another issue is that this doesn't seem to be implemented anywhere
2. A better approach is to do this via the substitution process in SealPIR.
- Essentially, a RLWE ciphertext is Enc(f(x)), and by doing substitution(Enc(f(x)), i) where i is some odd number, we make it Enc(f(x^i) mod x^N + 1).
- Therefore, if we do ct' = ct' + sub(ct', 2^{i}+ 1) for i = log(N) to 1, each iteration would zero out half of the remaining non-zero coefficients. Please refer to the screenshot above and SealPIR section 3.3 for details. The resulted ciphertext encrpypts m(x) = mN. (Note that it's m(x) = mN not m(x) = m, but that doesn't matter much as we can easily multiply it by N^-1 or simply leave it and deal with it after finishing the PIR query)
- This is also discussed [here](https://eprint.iacr.org/2020/015.pdf) section 3.3, and they use EvalAuto() for substitution.
- This process requires then log(N) substitution, which is much faster.
- Substitution is essentially eval a Galois automorphism (which is also why they call it EvalAuto), and is the same procedure as rotation. (Rotation is essentially also evaluating the Galois automorphism.)
- Example implementation can be seen [here](https://github.com/microsoft/SealPIR/blob/master/src/pir_server.cpp#L303), and apply_galois is substitution.

## RLWE to RGSW:

For our protocol, we need to extract log(n) RGSW ciphertexts each is simply d RLWE ciphertexts. (Recall that RGSW_Enc = (RLWE(0) ... RLWE(0) + mG, equation 2 page 8 [here](https://eprint.iacr.org/2020/086.pdf)).

Therefore, we can simply pack all log(n) RGSW ciphertexts into one BFV ciphertext, as long as dlog(n) < N where N is the ring dimension of BFV.
Let's say we need (RGSW1 = (RLWE(1), RLWE(2), ...), RGSW2 = (RLWE(0), RLWE(0), ...), ......, RGSWlogn = (RLWE(1), RLWE(2), ...)), we can do BFV.Enc(1x^0 + 2x + ... + 0x^d + 0x^d+1+ ... + 1x^(d(logn-1)) + 2x^(d(logn-1) + 1) + ...).

Then, if we transfer them all into dlogn LWE ciphertexts can transfer these LWE ciphertexts back to RLWE ciphertexts, we get log(n) RGSW ciphertexts.

## Additional notes:

It occurs to me that we don't need the RLWE to LWE step. We can simply do oblivious expansion to get logn RGSW ciphertexts from a single BFV ciphertexts using oblivious expansion from SealPIR (which is also almost the same as the idea as the point 2 in the RLWE to LWE section above).

This should speed things up, but not too much (I mean compare to point 2 above; if we are comparing to point 1, it should be much faster).
However, conceptually speaking, it's much clearer in this way.

## Some additional papers

As mentioned above, we can omit the RLWE to LWE step and directly perform RLWE to RGSW using oblivious expansion, which should give us a decent improvement.

However, I was searching around the internet and found out a related [paper](https://eprint.iacr.org/2021/1081.pdf) and this paper seems to use a relatively similar technique. They are also trying to expand an RLWE ciphertext into several RGSW ciphertexts using oblivious expansion. Their implementation is available [here](https://github.com/mhmughees/Onion-PIR). I haven't read the full yet, but seems quite similar to Shecs-pir in the sense of using RGSW×RLWE

I did some further search and found this [paper](https://eprint.iacr.org/2022/368.pdf). I haven't read this paper in detail and am not sure about the techniques inside, but based on the intro, it seems to be quite relavent.

Goal: one BFV ciphertext encrypting (a1 + a2x + ... + anxn)
to n BFV ciphertexts, each encrypting ai for i \in [n]

SHECS-PIR: 1. to n LWE ciphertexts, each encrypting ai

1 x x^2 ... x^n-1
RING-LWE-ciphertext = (A,B) = (a1, a2, ..., an, b1, b2, ..., bn
B ~= AS + m(x) = (a1*s1 - a2 * sn - a3 * sn-1 - ...)
a2x * sn x^n-1 = -a2*sn