Homomorphic Modular Reduction for Secure Storage

Question

My question is quite similar to Homomorphic modulo, but I want to give a context where the operation is carried in an outsourced environment.

Are there any specific homomorphic cryptographic schemes that could do the modular reduction and subtraction operations at the same time.

Suppose $Enc(x)$ a ciphertext of $x$ after homomorphic encryption, and $mod$ is modular reduction operation.
$$(Enc(x)-Enc(a))\ mod\ Enc(N) == (x-a)\ mod\ N$$ While $x$, $a$ and $N$ are all natural numbers. And $N$ are bigger than $x$ and $a$.

I know that $mod$ can be transformod into additional ($+$) and multiplicative ($*$) operations, which are operations supported by HE. But I don't want the factors exposed to someone who carry such operations, like $Server$.

For example

$(6-5)\ mod\ 10 = 1+(0*10)=1$, $(4-5)\ mod\ 10 = -1+(1*10)=9$

But when a $Server$ is assigned do this, the factors like $0$ and $1$ here are exposed.

So I'm wondering, are there any specific HE schemes that can do modular reduction operation directly, or are there any solutions that can keep $Server$ from knowing the factors?

Answer 1

Your modulo operation does not require a real division, because you are not far from your modulus.

Represent your numbers with 2's complement by using TFHE, or HELib libraries. In this case, your numbers use bit arithmetic in FHE, i.e. you will have a cyphertext $\{c_0,c_1,\ldots,c_{k-1}\}$ for $k$-bit numbers.

What operation do you need?

• $Add(A,B)$ : homomorphic addition
• $Sub(A,B) = Add(A,-B)$ : homomorphic substraction by using $Add$.
• $MSB(A)$ : return the most significant bit of the ciphertext
• Comparison $Comp(A,B) = MSB(Sub(A,B)) = MSN(Add(A,-B)) $
• If : for singe if else case with single encrypted bit $S$, $$I = S \cdot A + S' \cdot B$$ where $\cdot$ is the $\text{AND}$ operation. According to value of $S$, $I$ is either $A$ or $B$.

More details on these operations can be found in a previous answer about common circuits in FHE.

Let $A = Enc_{pk}(A)$, $B=Enc_{pk}(b)$, and $N = Enc_{pk}(n)$ be encryption of plaintexs $a,b,\text{and } n$ under a semantically secure Fully homomoerphic Encryption with public key $pk$, where $n$ is the modulus.

1. $S = Sub(A,B) = Add(A,-B)$
2. $C = MSB(S)\quad\quad\quad\;$ //one bit comparison the result.
3. $F = S + N\quad\quad\quad\quad\;$ // adding modulus if needed
4. $R = C * F + C' * S\quad$ // If condition on $C$ selects either $F$ or $S$.
5. Return $R$

The circuit is not complete because the answer can still be negative. In this case, compare with encryption of zero $E_0 =Enc_{pk}(0)$and add $N$ again.

Answer 2

A general solution is to fix the bit length of $N$ to be, say, $\ell$, then represent $a, x$, and $N$ as $\ell$-dimensional binary vectors and encrypt each bit (obtaining $3\ell$ ciphertexts), then execute homomorphically a circuit that performs a subtraction of two $\ell$-bit integers and a circuit that performs a reduction (as in @kelalaka's answer)...

However, if $N$ is small, then you can simply use a scheme whose message space $\mathcal M$ is big enough for the possible values of $x - a$ to be in it, that is, $[-N, N]\cap\mathbb{Z} \subset \mathcal M.$ In this case, the subtraction will not "overflow" and you will still be able to recover the result by simple doing a decryption and performing the modular reduction yourself.

This is more or less equivalent to choosing a homomorphic encryption scheme whose message space is $\mathbb{Z}_N$, which would also be a simple solution if $N$ is small.

Most of the schemes are presented with a binary message space, but they can be easily extended to work over $\mathbb{Z}_N$ instead of $\mathbb{Z}_2$.