Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.

arXiv:quant-ph/0309036Physical Review AFeb 18, 200425 citations

Quantum fingerprints that keep secrets

Dmitry Gavinsky, Tsuyoshi Ito

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.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.

arXiv:1010.5342Quantum Information and ComputationMay 1, 201323 citations

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

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.