Paillier cryptosystem has self-blinding property. (change one ciphertext into another without changing the content of its decryption)

Is there any threshold encryption scheme (or just encryption scheme) which provides one time blinding?

(One time blinding means that the number of changing is limited to one.)

  • $\begingroup$ Is there any non-threshold encryption scheme which provides "one time blinding"? $\endgroup$
    – mikeazo
    Oct 31 '17 at 14:44
  • $\begingroup$ @mikeazo it is my question. 'just encryption scheme' meant non-threshold encryption scheme. $\endgroup$
    – takita
    Oct 31 '17 at 15:55
  • $\begingroup$ Okay, I didn't see that on my first pass. I doubt that there is a scheme that only supports a single blinding (which is sometimes called rerandomization in the literature). $\endgroup$
    – mikeazo
    Oct 31 '17 at 15:57
  • $\begingroup$ @mikeazo Thanks for your replying. I'll search about 'rerandomization'. Since there exists schemes like blind signatures that are 'extracted' once, I think there may be one time blinding encryption schemes either. $\endgroup$
    – takita
    Oct 31 '17 at 16:06

Ok, here is a random idea I had; it needs further analysis, especially in regards to the security parameters.

It's based on RSA; I believe that there are ways to run RSA as a threshold scheme; I'll assume that you'll use one of those.

The public key will be the normal RSA parameters $N, e$, as well as an integer $C$. The private key will be the RSA private key (and the integer $T$).

Definitions: we will call an integer $x$ smooth if all its prime factors are $< T$. We will call an integer $x$ rough if all its prime factors are $\ge T$.

Encryption method: we first encode the plaintext as a rough integer $P$ between $\sqrt[4]{N}$ and $\sqrt[4]{N}/2$. Then, the ciphertext is the value $P^e \bmod N$.

Blinding method: we take the ciphertext $C$, and select a random smooth value $\sqrt{N}/2 < S < \sqrt{N}$. Then, the blinded ciphertext is the value $C^2 S^e \bmod N$.

Decryption method: we take the ciphertext $C$, and compute $D = C^d \bmod N$. If $\sqrt[4]{N}/ 2 < D < \sqrt[4]{N}$, then $D$ is the resulting plaintext. If $D > \sqrt[4]{N}$, then we divide out all the prime factors $< T$ from $D$, and then compute the integer squareroot (and if it's not a perfect square, decryption fails); the resulting squareroot is the plaintext.


  • Blinding works because the blinded value $C^2S^e = (P^2S)^e \pmod N$, and as $P^2S < N$, RSA decryption results in the integer $P^2S$.

  • It should be obvious why blinding an already blinded value doesn't work.

  • Obviously, we need to specify the sizes of $N$ and $T$. One requirement is to make the blinding recognization problem hard, that is, given two ciphertexts $C_1$, $C_2$, determine whether one the blinded version of the other. There is a MITM attack available, such to be $s$-bits secure, there needs to be at least $2^{2s}$ smooth numbers below $\sqrt{N}$. I suspect this will imply that $N$ will need to be larger than normally required for RSA, however that needs to be analyzed. My instincts say that $N \approx 2^{4096}$ and $C = 10000$ should work reasonably, but again, real analysis is needed.

  • One thing that needs to be considered are possible weaknesses due to the homomorphic properties of RSA. Even though we're not using a conventional padding scheme, I believe we're safe (because $T$ is large and rough), however that really does need analysis.

  • Of course, this doesn't work for $e=3$; the standard $e=65537$ should be fine.

  • We also need to spell out how to randomly select a large smooth value, but again, should be spelled out.

  • The process of encoding the plaintext as a rough integer (and decoding it at the end) is straight-forward.

On review, the idea isn't perfect; an attacker could generate a "weak blind" on an already blinded value by multiplying it by $(a/b)^e$ (for small $a, b$); this works if $b$ is a factor of the $S$ the blinding used. I'll leave this answer open, in case someone sees a way to address this...


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.