2017/01/04 by Cupjin Huang, Yaoyun Shi, Huang, Cupjin +1
Computer Science · Physics and Astronomy · #Chaos-based Image/Signal Encryption #Cryptographic Implementations and Security #Cryptography and Data Security #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1701.01091
23 pages
openalex publication_date 2017/01/04 · arxiv created 2017/02/06 · arxiv updated 2017/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cryptographic hash functions are fundamental primitives widely used in practice. For such a function f:\0, 1\n→\0, 1\m, it is nearly impossible for an adversary to produce the hash f(x) without knowing the secret message x∈\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≪ 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 ω(log2 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.