User talk:Wonderstruck

From Wikipedia, the free encyclopedia

[edit] Welcome

Hello Wonderstruck and welcome to Wikipedia! I'm glad you've chosen to join us. This is a great project with lots of dedicated people, which might seem intimidating at times, but don't let anything discourage you. Be bold!, explore, and contribute. Try to be civil by following simple rules and signing your talk comments with ~~~~ but never forget that one of our central tenets is to ignore all rules.

If you want to learn more, Wikipedia:Tutorial is the place to go, but eventually the following links might also come in handy:
Help
FAQ
Glossary
Manual of Style

Float around until you find something that tickles your fancy. One easy way to do this is to hit the random page button in the navigation bar to the left. Additionally, the Community Portal offers a more structured way to become acquainted with the many great committees and groups that focus on specific tasks. My personal favorite stomping grounds are Wikipedia:Translation into English as well as the cleanup, welcoming, and counter-vandalism committees. Finally, the Wikimedia Foundation has several other wiki projects that you might enjoy. If you have any more questions, always feel free to ask me anything on my talk page. Again, welcome! -- Draeco 17:44, 9 February 2006 (UTC)

[edit] CSPRNGs and root-finding algorithms

Re this edit of yours: Could you please explain the link? I'm having trouble seeing the connection. Thanks. -- Jitse Niesen (talk) 00:15, 14 February 2007 (UTC)

Sure. A PRNG is an algorithm that takes a finite number of bits as input (the "seed") and produces a much larger (though finite) number of output bits. Therefore, every PRNG can be represented as a function, f(x), where x is the seed. More formally:

One of the requirements of a cryptographically secure PRNG is that it has to pass the "next-bit test". One way to formulate the next-bit test is to define a function g_m(x) that evaluates to the leftmost m bits of f(x). A PRNG passes the next-bit test if and only if for every m < n, the probability of correctly guessing g_{m + 1}(x), given only g_m(x), is no higher than 50%.

Imagine that Alice wants to convince her colleague, Bob, that a given PRNG f(x) fails the next-bit test. Bob chooses a random 128-bit secret x, computes a₂₀₀ = g₂₀₀(x), and reveals a₂₀₀ to Alice. If Alice can predict the next 100 bits of PRNG output (that is, if she can correctly guess the value of g₃₀₀(x)) without being given x, then Bob will be convinced that f(x) fails the next-bit test.

Let h(y) = g₂₀₀(y) − a₂₀₀. If Alice can use a root-finding algorithm to find y such that h(y) = 0, then it is likely that y = x, and, therefore, that g₃₀₀(y) = g₃₀₀(x).

In other words, if a PRNG can be solved using a root-finding algorithm (in polynomial time), then it is not cryptographically secure. So, cryptographically secure PRNGs are designed so that they can't be solved (in polynomial time) by any known root-finding algorithms.

Does that make sense?

P.S. I just added the link as an interesting bit of trivia, so if you think it should be removed, that's fine.

-- Wonderstruck 05:40, 14 February 2007 (UTC)