Quantum Fingerprints that Keep Secrets

Details Quantum Fingerprints that Keep Secrets Quantum Fingerprints that Keep Secrets

2010-10-26

arxiv.org/abs/1010.5342v1

Physics

Quantum Physics

28 pages

Scientific paper

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 $d\ll 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 $\epsilon$ necessarily reveals $\Omega(\log(1/\ epsilon))$ bits about $x$. We call a scheme hiding if it reveals $o(\log(1/\epsilon))$ 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.

Affiliated with

Also associated with

No associations

Rating

Quantum Fingerprints that Keep Secrets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Fingerprints that Keep Secrets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Fingerprints that Keep Secrets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159276