# Is it possible to trim some encrypted values under fully homomorphic encryption

Suppose we have $$N$$ encrypted values under homomorphic encryption (BFV/BGV ..), and we know that $$M$$ of them are below $$t$$. Is it possible to remove those $$M$$ values?

It is known that some methods (e.g. homomorphic comparison) can out put $$N$$ encrypted $$1$$ or $$0$$s denoting whether the value is above $$t$$ or not, but I need to crop those below $$t$$, leaving $$N-M$$ encrypted values.

Edit: I understand it's not possible to directly remove the $$M$$ values, but is it possible to output $$N-M$$ new encrypted values, whose plaintext is exactly those $$N-M$$ values above $$t$$.

As long as you can design a circuit to do it, then yes. There are a few ways to do this. One is to build a sorting network and output the highest $$N-M$$ values.
• @ChengHong the semantical security prevents a usual if, you might consider according to this. Commented Aug 6, 2020 at 6:24
If you want to directly output an array of $$N-M$$ new values, you likely require a sorting network. Another option is to output an array of $$N$$ values, where all values are either 0 or $$\geq t$$ (but you do not know which). This may still be useful in applications. You could do this by mapping the function: $$f(x) = \mathsf{compare}(x, t) \times x$$ Over the array, where: $$\mathsf{compare}(x, t) = \begin{cases} 0 & x < t\\ 1 & x \geq t\end{cases}$$ This gives a complexity of $$N$$ compare computations, and $$N$$ multiplications. A sorting network which is practical would require $$\Omega(N(\log N)^2)$$ compare-exchange gates (I believe the constant is small, something like 1/2), where: $$\mathsf{compare}\text{-}\mathsf{exchange}(x, y) = (\min(x, y), \max(x, y))$$ Of course compare gates and compare-exchange gates are different, but I imagine they are roughly of equivalent difficulty to homomorphically evaluate. So you can save a $$O((\log N)^2)$$ factor by not removing the 0 values using a sorting network.