1
$\begingroup$

I was thinking about how to use the homeomorphic property of that cryptosystem to achieve not a "semantic security" 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 "resistance" per bit but i don't know how.

$\endgroup$
2
  • $\begingroup$ "homeomorphic" is a thing, but only distantly related to homomorphic. There's a wide gap between obfuscating code in a way allowing it's execution, and what Paillier encryption achieves. Thus the goal is not clear. Is it asked the estimated cost of breaking Paillier encryption? $\endgroup$
    – fgrieu
    May 6 at 10:13
  • $\begingroup$ @fgrieu yes my question is about that. i just added a bit of context on the why i would use short (and thus weak) keys. To rephrase the question i would ask : how much it cost, to break a 64bit keypair? and a 128bit? and so on (till 256 or so because above then seems to me too costly for what i am thinking about) $\endgroup$
    – Skary
    May 6 at 10:24
2
$\begingroup$

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 "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)".

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the reference and explanation. So seems that under 512bit it's so simple that does not constitute even a small barier valuable for obfuscation $\endgroup$
    – Skary
    May 6 at 10:43

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.