Open access peer-reviewed chapter

On Quantum Fingerprinting and Quantum Cryptographic Hashing

By Farid Ablayev and Marat Ablayev

Submitted: January 25th 2017Reviewed: August 24th 2017Published: May 30th 2018

DOI: 10.5772/intechopen.70692

Downloaded: 563

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.

Keywords

  • quantum computations
  • quantum cryptography
  • fingerprinting
  • 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 Sis ε-biased iff every pair of distinct code words of corresponding error correcting code CShas 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 Quses for computation and a number time(Q) of computational steps of QBP Q. Such QBP Qis 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.

Advertisement

2. Preliminaries

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

2s=2,,2=2s.E1

Conventionally, we use notation |i⟩ for the vector from Hd, 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 qto be a finite additive group of Z/qZ, the integers modulo q. Let Σkbe a set of words of length kover a finite alphabet Σ. Let Xbe a finite set. In this paper, we let X=Σkor X=q. For K=Xand integer s ≥ 1, we define a (K; s) classical-quantum function (or just quantum function) to be mapping

ψ:X2sorψ:wψw.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 wX) of the initial state |ψ0⟩ ∈ (2)sto a quantum state |ψ(w)⟩ ∈ (2)s

ψ:{ψ0}×X2sψw=Uwψ0,E3

where U(w) is a unitary matrix.

Extracting information on wfrom |ψ(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 codeis a map C : Σk→Σnsuch 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 kbe a positive integer and n = ck. Let E : {0, 1}k→{0, 1}nbe a (n, k, d) binary error-correcting code with Hamming distance d ≥ (1 − ε)n.

  • Define a family of functions FE = {E1,  … , En}, where Ei:01kF2is defined by the rule: Ei(w) is the i-th bit of the codeword E(w).

  • Let s = log n + 1. Define the quantum function ψFE : {0, 1}k→(2)s, determined by a word was

|ψFEw=1ni=1niEiw.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)⟩2), 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→(2)sdetermined by a word was

ψFEw=1ni=1n1EiwiE5

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

ψFExψFEy=1ni=1n1EiwEiw=ndEwEwnε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}n→{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:

0ψσ=cosθ0+sinθ1E7

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 cos2π(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:

|0|0logt|01ti=1ticosθi0+sinθi1,E8

where θi=2πsiσqand the set S = {s1,  … , st} ⊆ qis chosen in order to guarantee the small probability of error [11, 15]. That is, the last qubit is simultaneously rotated in tdifferent 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 1tj=1tj0of the basis states {|j⟩|0⟩ : j ∈ {1,  … , t}}.

  3. Based on the input σ, its fingerprint is created: 1tj=1t|jcos2πsjσq|0+sin2πsjσq|1.

  4. The Hadamard transform turns the fingerprint into the state |ψ=1tl=1tcos2πslσq|0logt0+

  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ψ0,E9

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

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

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

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

  2. The j-th instructionof Q reads the input symbol σij(the value of xij) and applies the transition matrix Uj = Uj(σij) to the current state|ψto obtain the state|ψ⟩ = Uj(σij)|ψ⟩.

  3. The final state is

|ψσ=j=l1Ujσij|ψ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, Qmeasures its configuration |ψσ⟩ = (α1,  … , αd)Tand the input σis accepted with probability

Pracceptσ=iAcceptαi2.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. Variablesxi1 ,  …  , xildenoting 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 Mbe a function M:2sX. Informally speaking, mechanism Mmakes some measurements to state |ψ⟩ ∈ (2)sand decodes the result of measurement to X.

Definition 2 ([21])Let X be a random variable distributed overXPrX=w:wX. Letψ:X2sbe a quantum function. Let Y be any random variable overXobtained by some mechanismMmaking measurement to the encoding ψ of X and decoding the result of the measurement toX. 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 particularwXcan be determined using a polynomial-time algorithm.

  2. for any mechanismM, the probabilityPr[Y = X] thatMsuccessfully decodes Y is bounded by δ

PrY=Xδ.E12

For the cryptographic purposes, it is natural to expect (and we do this in the rest of the paper) that random variable Xis 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→(2)sbe a quantum function. Let Y be a random variable over{0, 1}k obtained by some mechanismMmaking 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

PrY=X2s2k.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ψ:X2sa 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 vand 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 PrSWAP[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 elementsv,wX, it is true that|⟨ψ(v)| ψ(w)⟩| ≤ ε. Then,

Prswapv=w121+ε2.E14

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

Prswapv=w=121+ψvψw2.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 vby 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 wby unitary transformation U(w): i.e., quantum hashing produces quantum state |ψ(w)⟩ = U(w)|0⟩. Then, the REVERSE test, given vand |ψ(w)⟩, applies U−1(v) to the state |ψ(w)⟩ and measures the resulting state with respect to initial state |0⟩. The output of REVERSE testis “v = w” iff the measurement outcome is |0⟩. The output of REVERSE test is “v=w” iff the measurement outcome is different from |0⟩. The probability that the REVERSE testhaving quantum state |ψ(w)⟩ and an element voutputs the result v = w are denoted by PrREVERSE[v = w] .

Property 3 ([23])Let hash function ψ : w↦|ψ(w)⟩ satisfies the following condition. For any two different elements,vandwX, it is true that|⟨ψ(v)| ψ(w)⟩| ≤ ε. Then, 

PrREVERSEv=wε2.E16

PrREVERSE[v = w] = ∣⟨0|U−1(v)ψ(w)⟩|2 = ∣⟨U−1(v)ψ(v)|U−1(v)ψ(w)⟩|2

=ψvψw2ε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])LetK=Xands ≥ 1. Let δ > 0 and ε > 0. We call a functionψ:X2sa 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,  … , 2k − 1}. Number v is encoded by a single qubit as follows:

ψ:vcos2πv2k0+sin2πv2k1.E18

Extracting information from |ψ⟩ by measuring |ψ⟩ with respect to the basis {|0⟩, |1⟩} gives the following result. The function ψis one-way 22kresistant (see Property 1) and collision cos(π/2k − 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 kone can store all numbers from {0,  … , 2k − 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 sclassical 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, ware the same”), while the numbers vand ware different. For example, two numbers 0 and 2k − 2 generate orthogonal states |ψ(0)⟩ = |1⟩ and |ψ(2k − 2)⟩ = |0⟩. So, numbers 0 and 2k − 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 = σ1 ,  …  , σk ∈ {0, 1}k encoded by k qubits (each bit encoded by a qubit): ψ : v↦|v⟩ = |σ1⟩ ,  ⋯  , |σ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 vand 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 andK=X4. Letψ:X2sbe a collision ε-resistant quantum hash function. Then,

sloglogKloglog1+2/1ε1.E19

Proof. First, we observe that from the definition ψ=ψψof the norm, it follows that

ψψ2=ψ2+ψ22ψψ.E20

Hence, for an arbitrary pair w , w of different elements from X, we have that

ψwψw21ε.E21

We let Δ=21ε. For short, we let (2)s = Vin this proof. Consider a set Φ=ψw:wX. If we draw spheres of radius Δ/2 with centers |ψ⟩ ∈ Φ, then spheres do not pairwise intersect. All these Kspheres are in a large sphere of radius 1 + Δ/2. The volume of a sphere of radius rin Vis cr2s + 1 for the complex space V. The constant cdepends on the metric of V. From this, we have that the number Kis bonded by the number of “small spheres” in the “large sphere”

Kc1+Δ/22s+1cΔ/22s+1.E22

Hence,

sloglogKloglog1+2/1ε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 wfrom the domain Xwith X=Kand if one can build for an ε > 0 a collision ε-resistant (K; s) hash function ψwith s ≈ loglogK − c(ε) qubits, then the function fis 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 χaof qis a homomorphism χa : qμq, where μqis the (multiplicative) group of complex q-th roots of unity. That is, χa(x) = ωax, where ω=e2πiqis a primitive q-th root of unity. The character χ0 ≡ 1 is called a trivial character.

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

1S|xSχx|ε.E24

These sets are interesting when ∣S∣ ≪ ∣q∣ (as S = qis 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 1Note that a set S of O(log q/ε2) 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 HS = {ha(x) = ax(mod q), a ∈ S, ha : qq} be a set of functions determined by S. Then, a quantum function ψHS : q→(2)⊗ log ∣S

|ψHSx=1SaSωhaxaE25
is a(δ, ε)-resistant quantum hash function, where δ ≤ ∣S∣/q.

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

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

|ψHSx=1SaSωhax|a=1SaSχxaa.E26

We will prove that for arbitrary different elements v , v ∈ q, it is true that

ψHSvψHSv=1S|aSχvaχva|ε.E27

Let χv(x) and χv(x) be characters of group q. Then, χvxis also a character of qand so the following function is χx=χvxχvx. χ(x) is nontrivial character of q, since χvxχvxand χx=χvxχvxχvxχvx1, where 1 is a trivial character of q. Thus, the statement of Theorem 1 follows from the definition of an ε-biased set.

|ψHSv|ψHSv|=1S|aSχvaχva|=1S|aSχa|ε.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=2n, its characters can be written in the form χa(x) = (−1)(a, x), and the corresponding quantum hash function is the following

|ψSa=1Sj=1S1asjj.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

|ψSa=1Sj=1Sωasjj.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 HSof functions (formed from ε-biased set S) a uniform quantum(δ, ε)-hash generatorfor δ = O(| S| /(q log q)).

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

Property 5For an ε-biased setS=a1aTFqwith T = O(logq/ε2), for s = logT, for δ = O(1/(2)), a quantum uniform(δ, ε)-hash generator HS generates quantum(δ, ε)-hash function

ψHS:Fq2sE31
|ψHSx=1Tj=0T1ωajx,E32

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

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

ψHS:Fq2sE33
can be computed by quantum branching program Q composed from s = O(log log q) qubits inlog q steps.

Proof. Quantum function ψHS(6) for an input xFqdetermines quantum states (7)

|ψHSx=1Tj=0T1ωajxj,E34
which is a result of quantum Fourier transformation (QFT) of the initial state
|ψ0=1Tj=0T1j.E35

Such a QFT is controlled by the input x. QBP Qfor computing quantum hash |ψHS(x)⟩ determined as follows. We represent an integer x ∈ {0,  … , q − 1} as the bit-string x = x0 … xlogq − 1 that is, x = x0 + 21x1 +  …  + 2logq − 1xlogq − 1. For a binary string x = x0 … xlogq − 1 a quantum branching program Qover the space (2)sfor computing |ψHS(x)⟩ (composed of s = log Tqubits) is defined as

Q=Tψ0,E36

where |ψ0⟩ is the initial state and Tis a sequence of log qinstructions:

Tj=xjUj0Uj1E37
is determined by the variable xjtested on the step j, and Uj(0) and Uj(1) are unitary transformations in (2)s. More precise Uj(0) is T × Tidentity matrix. Uj(1) is the T × Tdiagonal matrix whose diagonal entries are ωa02j , ωa12j, …, ωaT − 12jand the off-diagonal elements are all zero. That is,
Uj1=ωa02jωa12jωaT12j.E38

We define a computation of Qon an input x = x0 ,  …  , xlogq − 1 ∈ {0, 1}logqas follows:

1. A computation of Qstarts from the initial state |ψ0⟩.

2. The j-th instruction of Qreads the input symbol xj(the value of x) and applies the transition matrix Uj(xj) to the current state |ψ⟩ to obtain the state |ψ⟩ = Uj(xj)|ψ⟩.

3. The final state is

|ψHSx=j=0logq1Ujxjψ0.E39

5.1. Complexity measures

We consider the following notations. For the QBP Qfrom Theorem 2, we let width(Q) = sand timeQ=T. Next for quantum hash function ψHS(6), we let

width(ψHS)=minwidthQ,time(ψHS)=mintimeQE40

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

width(ψHS)=Ologlogq,E41
time(ψHS)=Ologq.E42

5.1.2. Lower bounds

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

Theorem 4

width(ψHS)=Ωloglogq,E43
time(ψHS)=Ωlogq.E44

Proof. Let Qbe a QBP for the function ψHScomputation. ψHSpresented by Qas follows:

ψHS:{|ψ0}×01logq2s.E45

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

sloglogqloglog1+2/1ε.E46

The lower bound (11) for time(ψHS) follows from the fact that ψHSis collision ε-resistant function. Indeed, the assumption that QBP Qfor ψHScan test less than logq(that is, not all logq) variables of inputs xFqmeans existence of (at least) two different inputs w,wFqsuch that Qproduces the same quantum hashes |ψ(w)⟩ and |ψ(w)⟩ for wand w, that is, |ψ(w)⟩ = |ψ(w)⟩ = |ψ⟩. The last contradicts to the fact that states |ψ(w)⟩ and |ψ(w)⟩ are εorthogonal.

ψwψwε.E47

Advertisement

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 GRSbased on Reed-Solomon code.

© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Farid Ablayev and Marat Ablayev (May 30th 2018). On Quantum Fingerprinting and Quantum Cryptographic Hashing, Advanced Technologies of Quantum Key Distribution, Sergiy Gnatyuk, IntechOpen, DOI: 10.5772/intechopen.70692. Available from:

chapter statistics

563total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Quantum Flows for Secret Key Distribution

By Luis A. Lizama-Pérez, J. Mauricio López and Eduardo de Carlos Lopez

Related Book

First compact

Partition-Based Trapdoor Ciphers

By Arnaud Bannier and Eric Filiol

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us