Sudoku and zero-knowledge proofs

The semester has just begun here, and my rate of posting will likely taper off. I do hope to finish the story I started earlier on exponential sums. In the meantime, I would like to explain a fun topic discussed in cryptography class today.

There are a lot of situations in which one party wants to prove to another that something is true, for instance that they have a certain bit of information (say, a solution to a computationally intractable problem, such as a Hamiltonian path in a large graph). However, either because the second party is not trustworthy, or because the transmission medium may be insecure, it may be ideal to make “proof” zero-knowledge. In other words, the second party needs to be convinced that the first party possesses the valuable information, but without actually learning what this information is (e.g. in the earlier example, the second party shouldn’t find out the Hamiltonian cycle).

There are a bunch of parables to illustrate the idea of a zero-knowledge proof. For instance, the Wikipedia article describes an example of a zero-knowledge proof that a graph has a Hamiltonian cycle. This protocol relies essentially on randomness, however — without it, a dishonest “prover” claiming to possess a Hamiltonian cycle could fool the verifier.

But there is a simple example of a zero-knowledge proof that does not use randomness in any way. This is a protocol to convince another party that one has a solution to a Sudoku puzzle.

 

IP=PSPACE (almost)

I gave a talk at the undergraduate mathematics colloquium on interactive proofs. The notes I prepared for myself are here.

This is a way of saying that I’m still alive, even if I haven’t had time to update this blog recently! My interests have been getting more and more homotopical in nature. I’ve been thinking about the cotangent complex, which is a non-abelian example of a derived functor—you derive the functor of Kahler differentials, defined on the (nonadditive) category of algebras over a ring. The way to do this is to use Quillen’s language of model categories. The key point is that if you derive an additive functor by taking a projective resolution, which is a cofibrant replacement in some model structure on the category of chain complexes, then naturally you should derive a non-additive functor by taking a cofibrant replacement in the category of simplicial whatever. Say, simplicial algebras over a ring. I’m hoping to be able to blog about the cotangent complex in a few days.

 

GILA 4: Testing when large polynomials are identically equal

Oftentimes, we might want to test that two polynomials are equal. Many problems can be encoded as the equality of two polynomials—as we are going to see later, the existence of a bipartite matching in a graph can be phrased by saying that a certain determinant polynomial is nonzero.

1. Polynomials

Testing that a polynomial in the usual encoding (as a list of coefficients) is nontrivial is, of course, a trivial task, one that a simple linear scan would accomplish. But, as we are going to see, the polynomials that one may wish to test for being nonzero need not be presented to us in this form. Rather, they may come to us recursively.

Here is one example. We can think of a boolean formula as a tree of gates. Each gate has one or two ends flowing into it and one edge leaving. The gates can be and, or, and not (in the last case, one edge flows in). Given the boolean inputs that flow into it, the gate outputs true or false according to the usual formulas. Finally, there are input gates where one can choose to place either true or false, and one final output gate at the end. We can connect the output lines of gates as input lines of new gates, and combining them, we can get a boolean formula.

Similarly, we could present a polynomial as a tree of gates. Each gate is either addition or multiplication; the input gates can hold variables or constants. When we put the inputs in, we get a polynomial. But in a gate of size , the total output (because of all the multiplications) could be exponential in the degree! The upshot of this is that, if we are presented with a polynomial in the form of a tree of gates, we find that actually evaluating the coefficients of the polynomial may be an exponential-time, intractable task. But if we wanted to evaluate the polynomial at a specific value, and modulo some (not too large) value, we could do it efficiently, by working through the gates and reducing mod the value at each step to keep things from getting too large.

So we get the idea that to test whether a polynomial is nonzero, it may be useful, instead of expanding it out, to evaluate it on some specific values, in which case we will get a probabilistic algorithm. However, nonzero polynomials have roots, and to make such an approach of testing work, we will have to randomize things.

 

GILA 3: Probabilistic algorithms for primality testing

Last time, we showed that prime numbers admit succinct certificates. Given a number containing bits, one could produce a “proof” that the number is prime in polynomial in space. In other words, the language containing all primes (represented in the binary expansion, say) lies in the complexity class .

In practice, though, being in does not give a good way of solving the problem by itself; for that, we want the problem to be in . Perhaps, though, that is too strict. One relaxation is to consider classes of problems that can be solved by randomized algorithms that run in polynomial time—randomized meaning that the right output comes out with high probability, that is. This is the class : by definition, something belongs to the class if there is a polynomial-time nondeterministic Turing machine such that on any computation, at least of the computation tree leads to the right answer. So the idea of is that, to decide whether a string belongs to our language , we generate a bunch of random bits and then run a deterministic algorithm on the string together with the random bits. Most likely, if the random bits were not too bad, we will get the right answer.

In practice, people tend to believe that while . But, in any case, probabilistic algorithms may be more efficient than deterministic ones, so even if the former equality holds they are interesting.

Today, I want to describe a probabilistic algorithm for testing whether a number is prime. As before, the algorithm will rely on a little elementary number theory.

 

GILA 2: Pratt certificates for primality

A strange thing has happened to me this semester. I’ve been spending more time thinking about physics and computer science than math! Granted, most of what I have been thinking about is pretty mathematical in nature, and I’ve tried to think of it that way if not.

So today in my algorithms class we were talking a bit about primality testing. It is, of course, necessary to know in practice if a given number of, say, digits is prime, for instance to use the RSA algorithm. To do this efficiently, we want our algorithm to be polynomial in . The existence of such an algorithm (the AKS algorithm) is fairly recent, and only appeared in 2002. But before that, partial results were known.

Let us consider the language that consists of all . Integers are represented in their binary expansion (or more generally their -ary expansion where ). The AKS algorithm shows that lies in the complexity class .

It is straightforward to see that ; that is, there exist short certificates to show efficiently that a number is composite. This is easy: just take a factoring as the certificate. It was also shown in the 1970s by V. Pratt that succinct certificates for primality exist, or that . I would like to explain this result, which is of course immediate from the AKS algorithm, but which has an elegant approach of its own.

 

Spanning trees, the cut property, and Kruskal’s algorithm

I decided this semester to take an algorithms course, in an attempt to finally learn some discrete math. As of late, we have been talking about graph algorithms. The problem is that, having never thought much about graphs, I don’t have a great deal of intuition for them. So I want to devote a post to try to help myself understand this material better.

The problem we are currently concerned with is the following. Let be an undirected graph, such that each edge has a “weight” or “cost” associated with it. The problem is to find a minimal spanning tree. That is, a subtree containing all the vertices and such that is minimal. The naive approach of listing every possible tree and calculating the weights for each of them is horribly inefficient here, as the number of trees on a complete graph of size grows super-exponentially.

1. Trees

To start with, I will recall the definition of a tree. All graphs will be undirected.

Definition 1 A tree is a connected graph containing no cycles.

Intuitively, one has the standard picture of a node branching out into several nodes, each of which branch into several other nodes, and so on. In fact, with the above definition one can show in fact the precise analog of the preceding statement: the “geometric realization” of a tree (when considered as a simplicial complex) is contractible. The above definition is precise, and furthermore is equivalent to the following. An easy consequence of the definition, that we will use, is that a connected subgraph of a tree is tree.

Given a graph , we are interested in the following problem: Is there a subgraph which is a tree and which contains every vertex of ? Such a subgraph is called a spanning tree. Physically, there are reasonable instances where one might wish to find one, such as in building a pipeline system. The claim is that a spanning tree always exists. To see this, we shall use the following characterization of trees:

Proposition 2 A graph is a tree if and only if it is connected and removing any edge would make it disconnected.

So trees are precisely the minimal connected graphs.

 

GILA 1: Turing machines and the halting problem

I’ve decided to bow to imaginary public pressure and do a post in a different vein, which should be accessible to anyone, and which will belong to my own GILA—for those not immersed in the know of math blog lingo, that’s generally interested lay audience—series. (OK, so I just have a new interest and need some excuse for breaking my previous promises.) So, we’re going to do a bit of theoretical computer science.

Turing machines

For theoretical computer science, we need a notion of an algorithm. One could readily agree that adding two decimal numbers via the elementary school procedure, sorting integers via mergesort, and the sieve of Eratosthenes are all algorithms. In particular, anything that can be written in a programming language should qualify as one. However, this intuitive notion needs to be made precise if one wishes to use it in a mathematical sense.

It is widely agreed (the Church-Turing thesis) that the appropriate notion of algorithm is given by Turing-computability.

First of all, we will describe what a problem is. To us, it will be represented simply as a string of characters belonging to a fixed finite alphabet . For instance, there is the problem of testing whether two integers are equal can be represented as follows one has a string over the alphabet , where the separator is used to separate the two integers. Then, the (rather trivial) problem of testing whether two integers are equal becomes a question about whether a certain string has a certain property. Or, equivalently, whether it belongs to a certain language, which is a collection of strings over a fixed alphabet. In practice, we will generally speak of languages rather than problems.

A Turing machine is a device used to simulate an algorithm. Informally, a Turing machine has the following parts: