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.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.01091Jan 4, 20171 citation

Enabling New Generation Security Paradigm With Quantum Cryptography

Thota Venkat Narayana Rao, Maithreyi Simhachalam, Smitha Bandyala +1 more

Oriental journal of computer science and technologyAug 18, 20150 citations

Information theory and secure multi-party computation

Ueli M. Maurer

Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.

IEEE Information Theory Workshop (ITW)Nov 27, 20020 citations

Advancing Cyber Security Through Quantum Cryptography

Advances in information security, privacy, and ethics book seriesOct 23, 20244 citations

Uncloneable Quantum Encryption via Random Oracles

Lord, Sébastien

One of the key distinctions between classical and quantum information is given by the no-cloning theorem: unlike bits, arbitrary qubits cannot be perfectly copied. This fact has been the inspiration for many quantum cryptographic protocols. In this thesis, we introduce a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but non-communicating adversaries may not both simultaneously recover the message, even when the encryption key is revealed. We achieve this functionality by using Wiesner’s conjugate coding scheme to encrypt the message. We show that the adversaries cannot both obtain all the necessary information for the correct decryption with high probability. Quantum-secure pseudorandom functions, modelled as random oracles, are then used to ensure that any partial information that the adversaries obtain does not give them an advantage in recovering the message.One of the key distinctions between classical and quantum information is given by the no-cloning theorem: unlike bits, arbitrary qubits cannot be perfectly copied. This fact has been the inspiration for many quantum cryptographic protocols. In this thesis, we introduce a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but non-communicating adversaries may not both simultaneously recover the message, even when the encryption key is revealed. We achieve this functionality by using Wiesner’s conjugate coding scheme to encrypt the message. We show that the adversaries cannot both obtain all the necessary information for the correct decryption with high probability. Quantum-secure pseudorandom functions, modelled as random oracles, are then used to ensure that any partial information that the adversaries obtain does not give them an advantage in recovering the message.

Feb 27, 20195 citations

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.