Quantum fingerprints that keep secrets
Dmitry Gavinsky, Tsuyoshi Ito · Quantum Information and Computation · 2013
We introduce a new type of cryptographic primitive that we call a \e{hiding fingerprinting scheme}. A (quantum) fingerprinting scheme maps a binary string of length $n$ to $d$ (qu)bits, typically $d\ll n$, such that given any string $y$ and a fingerprint of $x$, one can decide with high accuracy whether $x=y$. It can be seen that a classical fingerprint of $x$ that guarantees error $\le\eps$ necessarily reveals \asOm{\Min{n,\log(1/\eps)}} bits of information about $x$. We call a scheme \e{hiding} if it reveals \aso{\Min{n,\log(1/\eps)}} bits; accordingly, no classical scheme is hiding. }{We construct quantum hiding fingerprinting schemes. Our schemes are computationally efficient and their hiding properties are shown to be optimal.