Title: Quantum Fingerprints that Keep Secrets
Speaker: Dmitry Gavinsky, NEC Labs
Date: Wednesday, April 27, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the pre-image, where epsilon is the error ("collision") probability. It is easy to see that classically this is not achievable; our construction is quantum, and it gives a new example of (unconditional) qualitative advantage of quantum computers. \
Technically speaking, for any constant c we give a quantum fingerprinting scheme that maps an n-bit string x to O(log n) qubits, guarantees error at most 1/n^c and leaks at most 1/n^c bits of information about x (any classical scheme with such error would leak Omega(log n) bits). We also demonstrate that our scheme is optimal.