single slot operations on SIMD fully homomorphic polynomial

According to https://eprint.iacr.org/2011/133.pdf and many other papers, there's an isomorphsim between the space of polynomials and its coefficients. So, at least in the BFV scheme, we can do:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

So applying one operation to the polynomial is the same as applying to all elements, sort of like SIMD works on CPUs. This is also galled Galois automorphism on some schemes.

Now, suppose I want to operate just on the second element so somehow I find a way to extract it with a bitmask and thus I get:

$$p_2(x) = [0, \phi(a_2), ..., 0]$$

I can now operate on $p_2(x)$ to modify $\phi(a_2)$ however I want. Is there a way to put it back on the $p(x)$ with my modifications? I think also that some operations that I do on p_2(x) could make the other elements nonzero, which is also a challenge.

There is a simple way to do this. Specifically, you have already mentioned you have a bitmask extraction procedure. Therefore, given $p(x)$, $p_2(x)$, and $p_2'(x)$ (your homomorphic operations applied to $p_2$), let $p_3(x)$ be the result of applying the same bitmask to $p_2'$. Then, it is straightforward to verify that

$$p(x) - p_2(x) + p_3(x)$$

gives you the result you want.

This reduces everything to two "bitmask extraction" procedures, the homomorphic evaluation (which seems unavoidable), and a few additions (which should be cheap). There are then natural questions:

• can one bitmask extraction suffice?
• How can one efficiently apply bitmask extraction?

If the slot you want to compute on is public, it should suffice to multiply by a suitable constant (with 0/1 coefficients) polynomial, giving a multiplicative overhead of 1 for each bitmask extraction. Private bitmasks seems less efficient --- I can think of something that uses $O(n)$ multiplications (but at least has depth 1), essentially by computing a multiplication of an (encrypted) 0/1 boolean for each index to "select" the right indices, and then adding everything in the end.

I do not know how the above compares to state-of-the-art though.

It's also worth mentioning that if your operations on $p_2(x)$ do not depend on the other coordinates $\phi(a_i)$ (but may simply "overwrite" them), one can remove one of (namely the first) bitmask extraction operations. This depends on the particular function you are evaluating of course though.