Quantum Hashing via ∈-Universal Hashing Constructions and Classical Fingerprinting

摘要

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 e-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.