Dear Scott, Please keep the focus of your blog.\u00a0 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.<\/p><\/blockquote>\n
So today I noticed something bizarre.\u00a0 A celebrated result in cryptography, due to Goldreich, Goldwasser, and Micali, states that any pseudorandom generator gives rise to a pseudorandom function family.\u00a0 See Luca’s notes<\/a> or the original GGM paper<\/a> for more.<\/p>\n 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.\u00a0 But now that I’m writing a paper that actually relies on this “fact,” I realized I have no idea why it’s true.<\/p>\n Look: in the GGM argument, you start with a pseudorandom generator G:{0,1}n<\/sup>\u2192{0,1}2n<\/sup>, and you apply it recursively to produce a family of functions fs<\/sub>:{0,1}n<\/sup>\u2192{0,1}n<\/sup>, where s is the seed.\u00a0 You then consider a hypothetical polynomial-time algorithm A that distinguished fs<\/sub> from a truly random function.\u00a0 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.<\/p>\n The trouble is, the argument relies crucially on the fact that A examines only a polynomial number of outputs of fs<\/sub>—intuitively so that you can run a hybrid argument, changing the outputs that A actually examines one by one into truly random strings.\u00a0 But if A is a quantum algorithm, then (duh) it can examine all 2n<\/sup> outputs of fs<\/sub> in superposition!\u00a0 So any argument that depends on “watching A to see which inputs it queries” is toast.<\/p>\n But maybe we can recover the same conclusion in a fancier way?\u00a0 For at least seven years, I’ve been going around conjecturing the following:<\/p>\n Conjecture ( My motivation for Conjecture ( It now occurs to me that, if we knew how to prove Conjecture ( So the task remains: prove a quantum GGM theorem.<\/strong><\/font>\u00a0 Or maybe I’m missing something completely obvious?<\/p>\n PS. The promised report on the QIS conference in Virginia is coming tomorrow.\u00a0 Take that, future self!<\/p>\n Update (5\/3):<\/strong><\/font> An anonymous commenter points out that we can use a simpler hybrid argument of Razborov and Rudich—which doesn’t<\/em> break down in the quantum case—to show that if there exists a PRG that’s secure against 2n^\u03a9(1)<\/sup>-time quantum adversaries, then there also exists a PRF with polynomial seed length that’s secure against exponential-time quantum adversaries.\u00a0 That somehow hadn’t occurred to me, and it’s good enough for my purposes.\u00a0 (Masked cryptographer: emerge ye from the shadows, and claim thy rightful honour in my Acknowledgments!)\u00a0 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)\u03a9(1)<\/sup>-time quantum adversaries, for any superpolynomial f.<\/p>\n","protected":false},"excerpt":{"rendered":" A commenter on my last post writes: Dear Scott, Please keep the focus of your blog.\u00a0 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,18,4],"tags":[],"class_list":["post-403","post","type-post","status-publish","format-standard","hentry","category-complexity","category-embarrassing-myself","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=403"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/403\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\":)\"](\"https:\/\/scottaaronson.blog\/wp-includes\/images\/smilies\/icon_smile.gif\"){kind=icon}
):<\/strong> Let Q be a quantum algorithm that makes T queries to a Boolean input X\u2208{0,1}N<\/sup>.\u00a0 Then for all \u03b5,\u03b4>0, there exists a deterministic classical algorithm that makes poly(T,1\/\u03b5,log(1\/\u03b4)) queries to X, and that approximates Q’s acceptance probability to within \u03b5 on a 1-\u03b4 fraction of inputs.<\/em><\/p>\n<\/strong>) had nothing to do with cryptography.\u00a0 I was interested in whether we could rule out the possibility that P<\/strong>=BQP<\/strong> relative to a random oracle with probability 1.\u00a0 If Conjecture (<\/strong>) holds—and if the classical algorithm is anything like I think it is—then we can’t<\/em> rule it out, at least not without proving P<\/strong>\u2260PSPACE<\/strong> or an even stronger separation in the unrelativized world.<\/p>\n<\/strong>), then maybe<\/em> we could push through a quantum GGM argument using similar ideas—that is, by identifying a tiny subset of inputs to fs<\/sub> that the quantum algorithm’s acceptance probability “really” depends on.\u00a0 Alas, I have good reason to believe that Conjecture (<\/strong>) is hard.<\/p>\n