On Quantum Fingerprinting and Quantum Cryptographic Hashing

Abstract

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, whereas hashing methods are one of the central cryptographical primitives. Fingerprinting and hashing methods are being developed from the mid of the previous century, whereas quantum fingerprinting and quantum hashing have a short history. In this chapter, we investigate quantum fingerprinting and quantum hashing. We present computational aspects of quantum fingerprinting and quantum hashing and discuss cryptographical properties of quantum hashing.

1. Introduction

Fingerprinting and hashing are well-known techniques. Fingerprinting is widely used in various meanings in different areas of computer science. We restrict ourselves to the area of computational complexity theory where the notion of fingerprinting is more or less formalized. Cryptographic hashing allows to securely present objects and mathematically is more formalized. 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, whereas hashing methods are one of the central cryptographical primitives.

Fingerprinting and hashing methods are being developed from the mid of the previous century, whereas quantum fingerprinting and quantum hashing have a short history.

In this chapter, 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 (QMAC).

1.1. Classical and quantum fingerprinting

Fingerprinting in complexity theory is a procedure that maps a large data item to a much shorter string, its fingerprint, that identifies the original data (with high probability). The key properties of classical fingerprinting methods are (i) they allow to build efficient randomized computational algorithms and (ii) the resulting algorithms have bounded error [1].

Rusins Freivalds was one of the first researchers who introduced methods (later called fingerprinting) for constructing efficient randomized algorithms (which are more efficient than any deterministic algorithm) [2, 3].

In quantum case, fingerprinting is a procedure that maps classical data to a quantum state that identifies the original data (with high probability). One of the first applications of the quantum fingerprinting method is due to Ambainis and Freivalds [4]: for a specific language, they have constructed a quantum finite automaton with an exponentially smaller size than any classical randomized automaton. An explicit definition of the quantum fingerprinting was introduced by Buhrman et al. [5] in (2001) for constructing efficient quantum communication protocol for equality testing. It is worth noting that the fingerprinting by Buhrman et al. has been used as a cryptographic hash function in [6, 7].

1.2. Cryptographic quantum hashing

Cryptographic hashing has a lot of fruitful applications in cryptography. Note that in cryptography functions satisfying (i) one-way property and (ii) collision resistance property (in different specific meanings) are called hash functions, and we propose to do so when we are considering cryptographical aspects of quantum functions with the above properties. So, we suggest to call a quantum function that satisfies properties (i) and (ii) (in the quantum setting), a cryptographic quantum hash function or just quantum hash function. Note, however, that there is only a thin line between the notions of quantum fingerprinting and quantum hashing. One of the first considerations of a quantum function (that maps classical words into quantum states) as a cryptographic primitive, having one-way property and collision resistance property is due to [6], where the quantum fingerprinting function from [5] was used. Another approach to constructing quantum hash functions from quantum walks was considered in [8, 9, 10], and it resulted in privacy amplification in quantum key distribution and other useful applications.

1.3. The chapter organization

In Section 3, we consider quantum fingerprinting as a mapping of classical inputs to quantum states, which allows to construct efficient quantum algorithms for computing Boolean functions. We consider the quantum fingerprinting function from [5] as well as the quantum fingerprinting technique from [11]. The latter was motivated by the paper [4] and its generalization [12].

We define a notion of quantum (δ, ε)-hash function that is quantumly one-way δ-resistant and quantumly collision ε-resistant.

We show that one-way property and collision resistance property are correlated for a quantum hash function. The more the function is one-way, the less it is collision resistant and vice versa. We show that such a correlation can be balanced.

We present an approach for quantum hash function constructions by establishing a connection with small-biased sets [13] and quantum hash function constructions: we prove that each ε-biased set allows to generate quantum collision ε-resistant function. Note that one-way property of this function depends on the size of such ε-biased set: the smaller ε-biased set allows to generate a quantum function with the better one-way characteristics. Such a connection adds to the long list of small-biased sets’ applications.

In particular, it was observed in [13, 14] that the ε-bias property is closely related to the error-correcting properties of linear codes. In particular, for the binary case, a set S is ε-biased iff every pair of distinct code words of corresponding error correcting code C_S has relative Hamming distance (1 ± ε)/2.

Note that the quantum fingerprinting function from [5] is based on a binary error-correcting code, and so it solves the problem of constructing quantum hash functions for the binary case. For the general (nonbinary) case, ε-bias does not correspond to Hamming distance. Thus, in contrast to the binary case, an arbitrary linear error correcting code cannot be used directly for quantum hash functions.

Note that one-way property of function means computational effectiveness of this function. We show that considered construction of quantum (δ, ε)-hash function is computed effectively in the model of quantum branching programs. We consider two complexity measures: a number width(Q) of qubits that QBP Q uses for computation and a number time(Q) of computational steps of QBP Q. Such QBP Q is of width(Q) = O(log log q) and time(Q) = log q.

We prove that such QBP construction is optimal. That is, we prove lower bounds Ω(log log q) for QBP width and Ω(log q) for QBP time for quantum (δ, ε)-hash function presentation.

2. Preliminaries

We recall that mathematically a qubit is described as a unit vector in the two-dimensional Hilbert complex space ℋ². Let s ≥ 1. Let ℋ^d be the d = 2^s-dimensional Hilbert space, describing the states of s qubits. Another notation for ℋ^d is (ℋ²)^⊗s, i.e., ℋ^d is made up of s copies of a single qubit space ℋ².

${\left({\mathscr{H}}^2\right)}^{\otimes s}={\mathscr{H}}^2\otimes ,\dots ,\otimes {\mathscr{H}}^2={\mathscr{H}}^{2^s}.$ E1

Conventionally, we use notation |i⟩ for the vector from H^d, which has a 1 on the i-th position and 0 elsewhere. An orthonormal basis |1⟩, … ,|d⟩ is usually referred to as the standard computational basis.

We let ℤ_q to be a finite additive group of Z/qZ, the integers modulo q. Let Σ^k be a set of words of length k over a finite alphabet Σ. Let $\mathbb{X}$ be a finite set. In this paper, we let $\mathbb{X}={\mathrm{\Sigma }}^k$ or $\mathbb{X}={\mathbb{Z}}_q$ . For $K=\mid \mathbb{X}\mid$ and integer s ≥ 1, we define a (K; s) classical-quantum function (or just quantum function) to be mapping

$\psi :\mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}\text{or}\psi :w\mapsto \left|\psi \left(w\right)⟩\right..$ E2

In order to outline a computational aspect and present a procedure for quantum function ψ, we define ψ to be a unitary transformation (determined by an element $w\in \mathbb{X}$ ) of the initial state |ψ₀⟩ ∈ (ℋ²)^⊗s to a quantum state |ψ(w)⟩ ∈ (ℋ²)^⊗s

$\psi :\left\{\left|{\psi }_0⟩\right.\right\}\times \mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}\left|\psi \left(w\right)⟩\right.=U\left(w\right)\left|{\psi }_0⟩\right.,$ E3

where U(w) is a unitary matrix.

Extracting information on w from |ψ(w)⟩ is a result of measurements of quantum state |ψ(w)⟩. In this chapter, we consider quantum transformations and measurements of quantum states with respect to computational basis.

3. Quantum fingerprinting

The ideas of the fingerprinting technique in the quantum setting for the first time appeared in [4]. The authors used a succinct presentation of the classical input by a quantum automata state, which resulted in an exponential improvement over classical algorithm. Later in the works of [12] the ideas were developed further to give an arbitrarily small probability of error. This was the basis for the general quantum fingerprinting framework proposed in [11].

However, the term “quantum fingerprinting” is mostly used in scientific literature to address a seminal paper [5], where this notion first appeared explicitly. To distinguish between different versions of the quantum fingerprinting techniques, the fingerprinting function from [5] is called as “binary” (since it uses some binary error-correcting code in its construction), whereas the fingerprinting from [11] is called “q-ary” for it uses presentation of the input in ℤ_q.

3.1. Binary quantum fingerprinting

The quantum fingerprinting function was formally defined in [5], where it was used for quantum equality testing in a quantum communication model. It is based on the notion of a binary error-correcting code.

An (n, k, d) error-correcting code is a map C : Σ^k→Σⁿ such that, for any two distinct words w , w^′ ∈ Σ^k, the Hamming distance d(C(w), C(w^′)) between code words C(w) and C(w^′) is at least d. The code is binary if Σ = {0, 1}.

The construction of the quantum fingerprinting function is as follows.

• Let c > 2 and ε < 1. Let k be a positive integer and n = ck. Let E : {0, 1}^k→{0, 1}ⁿ be a (n, k, d) binary error-correcting code with Hamming distance d ≥ (1 − ε)n.

• Define a family of functions F_E = {E₁,  … , E_n}, where $E_i:{\left\{0,1\right\}}^k\to {\mathbb{F}}_2$ is defined by the rule: E_i(w) is the i-th bit of the codeword E(w).

• Let s = log n + 1. Define the quantum function ψ_FE : {0, 1}^k→(ℋ²)^⊗s, determined by a word w as

$|{\psi }_{F_E}\left(w\right)⟩=\frac{1}{\sqrt{n}}\sum _{i=1}^n\hspace{0.17em}\left|i⟩\right.\left|E_i\left(w\right)⟩\right..$ E4

Original paper of [5] used this function to construct a quantum communication protocol that tests equality in the simultaneous message passing (SMP) model with no shared resources. This protocol requires O(log n) qubits to compare n-bit binary strings, which is exponentially smaller than any classical deterministic or even randomized protocol in the SMP setting with no shared randomness. The proposed quantum protocol has one-sided error of 1/2(1 + ⟨ψ_FE(x)| ψ_FE(y)⟩²), where |ψ_FE(x)⟩ and |ψ_FE(y)⟩ are two different quantum fingerprints. Their inner product |⟨ψ_FE(x)| ψ_FE(y)⟩| is bounded by ε, if the Hamming distance of the underlying code is (1 − ε)n. Thus, ε is determined by the chosen error-correcting code. For instance, Justesen codes mentioned in the paper give ε < 9/10 + 1/(15c) for any chosen c > 2.

In the same paper, it was shown that this result can be improved by choosing an error-correcting code with Hamming distance between any two distinct code words (1 − ε)n/2 and (1 + ε)n/2 for any ε > 0 (however, the existence of such codes can only be proved nonconstructively via probabilistic argument).

Further research on this topic mostly used the following phase presentation version of quantum fingerprinting. We define the quantum fingerprinting function ψ : {0, 1}^k→(ℋ²)^⊗s determined by a word w as

${\psi }_{F_E}\left(w\right)=\frac{1}{\sqrt{n}}\sum _{i=1}^n\hspace{0.17em}{\left(-1\right)}^{E_i\left(w\right)}\left|i⟩\right.$ E5

This function gives the following bound for the fingerprints of distinct inputs

$\left|⟨{\psi }_{F_E}\left(x\right)|{\psi }_{F_E}\left(y\right)⟩\right|=\frac{1}{n}\sum _{i=1}^n\hspace{0.17em}{\left(-1\right)}^{E_i\left(w\right)\oplus E_i\left(w\prime \right)}=\frac{n-d\left(E\left(w\right),E\left(w^{\prime }\right)\right)}{n}\le \epsilon$ E6

3.2. q-ary quantum fingerprinting

In this section, we demonstrate the generalization of binary fingerprinting function to the q-ary case. General technique is presented in [11, 15]. Here, we present the idea using specific Boolean function g : {0, 1}ⁿ→{0, 1} where g(σ) = 1 iff σ = 0 mod sq. We treat σ also as an integer encoded by binary string σ.

To test g, we rotate the initial state |0⟩ of a single qubit by an angle θ = πσ/q:

$\left|0⟩\right.\to \left|\mathrm{\psi }\left(\mathrm{\sigma }\right)⟩\right.=\text{cos}\text{θ}\left|0⟩\right.+\text{sin}\text{θ}\left|1⟩\right.$ E7

Then, this state |ψ(σ)⟩ is measured and the input σ is accepted iff the result of the measurement is |0⟩.

Obviously, this quantum state is ±|0⟩ iff σ = 0 mod q. In the worst case, this algorithm gives the one-sided error of cos²π(q − 1)/q, which can be arbitrarily close to 1.

The above description can be presented as follows using log t + 1 = (log log q) + 1 qubits:

$\underset{\text{log}t}{\underbrace{|0⟩\otimes \cdots \otimes |0⟩}}\otimes |0⟩\to \frac{1}{\sqrt{t}}\sum _{i=1}^t\hspace{0.17em}\left|i⟩\right.\left(\text{cos}{\theta }_i\left|0⟩\right.+\text{sin}{\theta }_i\left|1⟩\right.\right),$ E8

where ${\theta }_i=\frac{2\pi s_i\sigma }{q}$ and the set S = {s₁,  … , s_t} ⊆ ℤ_q is chosen in order to guarantee the small probability of error [11, 15]. That is, the last qubit is simultaneously rotated in t different subspaces by corresponding angles θ_i.

The above q-ary quantum fingerprinting method can be presented in the following procedure:

1. The initial state of the quantum register is |0⟩^⊗ log t|0⟩.

2. The Hadamard transform creates the uniform superposition $\frac{1}{\sqrt{t}}\sum _{j=1}^t\hspace{0.17em}\left|j⟩\right.\left|0⟩\right.$ of the basis states {|j⟩|0⟩ : j ∈ {1,  … , t}}.

3. Based on the input σ, its fingerprint is created: $\frac{1}{\sqrt{t}}{\sum }_{j=1}^t\hspace{0.17em}|j⟩\left(\text{cos}\frac{2\pi s_j\sigma }{q}|0⟩+\text{sin}\frac{2\pi s_j\sigma }{q}|1⟩\right)$ .

4. The Hadamard transform turns the fingerprint into the state $|\psi ⟩=\left(\frac{1}{t}{\sum }_{l=1}^t\hspace{0.17em}\text{cos}\frac{2\pi s_l\sigma }{q}\right)|{0⟩}^{\otimes \text{log}t}\left|0⟩\right.+\dots$

5. The quantum state |ψ⟩ is measured and the input is accepted iff the result is |0⟩^⊗ log t|0⟩.

In [11, 15, 16], we have applied this technique to construct efficient quantum algorithms for a certain class of Boolean functions in the model of read-once quantum branching programs [17].

3.2.1. Quantum branching programs

Branching program is a well-known computational model in computer science, also known as a binary decision diagram in Applied Computer Science. Informally speaking, branching program is a circuit with ability to test in each of its computational step a needed bit of an input. Such circuit is a realization of a program that uses only “if then else” and “go to” primitives. We use the definition from [18]

Definition 1 ([18]) A Quantum Branching Program Q over the Hilbert space ℋ^d is defined as

$Q=⟨T,\left|{\psi }_0⟩\right.⟩,$ E9

where T is a sequence of l instructions: T_j = (x_ij, U_j(0), U_j(1)) is determined by variable x_ij tested on the step j, and U_j(0) and U_j(1) are unitary transformations in ℋ^d.

Vectors |ψ⟩ ∈ ℋ^d are called states (state vectors) of Q, |ψ₀⟩ ∈ ℋ^d is the initial state of Q.

We define a computation of Q on an input σ = σ₁ ,  …  , σ_n ∈ {0, 1}ⁿ as follows:

1. A computation of Q starts from the initial state |ψ₀⟩.

2. The j-th instruction of Q reads the input symbol σ_ij (the value of x_ij) and applies the transition matrix U_j = U_j(σ_ij) to the current state |ψ⟩ to obtain the state |ψ^′⟩ = U_j(σ_ij)|ψ⟩.

3. The final state is

$|\psi \left(\sigma \right)⟩=\left(\prod _{j=l}^1\hspace{0.17em}{U}_j\left({\sigma }_{i_j}\right)\right)|{\psi }_0⟩.$ E10

Accepting of an input sequence is a result of measuring of final state |ψ(σ)⟩ in computational basis and is formalized as follows. Let Accept ⊆ {1, 2, …d} be the set of indices of accepting basis states. After the l-th (last) step of quantum transformation, Q measures its configuration |ψ_σ⟩ = (α₁,  … , α_d)^T and the input σ is accepted with probability

$P{r}_{\text{accept}}\left(\sigma \right)=\sum _{i\in \text{Accept}}\hspace{0.17em}{\left|{\alpha }_i\right|}^2.$ E11

3.2.2. Circuit representation

Quantum circuits are good formalism for quantum algorithms representation [19, 20]. A quantum branching programs can be viewed as a quantum circuit aided with an ability to read classical bits as control variables for unitary operations (see Figure 1).

Figure 1.

Branching program in the form of circuit. Variables x_i1 ,  …  , x_il denoting classical control (input) bits. Single wires carry quantum information, and double wires denote classical information and control.

4. Quantum hashing

In this section, we present notion of quantum (δ, ε)-resistant hash function based on [21].

4.1. One-way δ resistance

We present the following definition of a quantum δ-resistant one-way function. Let “information extracting” mechanism M be a function $M:{\left({\mathscr{H}}^2\right)}^{\otimes s}\to \mathbb{X}$ . Informally speaking, mechanism M makes some measurements to state |ψ⟩ ∈ (ℋ²)^⊗s and decodes the result of measurement to $\mathbb{X}$ .

Definition 2 ([21]) Let X be a random variable distributed over $\mathbb{X}$ $\left\{\mathit{Pr}\left[X=w\right]:w\in \mathbb{X}\right\}$ . Let $\psi :\mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ be a quantum function. Let Y be any random variable over $\mathbb{X}$ obtained by some mechanism M making measurement to the encoding ψ of X and decoding the result of the measurement to $\mathbb{X}$ . Let δ > 0. We call a quantum function ψ a one-way δ-resistant function if

1. it is easy to compute, i.e., a quantum state |ψ(w)⟩ for a particular $w\in \mathbb{X}$ can be determined using a polynomial-time algorithm.

2. for any mechanism M, the probability Pr[Y = X] that M successfully decodes Y is bounded by δ

$\mathit{Pr}\left[Y=X\right]\le \delta .$ E12

For the cryptographic purposes, it is natural to expect (and we do this in the rest of the paper) that random variable X is uniformly distributed.

A quantum state of s ≥ 1 qubits can theoretically record an infinite amount of information. On the other hand, the Holevo’s theorem [22] states that by a quantum measurement, one can extract O(s) bits of information about the state. Here, we use the result of [23] motivated by the Holevo’s theorem.

Property 1 ([23]) Let X be a random variable uniformly distributed over {0, 1}^k. Let ψ : {0, 1}^k→(ℋ²)^⊗s be a quantum function. Let Y be a random variable over {0, 1}^k obtained by some mechanism M making some measurement of the encoding ψ of X and decoding the result of measurement to {0, 1}^k. Then, the probability of correct decoding is given by

$\mathit{Pr}\left[Y=X\right]\le \frac{2^s}{2^k}.$ E13

So, extracting an information on input σ from state |ψ(σ)⟩ in conditions of Property 1 is “hard.” The effectiveness of computation |ψ(σ)⟩ depends on construction of quantum hash function ψ. In Section 4.4, we consider quantum hash function construction based on small-biased sets and prove effectiveness of this construction.

4.2. Collision ε resistance

The following definition was presented in [24].

Definition 3 Let ε > 0. We call a quantum function $\psi :\mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ a collision ε-resistant function if for any pair w , w^′ of different inputs, |⟨ψ(w)| ψ(w^′)⟩| ≤ ε.

Informally speaking, we need two states |ψ(w)⟩ and |ψ(w^′)⟩ that is almost orthogonal in order to get small probability of collision, that is, if one tests states |ψ(w)⟩ and |ψ(w^′)⟩ for equality, then a testing procedure should give positive result with a small probability. We start with quantum testing procedures.

4.2.1. Testing equality

The crucial procedure for quantum hashing is an equality test for |ψ(v)⟩ and |ψ(w)⟩ that can be used to compare encoded classical messages v and w. This procedure can be a well-known SWAP test [5] or something that is adapted for specific hashing function, like REVERSE test, see for example [6].

The SWAP test is the known quantum test for the equality of two unknown quantum states |ψ⟩ and |ψ^′⟩ (see [6, 25] for more information).

We denote Pr_SWAP[v = w] a probability that the SWAP test having quantum hashes |ψ(v)⟩ and |ψ(w)⟩ outputs the result “v = w” (outputs the result “|ψ(v)⟩ = |ψ(w)⟩”).

Property 2 ([6]) Let function ψ : w↦|ψ(w)⟩ satisfy the following condition. For any two different elements $v,w\in \mathbb{X}$ , it is true that |⟨ψ(v)| ψ(w)⟩| ≤ ε. Then,

$P{r}_{\text{swap}}\left[v=w\right]\le \frac{1}{2}\left(1+{\epsilon }^2\right).$ E14

Proof. From the description of SWAP test, it follows that

$P{r}_{\text{swap}}\left[v=w\right]=\frac{1}{2}\left(1+|⟨\psi \left(v\right){\left|\psi \left(w\right)⟩\right|}^2\right).$ E15

4.2.1.1. REVERSE test

The test for equality, which we are presenting here, was first mentioned in [6]. In our paper [25], we call this test a REVERSE test. This test checks if a quantum state |ψ⟩ is a hash of an element v by applying the procedure that inverts the creation of a quantum quantum hash. That is, the REVERSE test procedure transforms the quantum hash to the initial quantum state.

Formally, let the procedure of quantum hashing, given initial state |0⟩, maps the input w by unitary transformation U(w): i.e., quantum hashing produces quantum state |ψ(w)⟩ = U(w)|0⟩. Then, the REVERSE test, given v and |ψ(w)⟩, applies U⁻¹(v) to the state |ψ(w)⟩ and measures the resulting state with respect to initial state |0⟩. The output of REVERSE test is “v = w” iff the measurement outcome is |0⟩. The output of REVERSE test is “ $v\cancel{=}w$ ” iff the measurement outcome is different from |0⟩. The probability that the REVERSE test having quantum state |ψ(w)⟩ and an element v outputs the result v = w are denoted by Pr_REVERSE[v = w] .

Property 3 ([23]) Let hash function ψ : w↦|ψ(w)⟩ satisfies the following condition. For any two different elements, $v\mathit{and}w\in \mathbb{X}$ , it is true that |⟨ψ(v)| ψ(w)⟩| ≤ ε. Then, 

$P{r}_{\text{REVERSE}}\left[v=w\right]\le {\epsilon }^2.$ E16

Pr_REVERSE[v = w] = ∣⟨0|U⁻¹(v)ψ(w)⟩|² = ∣⟨U⁻¹(v)ψ(v)|U⁻¹(v)ψ(w)⟩|²

$=\mid ⟨\psi \left(v\right){\left|\psi \left(w\right)⟩\right|}^2\le {\epsilon }^2.$ E17

4.3. Balanced quantum (δ, ε) resistance

The combination of one-way and collision-resistant function definitions gives the definition of quantum cryptographic function.

Definition 4 ([21]) Let $K=\mid \mathbb{X}\mid$ and s ≥ 1. Let δ > 0 and ε > 0. We call a function $\psi :\mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ a quantum (δ, ε)-hash function iff ψ is one-way δ-resistant and is collision ε-resistant function.

We present below the following two examples to demonstrate how one-way δ resistance and collision ε resistance are correlated. The first example was presented in [4] in terms of quantum automata.

Example 1 Let v ∈ {0,  … , 2^k − 1}. Number v is encoded by a single qubit as follows:

$\psi :v\mapsto \text{cos}\left(\frac{2\mathit{\pi v}}{2^k}\right)\left|0\right.⟩+\text{sin}\left(\frac{2\mathit{\pi v}}{2^k}\right)\left|1⟩\right..$ E18

Extracting information from |ψ⟩ by measuring |ψ⟩ with respect to the basis {|0⟩, |1⟩} gives the following result. The function ψ is one-way $\frac{2}{2^k}$ resistant (see Property 1) and collision cos(π/2^k − 1) resistant. Thus, the function ψ has a good one-way property but has a bad collision resistance property for large k.

Clearly, that one can store (to hash) in this way an arbitrary large amount of classical information, that is, for arbitrary large k one can store all numbers from {0,  … , 2^k − 1} in a single qubit. Holevo bound [22] proves that given s ≥ 1 qubits, the amount of classical information that can be retrieved, i.e., accessed, can be only up to s classical bits. This is a quantum mechanical approach for the one-way property.

The map ψ is one to one. So, there is no collision in a “quantum level.” But extracting the result from quantum state is a probabilistic procedure. This means that one can get the situation when some procedure that tests the equality of different quantum hashes |ψ(v)⟩, |ψ(w)⟩ outputs “the hashes are the same” (equivalently “the numbers v, w are the same”), while the numbers v and w are different. For example, two numbers 0 and 2^k − 2 generate orthogonal states |ψ(0)⟩ = |1⟩ and |ψ(2^k − 2)⟩ = |0⟩. So, numbers 0 and 2^k − 2 are distinguishably reliable in respect of the above encoding. But two numbers 0 and 1 cannot be reliably distinguished by encoding ψ.

Example 2 Binary word v = σ₁ ,  …  , σ_k ∈ {0, 1}^k encoded by k qubits (each bit encoded by a qubit): ψ : v↦|v⟩ = |σ₁⟩ ,  ⋯  , |σ_k⟩.

Clearly, we have that such encoding is collision one-way, 1-resistant, and 0-resistant. So, in contrast to Example 1, the encoding ψ from Example 2 for different words v and w, their images (quantum states) |ψ(v)⟩ and |ψ(v)⟩ are orthogonal and therefore reliably distinguished; but ψ is easily invertible: the function ψ is not one-way resistant.

The following result [24] proves that a quantum collision ε-resistant function needs at least log log K − c(ε) qubits.

Property 4 ([24]) Let s ≥ 1 and $K=\mid \mathbb{X}\mid \ge 4$ . Let $\psi :\mathbb{X}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ be a collision ε-resistant quantum hash function. Then,

$s\ge \text{log}\text{log}K-\text{log}\text{log}\left(1+\sqrt{2/\left(1-\epsilon \right)}\right)-1.$ E19

Proof. First, we observe that from the definition $\mid \mid \left|\psi ⟩\right.\mid \mid =\sqrt{⟨\psi |\psi ⟩}$ of the norm, it follows that

$\mid \mid \mid \psi ⟩-\mid {\psi }^{\prime }⟩\mid {\mid }^2=\mid \mid \mid \psi ⟩\mid {\mid }^2+\mid \mid \mid \psi ,\prime ⟩\mid {\mid }^2-2⟨\psi |{\psi }^{\prime }⟩.$ E20

Hence, for an arbitrary pair w , w^′ of different elements from $\mathbb{X}$ , we have that

$\mid \mid \mid \psi \left(w\right)⟩-\mid \psi \left(w^{\prime }\right)⟩\mid \mid \ge \sqrt{2\left(1-\epsilon \right)}.$ E21

We let $\mathrm{\Delta }=\sqrt{2\left(1-\epsilon \right)}$ . For short, we let (ℋ²)^⊗s = V in this proof. Consider a set $\mathrm{\Phi }=\left\{\left|\psi \left(w\right)⟩\right.:w\in \mathbb{X}\right\}$ . If we draw spheres of radius Δ/2 with centers |ψ⟩ ∈ Φ, then spheres do not pairwise intersect. All these K spheres are in a large sphere of radius 1 + Δ/2. The volume of a sphere of radius r in V is cr^2s + 1 for the complex space V. The constant c depends on the metric of V. From this, we have that the number K is bonded by the number of “small spheres” in the “large sphere”

$K\le \frac{c{\left(1+\mathrm{\Delta }/2\right)}^{2^{s+1}}}{c{\left(\mathrm{\Delta }/2\right)}^{2^{s+1}}}.$ E22

Hence,

$s\ge \text{log}\text{log}K-\text{log}\text{log}\left(1+\sqrt{2/\left(1-\epsilon \right)}\right)-1.$ E23

Properties 1 and 4 provide a basis for building a “balanced” one-way δ-resistance and collision ε-resistance properties. That is, roughly speaking, if we need to hash elements w from the domain $\mathbb{X}$ with $\mid \mathbb{X}\mid =K$ and if one can build for an ε > 0 a collision ε-resistant (K; s) hash function ψ with s ≈ loglogK − c(ε) qubits, then the function f is one-way δ resistant with δ ≈ (logK/K). Such a function is balanced with respect to Property 4.

To summarize the above considerations, we can state the following. A quantum (δ, ε)-hash function is a function that satisfies all of the properties that a “classical” hash function should satisfy. Preimage resistance follows from Property 1. Second preimage resistance and collision resistance follow, because all inputs are mapped to states that are nearly orthogonal. Therefore, we see that quantum hash functions can satisfy the three properties of a classical cryptographic hash function.

4.4. Quantum hash functions construction via small-biased sets

This section is based on the paper [26]. We first present a brief background on ε-biased sets. For more information, see [27]. Note that ε-biased sets are generally defined for arbitrary finite groups, but here we restrict ourselves to ℤ_q.

For an a ∈ ℤ_q, a character χ_a of ℤ_q is a homomorphism χ_a : ℤ_q→μ_q, where μ_q is the (multiplicative) group of complex q-th roots of unity. That is, χ_a(x) = ω^ax, where $\omega =e^{\frac{2\mathit{\pi i}}{q}}$ is a primitive q-th root of unity. The character χ₀ ≡ 1 is called a trivial character.

Definition 5 A set S ⊆ ℤ_q is called ε biased, if for any nontrivial character χ ∈ {χ_a : a ∈ ℤ_q}

$\frac{1}{\mid S\mid }\left|\sum _{x\in S}\hspace{0.17em}\chi \left(x\right)\right|\le \epsilon .$ E24

These sets are interesting when ∣S∣ ≪ ∣ℤ_q∣ (as S = ℤ_q is 0 biased). In their seminal paper, Naor and Naor [13] defined these small-biased sets, gave the first explicit constructions of such sets, and demonstrated the power of small-biased sets for several applications.

Remark 1 Note that a set S of O(log q/ε²) elements selected uniformly at random from ℤ_q is ε biased with positive probability [28].

Many other constructions of small-biased sets followed during the last decades.

Vasiliev [26] showed that ε-biased sets generate (δ,ε)-resistant hash functions. We present the result of [26] in the following form.

Theorem 1 Let S ⊆ ℤ_q be an ε-biased set. Let H_S = {h_a(x) = ax(mod q), a ∈ S, h_a : ℤ_q→ℤ_q} be a set of functions determined by S. Then, a quantum function ψ_HS : ℤ_q→(ℋ²)^{⊗ log ∣S∣}

$|{\psi }_{H_S}\left(x\right)⟩=\frac{1}{\sqrt{\mid S\mid }}\sum _{a\in S}\hspace{0.17em}{\omega }^{h_a\left(x\right)}\left|a⟩\right.$ E25

is a (δ, ε)-resistant quantum hash function, where δ ≤ ∣S∣/q.

Proof. One-way δ-resistance property of ψ_HS follows from Property 1: a probability of correct decoding an x from a quantum state |ψ_HS(x)⟩ is bounded by ∣S∣/q.

Collision ε-resistance property of ψ_HS follows directly from the corresponding property of [26]. Note that

$|{\psi }_{H_S}\left(x\right)⟩=\frac{1}{\sqrt{\mid S\mid }}\sum _{a\in S}\hspace{0.17em}{\omega }^{h_a\left(x\right)}|a⟩=\frac{1}{\sqrt{\mid S\mid }}\sum _{a\in S}\hspace{0.17em}{\chi }_x\left(a\right)\left|a⟩\right..$ E26

We will prove that for arbitrary different elements v , v^′ ∈ ℤ_q, it is true that

$\left|⟨{\psi }_{H_S}\left(v\right)|{\psi }_{H_S}\left(v^{\prime }\right)⟩\right|=\frac{1}{\mid S\mid }\left|\sum _{a\in S}\hspace{0.17em}{\chi }_v^{\ast }\left(a\right){\chi }_{v\prime }\left(a\right)\right|\le \epsilon .$ E27

Let χ_v(x) and χ_v′(x) be characters of group ℤ_q. Then, ${\chi }_v^{\ast }\left(x\right)$ is also a character of ℤ_q and so the following function is $\chi \left(x\right)={\chi }_v^{\ast }\left(x\right){\chi }_{v\prime }\left(x\right)$ . χ(x) is nontrivial character of ℤ_q, since ${\chi }_v\left(x\right)\cancel{\equiv }{\chi }_{v\prime }\left(x\right)$ and $\chi \left(x\right)={\chi }_v^{\ast }\left(x\right){\chi }_{v\prime }\left(x\right)\cancel{\equiv }{\chi }_v^{\ast }\left(x\right){\chi }_v\left(x\right)\equiv 1$ , where 1 is a trivial character of ℤ_q. Thus, the statement of Theorem 1 follows from the definition of an ε-biased set.

$\left|⟨{\psi }_{H_S}\left(v\right)|{\psi }_{H_S}\left(v^{\prime }\right)⟩\right|=\frac{1}{\mid S\mid }\left|\sum _{a\in S}\hspace{0.17em}{\chi }_v^{\ast }\left(a\right){\chi }_{v\prime }\left(a\right)\right|=\frac{1}{\mid S\mid }\left|\sum _{a\in S}\hspace{0.17em}\chi \left(a\right)\right|\le \epsilon .$ E28

4.5. Quantum fingerprinting functions as hash functions

In this section, we give two explicit examples of the quantum hashing for specific finite abelian groups, which turn out to be the known quantum fingerprinting schemas.

4.5.1. Hashing the elements of the Boolean cube

For $G={\mathbb{Z}}_2^n$ , its characters can be written in the form χ_a(x) = (−1)^(a, x), and the corresponding quantum hash function is the following

$|{\psi }_S\left(a\right)⟩=\frac{1}{\sqrt{\mid S\mid }}\sum _{j=1}^{\mid S\mid }\hspace{0.17em}{\left(-1\right)}^{\left(a,s_j\right)}\left|j⟩\right..$ E29

The resulting hash function is exactly the quantum fingerprinting by Buhrman et al. [5], once we consider an error-correcting code, whose matrix is built from the elements of S. Indeed, as stated in [29] an ε-balanced error-correcting code can be constructed out of an ε-biased set. Thus, the inner product (a, x) in the exponent is equivalent to the corresponding bit of the code word, and altogether, this gives the quantum fingerprinting function that stores information in the phase of quantum states de Wolf [30].

4.5.2. Hashing the elements of the cyclic group

For group G = ℤ_q, the corresponding quantum hash function is given by

$|{\psi }_S\left(a\right)⟩=\frac{1}{\sqrt{\mid S\mid }}\sum _{j=1}^{\mid S\mid }\hspace{0.17em}{\omega }^{a{s}_j}\left|j,⟩\right..$ E30

The above quantum hash function is essentially equivalent to the one we have defined earlier in [25], which is in turn based on the quantum fingerprinting function from [11].

• In the content of the definition of quantum hash generator [24] and the above consideration, it is natural to call the set H_S of functions (formed from ε-biased set S) a uniform quantum (δ, ε)-hash generator for δ = O(| S| /(q log q)).

As a corollary from Theorem 1 and the above consideration, we can state the following.

Property 5 For an ε-biased set $S=\left\{a_1,\dots ,a_T\right\}\subset {\mathbb{F}}_q$ with T = O(logq/ε²), for s = logT, for δ = O(1/(qε²)), a quantum uniform (δ, ε)-hash generator H_S generates quantum (δ, ε)-hash function

${\psi }_{H_S}:{\mathbb{F}}_q\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ E31

$|{\psi }_{H_S}\left(x\right)⟩=\frac{1}{\sqrt{T}}\sum _{j=0}^{T-1}\hspace{0.17em}{\omega }^{a_{j}x},$ E32

5. Computing a quantum hash |ψ_HS(x)⟩ by QBP

Theorem 2 Quantum (δ, ε)-hash function (6)

${\psi }_{H_S}:{\mathbb{F}}_q\to {\left({\mathscr{H}}^2\right)}^{\otimes s}$ E33

can be computed by quantum branching program Q composed from s = O(log log q) qubits in log q steps.

Proof. Quantum function ψ_HS (6) for an input $x\in {\mathbb{F}}_q$ determines quantum states (7)

$|{\psi }_{H_S}\left(x\right)⟩=\frac{1}{\sqrt{T}}\sum _{j=0}^{T-1}\hspace{0.17em}{\omega }^{a_{j}x}\left|j⟩\right.,$ E34

which is a result of quantum Fourier transformation (QFT) of the initial state

$|{\psi }_0⟩=\frac{1}{\sqrt{T}}\sum _{j=0}^{T-1}\hspace{0.17em}\left|j⟩\right..$ E35

Such a QFT is controlled by the input x. QBP Q for computing quantum hash |ψ_HS(x)⟩ determined as follows. We represent an integer x ∈ {0,  … , q − 1} as the bit-string x = x₀ … x_{logq − 1} that is, x = x₀ + 2¹x₁ +  …  + 2^{logq − 1}x_{logq − 1}. For a binary string x = x₀ … x_{logq − 1} a quantum branching program Q over the space (ℋ²)^⊗s for computing |ψ_HS(x)⟩ (composed of s = log T qubits) is defined as

$Q=⟨\mathbb{T},\left|{\psi }_0⟩\right.⟩,$ E36

where |ψ₀⟩ is the initial state and $\mathbb{T}$ is a sequence of log q instructions:

${\mathbb{T}}_j=\left(x_j,U_j\left(0\right),U_j\left(1\right)\right)$ E37

is determined by the variable x_j tested on the step j, and U_j(0) and U_j(1) are unitary transformations in (ℋ²)^⊗s. More precise U_j(0) is T × T identity matrix. U_j(1) is the T × T diagonal matrix whose diagonal entries are ω^a₀2j , ω^a₁2j, …, ω^{a_T − 12j} and the off-diagonal elements are all zero. That is,

$U_j\left(1\right)=\left[\begin{array}{llll}{\omega }^{a_0{2}^j}& & & \\ & {\omega }^{a_1{2}^j}& & \\ & & \ddots & \\ & & & {\omega }^{a_{T-1}{2}^j}\\ & & & \end{array}\right].$ E38

We define a computation of Q on an input x = x₀ ,  …  , x_{logq − 1} ∈ {0, 1}^logq as follows:

1. A computation of Q starts from the initial state |ψ₀⟩.

2. The j-th instruction of Q reads the input symbol x_j (the value of x) and applies the transition matrix U_j(x_j) to the current state |ψ⟩ to obtain the state |ψ^′⟩ = U_j(x_j)|ψ⟩.

3. The final state is

$|{\psi }_{H_S}\left(x\right)⟩=\left(\prod _{j=0}^{\text{log}q-1}\hspace{0.17em}{U}_j\left(x_j\right)\right)\left|{\psi }_0⟩\right..$ E39

5.1. Complexity measures

We consider the following notations. For the QBP Q from Theorem 2, we let width(Q) = s and $\mathit{\text{time}}\left(Q\right)=\mid \mathbb{T}\mid$ . Next for quantum hash function ψ_HS (6), we let

$\mathit{\text{width}}\left({\psi }_{H_S}\right)=\text{min}\mathit{\text{width}}\left(Q\right),\mathit{\text{time}}\left({\psi }_{H_S}\right)=\text{min}\mathit{\text{time}}\left(Q\right)$ E40

where minimum is taken over all QBPs that compute ψ_HS.

5.1.1. Upper bounds

Then from Theorem 2, we have the following corollary

Theorem 3

$\mathit{\text{width}}\left({\psi }_{H_S}\right)=O\left(\text{log}\text{log}q\right),$ E41

$\mathit{\text{time}}\left({\psi }_{H_S}\right)=O\left(\text{log}q\right).$ E42

5.1.2. Lower bounds

Here, we show that the quantum branching program from Theorem 2 is optimal for function ψ_HS

Theorem 4

$\mathit{\text{width}}\left({\psi }_{H_S}\right)=\mathrm{\Omega }\left(\text{log}\text{log}q\right),$ E43

$\mathit{\text{time}}\left({\psi }_{H_S}\right)=\mathrm{\Omega }\left(\text{log}q\right).$ E44

Proof. Let Q be a QBP for the function ψ_HS computation. ψ_HS presented by Q as follows:

${\psi }_{H_S}:\left\{\right|{\psi }_0⟩\}\times {\left\{0,1\right\}}^{\text{log}q}\to {\left({\mathscr{H}}^2\right)}^{\otimes s}.$ E45

The lower bound (10) for width(ψ_HS) follows immediately from Property 4

$s\ge \text{log}\text{log}q-\text{log}\text{log}\left(1+\sqrt{2/\left(1-\epsilon \right)}\right).$ E46

The lower bound (11) for time(ψ_HS) follows from the fact that ψ_HS is collision ε-resistant function. Indeed, the assumption that QBP Q for ψ_HS can test less than logq (that is, not all logq) variables of inputs $x\in {\mathbb{F}}_q$ means existence of (at least) two different inputs $w,w^{\prime }\in {\mathbb{F}}_q$ such that Q produces the same quantum hashes |ψ(w)⟩ and |ψ(w^′)⟩ for w and w^′, that is, |ψ(w)⟩ = |ψ(w^′)⟩ = |ψ⟩. The last contradicts to the fact that states |ψ(w)⟩ and |ψ(w^′)⟩ are ε orthogonal.

$\left|⟨\psi \left(w\right)|\psi \left(w^{\prime }\right)⟩\right|\le \epsilon .$ E47

6. Concluding remarks

To conclude, we first like to mention the results of the paper [31], which presents further development of quantum hash functions construction.

Recall that any ε-biased set gives rise to a Cayley expander graph [28]. We show how such graphs generate balanced quantum hash functions. Every expander graph can be converted to a bipartite expander graph. The generalization of these bipartite expander graphs is the notion of extractor graphs. Such point of view gives a method for constructing quantum hash functions based on extractors. This construction of quantum hash functions is applied to define the notion of keyed quantum hash functions. The latter is used for constructing quantum hash-based message authentication codes (QMAC). The security proof of QMAC is based on using strong extractors against quantum storage developed by Ta-Shma [32].

Secondly, in [24], we offered a design that 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 H_δ , q, a quantum hash generator. A resulting family of functions is a new quantum hash generator. In particular, we present a quantum hash generator G_RS based on Reed-Solomon code.