Quantum Fingerprints that Keep Secrets

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. A (quantum) fingerprinting scheme translates a binary string of length n to d (qu)bits, typically dll n, such that given any string y and a fingerprint of x, one can decide with high accuracy whether x=y. Classical fingerprinting schemes cannot hide information very well: a classical fingerprint of x that guarantees error at most ε necessarily reveals Ω\(log(1/ epsilon\)) bits about x. We call a scheme hiding if it reveals o\(log(1/ε\)) bits; accordingly, no classical scheme is hiding. For any constant c, we construct two kinds of hiding fingerprinting schemes, both mapping n-bit strings to O\(log n\) qubits and guaranteeing one-sided error probability at most 1/n^c. The first kind uses pure states and leaks at most O(1) bits, and the second kind uses mixed states and leaks at most 1/n^c bits, where the "leakage" is bounded via accessible information. The schemes are computationally efficient. Our mixed-state scheme is optimal, as shown via a generic strategy that extracts 1/poly(n) bits from any fingerprint over O\(log n\) qubits.