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

Lobachevskii Journal of Mathematics

Efficient Branching Programs for Quantum Hash Functions Generated by Small-Biased Sets

Marat Ablayev

Published Sep 1, 2018• 1 citation
Publisher

Abstract

In the paper we consider quantum ( δ , ϵ )-hash functions in so called phase form (phase quantum ( δ , ϵ )-hash function). It is known that ϵ -biased sets generate phase quantum ( δ , ϵ )- hash function. We show that the construction is invertible, that is, phase quantum ( δ , ϵ )-hash function defines ϵ -biased sets. Next, we present an efficient (in the sense of time and qubits needed) Branching program construction for phase quantum ( δ , ϵ )-hash function.

DOI
10.1134/s199508021807003x

Related papers

Analysis of the amplitude form of the quantum hash function

Marat Ablayev, Farid Mansurovich Ablayev, Alexander Vasiliev

In this article, the properties of quantum hash functions are further explored. Previous findings show that so-called small-bias sets (special subsets of the set of elements of a cyclic group) generate a “phase” quantum hash function. Here, it was proved that they also generate an “amplitude” quantum hash function. Namely, it turned out that constructing small-bias sets while generating amplitude quantum functions yields a well-balanced combination of the cryptographic properties of unidirectionality and collision resistance. As a corollary of the obtained theorem, a general statement about the generation of new amplitude quantum hash functions based on universal hash families and small-bias sets was proved.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Nov 13, 2023•2 citations

Computing quantum hashing in the model of quantum branching programs

Farid Mansurovich Ablayev, Marat Ablayev, Alexander Vasiliev

We investigate the branching program complexity of quantum hashing. We consider a quantum hash function that maps elements of a finite field into quantum states. We require that this function is preimage-resistant and collision-resistant.We consider two complexity measures for Quantum Branching Programs (QBP): a number of qubits and a number of compu-tational steps. We show that the quantum hash function can be computed efficiently. Moreover, we prove that such QBP construction is optimal. That is, we prove lower bounds that match the constructed quantum hash function computation.

AIP conference proceedings•Jan 1, 2018•3 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.

arXiv:1509.01268•Laser Physics Letters•Nov 10, 2015•28 citations

Quantum hashing via ∈-universal hashing constructions and classical fingerprinting

Farid Mansurovich Ablayev, Marat Ablayev

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. In particular, using the relationship between ∈ -universal hash families and Freivalds fingerprinting schemas we present explicit quantum hash function and prove that this construction is optimal in the sense of number of qubits needed for construction.

Lobachevskii Journal of Mathematics•Apr 1, 2015•14 citations

Quantum hashing and Fourier transform

Farid Mansurovich Ablayev, Alexander Vasiliev

In the paper based on the notion of small-biased sets we define the quantum transformation that describes the quantum hash function over the cyclic group. We discuss its similarity to the well-known Quantum Fourier Transform and show possible applications to constructing space-efficient algorithms in various computational scenarios, including two-party quantum communication model, simultaneous message passing model, and the model of quantum online streaming algorithms.

Journal of Physics Conference Series•Dec 1, 2020•4 citations

Quantum Hashing via Classical εεε-universal Hashing Constructions

Farid Mansurovich Ablayev, Marat Ablayev

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.1503•Apr 5, 2014•6 citations
In the paper we consider quantum ( δ , ϵ )-hash functions in so called phase form (phase quantum ( δ , ϵ )-hash function). It is known that ϵ -biased sets generate phase quantum ( δ , ϵ )- hash function. We show that the construction is invertible, that is, phase quantum ( δ , ϵ )-hash function defines ϵ -biased sets. Next, we present an efficient (in the sense of time and qubits needed) Branching program construction for phase quantum ( δ , ϵ )-hash function.
In this article, the properties of quantum hash functions are further explored. Previous findings show that so-called small-bias sets (special subsets of the set of elements of a cyclic group) generate a “phase” quantum hash function. Here, it was proved that they also generate an “amplitude” quantum hash function. Namely, it turned out that constructing small-bias sets while generating amplitude quantum functions yields a well-balanced combination of the cryptographic properties of unidirectionality and collision resistance. As a corollary of the obtained theorem, a general statement about the generation of new amplitude quantum hash functions based on universal hash families and small-bias sets was proved.
We investigate the branching program complexity of quantum hashing. We consider a quantum hash function that maps elements of a finite field into quantum states. We require that this function is preimage-resistant and collision-resistant.We consider two complexity measures for Quantum Branching Programs (QBP): a number of qubits and a number of compu-tational steps. We show that the quantum hash function can be computed efficiently. Moreover, we prove that such QBP construction is optimal. That is, we prove lower bounds that match the constructed quantum hash function computation.
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 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. In particular, using the relationship between ∈ -universal hash families and Freivalds fingerprinting schemas we present explicit quantum hash function and prove that this construction is optimal in the sense of number of qubits needed for construction.
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.