1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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 public 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
$\endgroup$
10
  • $\begingroup$ Thanks, and r can be of any dimension ? $\endgroup$
    – witdev
    Commented Apr 8, 2020 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
    Commented Apr 8, 2020 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
    Commented Apr 8, 2020 at 16:34
  • $\begingroup$ @witdev: no, using the same $r$ would leak information; use a different random $r$ each time. $\endgroup$
    – poncho
    Commented Apr 8, 2020 at 18:33
  • $\begingroup$ I have no idea what that url is - it doesn''t resolve for me $\endgroup$
    – poncho
    Commented Apr 9, 2020 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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