12 events
when toggle format what by license comment
Aug 12 '21 at 13:35 comment added Raphael @Acccumulation That's switching the computation model (including randomization), IMHO in a not helpful way. Yes, brute force always works but is prohibitive. The problem with easy instances is that given the public information, deterministic solvers can find the key quickly. That would make the best case easier than guessing, which we should try to avoid.
Aug 11 '21 at 23:08 comment added Acccumulation @Raphael The best case scenario (at least from the point of view of the person trying to break the encryption) is that they randomly guess a key that happens to be correct. There's no way for an encryption system to have the best-case hardness be more difficult than the knows-the-key hardness.
Feb 10 '14 at 13:37 comment added quazgar @Raphael, it should be enough if the probability to get an undesirable "good" case is small enough. If it's say smaller than the probability to guess the correct key of a desirable "bad" case, this risk should be considered acceptable IMHO.
May 4 '12 at 22:55 history edited Juho CC BY-SA 3.0
unified format of "P != NP"
S Mar 25 '12 at 15:00 history suggested Kaveh CC BY-SA 3.0
adding a link to the cited article
Mar 25 '12 at 14:47 review Suggested edits
S Mar 25 '12 at 15:00
Mar 14 '12 at 13:49 comment added Kaveh moreover, we should be able to generate hard instances in reasonable time. In short, we need much more than just $\sf{NP\text{-}hard}$ness.
Mar 14 '12 at 10:53 history edited Mohammad Al-Turkistany CC BY-SA 3.0
added 411 characters in body
Mar 14 '12 at 10:44 history edited Mohammad Al-Turkistany CC BY-SA 3.0
added 107 characters in body
Mar 14 '12 at 10:37 comment added Raphael Don't we need hardness in the best case, too? After all, all of our keys should be secure. Or can we effectively (and efficiently) prevent the best case from happening?
Mar 14 '12 at 10:36 history edited Raphael CC BY-SA 3.0
Mar 14 '12 at 10:34 history answered Mohammad Al-Turkistany CC BY-SA 3.0