I would like to know if this process is feasible under homomorphic encryption, ideally under paillier or any other additive scheme

  1. Apply a mask X to obfuscate a message A ie. Am = A (op) X where (op) can be +, x, ...
  2. Homomorphically encrypt Am => E(Am)
  3. Remove X from E(Am) in order to obtain E(A) without any decryption (without knowing the private key)

A can be a matrix, vector, ...etc.


It sounds like you're looking for a way to do blinded encryption (that is, encryption in such a way that the encryptor does not know what he is encrypting).

It is certainly possible with Paillier. Here is one way:

  • The (op) will be multiplication modulo $n$ the Paillier modulus (which is in the public key).

  • To mask, we pick a random $r$ relatively prime to $n$, and compute $Am = A \cdot r \bmod n$. We can see that, if we selected $r$ uniformly, then $Am$ is distributed independently of $A$ (except for values not relatively prime to $n$)

  • We ask the encryptor to take $Am$ to compute $E(Am)$

  • To unmask, we compute $rinv = r^{-1} \bmod n$, and then homomorphically compute $E(rinv \cdot Am)$; this Paillier, this is done by computing $E(Am)^{rinv} \bmod n = E(A)$.

One drawback to this is that it doesn't actually mask the value $A=0$; is that a concern?

If it is, you can still do it by asking the encryptor to perform two masked encrypted operations.

First, you generate two random values $r, s$, making sure that neither is $0$

Then, you have the encryptor encrypt the values $A-s$ and $r\cdot s$, producing $E(A-s)$ and $E(r \cdot s)$. Then, you use the above procedure to recover $E(s)$ from $E(r \cdot s)$. Then, you homomorphically add $E(s)$ to $E(A-s)$, producing $E(A)$

You could just generate $E(s)$ yourself with $s$ and the pubic key. However, if you could perform encryption yourself, you could just generate $E(A)$ from $A$, and it would appear you wanted to avoid that...

| improve this answer | |
  • $\begingroup$ Thanks, and r can be of any dimension ? $\endgroup$ – witdev Apr 8 at 10:51
  • $\begingroup$ @witdev: For Paillier, it would be a value between 1 and $n-1$, If the value $A$ is a vector, then you would have a vector of $r$'s, and blind encrypt each element of the vector separately. $\endgroup$ – poncho Apr 8 at 12:48
  • $\begingroup$ Thanks again, 1. Could it be a vector with a different $r$ in each of its elements or you mean a vector with the same $r$ repeated ? 2. I found in shorturl.at/jZ026 that the equivalence of $E(a [mult] b)$ is $E(a)^{E(b)}$, while you used $E(Am)^{rinv} mod n$ .. what is the difference ? $\endgroup$ – witdev Apr 8 at 16:34
  • $\begingroup$ @witdev: no, using the same $r$ would leak information; use a different random $r$ each time. $\endgroup$ – poncho Apr 8 at 18:33
  • $\begingroup$ I have no idea what that url is - it doesn''t resolve for me $\endgroup$ – poncho Apr 9 at 3:06

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.