# Homomorphic modulo

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

• 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. – Ilmari Karonen May 10 '19 at 11:04
• Can you be more explicit, please? – mip May 10 '19 at 11:19
• @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. – SEJPM May 10 '19 at 12:34
• @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$? – Ilmari Karonen May 10 '19 at 14:05
• 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. – Hilder Vitor Lima Pereira May 11 '19 at 9:57

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.