= 27d567bc2d48d9f40e9ccc20ea370b15)
Warrigal comments on Open Thread: March 2010 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (658)
Suppose you're a hacker, and there's some information you want to access. The information is encrypted using a public key scheme (anyone can access the key that encrypts, only one person can access the key that decrypts), but the encryption is of poor quality. Given the encryption key, you can use your laptop to find the corresponding decryption key in about a month of computation.
Through previous hacking, you've found out how the encryption machine works. It has two keys, A and B already generated, and you have access to the encryption keys. However, neither of these keys is currently in use; one month from now, it will randomly choose one of the keys and start using it. You find that, through really complicated and difficult means, you can influence which of the keys the machine chooses, setting the probability to various things.
Needless to say, you might as well start cracking one of the keys now, but if the machine selects the other key, all the time you spent trying to crack the first key ends up being wasted.
Write your expected utility in terms of the probability that the machine chooses key A.
Smartass answer: use two computers, one for each of the keys. Computer time is cheap these days. If you don't have two computers, rent computation time from a cloud.
Why would you do that? If one key is more likely than the other, you should devote all your time toward breaking that key.
All else equal, in practical terms you should probably devote all your time to first finding the person(s) that already know the private keys, and then patiently persuading them to share. I believe the technical term for this is "rubber hose cryptanalysis".
Even if there is a high probability of completing both decryptions and the probability the machine chooses A over B is only slightly over .5?
Yes. At the beginning, it is better to work on A than to work on B, because the machine choosing A is more likely. After the beginning, it is still better to work on A than to work on B, because finishing A will be easier than finishing B if you've already worked on it some. On the off chance that you don't complete both decryptions, it's better to have the one you're more likely to need.
I think some of us know considerably less about cryptography than you do. I think sketerpot's suggestion was based on the assumption that most of the work would just be done by the computer and that the hacker could just sit back and relax while his two laptops went to work on the encryptions (you know, like in movies!). If the hacker needs to spend a month of his/her time (rather than computer time) to complete the decryption, then I see what you're talking about.
The assumption that most of the work would be done by the computer is correct. Perhaps sketerpot was assuming that breaking a decryption key is an operation that's impossible to parallelize (i.e. two computers both working on a single key would be no better than just one computer doing so), whereas I'm pretty sure that two computers would do the job twice as fast as one computer.
Ah, yes. That makes sense. Thanks for your patience.
Can people ROT13 their answers so I get a chance to solve this on my own? Or will there be too much math for ROT13 to work well?
It's not a puzzle; it's supposed to make a point.
Oh.
hidden answer
Do we choose a probability p the machine picks A, or does the machine start with a probability p, which we adjust to p+q chance it picks A?
You choose a probability p that the machine picks A. I guess.