{"id":15651,"date":"2015-10-15T22:14:14","date_gmt":"2015-10-16T03:14:14","guid":{"rendered":"http:\/\/bucktownbell.com\/?p=15651"},"modified":"2015-10-15T22:14:14","modified_gmt":"2015-10-16T03:14:14","slug":"nsa-in-ppoly-the-power-of-precomputation","status":"publish","type":"post","link":"http:\/\/bucktownbell.com\/?p=15651","title":{"rendered":"NSA in P\/poly: The Power of Precomputation"},"content":{"rendered":"<blockquote><p>Diffie-Hellman is the thing where Alice and Bob first agree on a huge prime number p and a number g, then Alice picks a secret a and sends Bob ga (mod p), and Bob picks a secret b and sends Alice gb (mod p), and then Alice and Bob can both compute (ga)b=(gb)a=gab (mod p), but an eavesdropper who\u2019s listening in only knows p, g, ga (mod p), and gb (mod p), and one can plausibly conjecture that it\u2019s hard from those things alone to get gab (mod p). So then Alice and Bob share a secret unknown to the eavesdropper, which they didn\u2019t before, and they can use that secret to start doing cryptography.<\/p><\/blockquote>\n<p>Source: <em><a href=\"http:\/\/www.scottaaronson.com\/blog\/?p=2293\">Shtetl-Optimized \u00bb Blog Archive \u00bb NSA in P\/poly: The Power of Precomputation<\/a><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Diffie-Hellman is the thing where Alice and Bob first agree on a huge prime number p and a number g, then Alice picks a secret a and sends Bob ga (mod p), and Bob picks a secret b and sends &hellip; <a href=\"http:\/\/bucktownbell.com\/?p=15651\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[338,107],"class_list":["post-15651","post","type-post","status-publish","format-standard","hentry","category-technical","tag-encryption","tag-reference"],"_links":{"self":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15651","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=15651"}],"version-history":[{"count":1,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15651\/revisions"}],"predecessor-version":[{"id":15652,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=\/wp\/v2\/posts\/15651\/revisions\/15652"}],"wp:attachment":[{"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15651"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/bucktownbell.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}