Skip to main content
added 60 characters in body
Source Link
Luis Casillas
  • 14.7k
  • 2
  • 32
  • 53

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

When cryptographers use the word random they use it in the sense of probability theory. What you're calling "randonmess"randomness," however, is Kolmogorov complexity, "the length of the shortest possible description of the string in some fixed universal description language." What you're calling a "compressible string" is a string whose complexity is lower than the length of the description that just hardcodes the string. And when you say "random string" you're equivocating between non-compressible string and randomly selected string, two different concepts.

A bitstring selected uniformly at random from all bitstrings of length $n$ has an expected complexity proportional to $n$—meaning that most strings by far of length $n$ are non-compressible. But such a random selection is equally likely to result in 11111111111111 as 01101001001101, so you can't categorically assert that a string so selected will be complex—only that the chance of drawing a compressible string is low.

But none of that is relevant to the security of one-time pads, which has nothing to do with the complexity or compressibility of the keys, only with the uniform random choice thereof. The secrecy of one-time pads rests on the theorem that if $p$ is a random variable with any distribution over $\{0,1\}^n$, and $k$ is a uniform random variable over $\{0,1\}^n$, then $c = p \oplus k$ is a uniform random variable over $\{0,1\}^n$. It's possible that either the randomly drawn $k$ or the computed $c$ could turn out to be compressible strings, but unlikely and irrelevant.

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

When cryptographers use the word random they use it in the sense of probability theory. What you're calling "randonmess," however, is Kolmogorov complexity, "the length of the shortest possible description of the string in some fixed universal description language." What you're calling a "compressible string" is a string whose complexity is lower than the length of the description that just hardcodes the string. And when you say "random string" you're equivocating between non-compressible string and randomly selected string, two different concepts.

A bitstring selected uniformly at random from all bitstrings of length $n$ has an expected complexity proportional to $n$—meaning. But such a random selection is equally likely to result in 11111111111111 as 01101001001101, so you can't categorically assert that a string so selected will be complex—only that the chance of drawing a compressible string is low.

But none of that is relevant to the security of one-time pads, which has nothing to do with the complexity or compressibility of the keys, only with the uniform random choice thereof. The secrecy of one-time pads rests on the theorem that if $p$ is a random variable with any distribution over $\{0,1\}^n$, and $k$ is a uniform random variable over $\{0,1\}^n$, then $c = p \oplus k$ is a uniform random variable over $\{0,1\}^n$. It's possible that either the randomly drawn $k$ or the computed $c$ could turn out to be compressible strings, but unlikely and irrelevant.

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

When cryptographers use the word random they use it in the sense of probability theory. What you're calling "randomness," however, is Kolmogorov complexity, "the length of the shortest possible description of the string in some fixed universal description language." What you're calling a "compressible string" is a string whose complexity is lower than the length of the description that just hardcodes the string. And when you say "random string" you're equivocating between non-compressible string and randomly selected string, two different concepts.

A bitstring selected uniformly at random from all bitstrings of length $n$ has an expected complexity proportional to $n$—meaning that most strings by far of length $n$ are non-compressible. But such a random selection is equally likely to result in 11111111111111 as 01101001001101, so you can't categorically assert that a string so selected will be complex—only that the chance of drawing a compressible string is low.

But none of that is relevant to the security of one-time pads, which has nothing to do with the complexity or compressibility of the keys, only with the uniform random choice thereof. The secrecy of one-time pads rests on the theorem that if $p$ is a random variable with any distribution over $\{0,1\}^n$, and $k$ is a uniform random variable over $\{0,1\}^n$, then $c = p \oplus k$ is a uniform random variable over $\{0,1\}^n$. It's possible that either the randomly drawn $k$ or the computed $c$ could turn out to be compressible strings, but unlikely and irrelevant.

Source Link
Luis Casillas
  • 14.7k
  • 2
  • 32
  • 53

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

When cryptographers use the word random they use it in the sense of probability theory. What you're calling "randonmess," however, is Kolmogorov complexity, "the length of the shortest possible description of the string in some fixed universal description language." What you're calling a "compressible string" is a string whose complexity is lower than the length of the description that just hardcodes the string. And when you say "random string" you're equivocating between non-compressible string and randomly selected string, two different concepts.

A bitstring selected uniformly at random from all bitstrings of length $n$ has an expected complexity proportional to $n$—meaning. But such a random selection is equally likely to result in 11111111111111 as 01101001001101, so you can't categorically assert that a string so selected will be complex—only that the chance of drawing a compressible string is low.

But none of that is relevant to the security of one-time pads, which has nothing to do with the complexity or compressibility of the keys, only with the uniform random choice thereof. The secrecy of one-time pads rests on the theorem that if $p$ is a random variable with any distribution over $\{0,1\}^n$, and $k$ is a uniform random variable over $\{0,1\}^n$, then $c = p \oplus k$ is a uniform random variable over $\{0,1\}^n$. It's possible that either the randomly drawn $k$ or the computed $c$ could turn out to be compressible strings, but unlikely and irrelevant.