Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1010.5342 · Quantum Information and Computation

Quantum fingerprints that keep secrets

Dmitry Gavinsky, Tsuyoshi Ito

Published May 1, 2013• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic13.7-8-3

Related papers

On Quantum Fingerprinting and Quantum Cryptographic Hashing

Farid Mansurovich Ablayev, Marat Ablayev

Fingerprinting and cryptographic hashing have quite different usages in computer science, but have similar properties. Interpretation of their properties is determined by the area of their usage: fingerprinting methods are methods for constructing efficient randomized and quantum algorithms for computational problems, whereas hashing methods are one of the central cryptographical primitives. Fingerprinting and hashing methods are being developed from the mid of the previous century, whereas quantum fingerprinting and quantum hashing have a short history. In this chapter, we investigate quantum fingerprinting and quantum hashing. We present computational aspects of quantum fingerprinting and quantum hashing and discuss cryptographical properties of quantum hashing.

InTech eBooks•May 30, 2018•0 citations

Classical vs Quantum Fingerprinting

Barry C. Sanders

When communication is expensive, the important task of testing two binary strings for equality can be achieved by generating relatively short fingerprints of each string and comparing those fingerprints. Quantum fingerprinting, in which the fingerprint is encoded onto qubits (the quantum version of the bit), is significantly less expensive: exponentially better in the case of no shared randomness and potentially perfect for the case of shared entanglement. Single-qubit quantum fingerprinting is feasible, and we have demonstrated its advantages theoretically and experimentally

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 24, 2005•0 citations

Quantum hashing is maximally secure against classical leakage

Cupjin Huang, Yaoyun Shi

Cryptographic hash functions are fundamental primitives widely used in practice. For such a function $f:\{0, 1\}^n\to\{0, 1\}^m$, it is nearly impossible for an adversary to produce the hash $f(x)$ without knowing the secret message $x\in\{0, 1\}^n$. Unfortunately, all hash functions are vulnerable under the side-channel attack, which is a grave concern for information security in practice. This is because typically $m\ll n$ and an adversary needs only $m$ bits of information to pass the verification test. In sharp contrast, we show that when quantum states are used, the leakage allowed can be almost the entire secret. More precisely, we call a function that maps $n$ bits to $m$ qubits a quantum cryptographic function if the maximum fidelity between two distinct hashes is negligible in $n$. We show that for any $k=n-ω(\log n)$, all quantum cryptographic hash functions remain cryptographically secure when leaking $k$ bits of information. By the quantum fingerprinting constructions of Buhrman et al.~({\em Phys. Rev. Lett.} 87, 167902), for all $m=ω(\log n)$, there exist such quantum cryptographic hash functions. We also show that one only needs $ω(\log^2 n)$ qubits to verify a quantum cryptographic hash, rather than the whole classical information needed to generate one. Our result also shows that to approximately produce a small amount of quantum side information on a classical secret, it may require almost the full information of the secret. This large gap represents a significant barrier for proving quantum security of classical-proof extractors.

arXiv:1701.01091•Jan 4, 2017•1 citation

Efficient Threshold Function Secret Sharing With Information-Theoretic Security

Jinglong Luo, Liang Feng Zhang, Fuchun Lin +1 more

Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.

IEEE Access•Jan 1, 2020•7 citations

Hiding Secrets Using Quantum Entanglement

Sophia Chen

Three experiments demonstrate the key elements of a quantum cryptographic scheme that predictions indicate should be unhackable, bringing the promise of quantum encryption technologies a step closer to reality.

Physics•Jul 27, 2022•0 citations

Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations

Farid Mansurovich Ablayev, Marat Ablayev, Alexander Vasiliev

Lecture notes in computer science•Jan 1, 2020•6 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 nnn to ddd (qu)bits, typically d≪nd\ll nd≪n, such that given any string yyy and a fingerprint of xxx, one can decide with high accuracy whether x=yx=yx=y. It can be seen that a classical fingerprint of xxx that guarantees error ≤\eps\le\eps≤\eps necessarily reveals \asOm{\Min{n,\log(1/\eps)}} bits of information about xxx. 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.
Fingerprinting and cryptographic hashing have quite different usages in computer science, but have similar properties. Interpretation of their properties is determined by the area of their usage: fingerprinting methods are methods for constructing efficient randomized and quantum algorithms for computational problems, whereas hashing methods are one of the central cryptographical primitives. Fingerprinting and hashing methods are being developed from the mid of the previous century, whereas quantum fingerprinting and quantum hashing have a short history. In this chapter, we investigate quantum fingerprinting and quantum hashing. We present computational aspects of quantum fingerprinting and quantum hashing and discuss cryptographical properties of quantum hashing.
When communication is expensive, the important task of testing two binary strings for equality can be achieved by generating relatively short fingerprints of each string and comparing those fingerprints. Quantum fingerprinting, in which the fingerprint is encoded onto qubits (the quantum version of the bit), is significantly less expensive: exponentially better in the case of no shared randomness and potentially perfect for the case of shared entanglement. Single-qubit quantum fingerprinting is feasible, and we have demonstrated its advantages theoretically and experimentally
Cryptographic hash functions are fundamental primitives widely used in practice. For such a function f:{0,1}n→{0,1}mf:\{0, 1\}^n\to\{0, 1\}^mf:{0,1}n→{0,1}m, it is nearly impossible for an adversary to produce the hash f(x)f(x)f(x) without knowing the secret message x∈{0,1}nx\in\{0, 1\}^nx∈{0,1}n. Unfortunately, all hash functions are vulnerable under the side-channel attack, which is a grave concern for information security in practice. This is because typically m≪nm\ll nm≪n and an adversary needs only mmm bits of information to pass the verification test. In sharp contrast, we show that when quantum states are used, the leakage allowed can be almost the entire secret. More precisely, we call a function that maps nnn bits to mmm qubits a quantum cryptographic function if the maximum fidelity between two distinct hashes is negligible in nnn. We show that for any k=n−ω(log⁡n)k=n-ω(\log n)k=n−ω(logn), all quantum cryptographic hash functions remain cryptographically secure when leaking kkk bits of information. By the quantum fingerprinting constructions of Buhrman et al.~({\em Phys. Rev. Lett.} 87, 167902), for all m=ω(log⁡n)m=ω(\log n)m=ω(logn), there exist such quantum cryptographic hash functions. We also show that one only needs ω(log⁡2n)ω(\log^2 n)ω(log2n) qubits to verify a quantum cryptographic hash, rather than the whole classical information needed to generate one. Our result also shows that to approximately produce a small amount of quantum side information on a classical secret, it may require almost the full information of the secret. This large gap represents a significant barrier for proving quantum security of classical-proof extractors.
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.