Quantum Hashing via ∈-Universal Hashing Constructions and Freivalds' Fingerprinting Schemas

摘要

We define the concept of a quantum hash generator and offer a design, which allows one to build a large number of different quantum hash functions. The construction is based on composition of a classical ∈-universal hash family and a given family of functions - quantum hash generators. 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 with respect to the number of qubits needed for the construction.