I am not a Probabalistic Polynomial Time Turing Machine; I am a Free Man!
In a jargon-rich yet readable essay, (“Cryptographic Commitments“) David Molnar discusses the assumptions that he brings to his work as a cryptographer. Its fascinating to me to see someone lay out the assumptions portion of their orientation like this, and I think readers can ignore the specifics and get a lot out of the essay. Some tidbits:
In particular, I’ve noticed that I make certain assumptions about the world when I set up a problem. These assumptions are what make it possible for me to map a messy real-world problem into a model where I can apply the tools I have to solve the problem. You might call these philosophical commitments. I’m at the point where these cryptographic “commitments” seem so natural to me that it’s a shock when I run across technical work that makes different assumptions.
- Everything in sight is an (efficient) algorithm. Efficient, in turn, means probabilistic polynomial time. If we have a problem where Alice and Bob communicate, but they want to prevent Eve from listening in, then Alice and Bob are going to “be” probabilistic polynomial time Turing Machines or possibly families of polynomial-size circuits. Eve might be allowed arbitrarily large running time, but in any case Eve is an algorithm, and one not known to Alice and Bob (or me) in advance.
…Possibly more subtle is this example: suppose we have two theories as to why, say, real estate prices are still so high in the Bay Area after the end of dot-com boom. Theory A implicitly or explicitly requires homebuyers to solve a problem that will take them 2^(2^100) steps. Theory B does not. From my point of view, theory A will be difficult to believe, regardless of how well it performs on other criteria, such as predicting real home prices.
The issue of Alice and Bob being replaced by their representations is one that I touched on in the previous post, “Identity is Hard, Let’s go Shopping.”
Whether or not people are turing machines has interesting implications for how well we can possibly write secure code in a turning-complete language.