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:1412.5135 · Lobachevskii Journal of Mathematics

Quantum Hashing. Group approach

Mansur Ziatdinov

Published Mar 1, 2016• 9 citations
arXivHTMLPDF

Abstract

In this paper we consider a generalization of quantum hash functions for arbitrary groups. We show that quantum hash function exists for arbitrary abelian group. We construct a set of “good” automorphisms—a key component of quantum hash funciton. We prove some restrictions on Hilbert space dimension and group used in quantum hash function.

DOI
10.1134/s1995080216020165

Related papers

Quantum hashing for finite abelian groups

Alexander Vasiliev

We propose a generalization of the quantum hashing technique based on the notion of small-bias sets. These sets have proved useful in different areas of computer science, and here their properties give an optimal construction for succinct quantum presentation of elements of any finite abelian group, which can be used in various computational and cryptographic scenarios. We consider two special cases of the proposed quantum hashing which turn out to be the known quantum fingerprinting schemas.

arXiv:1603.02209•Lobachevskii Journal of Mathematics•Nov 1, 2016•33 citations

Quantum hashing based on symmetric groups

Mansur Ziatdinov

The notion of quantum hashing formalized by F. Ablayev and A. Vasiliev in 2013. F. Ablayev and M. Ablayev in 2014 introduced the notion of quantum hash generator which is convenient technical tool for constructing quantum hash func- tions. M. Ziatdinov in 2014 presented group approach for constructing quantum hash functions. All these mentioned above results present constructions of quan- tum hash functions based on abelian groups. This paper continue the research on quantum hashing. Our approach allows us to construct quantum hash function working on any (finite) group. Also our approach allows us to construct quantum hash functions based on classical hash function from $NC^1$.

arXiv:1612.07646•Dec 21, 2016•0 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 collision finding for homomorphic hash functions

Juan Carlos García-Escartín, Vicent Gimeno, Julio José Moyano‐Fernández

Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to $\oplus$-linear hash functions and for certain multiplicative homomorphic hash schemes.

arXiv:2108.00100•Jul 30, 2021•1 citation

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

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
In this paper we consider a generalization of quantum hash functions for arbitrary groups. We show that quantum hash function exists for arbitrary abelian group. We construct a set of “good” automorphisms—a key component of quantum hash funciton. We prove some restrictions on Hilbert space dimension and group used in quantum hash function.
The notion of quantum hashing formalized by F. Ablayev and A. Vasiliev in 2013. F. Ablayev and M. Ablayev in 2014 introduced the notion of quantum hash generator which is convenient technical tool for constructing quantum hash func- tions. M. Ziatdinov in 2014 presented group approach for constructing quantum hash functions. All these mentioned above results present constructions of quan- tum hash functions based on abelian groups. This paper continue the research on quantum hashing. Our approach allows us to construct quantum hash function working on any (finite) group. Also our approach allows us to construct quantum hash functions based on classical hash function from NC1NC^1NC1.
Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to ⊕\oplus⊕-linear hash functions and for certain multiplicative homomorphic hash schemes.
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 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.