How to Construct Quantum Random Functions

In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function; standard-security, which allows the adversary to be quantum, but requires queries to the function to be classical and quantum-security, which allows the adversary to query the function on a quantum superposition of inputs, thereby giving the adversary a superposition of the values of the function at many inputs at once. Existing techniques for proving the security of pseudorandom functions fail when the adversary can make quantum queries. The authors give the first quantum-security proofs for pseudorandom functions by showing that some classical constructions of pseudorandom functions are quantum-secure.

Provided by: Stanford Technology Ventures Program Topic: Security Date Added: Oct 2012 Format: PDF

Find By Topic