**Overview of eprint 2024/155**

the key idea is that they reduce the number of external products by splitting the homomorphic inner product $a \cdot s$

Define $m$ st it divides $n$. Then split the secret key into $n/m$ continuous chunks. Define $s_k$ as the $k^{th}$ chunk.

We can re-write
$$a \cdot s = \sum_{k=0}^{(n/m)-1} a_k \cdot s_k$$
Define $\delta_{j, s^k} = 1$ when $j == s^k$ where $j \in S^{m}$ ($S^m$ is essentially all possible values that $s^k$, for some $k$, can have).

We can write

$$a_k \cdot s_k = \sum \delta_{j, s^k} (a_k \cdot j)$$
Think of $\delta_{j, s^k}$ as selector that selects the inner product corresponding to the case where $j == s^k$ and zeros rest of the inner products (i.e. zeros $a_k \cdot j$ for all possible values of $j$ where $j \neq s^k$)

So if the client provides
$$RGSW(\delta_{j, s^k})$$
for $j \in S^{m}$

then server can calculate $RGSW(X^{a_k \cdot s_k})$ as
$$RGSW(X^{a_k \cdot s_k}) = \sum_{j \in S^m} X^{a_k \cdot j} \cdot RGSW(\delta_{j, s^k})$$
This require simple modular multiplications and additions. Moreover, noise in resulting $RGSW(X^{a_k \cdot s_k})$ remains roughly equal to fresh RGSW ciphertext.

Then server can evaluate $RLWE(v(x) X^{a \cdot s})$ as
$$RLWE(v(x) X^{a \cdot s}) = RGSW(X^{a_{k-1}s_{k-1}})\boxtimes(...\boxtimes(RGSW(X^{a_1 \cdot s_1})\boxtimes(RGSW(X^{a_0 \cdot s_0}) \boxtimes RLWE(v(x)))))$$
This requires only n/m inner products.

**Quick observations**
1. Their technique gets worse as hamming weight of secret key increases. If the cardinality of $S$ is $L$ then each $s^k$ has $L^m$ possibilities. Hence the client needs to upload $n/m \times L^m$ RGSW ciphertexts. Plus the runtime to calculate $RGSW(X^{a_k \cdot s^k})$ increases.
2. Due to (1), in multi-party setting runtime degrades with no. of parties.
3. Even if we are ok with degradation of runtime in multi-party setting, I still cannot figure out a way to port the technique to multi-party setting. In particular, I cannot figure out how to calculate $RGSW(\delta_{j, s^{k}})$ when $s^{k}$, which is the $k^{th}$ component of ideal secret key $s$, is not known to anyone.
4. A key thing to note is that the technique is very similar to FHEW. In FHEW client uploads RGSW ciphertexts proportional to the cardinality of $Z_q$ where $q$ is ciphertext modulus (because $a_i \in Z_q$). Here, they switched to client having to upload RGSW ciphertexts proportional to the cardinality of secret key distribution.
5. They show for the first time that $n$, the lwe dimension, is not lower bound on internal products in blind rotation.
6. It is exactly due to reducing internal products to $n/m$ they are able to increase the plaintext space without degrading performance. Hence finally making FHEW/TFHE like schemes suitable for CRT representation of big plaintexts that approximately equal word sizes used in practice (for ex, 2^32, 2^64). This is because increasing the plaintext space of single ciphertext allows to find enough different primes of which product equals some big value of relevance.
7. I have started to think that the only practical way to use FHEW like schemes is to use CRT representation. This is because basic arithemtic can be done on each component independently, unlike binary representation which requires additional (expensive) operations for carry forwards. Subsequent paper (eprint 2024/156) shows a way to evaluate sign of a value in CRT representation with very few bootstrapping operations. After which max and min operations are trivial. However, we still need to figure out how to evaluate (a) logic shifts (b) division in CRT representation (I think there already exist some way for division).
8. A question we should answer is "can we reduce internal products in blind rotation, making them relatively independent of lwe dimension n and distribution of secret key" . Answering this will be vital in finding efficient blind rotation technique in multi-party setting with big plaintext space without degrading performance.

---

I tried a few things but still couldn't get anything concrete.

The basic restriction is that we require to have $RGSW(X^{a_k \cdot s_k})$ without any costly operation (no external/internal products).

This will require the client to upload k^{th} secret component $s_k = [s_{k, i}, ...]$ encoded in some structure into a single RGSW ciphertext. This is because if the secret elements of k^th compoenent are in two different RGSW ciphertexts then combing them will require either internal/external product.

The paper gets around this problem by homomorphically selecting the correct s^k. But we cannot do that either because the selection increases with cardinanlity of secret distribution.

**Questions**

- the main problem with the technique in 2024/155 is the complexity homomorphic selector increases linearly with cardinality of secret key distribution. For ex, if cardinality is 4 then 2^{2m} homomorphic selectors are needed whereas only 2^{m} selectors are needed when cardinality is 2. Can we reduce the complexity of homomorphic selector to logarithmic of cardinality?