You are currently browsing the monthly archive for May 2009.

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.

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.

Read the rest of this entry »

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)

[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 {G} is an {n}-vertex graph with {o(n^3)} triangles, then there is a set of {o(n^2)} edges such that the removal of those edges eliminates all the triangles. Equivalently, it says that if a graph has {\Omega(n^2)} triangles which are all pair-wise edge-disjoint, then there must be {\Omega(n^3)} triangles overall.

The connection with Szemerédi’s Theorem is that if {H} is an abelian group with {n} elements, and {A} is a subset of {H} with no length-3 arithmetic progressions (i.e., {A} is such that there are no three distinct elements {a,b,c} in {A} such that {b-a = c-b}), then we can construct a graph {G=(V,E)} that has {3n} vertices, {|A| \cdot n} pair-wise edge-disjoint triangles, and no other triangles. This contradicts the triangle removal lemma if {|A| = \Omega(n)}, and so we must have {|A| = o(n)}.

This is great, until we start looking at the relationships between the constants hidden by the {o(\cdot )} notation. Quantitatively, the Triangle Removal Lemma states that for every {\epsilon} there is a {\delta = \delta(\epsilon)} such that if a graph has at least {\epsilon \cdot n^2} pair-wise edge-disjoint triangles, then it has at least {\delta \cdot n^3} triangles. The only known proof, however, has {\delta} incredibly small: {1/\delta} grows like a tower of exponentials of height polynomial in {1/\epsilon}. 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 {{\mathbb Z}/N{\mathbb Z}}, {N} prime, has a subset {A} that contains no length-3 arithmetic progression and whose size is {N/2^{O(\sqrt {\log N})}}. (Last year, Elkin gave the first improvement in 62 years to Behrend’s bound, but the improvement is only a multiplicative polylog {N} factor.) Combined with the graph construction mentioned above, this gives a graph with {3N} vertices, {N^2/^{O(\sqrt {\log N})}} edge-disjoint triangles, and no other triangle. Thus, the graph has {\leq \delta N^3} triangles where {\delta < 1/N}, but one needs to remove {> \epsilon N^2} edges to make it triangle-free, where {\epsilon > 2^{-O(\sqrt{\log N})}}. This shows that, in the Triangle Removal Lemma, {1/\delta} must grow super-polynomially in {1/\epsilon}, and be at least {1/\epsilon^{\log 1/\epsilon}}.

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

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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 {H : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m}. 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.

Read the rest of this entry »

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.

Read the rest of this entry »

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 . . .”)

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.”

a

Follow

Get every new post delivered to your Inbox.

Join 263 other followers