/lesson/

IP = PSPACE (Little technical knowledge required)

I won't go into too many details, but a very very surprising result due to Adi Shamir proved that IP = PSPACE unconditionally. What this means is that the things you can prove with interactive proofs is very very very large.

Problems in PSPACE include things like generalized chess (an arbitrary size board but dont let the game go on forever).

This means that someone with infinite power can prove to you some sequence of moves in chess is optimal, and you can make sure she's not telling any lies, even though solving chess yourself is basically impossible!

--------

Formal definition of computational zero knowledge. CS/stats knowledge required.
This is just an interesting way to state what zero knowledge means.

Define a PPT as a probablistic polynomial-time Turing machine (or computer, if you don't know what Turing machines are).

Then two distributions of random variables A, and B, are indistinguishable if for any PPT (there are infinite of them), given some list of values from either A or B, they can't tell if the values came from A and B.

The random variables themselves could be very different, but as long as they're close enough such that you can't tell them apart in polynomial-time, we're good.

Then we define the zero knowledge property as, if an IP is ZK, and the statement we're trying to prove is true, then there exists some polynomial time simulator S that can simulate the prover's responses to the verifier. Note that S doesn't have infinite power, S has the same amount of power as V, but S can still produce the same distribution of output that the prover does.

This seems kind of weird right? That's why the invention of Zero Knowledge Proofs (by Goldwasser) was so revolutionary.

If you're interested in this, then I'd suggest looking at www.cs.cornell.edu/courses/cs6830/2009fa/scribes/lecture17.pdf, which suggests that assuming that commitment schemes exist, then all of NP has zero knowledge proofs.

Interesting stuff, OP.

Took a discrete mathematics class recently and that really got me in to this side of math and computer science, though I've always been interested in computer security in general.

Thanks for sharing

It turns out, due to a result of Goldwasser, Sipser, Micali, et al., assuming one-way functions exist, every single interactive proof also admits a zero knowledge proof. If you're following along a proof sketch is easy.

Convert the IP to be an Arthur-Merlin protocol, so the coins are public.

But then, instead of a plaintext response, the prover encrypts her messages before sending them to you so you can't understand them. So how do you verify? Well, the statement "If you know the encryption key, you would accept" is in NP. So you can reduce to 3-coloring (See the Cornell link I posted above) and prove that instead.

This has very serious implications in cryptography, and also in real life, since we do believe there exist one-way functions and we know of a few candidates (that are used by your computer every day to communicate securely over the Internet).

------------

If you're a math/CS person and want to learn more, I recommend Arora and Barak's Computational Complexity textbook, available online. For in depth information on zero knowledge proofs, I recommend Yehuda Lindell's notes: u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf.

-------------

This is it for me, for new information. Please respond if you have any questions about any of this, or if you're looking for more information.

A cute example I learned in discrete math was Shamir's Secret Sharing: en.wikipedia.org/wiki/Shamir's_Secret_Sharing. Only requires polynomials and modular arithmetic.

This is the same Shamir mentioned in . Also, the guy who invented Arthur Merlin proofs several decades ago is Laszlo Babai, the same person who came up with a quasipoly time algorithm for graph isomorphism. These people do a lot!

Can we make this a new general? Like everyweek someone decides to introduce a topic they're interested in and explain it to other anons. The topics could be anything science or maths related like this one just accessible to most people.

Seriously this is one of the best threads I've seen on sci in a while.

Great thread, OP!

If you wish to have more interesting, fun and educational threads on sci instead of shitty baits and popsci retards, as I know I do, take a look at this thread (it's not very presentable yet haha) and vote for the future of this board.

I know there are plenty of people just like you, and many more people who are interested in the content people like you produce, but they are barely able to communicate as they are drowning in a swamp of shit. This is not a way to go!

if you're never 100% sure about the socks how is it a real proof?

This is an interesting question both computationally and philosophically.

Most proof systems guarantee 100% soundness (for example Fitch-style for prop logic). So why are we justified claiming an IP is sound even if it's not 100% sound?

The idea is that it's because we can get arbitrarily close to 100% by just increasing the number of rounds.

If the IP guaranteed 99.999999999999% correctness no matter how many rounds there were, then this does not satisfy the definition of soundness. It has to become smaller with every round, and generally just repeating the rounds will lead to exponential amplification.

Thus you can get as close to 100% as you like without much work. Consider these two events.

A) You end up believing the socks are different colors when they're the same
B) Someone randomly picks an atom from the entire universe and it happens to be within your body

If you do the sock protocol 300 times, B is more likely than A. So for all practical purposes, we're good.

The other reason is that if we were to insist on 100% soundness, it turns out the number of things we could prove becomes very very small, in fact it's equal to the statements in NP, if you know complexity theory. So our interactive proofs aren't as powerful as they are if we're okay with arbitrarily high probability. Does that make sense?