Quantum Fingerprints that Keep Secrets

Dmytro Gavinsky, Tsuyoshi Ito
Arxiv ID: 1010.5342Last updated: 3/30/2022
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≪ 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/(n) bits from any fingerprint over O(log n) qubits.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.
Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.