4
$\begingroup$

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$.

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks, but a sorting network is not that efficient (compared to HE add / mul ..). It seems that when we talk about HE efficiency, it's not only the caculation speed gap, but the way of doing algorithms also changes (Trimming is almost zero cost in plaintext). $\endgroup$
    – Cheng Hong
    Commented Aug 5, 2020 at 8:00
  • $\begingroup$ @ChengHong What is efficient for you? $\endgroup$
    – kelalaka
    Commented Aug 5, 2020 at 15:29
  • $\begingroup$ @kelalaka I am thinking that the traditional way of expressing HE efficiency (e.g. HE calculations is 3~4 orders of magnitude slower than cleartext) is not accurate. Instead, some HE operations (like this question) could be slower by the factor of N. $\endgroup$
    – Cheng Hong
    Commented Aug 6, 2020 at 2:38
  • $\begingroup$ @ChengHong the semantical security prevents a usual if, you might consider according to this. $\endgroup$
    – kelalaka
    Commented Aug 6, 2020 at 6:24
  • $\begingroup$ @ChengHong You're right that there is an algorithmic overhead to applications for homomorphic encryption. This is because if the computational path chosen depends on the particular data being computed on, it can leak information about the data. People develop algorithms for this context, the relevant things to search are "Data oblivious algorithms". Most research so far has been because there are parallelism benefits to data oblivious algorithms though. $\endgroup$
    – Mark Schultz-Wu
    Commented Aug 6, 2020 at 17:54
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.