Timeline for Theoretical pi-based stream cipher
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2015 at 12:45 | comment | added | Code Jockey | @StephenTouset "must" be proven? Speaking practically, it should be proven before being responsibly promoted for "blind" acceptance/consumption by the masses as a fact, but there are countless cases in the past where unproven things were nonetheless "good enough" for effective use towards "progress", so I take issue with your use of "must" - maybe you meant something different than I interpreted...(?) | |
| May 5, 2013 at 18:02 | comment | added | Stephen Touset | That is the definition of "normal": all digits have uniform probability in every possible base. And as stated earlier, that doesn't imply that they are distributed randomly, only evenly. To flip your question around, what evidence is there that the digits in $\pi$ are indistinguishable from random? We can't just assume the property of randomness merely because it would be convenient. It must be proven. | |
| May 5, 2013 at 15:38 | comment | added | David Cary | Good point. Some numbers do have more "1"s than "9"s in its decimal representation, even if that number is normal. But I was under the impression that most mathemeticians believe that not only is pi normal, but also that the decimal representation of pi has (as far as we know) exactly the same number of "1"s, "2"s, "9"s, etc. -- see "Frequency of Each Digit of Pi" by Eve Andersson. What evidence is there that the distribution is distinguishable from random? | |
| Apr 25, 2013 at 17:31 | comment | added | Stephen Touset | @DavidCary The Champernowne constant is normal, but its $n$th digit is clearly not a uniform random variable. | |
| Apr 25, 2013 at 17:10 | comment | added | David Cary | @Thomas: "most certainly"? Many mathematicians would be very surprised if it turns out that pi is not a "normal number". Are you really saying "I have discovered a truly remarkable proof of this theorem which this margin is too small to contain."? | |
| Jan 28, 2013 at 20:04 | vote | accept | Joshua Galecki | ||
| Jan 26, 2013 at 23:02 | comment | added | Thomas | @fgrieu The question mentions a one-time-pad, but if we downgrade to stream cipher security, I know not of any such result either. It could work, but we're relying on unproven assumptions here (that it isn't possible to efficiently match an $n$-digit long string in base $b$ with its first occurrence in $\pi$, for all we know an algorithm exists to do it in time faster than $O(b^n)$). | |
| Jan 26, 2013 at 14:08 | comment | added | fgrieu♦ | @Thomas: I know not result hinting at any bias in the digits of $π$ in any base; or at a distinguisher that would, in time independent of $n$, recognize with sizable advantage a fixed-length uniform random sequence from an equal length extract of the digits of $π$ starting at the $n$th. Is there such a thing? | |
| Jan 26, 2013 at 5:57 | comment | added | Stephen Touset | Nothing we've not all been guilty of at some point. Regardless, it was absolutely worth pointing out. | |
| Jan 26, 2013 at 5:52 | comment | added | Thomas | Ah, I did not see Joshua's assumption - sorry! That'll teach me to comment without reading the entire thread.. | |
| Jan 26, 2013 at 5:51 | history | edited | Stephen Touset | CC BY-SA 3.0 |
added 229 characters in body
|
| Jan 26, 2013 at 5:48 | comment | added | Stephen Touset | One of the original stated assumptions was "there are no patterns in $\pi$", from which I (perhaps incorrectly) assumed he meant something along the lines of "the distribution of digits in $\pi$ is random". Certainly if the the digits of $\pi$ are not random (as you've correctly stated is the case), this mechanism is significantly weaker than a true OTP. | |
| Jan 26, 2013 at 5:30 | comment | added | Thomas | The $n$th digit of $\pi$ is most certainly not a uniform random variable over $\mathbb{Z}_{10}$, therefore claiming that this scheme is equivalent to an OTP is incorrect (it may seem that choosing a random "starting position" is enough, but it's not - the underlying distribution of $\pi$ actually matters and if it is not uniformly random, it will destroy entropy encoded in said starting position). | |
| Jan 26, 2013 at 0:58 | history | edited | Stephen Touset | CC BY-SA 3.0 |
added 3 characters in body
|
| Jan 25, 2013 at 23:58 | history | answered | Stephen Touset | CC BY-SA 3.0 |