2
$\begingroup$

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

$\endgroup$
  • $\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 Karonen May 10 '19 at 11:04
  • $\begingroup$ Can you be more explicit, please? $\endgroup$ – mip May 10 '19 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$ – SEJPM May 10 '19 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 Karonen May 10 '19 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 Pereira May 11 '19 at 9:57
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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