### DIMACS Theoretical Computer Science Seminar

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.