What homomorphic cryptographic scheme should I use to perform modular reduction?
I want an encryption scheme along with an operation $\otimes$ such that
$$c = Enc(m) \otimes Enc(d) \Rightarrow Dec(c) = m \bmod d.$$
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Note that a public-key encryption scheme (or a symmetric system with an accessible encryption oracle) with this property would be completely broken: it's possible to decrypt any ciphertext bit by bit, starting from the lowest, with two encryption queries per bit. $\endgroup$– Ilmari KaronenCommented May 10, 2019 at 11:04
-
$\begingroup$ Can you be more explicit, please? $\endgroup$– mipCommented May 10, 2019 at 11:19
-
2$\begingroup$ @IlmariKaronen Note that encryption may be non-deterministic and your encryption of 0 may not be the same as the one yielded by a modulo application. $\endgroup$– SEJPMCommented May 10, 2019 at 12:34
-
3$\begingroup$ @SEJPM: With non-deterministic encryption, you can't compare ciphertexts anyway. Perhaps the actual property the OP wants is something like $D_K(E_K(m) \bmod E_K(d)) = m \bmod d$? Or perhaps with some arbitrary binary operator acting on ciphertexts instead of the first $\bmod$? $\endgroup$– Ilmari KaronenCommented May 10, 2019 at 14:05
-
2$\begingroup$ I edited the question to make it consistent with the comments. Please, if that is not what you meant, undo the edit and do your own changes to make it clearer. $\endgroup$– Hilder Vitor Lima PereiraCommented May 11, 2019 at 9:57
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
Since the plaintext domain of of the HE scheme FV (https://eprint.iacr.org/2012/144) is $\mathbb{Z}_t$, it will by default return $m \ \text{mod} \ t$.
However if your aim is to compute the reduction modulo $Q$ for an arbitrary $Q$, then you need to express your modular reduction as a circuit of additions and multiplications (or other operations supported by the HE scheme you use).
This what is done for example in the bootstrapping of the HE scheme HEAAN (https://eprint.iacr.org/2018/153), where the reduction modulo $Q$ (i.e. $f(m + K \cdot Q) \approx m$, for $K$ in a given bound) is expressed as $f(x) = \frac{Q}{2\pi}\sin(\frac{2\pi x}{Q})$, for $x \ll Q$ (about 10 bits smaller than $Q$), and is approximated with a polynomial of small degree (which can be done just with multiplications and additions).
All in all, since the reduction modulo $Q$ is not a continuous function, it is hard to approximate and there is no (known) good way to do it homomorphically, it is currently a subject of research.
