IND-CPA 具有部分同態屬性的安全 RSA 填充
不久前，我要求為 RSA 提供一個 IND-CCA1 安全填充，它仍然允許 RSA 的乘法同態屬性，但（還）沒有得到答案。
現在我已經看到fgrieu關於標準 RSA 是確定性的答案和（僅？）這個具有同態性的弱版本。不是這再次提醒我，讓我出於好奇提出這個（較弱的）問題：
是否存在 RSA 填充，使得填充方案是 IND-CPA 安全的並表現出部分同態屬性？
這是我為這個問題設計的 RSA 填充方案。它允許對嚴格的正整數進行加密，直到某個適度的界限 $ b $ ，這樣明文的（普通）乘積可以從密文模公共模數的乘積中找到 $ N $ （在知道私鑰的情況下，通過該方法的正常解密和unpadding方法）。
純文字 $ x $ 和 $ 1\le x\le b<N^{1/8} $ 隨機填充為 $ y=x,r $ , 其中隨機填充乘數 $ r $ 是一個隨機播種的素數 $ N^{1/8}<r<N^{3/8} $ . 然後將原始 RSA 加密應用於 $ y $ .
原始 RSA 解密後，unpadding 拉取因子 $ y $ 最多 $ b $ , 並輸出他們的產品 $ x $ . 有可能通過使用同態屬性從不是的密文中辨識出一個密文，通過測試是否 $ y/x $ 是否複合。
這沒有明顯的實際意義，但看起來似乎是 IND-CPA 安全的，並且實際上是可行的：填充可以比 RSA 密鑰生成更有效；Pollard 的 Rho足以解密小 $ b $ , ECM將使 $ b=2^{128} $ 可行的。
變體是可能的，允許解密多達 $ h>2 $ 條款，通過調整 $ b $ 和界限 $ r $ . 我們想要那個 $ r_\text{max}<N^{1/h}/b $ 和 $ r_\text{min}>b $ . 如果我們走那條路，我們還需要檢查公共指數 $ e $ 足夠高，它仍然極有可能是 $ e\log_2r\gg\log_2N $ , 為了防止 $ e^\text{th} $ 根攻擊；並且在選擇的過程中仍然存在充足的熵 $ r $ （遠遠超過安全級別的兩倍）以避免一些中間相遇攻擊。
我們還可以選擇擴大填充乘數的選擇範圍 $ r $ ，允許任何 $ r $ 這樣它的所有主要因素都在明文範圍之上 $ b $ . 這允許選擇 $ r $ 以某種方式加快（至少平均而言）取消填充的分解工作。這對於通過同態屬性獲得的密文尤其可取，在這種情況下，它變得計算密集，以確保所有未知因素 $ y $ 在上面 $ b $ . 我們可以選擇 $ r=\prod s_i $ 作為隨機素數的乘積 $ s_i>b $ :
- 和 $ s_i $ 受一些溫和的限制 $ s_\text{max} $ ，這將使 Pollard 的 Rho 有效；
- 或與 $ s_i=1+\prod t_j $ 對於隨機素數 $ t_j $ 以一些更溫和的為界 $ t_\text{max} $ ，這將使Pollard 的 $ p-1 $ 高效的。