THEORY SEMINAR: Please join us on April 14th at 11am in Siebel 3401 where Kabir Tomer (UIUC) will give a talk, “Towards (Quantum) Cryptography from #P-hardness”. Please see the abstract below:
Abstract:
Classical cryptography is built on assuming the existence of "hard" problems. The weakest such assumption, necessary for the existence of any meaningful classical cryptography, is the existence of one-way functions, which are functions which can be efficiently computed but are hard to invert in the average case.
In a quantum world, however, the picture is quite different. Recent works have opened up the possibility of building powerful quantum cryptographic primitives from assumptions even weaker than the existence of one-way functions. In fact, there is evidence that these primitives could exist even if P=NP (in which case all classical cryptography would be insecure)!
This talk will give a brief introduction to this setting as well as cover the recent results on building such quantum cryptographic primitives from the (extremely mild) worst case assumption that #P-hard problems are infeasible for efficient quantum adversaries.
No background in quantum computation is needed to understand this talk.