Knowledge in Complexity Theory - High Level

What Is Knowledge?

Complexity Theory manages to answer this question without going into the philosophical entanglement, that one usually gets into when they try to answer this question.

Simply put; Knowledge is anything you could not have computed yourself.

This is actually not that simple and has a hidden gotcha.

Knowledge Vs Information

This is the gotcha. Lets use an analogy to figure this out.

In university/college, the first few lessons are usually a warm-up session. The lecture is usually about how to contact the professor and his office hours(when he is free).

Is this knowledge or information?

It is not knowledge because anyone could have figured this out themselves without much effort.

The professor then says “I am not available on the 25th January at 10:00”

Is this knowledge or information?

It depends. If students could have figured this out from his office hours, then it is information. If it is at a time, when he should have been free, but now he is not, then it is knowledge.

## Zero Knowledge

This distinction between knowledge and information is important, as it allows us to state when no knowledge has been provided. But still allow us to prove things are correct.

Using our college example, lets say the students want to prove that the majority of them already know the subject at the beginning of the semester. How can they prove this to the professor in zero knowledge?

What?

First off, what do I mean by “in zero knowledge”. According to our informal definition of zero knowledge. This term has a lot of weight. After proving to the professor that the students do indeed know the subject. How exactly do I show that I have not given him anything he could not have computed himself? What exactly can the professor possibly learn which he does not already know? This question has a general answer, but not for this post :)

We will assume that the only thing we want the professor to not learn is the name of students and their scores.

We can do the following:

• There are 50 students, so the teacher prepares a random exam for 50 students.
• The students then complete the exam and omit write their names.

In this instance, the professor did not learn the names of the students and upon marking all of the exams, he can verify whether the majority of students actually know the subject.

Zero Knowledge in The Real World

Zero knowledge in the real world is very much context sensitive and hard to achieve. For example, lets say that although the students did not write their names, the professor matched their handwriting to another test and using that he figured out their names with high probability. We did not take that into consideration, the handwriting itself leaks information, but only when combined with auxillary data. Although a trivial example, it is always good to look twice to see whether the public information which is leaked cannot be used to uncover the knowledge which you are attempting to hide.

Extra

Notice that randomness played an important role in the latest example. If the professor gave the students an exam to which they could prepare for, then they could look up the answers in advance.