LaTeX2WP minor update

LaTeX2WP is a program that converts a LaTeX file into something that is ready to be cut and pasted into the WordPress online editor. It makes it easier to write mathematical posts, to post lecture notes on WordPress, and so on.

A new version is now available, which fixes a couple of bugs:

• WordPress has trouble if a mathematical expression containing is followed by a mathematical expression containing . This is prevented by converting the inequality symbols to their HTML “character codes.”
• The previous version of LaTeX2WP had trouble with long sentences in square brackets; this is fixed.

In addition, \S for § and \v{C} for Č (as “in Stone–Čech compactification”) now work.

CS276 Lecture 27: Computational Zero Knowledge

Scribed by Madhur Tulsiani

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.

The Loser Gets Pregnant First

After reading the mouseover text of today’s dinosaur comic:

I couldn’t help looking up the Pseudobiceros hancockanus flatworm, and here is a PBS video of two of them engaged in penis fencing. (direct link)

The Triangle Removal Lemma

[At the end of a survey paper on additive combinatorics and computational complexity which is to appear in SIGACT News, I list three major open questions in additive combinatorics which might be amenable to a "computer science proof." They are all extremely well studied questions, by very smart people, for the past several years, so they are all very long shots. I don't recommend anybody to start working on them, but I think it is good that as many people as possible know about these questions, because when the right technique comes along its applicability can be more quickly realized.]

The first question is to improve the Triangle Removal Lemma. I have talked here about what the triangle removal lemma is, how one can prove it from the Szemerédi Regularity Lemma, and how it implies the length-3 case of Szemerédi’s Theorem.

As a short recap, the Triangle Removal Lemma states that if is an -vertex graph with triangles, then there is a set of edges such that the removal of those edges eliminates all the triangles. Equivalently, it says that if a graph has triangles which are all pair-wise edge-disjoint, then there must be triangles overall.

The connection with Szemerédi’s Theorem is that if is an abelian group with elements, and is a subset of with no length-3 arithmetic progressions (i.e., is such that there are no three distinct elements in such that ), then we can construct a graph that has vertices, pair-wise edge-disjoint triangles, and no other triangles. This contradicts the triangle removal lemma if , and so we must have .

This is great, until we start looking at the relationships between the constants hidden by the notation. Quantitatively, the Triangle Removal Lemma states that for every there is a such that if a graph has at least pair-wise edge-disjoint triangles, then it has at least triangles. The only known proof, however, has incredibly small: grows like a tower of exponentials of height polynomial in . The proof uses the Szemerédi Regularity Lemma, and the Regularity Lemma is known to require such very bad dependencies.

63 years ago, Behrend showed that , prime, has a subset that contains no length-3 arithmetic progression and whose size is . (Last year, Elkin gave the first improvement in 62 years to Behrend’s bound, but the improvement is only a multiplicative polylog factor.) Combined with the graph construction mentioned above, this gives a graph with vertices, edge-disjoint triangles, and no other triangle. Thus, the graph has triangles where , but one needs to remove edges to make it triangle-free, where . This shows that, in the Triangle Removal Lemma, must grow super-polynomially in , and be at least .

The question is to shorten the gap between the tower-of-exponential relationship between and coming from the proof via the Szemerédi Regularity Lemma and the mildly super-polynomial lower bound coming from the above argument.

CS276 Lecture 24: Zero Knowledge Protocols

Scribed by Milosh Drezgich

Summary

Today we introduce the notion of zero knowledge proof and design a zero knowledge protocol for the graph isomorphism problem.

CS276 Lecture 28: the CZK 3-Coloring Protocol

Summary

Today we define the notion of computational zero knowledge and show that the simulator we described in the last lecture establishes the computational zero knowledge property of the 3-coloring protocol.

CS276 Lecture 22: Signatures in the Random Oracle Model

Summary

In the last lecture we described a very complex signature scheme based on one-time signatures and pseudorandom functions. Unfortunately there is no known simple and efficient signature scheme which is existentially unforgeable under a chosen message attack under general assumptions.

Today we shall see a very simple scheme based on RSA which is secure in the random oracle model. In this model, all parties have oracle access to a random function . In implementations, this random function is replaced by a cryptographic hash function. Unfortunately, the proof of security we shall see today breaks down when the random oracle is replaced by hash function, but at least the security in the random oracle model gives some heuristic confidence in the design soundness of the construction.

CS276 Lecture 27 (draft)

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.

Simulatabilation

Writing notes on cryptography, it is useful to have an adjective to describe “the condition of something that can be simulated” and also to have an associated noun for the concept. Although such words are not to be found on the OED or the Webster, in theory, the adjective would be simulable, and that the noun would be simulability.

(Because simulate comes from the Latin verb simulare.)

Google, however, shows 17,500 hits for “simulatable” (mostly from cryptographers) and 7,040 hits for “simulable” (mostly from physicists), and an even wider gap in favor of “simulatability” over “simulability,” with a similar distribution of sources.

Score 1 for the physicists.

(p.s. The Webster list “simulative” as the adjective associated to verb simulate. So it should be uncontroversial to say “the simulative approach to defining security . . .”)

Italian-Style Marketing

I am often reminded of a “parable” I heard from Oded Goldreich, attributed to Silvio Micali. Here is my third-hand rendering:

How come Italian wine is underappreciated compared to French wine?

If you go visit a French winery, the owner will tell you “Well, French wines are the best wines in the world, as everybody knows. But this area is where there is the best soil and best weather in France for grapes, which is why the best French wines come from here. And in my winery, we make the best wine of the area.”

You then go visit an Italian winery, and the owner will tell you “In this country, everybody is a crook. The other wineries, they are all cheats, criminals, they put chemicals in the wine. I am the only honest person in this business, you shouldn’t drink anybody else’s wine.”