Paillier
出於安全原因，Paillier 密碼系統中的素數長度是否相同？
繼續這個關於素數長度的問題，我對素數長度本身的限製表示懷疑。
在 Paillier 密碼系統中，使用了等長的素數。
我懷疑這個限制是否只是為了確保以下條件
$$ \gcd(pq,(p-1)(q-1))=1 $$ 或者，還有另一個安全原因使得等長條件成為強制要求。
我的意思是，在像 RSA 這樣的密碼系統中，出於安全原因，通常首選長度大致相等的素數，如果長度大於指定值，則密碼系統不安全。
paillier cryptosysyem 是否也一樣？
不，完全相等的素數長度 $ p $ 和 $ q $ 對於Pailler 密碼系統中的安全性（或正常執行）來說，這不是強制性的。充分的要求是 $ p $ 和 $ q $ 是素數， $ N=p q $ 很難考慮，並且 $ \gcd(p q,(p-1)(q-1))=1 $ .
要求 $ p $ 和 $ q $ 通常在 Pailler 密碼系統中製作完全相同的大小，因為這個要求
- 暗示 $ p<2q<4p $ ，這意味著 $ \gcd(p q,(p-1)(q-1))=1 $ ，這是 Pailler 密碼系統工作的必要條件；
- 在 RSA 中是慣用的，因此是一個容易滿足的條件，並且從安全形度來看是無可非議的；
- 是FIPS 186-4和更早的 ANSI X9.31 RSA 密鑰生成標準要求的更嚴格條件的結果，這兩個標準都要求 $ 2^{k-1/2}<p<2^k $ 和 $ 2^{k-1/2}<q<2^k $ 對於整數 $ k $ 至少 512（並進一步受到限制，包括為 64 的倍數），因為它簡化了 RSA 的實現，包括使用CRT 方法；並且類似的實現考慮適用於 Pailler 密碼系統。
更準確地說，在安全方面：
- 即使強加 $ p $ 和 $ q $ 大小完全相同確實減少了選擇 $ N $ ，因此至少有助於一些分解算法（尤其是費馬和導數），如果這些算法可以擴展到具有賠率的因子，那將是一個驚喜 $ \epsilon $ 並且預期成本低於 $ \epsilon\min(p,q)^u $ 操作，其中 $ u\approx2/5 $ 在我們最瘋狂的夢想中，甚至 $ u\approx1/2 $ 難以到達；因此，這種算法一開始就不必擔心，因為如果兩個隨機生成的大小近似相等的素數的乘積使得GNFS分解足夠困難，它們就沒有值得考慮的可能性；說 $ N $ 至少 768 位（目前的學術記錄），因此 $ \min(p,q) $ 至少 350 位，使 $ \min(p,q)^{2/5} $ 至少 140 位。
- 相反，那 $ p $ 和 $ q $ 大小完全相同略微增加了預期的分解時間 $ N $ 由給定大小的次指數ECM $ N $ ，並且不會降低我們知道的任何其他次指數算法的預期成本；因此，從安全的角度來看，可以認為比不這樣做更有益。