Paillier estimate attack costs on short keys I was thinking about how to use the homeomorphic property of that cryptosystem to achieve not a &quot;semantic security&quot; but a less ambitous obfuscation of the source code (an ipotetical scenario in which a third party execute the obfuscated code, and get a still obfuscated result).
So i was asking myself how much computation time to break a small keysize? i am sure there is a way to calculate &quot;resistance&quot; per bit but i don't know how.
As far as we know, the most efficient attack against well-implemented Paillier encryption is to factor the public modulus $n$ part of the public key. That's also the best known attack against RSA, thus is well-studied.
For history of factorization open records, see this. In 2020, CADO-NFS has factored a 828-bit $n$ with &quot;roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)&quot;.
A smaller data point: CADO-NFS factors a 337 bit $n$ in 5 mn on a single 32-core system.


How much does it cost to break a 64bit keypair? And a 128bit? And so on till 256 or so?

Nothing worth consideration if there is a single such problem to solve.