The long-distance commuter

I am spending this semester as a member of the Institute for Advanced Study and a visiting professor at Princeton University, while living in New York and planning to spend some time at NYU and Columbia as well. Though this has no relation to my case, a friend once explained to me that the key to not having to do any work is to have (at least) two affiliations and two offices. When you are not at one place, people will think you are working at the other place and vice versa.

I haven’t been to New York much ever since moving out about seven years ago, and I am sure much has changed, most dramatically in the East Village. Hopefully, even as I work very, very hard, I will have time to explore the city again.

Meanwhile, night and weekend repairs in the 1-2-3 lines cause bizarrely complicated (and largely unannounced) schedule changes. To take a local uptown train from 14th street, for example, one goes to the uptown express track (there is no sign to this effect, only word of mouth). Apparently (I haven’t tested it) if one wants to go from Columbia to, say, South Ferry, one starts by going on a train that has a sign on the side that says “South Ferry.” Then one changes to the 2 or 3 express line before 14th street, while, of course, waiting for it on the local track. Then one gets down at Chambers, from which one finds a shuttle bus that will do all the stops of the 1 train until South Ferry. (Reminds me of the instructions given in the first minute of this hilarious Monty Python sketch — Note: after the first minute, the sketch keeps being famously funny, but is not, as they say, “work safe.”) It never ceases to amaze me how full the subway can be, and how safe it feels, at 3am or even 4am (to be fair, the MUNI too, in San Francisco, would probably be full around 2-2:30am, if it didn’t stop running at midnight).

Yesterday I found my way to Princeton and attended Scott’s talk on “algebrizing” proofs. The proof of a complexity result is algebrizing if it satisfies a certain property, all known non-relativizing and non-natural lower bound proofs are algebrizing, and an algebrizing proof cannot settles the P versus NP question.

Long ago, Goldreich, Micali and Wigderson proved that the existence of commitment schemes implies that every problem in NP has a computational zero knowledge interactive proofs. (I’ll refer to this result as the GMW theorem.)

Among the issues raised during and after Scott’s talk was the fact that the GMW theorem does not relativize, nor, probably, does it “algebrize.” Indeed, it seems impossible to abstract the known proofs of the GMW theorem to any model except one in which NP witnesses can be verified via a series of “local” checks, and, essentially, this property characterizes NP in the real world. (Similar issues arise when thinking about the PCP theorem, see this paper for an exploration of the issue of local checkability in non-relativizing proofs.) So one goes back to a question that has surfaced every now and then in the past twenty years: is there a model or a class of proofs where one can prove that commitment schemes imply NP is in CZK, but in which the P versus NP question cannot be settled?

Relative to a PSPACE oracle, the statement of the GMW theorem is vacuously true, because commitment schemes do not exist, and P=NP, so that P$\neq$NP is unprovable, so one cannot just use the statement of the GMW theorem plus relativizing techniques to prove $P\neq NP$, but this is quite far from a satisfactory answer.


5 thoughts on “The long-distance commuter

  1. Is it known that the GMW theorem does not relativize, or is it just the proof that does not relativize?

  2. Good question. I am sure that the result itself does not relativize, and possibly someone at some point proved it, but I don’t know any reference.

    Presumably you start from a PSPACE oracle and a random oracle. The random oracle gives you one-way functions. Then you define some predicate that is NP relative to the oracle (like that there is somewhere a certain sequence of consecutive zeroes) and provably not in P relative to the oracle. Then one argues that, for the protocol to be sound, there has to be some information-theoretic correlation between transcript and witness, and finally that such an interaction is not simulatable. (I am making it up as I go along, but it seems to be the kind of argument that could work.)

  3. Hi Luca,

    We briefly discussed that problem quite recently at the Kosher fish restaurant in LA last Fall, cast somewhat differently. (It came up during Jon Katz’s tutorial on black-box separations in cryptography.)

    Let \pi be a OWP, and consider the following NP-statement:

    { (x, r, b) | \pi^{-1}(x) . r = b }

    (here . represents dot product). This statement roughly says we’re given a commitment to a b (using Blum’s commitment scheme), and they arise fairly naturally in the other GMW work, namely the compiler for secure multi-party computation. We can prove such a statement in zero-knowledge via the GMW protocol, but we don’t know how to do it with black-box access to \pi, and as far as I know, there is no formal statement indicating that it cannot be done. I personally think that’s a shame, because it’s the classical example of a non-black-box technique in cryptography, and we have no indication that the “non-black-box”-ness is inherent.

  4. Hi Hoeteck,

    Are you aware of this paper? It seems to partially address you concern.

    Another relevant result is a
    recent construction by Chris Peikert and Brent Waters that achieves CCA secure encryption using the underlying primitive (lossy trapdoor functions) in a black box way. As far as I know, all previous constructions used the underlying primitive (trapdoor permutations and CPA secure encryption) in a non black-box way.

    Admittedly, one could also obtain CCA security from “smooth projective hashing” in a black-box way, but I wouldn’t feel totally comfortable treating smooth projective hashing as a “natural” cryptographic primitive.

  5. Hi Alon,

    Yes, yes, I’m aware of the work of Ishai et al., and it does address my question in the natural cryptographic settings. I was thinking about the complexity-theoretic statement “does the GMW theorem relativize?”. For the most natural notion of “relativizing”, an affirmative answer should mean that we can prove in zero knowledge NP-statements where the relation involves some oracle A, and all entities (the prover, verifier and simulator) treat A as a black box.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s