1 Introduction

The following problem is normally considered in classical and quantum communication scenarios: Bob have to communicate some secret message to Eve. They proceed the following procedure.

  • Encoding message and sending: Eve prepares some text message, namely in state |ψ 0〉, encodes it into a state |ψ 1〉 and send it to Bob

  • Queries and Back Sending: Bob makes some queries and transforms the received message into the state |ψ 2〉 and sends it back to Eve.

  • Decoding and Identifying the Secret: Eve decodes it and identifies the common secret share with Bob.

In their paper [5] Nagata and Nakamura described this procedure of quantum communication by using a scheme with Hadamard inverse transform H ⊗N, N queries Q: \((x_{i},y_{i}), i=\overline {1,N}\) and Hadamard gates H ⊗N :

$$|\psi_{0}\rangle \longrightarrow{H^{\otimes N}} |\psi_{1}\rangle \longrightarrow{Q: (x_{i},y_{i}),i=\overline{1,N}} |\psi_{2}\rangle \longrightarrow{H^{\otimes N}} |\psi_{3}\rangle $$

This scheme is applicable to the Bernstein-Vazirani algorithm for linear black boxes f for finding their coefficients as the secret.

In this paper we consider the Quatum Fourier and the inverse Quantum Fourier Trasnforms QFT, Q F T −1 in place of the Hadamard and inverse Hadamard gates and we discover that it is applicable to nonlinear black box function f of multivariate interpolation of polynomials in higer degrees. Our scheme works for nonlinear qudits in the same way as in the linear case for qubits because for qubits, d = 2 we have (−1)xz = exp(i2π x z/2) and the Quantum Fourier transform \(|x\rangle \mapsto {\sum }_{z\in \mathbb {F}_{q}^{k}} e(xz),\) with e(z) := exp(i2π Tr(z)/p), \(\text {Tr}(z) := z + z^{p^{1}} + {\dots } + z^{p^{d-1}}\) for qubits (d=2) becomes the Hadamard gate.

In the work [1] Chen et al. estimated the queries complexity of order \(k_{\mathbb {F}_q=p^{r}} = \frac {d}{n+d}\binom {n+d}{d}\) with probability 1 − O(1/q) and this complexity is optimal. Therefore we may use it to make distribution of secret scheme among \(k=k_{\mathbb {F}_{q}}\) users.

A novelty in the paper is that we use the multivariate polynomial interpolation in place of linear interpolation, qudits in place of qubits and apply to quantum key distribution for general interpolation as in the scheme of Shamir’s code or NSA codes.

The paper is organized as follows. In the next Section 2 we describe the quantum communication scheme, needed for our problem. In Section 3 we describe the quantum multivariate polynomial interpolation and then use it to the problem of quantum secret sharing communication.

2 Quantum Communication

The black box U f is given by a function

$$f: \mathbb{Z}_{2}^{N} = \{0,1\}^{N} \to \mathbb{Z}_{2}=\{0,1\}; f(x) = a.x =\sum\limits_{i=1}^{N} a_{i}x_{i} (\mod 2), $$

with \(x, a \in \mathbb {Z}_{2}^{N}\). The problem is to identify the coefficients \(a_{1},\dots ,a_{N} \in \mathbb {Z}_{2}\). To solve this problem, there is well-known

Bernstein-Vazirani algorithm:

  • Input the state \(|\psi _{0}\rangle = |0{\dots } 01\rangle \in \mathbb {Z}_{2}^{\otimes (N+1)}\). Let \(H=\frac {1}{\sqrt {2}}\left [\begin {array}{cc} 1 & 1\\ 1 & -1 \end {array}\right ]\) be the Hadamard gate, acting on pairs consisting of states, each from the first N qubits and the last (N+1)th qubit,

    $$H= H^{-1}: \left\{ \begin{array}{lll}|0\rangle & \mapsto& \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\\ |1\rangle & \mapsto& \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\end{array}\right. $$

    Apply H ⊗N to |ψ 0〉 to obtain the state |ψ 1〉 = H ⊗N|ψ 0〉;

    $$|\psi_{1} \rangle = \sum\limits_{x\in \mathbb{Z}_{2}^{N}} \frac{|x\rangle}{\sqrt{2^{N}}} \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right] $$

  • Make queries \(x_{i}, f(x_{i}), i=\overline {1,N}\), U f : |x,y〉↦|x,y ⊕ f(x)〉 to obtain the state |ψ 2〉 = (H)⊗N|ψ 1〉;

    $$|\psi_{2}\rangle = \pm \sum\limits_{x\in \mathbb{Z}_{2}^{N}} \frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^{N}}}\left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right] $$

  • Apply the Hadamard gates H ⊗N to qubits to obtain the state |ψ 3〉 = H ⊗N|ψ 2〉;

    $$\begin{array}{@{}rcl@{}} &|\psi_{3}\rangle = \pm \sum\limits_{z}\sum\limits_{x} \frac{(-1)^{xz+f(x)} |z\rangle}{2^{N}} \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]\\ &= \pm \sum\limits_{z}\sum\limits_{x} \frac{(-1)^{x.z+a.x} |z\rangle}{2^{N}} \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]\\ &= \delta_{z+a, 0} |z\rangle \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]\\ &= \pm |a_{1}{\dots} a_{N}\rangle \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]. \end{array} $$

    Make a measurement and obtain the values \(a_{1},\dots ,a_{N} \in \mathbb {Z}_{2}\).

We refer the readers to Ref [5] for more details.

This procedure gives us some application in secret sharing problem in quantum communication as follows. The scenario is that Bob wants to send a secret message to Eve, represented in form of coefficients of a linear function f.

The protocol is to proceed the following.

  • Encoding message and sending: Eve prepares some text message, namely in state \(|\psi _{0}\rangle = |0{\dots } 01\rangle \in \mathbb {Z}_{2}^{\otimes (N+1)}\), encodes it into a state |ψ 1〉 = H ⊗N|ψ 0〉;

    $$|\psi_{1} \rangle = \sum\limits_{x\in \mathbb{Z}_{2}^{N}} \frac{|x\rangle}{\sqrt{2^{N}}} \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right] $$

    and send it to Bob

  • Queries and Back Sending: Bob makes some queries \(Q: y_{i} = f(x_{i}), i=\overline {1,{\dots } N}\) and transforms it into the state |ψ 2〉 = Q|ψ 1〉;

    $$|\psi_{2}\rangle = \pm \sum\limits_{x\in \mathbb{Z}_{2}^{N}} \frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^{N}}}\left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right] $$

    and sends it back to Eve.

  • Decoding and Identifying the Secret: Eve decodes it by applying H ⊗N to obtain |ψ 3〉 = H ⊗N|ψ 2〉 and identifies the common secret share with Bob.

    $$\begin{array}{@{}rcl@{}} &|\psi_{3}\rangle = \pm \sum\limits_{z}\sum\limits_{x} \frac{(-1)^{xz+f(x)} |z\rangle}{2^{N}} \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]\\ &= \pm |a_{1}{\dots} a_{N}\rangle \left[ \frac{|0\rangle -|1\rangle}{\sqrt{2}} \right]. \end{array} $$

This code works well in the case of linear black box f. Next we want to do the same for f to be a polynomial in n variable and of degree d.

3 Quantum Secret Sharing Problem

Let \(\mathbb {K}= \mathbb {F}_{q}\) be a finite fields of q = p r elements, p being some fixed prime, and as above, e(z) = exp(i2π Tr(z)/p), \(\text {Tr}(z) := z + z^{p^{1}} + {\dots } + z^{p^{d-1}}\). The Quantum Fourier Transform (QFT) is defined as

$$QFT : |x\rangle \mapsto \frac{1}{\sqrt{q}}\sum\limits_{y\in \mathbb{F}^{k}_{q}} e(-x.y)|y\rangle, \forall x, y\in \mathbb{F}^{k}_{1}. $$

We will produce the following operations

$$|\psi_{0}\rangle \longrightarrow{QFT} |\psi_{1}\rangle \longrightarrow{Q: (x_{i},y_{i}),i=\overline{1,N}} |\psi_{2}\rangle \longrightarrow{QFT^{-1}} |\psi_{3}\rangle $$

The result is

$$|x,y\rangle \longrightarrow{QFT} \frac{1}{\sqrt{q}}\sum\nolimits_{y\in \mathbb{F}^{k}_{q}} e(-x.y)|x,z\rangle \longrightarrow{Q} \frac{1}{\sqrt{q}}\sum\nolimits_{y\in \mathbb{F}^{k}_{q}} e(-x.y)|x,z+f(x)\rangle $$
$$\longrightarrow{QFT^{-1}}\frac{1}{q}\sum\nolimits_{w\in \mathbb{F}^{k}_{q}}\sum\nolimits_{y\in \mathbb{F}^{k}_{q}} e(-x.z)e(w(z+f(x))|x,w\rangle\,\, {===={~~~~~}}\,\, e(yf(x))|x,y\rangle. $$

Producing the k-queries in parallel on have

$$y_{i}f(x_{i}) = \sum\limits_{i=1}^{k} \sum\limits_{j\in J} y_{i}{x_{i}^{j}}c_{j} $$

and denote the map

$$Z: \mathbb{F}_{q}^{nl} \times \mathbb{F}_{q}^{k} \to \mathbb{F}_{q}^{J} $$

the map with components

$$Z(x,y)_{j} = \sum\limits_{i=1}^{k} y_{i}{x_{i}^{j}} $$

one has \({\sum }_{i}y_{i}f(x_{i}) = Z(x,y).c\) with \(c\in \mathbb {F}_{q}^{k}\) as the coefficients vector of the polynomial f. We refer the reader to the work [1] of Chen et al. for more details.

It is natural now to produce the same protocol for the secret sharing communication using this Quantum Multivariate Interpolation

Theorem 3.1

Bob can send a secret message to Eve and Eve can decode the secret message with probability 1 − O(1/q).

Proof

The problem is solved by using the following

Procedure. Bob and Eve agree to use polynomials of degree d.

  • Encoding message and sending: Eve prepares some text message, devides it into a vector with k components, and looks at for a state, namely in state \(|\psi _{0}\rangle =|x,y\rangle \in \mathbb {F}_{q}^{2k}\), encodes it into a state |ψ 1〉 = Q F T|ψ 0〉; and send it to Bob.

  • Queries and Back Sending : Bob makes some queries \(Q: y_{i} = f(x_{i}), i=\overline {1,\dots , N}\) and transforms it into the state |ψ 2〉 = Q|ψ 1〉;

    $$|\psi_{2}\rangle =\frac{1}{\sqrt{q}}\sum\limits_{y\in \mathbb{F}^{k}_{q}} e(-x.y)|x,z+f(x)\rangle $$

    and sends it back to Eve.

  • Decoding and Identifying the Secret: Eve decodes the received message and identifies the common secret share with Bob.

    $$|\psi_{3}\rangle = \frac{1}{q}\sum\limits_{w\in \mathbb{F}^{k}_{q}}\sum\limits_{y\in \mathbb{F}^{k}_{q}} e(-x.z)e(w(z+f(x))|x,w\rangle = e(y.f(x))|x,y\rangle. $$
    $$y_{i}f(x_{i}) = \sum\limits_{i=1}^{k} \sum\limits_{j\in J} y_{i}{x_{i}^{j}}c_{j} $$

    and the map

    $$\begin{array}{@{}rcl@{}} &Z: \mathbb{F}_{q}^{nl} \times \mathbb{F}_{q}^{k} \to \mathbb{F}_{q}^{J}\\ &(x,y) \mapsto Z(x,y), \end{array} $$

    with components

    $$Z(x,y)_{j} = \sum\limits_{i=1}^{k} y_{i}{x_{i}^{j}} $$

    has \({\sum }_{i}y_{i}f(x_{i}) = Z(x,y).c\) with \(c\in \mathbb {F}_{q}^{k}\) as the coefficients vector of the polynomial f.

The theorem is therefore proved. □

There are the evident cases:

Example 1

d = 1, n is arbitrary. In this case one need only one query \(k= k_{\mathbb {F}_{q}} = \frac {1}{n+1}\binom {n+1}{1} = 1\).

Example 2

n = 1, d arbitrary. In this case we have interpolation on one variable and we have \(k=k_{\mathbb {F}_{q}} = \frac {d}{d+1}\binom {1+d}{d} = d\).

Quantum Secret Sharing Schemes

In the work [6], Smith considered the general access structure for quantum secret sharing system in appearance of athird part person. Let us remind alittle bit about this QSS schemes. An adversary structure \(\mathcal A \subseteq 2^{P}\) over the set P of all players is aset of subsets of P which is downward-closed under inclusion. It is \(\mathcal {Q}^{2}\) if there is no pair of two sets in \(\mathcal {A}\) being complemetary to each-another. It is \(\mathcal {Q}^{2*}\), if its dual \(\mathcal {A}^{*} =\{ B \subseteq P; B^{c} \notin \mathcal {A}\}\) is \(\mathcal Q^{2}\) and finally it is self-dual if it is both \(\mathcal {Q}^{2}\) and \(\mathcal {Q}^{2*}\). In the work [6], Smith had seen (Theorem 1) that

Given any \(\mathcal {Q}^{2*}\) structure \(\mathcal {A}\) on P one can find aQSS scheme and if the scheme is self-dual then the scheme is apure-state one.

Let \(k=k_{\mathbb {F}_{q}}= \frac {d}{d+1}\binom {1+d}{d} \) be the optimal number of interpolation points as above.

Theorem 3.2

Bob can send a secret message to k persons at Eve side and Eve can decode the secret from the concatenated message from k persons with probability 1 − O(1/q).

Proof

In the presence of some third part person, in order to keep secret, Eve use concatenated informations from k users, which provide a self-dual adversary structure \(\mathcal {A}\) and Bob sends each interpolation information to only one of them and receive information from these users.

Indeed, it is possible because the estimation \(k=k_{\mathbb {F}_{q}}\) is optimal [1], i.e. the concatenated information from any smaller number of persons can not resolve the secret (in the sense that the interpolation is impossible). Consider the adversary structure consisting of k person. Bob sends each interpolation query to a unique one of them.

The case when a third partite person receive all k informations from Bob is excluded because, following the noncloning principle of quantum computing, the message is destroyed completely and it could not be arrived to Eve, the confused message appears only when at least one of information is sended to Eve and the third part person can not discover the message because he/she knows only at most ≤ k − 1 interpolation points. That means that the third partite person cannot discover the secret and the secrecy is graranteed. The theorem is therefore proven. The probability is appeared from the multivariate polynomial interpolation. □

4 Conclusion

We have seen that for any qudit message, one can use the quantum multivariate interpolation to make secrecy of sending the information following the general scheme of Quantum Secret Sharing. In case of multivariate polynomial interpolation, we have some probability of correctly decoding the message, rather than in the one variable case with certainty.