2
$\begingroup$

A secure and somewhat fast way to "re-encrypt" (refresh? anonymise?) a Paillier ciphertext, $c$, is to multiply it by an exponentiated random value:

$c \gets c \cdot r^n \mod n^2$ (with $r \in \mathbb{Z}_n$ random)

However, that mod exponentiation of a large $r$ is quite costly (many orders more than the other operations involved). So, in cases where many successive re-encrypt would be necessary, it seems very tempting to store and reuse the same $s = r^n \mod n^2$.

Hence, after two re-encryptions, the cipher would contain:

$c \cdot s^2 \mod n^2$

and so on...

Such a re-encrypt method would only use multiplications and be vastly cheaper that the common method.

Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k, k < i$ (and thus preserve the security of all ciphertexts). Is this correct?

The weakness seems to be in the risk that one such multiplication would not trigger a wrap-around, but maybe a solution to that would be to keep multiplying until we are guaranteed one has occurred.

As a variant: we could use a small pool of such pre-calculated exponentiated random values for each re-encryption, thus ensuring the wrap-around always occurs.

Am I missing an obvious security flaw here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

The first obvious objection is that it would do a lousy job of blinding values; if you reuse the blinding factor, then it would be practical to correlate the blinded values with their original ones (and the entire point of blinding values is to prevent anyone from doing so).

Suppose we had two original encrypted values $c$, $d$, and the corresponded blinded versions $x = c \cdot r_1^n$ and $y = d \cdot r_2^n$. Knowing nothing else, it would be infeasible to decide whether $x$ is a blinded copy of $c$, or a blinded copy of $d$.

However, if $r_1 = r_2 = r$, we can check if $c \cdot y = d \cdot x$. If $x$ is a blinded version of $c$, and $y$ is a blinded version of $d$, then this check gives us $c \cdot d \cdot r^n = d \cdot c \cdot r^n$, or in other words, equality holds.

In addition, you ask:

Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k,k<i$ (and thus preserve the security of all ciphertexts). Is this correct?

That is also not correct. Given $c \cdot s^2$ and $c \cdot s$, the attacker can recover $c$ by computing:

$$(c \cdot s^2)^{-1} \cdot (c \cdot s)^2 = c$$

$(c \cdot s^2)^{-1}$ is the inverse of $c \cdot s^2$ modulo $n^2$, it can be computed as long as $c \cdot s^2$ is relatively prime to $n^2$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Indeed, the second equality also does seem to hold and would make single-value blinding a non-starter (not so surprisingly). I wonder if there would be any way to prove that, for a sufficiently large pool of random values, and using, say $k$ randomly picked items out of $n$ each time, we have security... $\endgroup$
    – Dave
    Jan 14, 2015 at 16:12
  • $\begingroup$ On further thought, such a variant seems like enough of a separate problem (mainly down to computing combinatorial odds, I think) to maybe warrant a separate question... $\endgroup$
    – Dave
    Jan 14, 2015 at 16:15
  • $\begingroup$ Here's my attempt at a more general protocol. Unlike the one above, this one seems intuitively "secure enough" to me in practice, but I'd be very interested in what can be attempted to evaluate its actual formal security level if you feel like a stab at it... $\endgroup$
    – Dave
    Jan 14, 2015 at 16:49

Your Answer

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

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