Also, you can't really prove that such an algorithm is secure.
Incorrect. One Time Pad encryption is provably secure. (Proven by Claude Shannon, no less; as in, the guy who invented information theory.) It is impossible to decrypt if you do not have the key.
One time pads strain the definition of "encryption" and are by convention a bozo filter for people talking about crypto. For instance, downthread, you have someone saying that an all-zeroes OTP key would in theory be fine.
In reality, all OTPs do is shift forward in time a relationship that must still be secured through some other means.
So, from now on, when we talk about the feasibility of breaking crypto, let's implicitly constrain "crypto" to "crypto that people can use in practice".
i think you've misunderstood what i was saying. the OTP is definitely not a practical method of encryption, obviously.
and no, OTPs do not require that the that any secure relationship be formed forward in time.
in fact, restricting "crypto" to "crypto that people can use in practise" doesn't rule out the OTP - it was used with great success in both world wars, owing to the fact that agents were able to share keys before the fact, use them once, and then discard them.
finally, at no point would i ever suggest using the OTP as a means of encryption in place of a public key system, especially one with a key of 0s. why you suggest such a thing is beyond me.
keeping the key safe, yes, using the key once, yes, but need not be random at all (with in reason - a key of 0s is feasible, under the pretense that the cipher text, which would be equal to the plain text, is the cipher text for any message with the same length, for some key)
the key space being the same size as the message space, and cipher text space means that all messages of equal length are possible, with no way of knowing which one is the correct one. i suppose, a theoretical attack would be to be to enumerate all messages in the english language, XOR them with the cipher text, and see which resulting keys come close the properties of the PRNG used..
even non-determinism can't help you here, i'm afraid.
I leave the reason that this is among the funnier HN crypto comments ever as an exercise to the reader. And, of course it happened on a Bitcoin thread.