10
$\begingroup$

A while ago, I asked for an IND-CCA1 secure padding for RSA that still allows for the multiplicative homomorphic property of RSA and got no answers (yet).

Now I've seen fgrieu's answer about standard RSA being deterministic and (only?) this weak version having the homomorphism. Not this reminded me again and made me formulate this (weaker) question out of curiosity:

Is there an RSA padding such that the padded scheme is IND-CPA secure and exhibits a partial homomorphic property?

$\endgroup$
4
$\begingroup$

Here is a padding scheme for RSA that I crafted for the question. It allows encryption of strictly positive integers up to some moderate bound $b$, and such that the (ordinary) product of the plaintexts can be found from the product of the ciphertexts modulo the public modulus $N$ (with knowledge of the private key, by the method's normal decryption and unpadding method).

Plaintext $x$ with $1\le x\le b<N^{1/8}$ is randomly padded as $y=x\,r$, where random padding multiplier $r$ is a randomly seeded prime with $N^{1/8}<r<N^{3/8}$. Raw RSA encryption is then applied to $y$.

After raw RSA decryption, unpadding pulls the factors of $y$ at most $b$, and outputs their product $x$. It is possible to recognize a ciphertext obtained by using the homomorphic property from one that is not, by testing if $y/x$ is composite or not.

This has no discernible practical interest, but seems plausibly IND-CPA secure, and actually workable: padding can be made more efficient than RSA key generation; Pollard's Rho is enough for decryption for small $b$, and ECM will make $b=2^{128}$ feasible.


Variants are possible allowing decryption of the product of up to $h>2$ terms, by adjusting $b$ and the bounds for $r$. We want that $r_\text{max}<N^{1/h}/b$ and $r_\text{min}>b$. If we go that route, we also need to check that the public exponent $e$ is high enough that it remains overwhelmingly likely that $e\log_2r\gg\log_2N$, in order to prevent an $e^\text{th}$ root attack; and that there remains ample entropy in the choice of $r$ (well over twice as many bits as the security level) in order to avoid some meet-in-the-middle attacks.

We also have the option to widen the choice of the padding multiplier $r$, allowing any $r$ such that all its prime factors are above the plaintext bound $b$. That allows selection of $r$ in ways speeding-up (at least on average) the factorization job for un-padding. This is especially desirable for ciphertext obtained by the homorphic property, where it becomes compute-intensive to ensure that all unknown factors of $y$ are above $b$. We can choose $r=\prod s_i$ as the product of random primes $s_i>b$ :

  • with $s_i$ bounded by some moderate $s_\text{max}$, which will make Pollard's Rho efficient;
  • or with $s_i=1+\prod t_j$ for random primes $t_j$ bounded by some even more moderate $t_\text{max}$, which will make Pollard's $p-1$ efficient.
$\endgroup$
  • 1
    $\begingroup$ I don't even see any IND-CCA1 attack on that. ​ ​ $\endgroup$ – user991 Mar 27 '17 at 4:31

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.