Wanted: Quantum GGM theorem
A commenter on my last post writes:
Dear Scott, Please keep the focus of your blog. You have lately been losing science to your blog and started blogging about various loosely related things. One of the ways I subscribed to your blog was because your articles were very computation-oriented. Now you no longer keep the theme. And as you might have heard, shifting topics in your blog will lose your readers.
So today I noticed something bizarre. A celebrated result in cryptography, due to Goldreich, Goldwasser, and Micali, states that any pseudorandom generator gives rise to a pseudorandom function family. See Luca’s notes or the original GGM paper for more.
Now I’d always assumed, without thinking about it, that the GGM result “obviously” carries over to the quantum case—so that any pseudorandom generator secure against quantum attack would give rise to a pseudorandom function family secure against quantum attack. But now that I’m writing a paper that actually relies on this “fact,” I realized I have no idea why it’s true.
Look: in the GGM argument, you start with a pseudorandom generator G:{0,1}n→{0,1}2n, and you apply it recursively to produce a family of functions fs:{0,1}n→{0,1}n, where s is the seed. You then consider a hypothetical polynomial-time algorithm A that distinguished fs from a truly random function. You show how you could use A to create a polynomial-time algorithm that distinguished the output of G from a truly random 2n-bit string—thereby contradicting the starting assumption that G was pseudorandom.
The trouble is, the argument relies crucially on the fact that A examines only a polynomial number of outputs of fs—intuitively so that you can run a hybrid argument, changing the outputs that A actually examines one by one into truly random strings. But if A is a quantum algorithm, then (duh) it can examine all 2n outputs of fs in superposition! So any argument that depends on “watching A to see which inputs it queries” is toast.
But maybe we can recover the same conclusion in a fancier way? For at least seven years, I’ve been going around conjecturing the following:
Conjecture (
): Let Q be a quantum algorithm that makes T queries to a Boolean input X∈{0,1}N. Then for all ε,δ>0, there exists a deterministic classical algorithm that makes poly(T,1/ε,log(1/δ)) queries to X, and that approximates Q’s acceptance probability to within ε on a 1-δ fraction of inputs.
My motivation for Conjecture () had nothing to do with cryptography. I was interested in whether we could rule out the possibility that P=BQP relative to a random oracle with probability 1. If Conjecture () holds—and if the classical algorithm is anything like I think it is—then we can’t rule it out, at least not without proving P≠PSPACE or an even stronger separation in the unrelativized world.
It now occurs to me that, if we knew how to prove Conjecture (), then maybe we could push through a quantum GGM argument using similar ideas—that is, by identifying a tiny subset of inputs to fs that the quantum algorithm’s acceptance probability “really” depends on. Alas, I have good reason to believe that Conjecture () is hard.
So the task remains: prove a quantum GGM theorem. Or maybe I’m missing something completely obvious?
PS. The promised report on the QIS conference in Virginia is coming tomorrow. Take that, future self!
Update (5/3): An anonymous commenter points out that we can use a simpler hybrid argument of Razborov and Rudich—which doesn’t break down in the quantum case—to show that if there exists a PRG that’s secure against 2n^Ω(1)-time quantum adversaries, then there also exists a PRF with polynomial seed length that’s secure against exponential-time quantum adversaries. That somehow hadn’t occurred to me, and it’s good enough for my purposes. (Masked cryptographer: emerge ye from the shadows, and claim thy rightful honour in my Acknowledgments!) On the other hand, the extremely interesting question still stands of whether one can prove a “strong,” GGM-style reduction: from PRGs secure against f(n)-time quantum adversaries to PRFs with linear seed length secure against f(n)Ω(1)-time quantum adversaries, for any superpolynomial f.
Follow
Comment #1 May 3rd, 2009 at 1:50 am
I am probably missing something, but it’s not clear that conjecture smiley-face is taking you closer to your goal of a quantum GGM; if your classical simulation of bounded query complexity requires exponential time, I don’t see how you would use inside a reduction. (That is, you might be able to show that the behavior of your quantum algorithm depends on few values of f(), but the reduction would need to know which values of f() are the ones that the behavior of the algorithm depends on.)
Comment #2 May 3rd, 2009 at 2:44 am
Luca: Of course you’re absolutely right; that’s one reason why I don’t know how to show that 🙂 would imply quantum GGM. (The other reason is that even if 🙂 holds, conceivably the quantum algorithm does something crazy and hard to simulate on the pseudorandom distribution.)
All I have is a meta-conjecture: that if we could prove 🙂 , it would be by an argument that also proved quantum GGM. More concretely, I think it should be possible to identify the influential inputs in BQP, using the following strategy:
(1) Run the quantum algorithm Q poly(T) times, on various pseudorandom functions g1,g2… of your own creation (i.e., not the “real” function f).
(2) On each run, measure Q after a random number of queries from 1 to T. Write down the input x∈{0,1}n that Q was “caught querying” at the time of measurement.
(3) For each input x that you wrote down, query f(x) for real.
(4) Create new functions g1,g2… that agree with f on the x’s you queried, but that are pseudorandom everywhere else.
(5) Go back to step (1), using your new g1,g2… Repeat until Q’s acceptance probability is almost entirely determined by the part of f that’s fixed (i.e., until it’s almost independent of the part of f that you made up pseudorandomly).
The conjecture, which implies 🙂 , would be that the above algorithm halts w.h.p. after poly(T) iterations.
Comment #3 May 3rd, 2009 at 4:48 am
And the contrary view is … not being a quantum computer jockey myself, I read your blog for all the other stuff. I’d hate it all to go away. So good luck judging how to tip the balance.
Comment #4 May 3rd, 2009 at 9:32 am
I read Shtetl Optimized for both Luca’s reasons *and* Michael’s reasons (except for posts about rap songs).
Thank you, Scott … you put in a lot of work either way.
Comment #5 May 3rd, 2009 at 10:00 am
Personally, Idon’t read Scott’s blog. I’m here to watch other people read it 🙂
Comment #6 May 3rd, 2009 at 10:24 am
Michael, yours is the most interesting reason of all! 🙂
Comment #7 May 3rd, 2009 at 12:28 pm
To the commenter on previous post: One of the things people like about Scott’s blog is its inclusive nature. I like the way he blogs about lot of different topics.
Comment #8 May 3rd, 2009 at 12:50 pm
Thanks for the clear example of when intuition from the classical fails to carry over to the quantum setting. Even if conjecture 🙂 is not enough, can you formulate a precise conjecture :)’ that is provably enough for a quantum GGM? Is the conjecture in your comment above that :)’ ? If so, then at least we’d have a clear place to start studying your question and its relationship to Conjecture 🙂 .
(Why the name, by the way?)
I actually came over to your blog because I was looking for a comment I thought you made a few years ago about how people were publishing too many theorems whose proofs could be obtained by “changing all the BPPs to BQPs.” I wanted to ask if you believed a meta-theorem was possible that could tell us when such a ‘trivial’ proof transformation is possible and when not.
Still curious. In any case, sounds like any such meta-theorem would have to be strong enough to “detect” the GGM proof technique given your remarks above.
Comment #9 May 3rd, 2009 at 2:05 pm
In my case, changing topics will earn you readers. And links (both in cyber- and meat-space). But there are more boring people on Earth, I know.
Comment #10 May 3rd, 2009 at 2:45 pm
Thanks for switching back to computational complexity, Scott. It really is the reason I read your blog (I can get the weird ideas elsewhere…)
But also I’d like to hijack this right back to a topic away from computational complexity. Remember the El Naschie case? Check out http://blog.bioethics.net/2009/05/merck-makes-phony-peerreview-journal/ which is linked to off slashdot. A fake peer review journal published by……Elsevier. Since many of the readers on this blog probably help keep Elsevier in the journal business by reviewing, submitting papers, etc…, I want to bring this up.
And with difficult economic times, I think a great way to save money would be for your university library to cancel all Elsevier journal subscriptions. Yes, this would mean dropping Annals of Physics, a great journal, and several others. But honestly, you can get every paper in there off the arxiv (years earlier in the case of Kitaev’s work), so it’s not worth buying Chaos, Solitons, and Fractals also just to get a print copy of Ann Phys.
Comment #11 May 3rd, 2009 at 2:45 pm
I’m almost certainly missing something, but why isn’t the smiley conjecture implied by the fact that deterministic and quantum query complexities for total functions are polynomially related? You have to do a little work to amplify the quantum circuit and estimate its success probability, but that part doesn’t seem so controversial.
Comment #12 May 3rd, 2009 at 3:14 pm
If your original PRG had exponential strength, couldn’t you use the simpler hybrid argument as in [Razborov Rudich] to conclude that the PRFG works also against a quantum adversary ?
Comment #13 May 3rd, 2009 at 5:00 pm
Aram: The trouble is that we have no guarantee that the quantum algorithm computes a total Boolean function. It could accept some inputs with probability between 1/3 and 2/3, or whatever our error bounds are. That seems like a minor technical problem, but it actually makes the BBCMW argument break down completely. (And for good reason: if it didn’t break down, then Simon’s and Shor’s algorithms would be impossible.)
Comment #14 May 3rd, 2009 at 5:00 pm
It sounds like this kind of issue could potentially arise in any cryptographic setting where there is a function oracle whose domain is exponentially large: e.g., reductions among PRFs, PRPs, hash functions, and so on.
Comment #15 May 3rd, 2009 at 5:23 pm
Anon: Aha! I think you’re right. Correct me if I’m wrong: what you’re saying is that if you don’t use GGM, then you take an exponential hit in the security parameter in going from a PRG to a PRF—but if your original security parameter was an even bigger exponential (say 2poly(n), as a result of starting with a polynomially larger seed), then it’s still a net win.
So the quantum GGM question is still extremely interesting from a query complexity perspective, but is less urgent than I thought.
Comment #16 May 5th, 2009 at 5:08 am
David M.: Sorry, I just realized I never answered your questions!
Yes, I can formulate a precise conjecture :)’ that would imply GGM, but the most natural such :)’ look almost exactly like GGM! I.e., suppose we have a polynomial-time quantum algorithm Q that distinguishes the GGM PRF from a random function. Then my conjecture is that, by using Q, we can also break the underlying PRG G in quantum polynomial time. Furthermore, the conjectured reduction won’t use Q entirely as a black box (such as the original GGM reduction doesn’t)—but, like GGM, it will be “almost” a black-box reduction, in the sense that it’s only interested in which of the input bits Q queries and which outputs Q produces, and not anything else about Q’s internal structure. (See my comment #2 to Luca for an elaboration of this idea.)
Why the name, by the way?
Dunno.
I actually came over to your blog because I was looking for a comment I thought you made a few years ago about how people were publishing too many theorems whose proofs could be obtained by “changing all the BPPs to BQPs.” I wanted to ask if you believed a meta-theorem was possible that could tell us when such a ‘trivial’ proof transformation is possible and when not.
No, because I don’t think there’s any limit to the number of nontrivial theorems that could be proved giving conditions under which it’s safe to replace BPP by BQP. At most, we could hope for theorems giving sufficient conditions for it to be safe, and indeed we have such conditions. For example, I’ve often found the following observation helpful: if all your proof needs about a complexity class C is that contains BPP, then in particular it works with C=BQP. 🙂
(It’s an extremely interesting fact about the GGM reduction that it needs more about the adversary’s complexity class C than just BPP⊆C.)
Comment #17 May 5th, 2009 at 3:22 pm
What about a post on geometric complexity theory ?
Comment #18 May 5th, 2009 at 9:21 pm
Pascal: It’s a-comin! (It’s been a-comin’ for two months, and is still a-comin’!)