In the paper, we define the concept of the quantum hash generator and offer design, which allows to build a large amount of different quantum hash functions. The construction is based on composition of classical $ε$ -universal hash family and a given family of functions -- quantum hash generator. The proposed construction combines the properties of robust presentation of information by classical error-correcting codes together with the possibility of highly compressed presentation of information by quantum systems. In particularly, we present quantum hash function based on Reed-Solomon code, and we proved, that this construction is optimal in the sense of number of qubits needed.In the paper, we define the concept of the quantum hash generator and offer design, which allows to build a large amount of different quantum hash functions. The construction is based on composition of classical $ε$-universal hash family and a given family of functions -- quantum hash generator. The proposed construction combines the properties of robust presentation of information by classical error-correcting codes together with the possibility of highly compressed presentation of information by quantum systems. In particularly, we present quantum hash function based on Reed-Solomon code, and we proved, that this construction is optimal in the sense of number of qubits needed.

arXiv:1404.1503Apr 5, 20146 citations

Универсальное квантовое хеширование

Аблаев Фарид Мансурович, Marat Ablayev, Васильев Александр Валерьевич

In the paper we propose a method of quantum hashing which mostly combines the existing constructions of universal hash families with quantum one-way functions. Next, we define the concept of a quantum hash generator and present an approach for building a large number of various quantum hash functions. The construction is based on the integration of a classical e-universal hash family and a given family of functions quantum hash generator. The proposed construction combines the properties of robust representation of information by classical error-correcting codes together with the possibility of highly reliable representation of information by quantum systems. In particular, we present a quantum hash function based on the Reed-Solomon code and prove that this construction is optimal in the sense of the number of qubits needed.In the paper we propose a method of quantum hashing which mostly combines the existing constructions of universal hash families with quantum one-way functions. Next, we define the concept of a quantum hash generator and present an approach for building a large number of various quantum hash functions. The construction is based on the integration of a classical e-universal hash family and a given family of functions quantum hash generator. The proposed construction combines the properties of robust representation of information by classical error-correcting codes together with the possibility of highly reliable representation of information by quantum systems. In particular, we present a quantum hash function based on the Reed-Solomon code and prove that this construction is optimal in the sense of the number of qubits needed.

Ученые записки Казанского университета. Серия Физико-математические наукиJan 1, 20140 citations

Quantum Fingerprinting and Quantum Hashing. Computational and Cryptographical Aspects

Farid Mansurovich Ablayev, Marat Ablayev, Alexander Vasiliev +1 more

Rusins Freivalds was one of the first researchers who introduced methods (later called fingerprinting) for constructing efficient classical randomized and quantum algorithms.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, while hashing methods are one of the central cryptographical primitives.Fingerprinting and hashing methods are being developed from the mid of the previous century, while quantum fingerprinting and quantum hashing have a short history.In the paper we present computational aspects of quantum fingerprinting, discuss cryptographical properties of quantum hashing, and present the possible use of quantum hashing for quantum hash-based message authentication codes.Rusins Freivalds was one of the first researchers who introduced methods (later called fingerprinting) for constructing efficient classical randomized and quantum algorithms.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, while hashing methods are one of the central cryptographical primitives.Fingerprinting and hashing methods are being developed from the mid of the previous century, while quantum fingerprinting and quantum hashing have a short history.In the paper we present computational aspects of quantum fingerprinting, discuss cryptographical properties of quantum hashing, and present the possible use of quantum hashing for quantum hash-based message authentication codes.

Baltic Journal of Modern ComputingDec 19, 201624 citations

Universal Hash Functions from Quantum Procedures

Farid Mansurovich Ablayev

Modern quantum technologies are NISQ (Noisy Intermediate-Scale Quantum) devices, which are used to create insufficiently accurate quantum computers with low computing power. However, quantum technologies have advanced considerably during the past years. Thus, the issue of demonstrating “quantum supremacy” in the era of NISQ technologies is on the agenda. This study demonstrates that “quantum supremacy” is forthcoming. We propose procedures for constructing a universal family of hash functions based on a quantum hashing process that maps the original sequence w to a quantum hash state and then by random transformation to the state |ψ) and generating the sequence u, which is an approximate description of the state |ψ). We proved that the proposed procedure generates a family of nondeterministic hash functions F, which allow us to reliably distinguish between different arguments. The F family can be considered an E-universal family of nondeterministic hash functions. We assume that the development of this research area will cast light on the effect of “quantum supremacy” and will also have a certain impact on the advance of post-quantum cryptography.Modern quantum technologies are NISQ (Noisy Intermediate-Scale Quantum) devices, which are used to create insufficiently accurate quantum computers with low computing power. However, quantum technologies have advanced considerably during the past years. Thus, the issue of demonstrating “quantum supremacy” in the era of NISQ technologies is on the agenda. This study demonstrates that “quantum supremacy” is forthcoming. We propose procedures for constructing a universal family of hash functions based on a quantum hashing process that maps the original sequence w to a quantum hash state and then by random transformation to the state |ψ) and generating the sequence u, which is an approximate description of the state |ψ). We proved that the proposed procedure generates a family of nondeterministic hash functions F, which allow us to reliably distinguish between different arguments. The F family can be considered an E-universal family of nondeterministic hash functions. We assume that the development of this research area will cast light on the effect of “quantum supremacy” and will also have a certain impact on the advance of post-quantum cryptography.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie naukiJan 1, 20205 citations

On the concept of cryptographic quantum hashing

Farid Mansurovich Ablayev, Marat Ablayev

In the letter we define the notion of a quantum resistant ( -resistant) hash function which consists of a combination of pre-image (one-way) resistance ( ε -resistance) and collision resistance ( δ -resistance) properties. We present examples and discussion that supports the idea of quantum hashing. We present an explicit quantum hash function which is ‘balanced’, one-way resistant and collision resistant and demonstrate how to build a large family of quantum hash functions. Balanced quantum hash functions need a high degree of entanglement between the qubits. We use a phase transformation technique to express quantum hashing constructions, which is an effective way of mapping hash states to coherent states in a superposition of time-bin modes. The phase transformation technique is ready to be implemented with current optical technology.In the letter we define the notion of a quantum resistant ( -resistant) hash function which consists of a combination of pre-image (one-way) resistance ( ε -resistance) and collision resistance ( δ -resistance) properties. We present examples and discussion that supports the idea of quantum hashing. We present an explicit quantum hash function which is ‘balanced’, one-way resistant and collision resistant and demonstrate how to build a large family of quantum hash functions. Balanced quantum hash functions need a high degree of entanglement between the qubits. We use a phase transformation technique to express quantum hashing constructions, which is an effective way of mapping hash states to coherent states in a superposition of time-bin modes. The phase transformation technique is ready to be implemented with current optical technology.

arXiv:1509.01268Laser Physics LettersNov 10, 201528 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.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

ε

-universal hash family and a given family of functions -- quantum hash generator. The proposed construction combines the properties of robust presentation of information by classical error-correcting codes together with the possibility of highly compressed presentation of information by quantum systems. In particularly, we present quantum hash function based on Reed-Solomon code, and we proved, that this construction is optimal in the sense of number of qubits needed.

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.