I worry that these summaries while roughly correct are vague enough that someone who isn’t already familiar with a lot of the results will end up interpreting the statements in ways that are incorrect. There may be an illusion of transparency issue in making many of these statements seem to you like they are uniquely determining the correct interpretations.
For example you wrote:
For example, if I give you randomly chosen x, y > 1, it is easy to compute their product xy. But if I give you their product xy, it is hard to recover x and y.
This isn’t quite true. The most nitpicky issue is that in order for this to even make sense x and y need to be integers). But even given that, it isn’t in general possible to recover x and y at all from x*y. The only circumstance where this makes sense is when x and y are prime (otherwise x*y is simply not enough information). If one doesn’t restrict to x and y being prime and just asks for given x*y find a non-trivial factorization, this is for most distributions of x and y easy. (I don’t know if this is easy in the sense of polynomial time, but it certainly has close to polynomial time bounds with probability 1 and in practice is generally doable even for very large integers.A random integer n must have a prime factor that is at most about n^(1/log log n). This follows since w(n), the number of distinct prime factors of n, has both average and normal order log log n. In fact one can using slightly more sophisticated methods get better results for how small the smallest prime factor must be).
Similarly, in your entry about private key cryptography you write:
Suppose that Alice and Bob share a secret of length k, and would like to send a message so that an eavesdropper who doesn’t know the secret can’t understand it. If they want to send a message of length at most k, they can use a one time pad. Private key encryption allows them to send a much longer message in a way that is indecipherable to someone who doesn’t know the secret. Private key cryptography is possible if a OWF exists.
This is misleading in that one-time pads are provably secure independent of whether or not one way functions exist. The issue here, as I understand it, is that private key exchange exists if one way function exists. That is, if one way functions exist, we can have the key exchange protocol be completely eavesdropped and still have a shared secret key at the end of the process.
You are correct that I do need to restrict to integers (which seems a forgivable omission) and that I really do need to make x and y k-bit integers, not just > 1 (which is less forgivable).
The statement about private key encryption is basically correct though. A one-time pad allows you to send a message which is no longer than the pad. But if you want to send a much longer message, as I said, or to send many messages, you can’t use a one-time pad. You need to do something different, such as inflate your shared random secret to a much longer psuedorandom secret.
In general, there are probably many slight untruths here. I didn’t think that was too horrible since most people’s understanding is very bad (and they are pretty slight untruths), but I don’t really know.
I worry that these summaries while roughly correct are vague enough that someone who isn’t already familiar with a lot of the results will end up interpreting the statements in ways that are incorrect. There may be an illusion of transparency issue in making many of these statements seem to you like they are uniquely determining the correct interpretations.
For example you wrote:
This isn’t quite true. The most nitpicky issue is that in order for this to even make sense x and y need to be integers). But even given that, it isn’t in general possible to recover x and y at all from x*y. The only circumstance where this makes sense is when x and y are prime (otherwise x*y is simply not enough information). If one doesn’t restrict to x and y being prime and just asks for given x*y find a non-trivial factorization, this is for most distributions of x and y easy. (I don’t know if this is easy in the sense of polynomial time, but it certainly has close to polynomial time bounds with probability 1 and in practice is generally doable even for very large integers.A random integer n must have a prime factor that is at most about n^(1/log log n). This follows since w(n), the number of distinct prime factors of n, has both average and normal order log log n. In fact one can using slightly more sophisticated methods get better results for how small the smallest prime factor must be).
Similarly, in your entry about private key cryptography you write:
This is misleading in that one-time pads are provably secure independent of whether or not one way functions exist. The issue here, as I understand it, is that private key exchange exists if one way function exists. That is, if one way functions exist, we can have the key exchange protocol be completely eavesdropped and still have a shared secret key at the end of the process.
You are correct that I do need to restrict to integers (which seems a forgivable omission) and that I really do need to make x and y k-bit integers, not just > 1 (which is less forgivable).
The statement about private key encryption is basically correct though. A one-time pad allows you to send a message which is no longer than the pad. But if you want to send a much longer message, as I said, or to send many messages, you can’t use a one-time pad. You need to do something different, such as inflate your shared random secret to a much longer psuedorandom secret.
In general, there are probably many slight untruths here. I didn’t think that was too horrible since most people’s understanding is very bad (and they are pretty slight untruths), but I don’t really know.
Good on you for knowing your inferential distances.