1 Introduction↩︎

Motivation: A typical advantage of quantum information processing is its ability to provide various information-theoretic secure protocols, such as quantum key distribution and secure quantum computation. This paper focuses on secure blind decryption, a communication task between users and servers. In this task, the users possess an encrypted ciphertext, while the servers hold several indexed keys including the key encrypting the ciphertext. The objective of secure blind decryption is to allow the users to decrypt their ciphertext through interaction with the servers without revealing its content to the servers. Additionally, the protocol ensures that the servers learn no information about the original message as well as the key index to identify the key encrypting the ciphertext, while one of the users ultimately receives the decrypted message.

The preceding studies [1]–[3] discussed a similar task with one user and one server. Their protocols for this task rely on computational security, meaning their security depends on the computational hardness assumptions underlying public-key cryptography. However, such security becomes vulnerable if an efficient decryption algorithm or a quantum algorithm capable of breaking the cryptography is discovered. To mitigate this risk, it is necessary to develop a protocol that provides information-theoretic security for this task, particularly when the encryption employs Shannon’s one-time pad keys.

In addition, their protocols work with only one key and ensure that the user obtains no information about the key and the server obtains no information about the encrypted ciphertext nor decrypted text. But, their protocol does not cover the secrecy of the key index. The goal of this paper is to propose quantum secure blind decryption protocols to fulfill the above secrecy requirements. These protocols can be applied, for example, to securely managing wills containing sensitive information. In such a scenario, since parents do not wish the contents of their wills to be known, they encrypt the will and leave the ciphertext with their lawyer, while the decryption key is sent to a trusted institution. Upon their passing, the secure decryption protocol ensures that the will can be securely transmitted from the lawyer to their child without revealing its contents to the institution.

Overview of Quantum Secure Blind Decryption: The task of quantum secure blind decryption involves two users: \(\mathop{\mathrm{User}}_1\), who possesses the ciphertext, and \(\mathop{\mathrm{User}}_2\), to whom the decrypted message is intended to be sent via communication with the server. The ciphertext is encrypted using a one-time pad. Unlike public-key cryptography, the server maintains a database of decryption keys, and \(\mathop{\mathrm{User}}_1\) holds a key index that specifies which key was used for encryption. The secrecy of the protocol is defined in terms of information-theoretic security. We introduce two types of quantum secure blind decryption protocols, each with different secrecy requirements, and propose concrete protocols for each protocol. In addition, we demonstrate that the proposed protocol for the second protocol achieves a performance unattainable by any classical system.

First Result: Protocol for the First Setting: The first result introduces a new communication task and a corresponding protocol for the first setting, involving two users (\(\mathop{\mathrm{User}}_1\) and \(\mathop{\mathrm{User}}_2\)) and one server. In this task, the two users are assumed to share entangled states beforehand. The purpose is to securely decrypt the ciphertext held by \(\mathop{\mathrm{User}}_1\) and transmit the message to \(\mathop{\mathrm{User}}_2\) without revealing the message to the server. While the message remains secret from the server, the user’s key index is not.

Our concrete protocol for this setting relies on superdense coding, with the security analysis provided in [4], [5]. However, the first setting has potential risks: since the server knows which decryption key was used, it can reconstruct the message if \(\mathop{\mathrm{User}}_1\) leaks the ciphertext after the protocol concludes.

Second Result: Protocol for the Second Setting: The second result introduces a new task with the second setting, which provides stronger secrecy compared to the first setting. In this case, in addition to keeping the message secret, the protocol ensures that the key index also remains secure against the server. To achieve key index secrecy, the second setting assumes two servers that store identical databases. Unlike the first protocol, the second protocol does not require pre-shared entangled states.

Third Result: Security against post attack: We emphasize that the second protocol achieves a level of secrecy unattainable in classical settings. In particular, we assume that the servers may communicate after the protocol concludes to infer the message, a scenario referred to as a post-attack model. This is because it is difficult to forbid the servers from communicating with each other after the completion of the protocol. We prove that our quantum protocol preserves message secrecy under the post-attack model, whereas no classical protocol can achieve this, demonstrating a clear quantum advantage.

In contrast, the task in the first setting can be realized using classical methods. Therefore, our protocol in the second setting highlights the importance of quantum communication. While some may argue that presenting only the second setting would suffice, it is due to the complexity of the second setting we prefer to present the first setting beforehand.

Organization of the Paper: The remainder of this paper is organized as follows: Section 2 introduces the basic notation used throughout the paper. Section 3 defines the first setting’s task, quantum one-server protocol, and presents a concrete protocol along with its secrecy analysis. Section 4 defines the second setting’s task, quantum two-server protocol, and proposes a concrete protocol for this setting, with a discussion of its secrecy. Section 5 analyzes secrecy under the post-attack model. Section 6 shows that the classical case cannot achieves the performance presented in Section 6. Section 7 concludes the paper.

2 Preliminary↩︎

Before stating our protocols, we prepare fundamental knowledge for Bell states. Let \(\{\ket{0}, \ket{1}\}\) be an orthonormal basis of two-dimensional Hilbert space \(\mathcal{A}\). We define the Pauli operators \(X, Z\) on \(\mathcal{A}\) as \[\begin{align} X = \ket{1}\!\bra{0} + \ket{0}\!\bra{1}, \quad Z = \ket{0}\!\bra{0} - \ket{1}\!\bra{1}. \end{align}\] These operators satisfy the following relation; \[\label{eq:commutative} XZ = - ZX.\tag{1}\] The maximally entangled state \(\ket{\phi}\) on \(\mathcal{A} \otimes \mathcal{A}\) is defined as \[\ket{\phi} = \frac{1}{\sqrt{2}}\left( \ket{00}+\ket{11}\right).\] For \(a \in \mathbb{F}_2^n\), \(i\)-th element of \(a\) is denoted as \(a_i\), \[a = (a_i,a_2,\dots,a_n).\] We define the sum on \(\mathbb{F}_2^n\) by the sum of each element on \(\mathbb{F}_2\) as follows. For \(a, b \in \mathbb{F}_2^{n}\), \[a \oplus b \coloneq (a_1 \oplus b_1, a_2 \oplus b_2, \dots a_n \oplus b_n).\] For \(k,j \in \mathbb{F}_2\), The discrete Weyl operator on the qubit system \(\mathbb{C}^2\) is defined as \[\operatorname{W}(k,j) \coloneq X^k Z^j.\] This operator satisfies the relations \[\begin{align} \mathop{\mathrm{W}}(k,j)^\dagger &= (-1)^{k \cdot j}\mathop{\mathrm{W}}(-k,-j), \\ \mathop{\mathrm{W}}(k,j)\mathop{\mathrm{W}}(u,v) &= (-1)^{t \cdot u} \mathop{\mathrm{W}}(s \oplus u, t \oplus v). \end{align}\] For \(s \in \mathbb{F}_2^{2n}\), the operator \(\mathop{\mathrm{W}}_n(s)\) on \((\mathbb{C}^2)^{\otimes n}\) is defined by \[\operatorname{W}_n(s) \coloneq \mathop{\mathrm{W}}(s_1,s_2) \otimes \dots \otimes \mathop{\mathrm{W}}(s_{2n-1},s_{2n}).\]

Next, for \(k,j \in \mathbb{F}_2\), we define the state \(\ket{\phi_{kj}}\) on the composite system \(\mathbb{C}^2 \otimes \mathbb{C}^2\) as \[\begin{align} \ket{\phi_{kj}} &\coloneq \frac{1}{\sqrt{2}}(\ket{k}\!\ket{0} + (-1)^j \ket{k \oplus 1}\!\ket{1})\\ &= (X^k \otimes Z^j) \ket{\phi} = (\mathop{\mathrm{W}}(k,j) \otimes I)\ket{\phi}. \end{align}\] Then, the set \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) forms an orthonormal basis of \(\mathcal{A} \otimes \mathcal{A}\). Further, for \(a,b,c,d,m,n \in \mathbb{F}_2\), the relation \[\begin{align} & (\mathop{\mathrm{W}}(a,b) \otimes \mathop{\mathrm{W}}(c,d)) \ket{\phi_{kj}}\!\bra{\phi_{kj}} (\mathop{\mathrm{W}}(a,b)^\dagger \otimes \mathop{\mathrm{W}}(c,d)^\dagger)\notag\\ =& \ket{\phi_{k \oplus a \oplus c, j \oplus b \oplus d}}\!\bra{\phi_{k \oplus a \oplus c, j \oplus b \oplus d}} \end{align}\] holds. In addition, throughout this paper, we use \(2\) as the base of the logarithm.

3 one-server protocol↩︎

This section studies the communication task involving two users, \(\mathop{\mathrm{User}}_1\) and \(\mathop{\mathrm{User}}_2\), and a server. The server stores the encryption keys, while \(\mathop{\mathrm{User}}_1\) possesses the ciphertext of a message encrypted using one of these keys. The goal of this task is to securely decrypt the ciphertext held by \(\mathop{\mathrm{User}}_1\) and transmit the decrypted message to \(\mathop{\mathrm{User}}_2\) without revealing the message to the server during the communication. In addition, it is required that both users obtain no information for keys. Notably, we do not impose any security constraints on the key index \(K\), meaning the server is allowed to know the key index \(K\). We refer to this task as one-server protocol.

First, we formally define the protocol and its associated security constraints, which formally clarifies our task. Next, we present a concrete code for performing this task and analyze its security.

3.1 Definition of protocol↩︎

We present a formal description of secure blind decryption protocol without key index secrecy. The communication flow is illustrated in Fig. 1. The server stores \(f\) keys, \(\mathop{\mathrm{Key}}_1, \dots, \mathop{\mathrm{Key}}_f \in \mathbb{F}_2^{2n}\), which are uniformly and independently distributed. \(\mathop{\mathrm{User}}_1\) holds a key index \(K\) and a ciphertext \(E\) corresponding to a message \(M \in \mathbb{F}_2^{2n}\), encrypted using the key \(\mathop{\mathrm{Key}}_K\), such that: \[E = M \oplus \mathop{\mathrm{Key}}_K.\] The task of this setting is the following.

Users \(\mathop{\mathrm{User}}_1\) and \(\mathop{\mathrm{User}}_2\) have access to \(n\) qubit quantum systems, \(\mathcal{H}^A_1, \dots, \mathcal{H}^A_n\) and \(\mathcal{H}^B_1, \dots, \mathcal{H}^B_n\), respectively. We define two \(n\)-qubit quantum systems as follows: \[\begin{align} \mathcal{H}^A = \mathcal{H}^A_1 \otimes \dots \otimes \mathcal{H}^A_n, \quad \mathcal{H}^B = \mathcal{H}^B_1 \otimes \dots \otimes \mathcal{H}^B_n. \end{align}\]

Although the users do not communicate directly with each other, classical and quantum communications are permitted between the users and the server. Then, our protocol is given as Protocol 2. Detailed procedure of secure decryption protocol without key index secrecy depends on the 4-tuple \((\rho_{prev}, \mathop{\mathrm{Enc}}_{user}, \mathop{\mathrm{Enc}}_{serv}, \mathop{\mathrm{Dec}})\). We call it a code for the secure blind decryption without key index.

3.2 Security conditions↩︎

We consider the following types of security condition. In the following conditions, we assume that all players make communication only at the time specified by the protocol. Also, it is assumed that the massage \(M\) is uniformly distributed.

3.3 First type of code↩︎

The first type of code is constructed as follows. The initial state \(\rho_{prev}\), the user encoder \(\mathop{\mathrm{Enc}}_{user}\), the server encoder \(\mathop{\mathrm{Enc}}_{serv}\) and the decoder \(\mathop{\mathrm{Dec}}\) defined by \[\begin{align} &m \coloneq n,\\ &\rho_{prev}\coloneq |\phi\rangle \langle \phi|^{\otimes n},\\ &\mathop{\mathrm{Enc}}_{user}(E) \coloneq W_n(E), \\ &\mathop{\mathrm{Enc}}_{serv}(K, \mathop{\mathrm{Key}}) \coloneq W_n(\mathop{\mathrm{Key}}_K), \\ &\mathop{\mathrm{Dec}} \coloneq \{\Pi_{\omega_1} \otimes \dots \otimes \Pi_{\omega_n} \mid \omega_i \in \mathbb{F}_2^2 \, (i = 1,\dots n) \}, \end{align}\] where \(\{\Pi_{\omega_i}\}\) is a POVM of the basis measurement \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) on \(\mathcal{H}_i^C \otimes \mathcal{H}_i^B\).

Then, we have the following theorem.

3.4 Proof of Theorem 1↩︎

Since \(\mathop{\mathrm{User}}_1\) sends the key index \(K\) to the server, the key-index secrecy against the server does not hold. We show other condition as follows.

3.4.1 Correctness↩︎

We prove that \(\mathop{\mathrm{User}}_2\) can obtain the correct message \(M\) after the protocol is finished, assuming that the users and the server execute Protocol 2 correctly. Let \(\rho_{user,i}\) be the state that \(\mathop{\mathrm{User}}_2\) receives on \(i\)-th composite system \(\mathcal{H}^A_i \otimes \mathcal{H}^B_i\). After Step 1, the state on \(\mathcal{H}^A_i \otimes \mathcal{H}^B_i\) that \(\mathop{\mathrm{User}}_1\) has is written as \[(\mathop{\mathrm{W}}(E_{2i-1},E_{2i}) \otimes I) \ket{\phi} = \ket{\phi_{E_{2i-1},E_{2i}}}.\] Since \[\begin{align} &\mathop{\mathrm{W}}(\mathop{\mathrm{Key}}_{K,2i-1},\mathop{\mathrm{Key}}_{K,2i})\mathop{\mathrm{W}}(E_{2i-1},E_{2i}) \notag\\ =& (-1)^{\mathop{\mathrm{Key}}_{K,2i}\cdot E_{2i-1}}\mathop{\mathrm{W}}(M_{2i-1},M_{2i}), \end{align}\] the state \(\rho_{user,i}\) is \[\begin{align} \label{eq:state1} \rho_{user,i} =& (\mathop{\mathrm{W}}(\mathop{\mathrm{Key}}_{K,2i-1},\mathop{\mathrm{Key}}_{K,2i}) \otimes I) \ket{\phi_{E_{2i-1},E_{2i}}} \!\notag\\ &\bra{\phi_{E_{2i-1},E_{2i}}}(\mathop{\mathrm{W}}(\mathop{\mathrm{Key}}_{K,2i-1},\mathop{\mathrm{Key}}_{K,2i}) \otimes I)^\dagger \\ =& \ket{\phi_{M_{2i-1},M_{2i}}}\!\bra{\phi_{M_{2i-1},M_{2i}}}. \stepcounter{equation}\end{align}\tag{5}\] This implies that the measurement outcome of the basis measurement \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) on \(\mathcal{H}^A_i \otimes \mathcal{H}^B_i\) is \((M_i,M_{2i})\) with probability 1, i.e., the relation \[\mathrm{Tr}\rho_{user,i} \ket{\phi_{k}}\!\bra{\phi_{k}} = \begin{cases} 1 & k = (M_i, M_{2i}), \\ 0 & \boldsymbol{otherwise} \end{cases}\] holds for \(k \in \mathbb{F}_2^2\). By performing similar measurements on each composite system \(\mathcal{H}^A_i \otimes \mathcal{H}^B_i\) respectively, \(\mathop{\mathrm{User}}_2\) obtains the message \(M = (M_1,M_2,\dots,\dots,M_{2n-1},M_{2n})\) with probability 1.

3.4.2 Key-and-key-index secrecy against \(\mathop{\mathrm{User}}_2\)↩︎

Assume that \(\mathop{\mathrm{User}}_2\) recovers the message \(M\) correctly. Let \(\rho_{user}(m, key,k)\) be a density matrix of the state that \(\mathop{\mathrm{User}}_2\) received when the message \(M\) is \(m\), and the key index \(K\) is \(k\), the keys \(\mathop{\mathrm{Key}}\) are \(key\). At the beginning of Step 3, the chain rule of the mutual information guarantees that \[\begin{align} I(M,K,\mathop{\mathrm{Key}};B,C)= I(M;B,C)+ I(K,\mathop{\mathrm{Key}};B,C|M). \end{align}\] Since \(\mathop{\mathrm{User}}_2\) recovers the message \(M\) correctly, \(I(M;B,C)\ge 2n\). Since the dimension of \(\mathcal{H}^B\otimes \mathcal{H}^C\) is \(2^{2n}\), \(I(M,K,\mathop{\mathrm{Key}};B,C) \le 2n\). Thus, \(I(K,\mathop{\mathrm{Key}};B,C|M)=0\), which implies the state \(\rho_{user}(m, key,k)\) does not depend on \(key,k\). This fact shows that any code satisfy key secrecy in this protocol. Further, \(\mathop{\mathrm{User}}_2\) has no information for the key index \(K\) as well as the keys \(\mathop{\mathrm{Key}}\). In this derivation, we assume only the no-communication condition between the users for \(\mathop{\mathrm{User}}_1\). That is, even when \(\mathop{\mathrm{User}}_1\) does not follow the protocol with no communication with \(\mathop{\mathrm{User}}_2\), the above analysis holds.

3.4.3 Message secrecy against the server:↩︎

Assuming that the users execute the protocol correctly, we prove that the message \(M\) is secure from the server regardless of whether the server runs the protocol correctly. In step. 3, the server obtains the maximally entangled state on \(\mathcal{H}^A_i\,(i=1,\dots,n)\). That is, the state on each \(\mathcal{H}^A_i \, (i=1,\dots,n)\) obtained by the server through the protocol is \[\rho_{serv,i} = \mathrm{Tr}_B \ket{\phi_{E_i,E_{2i}}} \bra{\phi_{E_i,E_{2i}}} = \frac{1}{2} I.\] This implies that the entire state \(\rho_{serv}(M,K)\) that the server receives is \(\rho_{serv}(M, K) = \frac{1}{2^n}I\) and the relation \[\rho_{serv}(j,K) = \rho_{serv}(l,K) \quad \forall j,l \in \mathbb{F}_2^{2n}\] holds. Therefore, we have proved the message secrecy defined by 4 .

3.5 Second type of code↩︎

The second type of code is constructed as follows. We construct our code only when \(n\) is an integer times of \(f\). The initial state \(\rho_{prev}\), the user encoder \(\mathop{\mathrm{Enc}}_{user}\), and the server encoder \(\mathop{\mathrm{Enc}}_{serv}\) defined by \[\begin{align} &m \coloneq \frac{n}{f}-1 ,\\ &\rho_{prev}\coloneq |\phi\rangle \langle \phi|^{\otimes n},\\ &\mathop{\mathrm{Enc}}_{user}(E) \\ &\coloneq id^{\otimes (m+1)(K-1)} \otimes W(1,0)\otimes W_m(E) \otimes id^{\otimes (m+1)(f-K)}, \\ &\mathop{\mathrm{Enc}}_{serv}(\mathop{\mathrm{Key}}) \coloneq W_{m+1}(\mathop{\mathrm{Key}}_1)\otimes \cdots \otimes, W_{m+1}(\mathop{\mathrm{Key}}_f) \end{align}\] The decoder \(\mathop{\mathrm{Dec}}\) is determined as follows. First, \(\mathop{\mathrm{User}}_2\) applies the following measurement. \[\begin{align} \{ \Pi_{\omega_1} \otimes \dots \otimes \Pi_{\omega_n} \mid \omega_i \in \mathbb{F}_2^2 \, (i = 1,\dots n) \}, \end{align}\] where \(\{\Pi_{\omega_i}\}\) is a POVM of the basis measurement \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) on \(\mathcal{H}_i^C \otimes \mathcal{H}_i^B\). \(\mathop{\mathrm{User}}_2\) finds an element \(k\) such that \(\omega_{(m+1)(k-1)+1}=(1,0)\). \(\mathop{\mathrm{User}}_2\) sets the outcome to be \(\omega_{(m+1)(k-1)+2}, \ldots, \omega_{(m+1)k}\).

From the above construction, we can easily find the following lemma.

3.6 No go theorem↩︎

4 Two-server protocol↩︎

In the previous section, Protocol 2 permits the server to access the key index \(K\) held by \(\mathop{\mathrm{User}}_1\). If the ciphertext \(E\) is leaked for any reason, there is a security risk because the server could decrypt the leaked \(E\) using the key \(\mathop{\mathrm{Key}}_K\) and retrieve the message \(M\). To mitigate this risk, we propose the concept of key index secrecy, which prevents a server from obtaining the message from the leaked encrypted ciphertext. That is, we propose a new communication task, two-server protocol. It is important to note that this task requires the secrecy of the key index in addition to other types of secrecy.

4.1 Definition of protocol↩︎

The protocol for two-server protocol is defined as follows. The communication flow and procedure for this protocol are described in Fig 3. This protocol involves two users, \(\mathop{\mathrm{User}}_1\) and \(\mathop{\mathrm{User}}_2\), and two servers, \(\mathop{\mathrm{Serv}}_1\) and \(\mathop{\mathrm{Serv}}_2\). The servers, \(\mathop{\mathrm{Serv}}_1\) and \(\mathop{\mathrm{Serv}}_2\), store \(f\) keys, \(\mathop{\mathrm{Key}}_1, \dots, \mathop{\mathrm{Key}}_f \in \mathbb{F}_2^{2n}\). These keys are assumed to be uniformly and independently distributed. \(\mathop{\mathrm{User}}_1\) possesses a key index \(K\) and a ciphertext \(E\) encrypted using the key \(\mathop{\mathrm{Key}}_K\), such that \(E = M \oplus \mathop{\mathrm{Key}}_K\). Additionally, \(\mathop{\mathrm{User}}_1\) has access to \(2n\) quantum systems, \(\mathcal{H}^A_i, \mathcal{H}^B_i , (i = 1, \dots, n)\), and \(n\) maximally entangled states \(\ket{\phi}^i \in \mathcal{S}(\mathcal{H}^A_i \otimes \mathcal{H}^B_i) , (i = 1, \dots, n)\). We introduce the following abbreviations for the composite systems: \(\mathcal{H}^A \coloneq \mathcal{H}^A_1 \otimes \dots \otimes \mathcal{H}^A_n, \, \mathcal{H}^B \coloneq \mathcal{H}^B_1 \otimes \dots \otimes \mathcal{H}^B_n\). Then, our protocol is given as Protocol 4.

The detail procedure of Protocol 4 is determined by a 4-tuple \((\mathop{\mathrm{Enc}}_{user}, \mathop{\mathrm{Enc}}_{serv_1}, \mathop{\mathrm{Enc}}_{serv_2}, \mathop{\mathrm{Dec}})\). Hence, we call this 4-tuple a code and denote it by \(\Phi_{2n}\).

4.2 Security condition↩︎

We consider the following types of security condition. In the following conditions, we assume that all players make communication only at the time specified by the protocol. Also, it is assumed that the massage \(M\) is uniformly distributed. The correctness, the message-and-key secrecy against \(\mathop{\mathrm{User}}_1\), and the key-and-key-index secrecy against \(\mathop{\mathrm{User}}_2\) are defined in the same way as in Protocol 2. The message secrecy against the servers and the key-index secrecy against the servers are defined as follows.

Also, we define the quantities, the upload cost, the download cost, and the rate of a code \(\Phi_{2n} = (\rho_{prev}, \mathop{\mathrm{Enc}}_{user}, \mathop{\mathrm{Enc}}_{serv}, \mathop{\mathrm{Dec}})\), by \[\begin{align} U(\Phi_{2n}) &\coloneq \sum_{t=1}^2 \log_2 |Q_t|, \\ D(\Phi_{2n}) &\coloneq \sum_{t=1}^2 \log_2 \dim \mathcal{A}^t, \\ R(\Phi_{2n}) &\coloneq \frac{2n}{D(\Phi_{2n})}. \end{align}\]

4.3 Construction of our code↩︎

We construct the concrete code for secure blind decryption protocol with key index secrecy. Our code is inspired by the idea of quantum symmetric private information retrieval (QSPIR) protocol with two servers given in [8]. First, the state \(\rho_{E,K}\) is defined as \[\rho_{E,K}= \mathop{\mathrm{W}}_n(E)|\phi\rangle \langle \phi|^{\otimes n} \mathop{\mathrm{W}}_n(E)^\dagger.\] Then, let \(R\) be a randomly chosen subset of \(\{1, \dots, f\}\) and we prepare \(Q_1\) and \(Q_2\) as follows. \[\label{eq:query} \begin{align} Q_1 &= R, \\ Q_2 &= \begin{cases} Q_1 \setminus \{K\} & \boldsymbol{if} \quad K \in Q_1 \\ Q_1 \cup \{K\} & \boldsymbol{otherwise}. \end{cases} \end{align}\tag{6}\] The server encoders and the decoder is \[\begin{align} & \mathop{\mathrm{Enc}}_{serv_1}(Q_1, \mathop{\mathrm{Key}}) \coloneq W_n(C^A), \quad C^A = \bigoplus_{i \in Q_1} \mathop{\mathrm{Key}}_i, \\ & \mathop{\mathrm{Enc}}_{serv_2}(Q_2, \mathop{\mathrm{Key}}) \coloneq W_n(C^B), \quad C^B = \bigoplus_{i \in Q_2} \mathop{\mathrm{Key}}_i, \\ & \mathop{\mathrm{Dec}}\coloneq \{\Pi_{\omega_1} \otimes \dots \otimes \Pi_{\omega_n} \mid \omega_i \in \mathbb{F}_2^2 \, (i = 1,\dots n) \}, \end{align}\] where \(\{\Pi_{\omega_i}\}\) is a POVM of the basis measurement \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) on \(\mathcal{H}_i^C \otimes \mathcal{H}_i^B\).

Then, we have the following theorem.

4.4 Proof of Theorem 4↩︎

4.4.1 Correctness↩︎

We prove that \(\mathop{\mathrm{User}}_2\) can obtain the desired message \(M\) when all the users and servers execute the protocol correctly. At the step 1, \(\mathop{\mathrm{User}}_1\) set the initial state on the \(i\)-th two-qubit system \(\tilde{\mathcal{A}}^1_i \otimes \tilde{\mathcal{A}}^2_i\) to be the state \(\ket{\phi_{{E_i},{E_{2i}}}}\). Then, since the message \(M\) has the relation \(M = E \oplus \mathop{\mathrm{Key}}_K\) and queries satisfy \(C^A \oplus C^B = \mathop{\mathrm{Key}}_K\), the state \(\rho_{user,i}\) on the \(i\)-th two-qubit system \(\mathcal{A}^1_i \otimes \mathcal{A}^2_i\) at the beginning of Step 3 is described as \[\begin{align} \label{eq:state2} &\rho_{user,i}\notag\\ =& (\mathop{\mathrm{W}}(C^A_i,C^A_{2i}) \otimes \mathop{\mathrm{W}}(C^B_i,C^B_{2i})) \notag\\ &\ket{\phi_{E_i,E_{2i}}} \bra{\phi_{E_i,E_{2i}}} (\mathop{\mathrm{W}}(C^A_i,C^A_{2i})^\dagger \otimes \mathop{\mathrm{W}}(C^B_i,C^B_{2i})^\dagger) \\ =& \ket{\phi_{E_i \oplus C^A_i \oplus C^B_i, E_{2i} \oplus C^A_{2i} \oplus C^B_{2i}}}\notag \\ &\bra{\phi_{E_i \oplus C^A_i \oplus C^B_i, E_{2i} \oplus C^A_{2i} \oplus C^B_{2i}}} \\ =& \ket{\phi_{M_i,M_{2i}}}\!\bra{\phi_{M_i,M_{2i}}}. \stepcounter{equation}\end{align}\tag{7}\] Therefore \(\mathop{\mathrm{User}}_2\) obtains the message \(M\) with probability 1 by the basis measurement \(\{\ket{\phi_{00}},\ket{\phi_{01}},\ket{\phi_{10}},\ket{\phi_{11}}\}\) on \(\mathcal{A}^1_i \otimes \mathcal{A}^2_i\), respectively.

4.4.2 Key-and-key-index secrecy against \(\mathop{\mathrm{User}}_2\)↩︎

Since the dimension of \(\mathop{\mathrm{User}}_2\) receives is \(2^{2n}\), in the same way as Subsection 3.4.2, we can show that any code of Protocol 4 satisfies the sever secrecy by using the chain rule of quantum mutual information.

4.4.3 Message secrecy against the servers↩︎

Assuming that the users follow the protocol, we prove that the message \(M\) is secure against the servers even if they do not execute it correctly. In Step 3, \(t\)-th server \(\mathop{\mathrm{Serv}}_t\) obtains only the system \(\tilde{\mathcal{A}}^t\) which is one side of the composite system of the maximally entangled state. Hence, when the message is \(M\) and the key index is \(K\), \(\mathop{\mathrm{Serv}}_t\) receives the following state \(\rho_{serv_t}(M, K)\) in Step 2; \[\rho_{serv_t}(M,K) = \frac{1}{2^n} I.\] Therefore, the following relation holds for \(\mathop{\mathrm{Serv}}_t\) with \(t=1,2\); \[\rho_{serv_t}(j,K) = \rho_{serv_t}(l,K) \quad \forall j,l \in \mathbb{F}_2^{2n},\] which shows the message secrecy against the servers.

4.4.4 Key-index secrecy against the servers↩︎

Assuming that the users run the protocol correctly, we prove that the servers obtains no information about the key index \(K\). Since the queries \(Q_1\) and \(Q_2\) are constructed randomly, they are independent from \(K\). That is, the condition \[I(K;Q_1) = I(K;Q_2) = 0\] holds. Therefore, we find that the code has the key-index secrecy against the servers.

5 Secrecy under the post-specious-attack model↩︎

In this section, we highlight the advantage of quantum two-server protocol over its classical counterpart under post-attack scenarios. Specifically, we define the concept of a post-attack and examine the classical version of Protocol 4. Subsequently, we compare the classical and quantum versions in the context of post-attack situations.

5.1 Definition of the post-specious-attack model↩︎

In quantum blind decryption with key index secrecy, there are two potential risks that may arise after the completion of the protocol. The first risk is that a server obtains the encrypted ciphertext. The second risk is that the servers communicate with each other. If both risks are realized, the servers can obtain the message because their communication enables them to identify the key index. However, these risks occur independently, and thus the likelihood of both occurring simultaneously is relatively low. It is therefore prudent to prepare for scenarios in which only one of these risks occurs.

We have already analyzed the secrecy of the message in the event of the first risk. This section focuses on the second risk, i.e., the scenario where the two servers may communicate with each other after the protocol’s completion if they act dishonestly. In this case, deviations from the prescribed operations during the protocol could enable the servers to infer the message. We now consider the scenario where the servers’ behavior is specious [9], which is explained as follows: The servers’ operations during the protocol may deviate from the correct operations, yet the information obtained by the users remains indistinguishable from the case where the servers strictly adhere to the protocol. When the servers engage in specious behavior during the protocol and subsequently communicate with each other after its completion, we refer to this scenario as a post-specious-attack. Since the discussion in the previous section does not address this type of attack, it is essential to analyze the message secrecy under post-specious-attacks. To formalize this concept, we define a post-specious-attack as follows:

The following points clarify the rationale behind this definition:

• Conditions PS1 and PS2: During the protocol, the servers are monitored by users and, therefore, cannot communicate with each other. However, after the protocol’s completion, user monitoring ceases, making communication between servers plausible.

• Condition PS3: By choosing the local memory system \({\cal H}{L(j)}\) to be sufficiently large, the local operation can always be expressed as a unitary operation \(U_j\), with the initial state on \({\cal H}{L(j)}\) being a pure state \(\rho_j\).

• Condition PS4: To avoid detection, the servers’ attacks are restricted to specious attacks.

5.2 Secrecy discussion↩︎

Under this definition, we establish the following theorem:

6 Classical version of secure blind decryption↩︎

6.1 Classical version without key index secrecy↩︎

The classical version of one-server protocol can be implemented by using Shannon’s one time pad key \(R\) shared between two users as follows. \(\mathop{\mathrm{User}}_1\) sends the modulo sum \(X=R \oplus E\) of the random number \(R\) and the encrypted ciphertext \(E= \mathop{\mathrm{Key}}_K \oplus M\) and and the key index \(K\) to the server. The server calculates \(Y= \mathop{\mathrm{Key}}_K\oplus X\) and sends it to \(\mathop{\mathrm{User}}_2\). \(\mathop{\mathrm{User}}_2\) obtains the message by \(R \oplus Y=R \oplus \mathop{\mathrm{Key}}_K\oplus R \oplus \mathop{\mathrm{Key}}_K \oplus M=M\).

The correctness and the message secrecy are trivial. The key secrecy can be shown as follows. Assume that \(\mathop{\mathrm{User}}_1\) and the server honest. \(\mathop{\mathrm{User}}_2\)’s information is \(M\) and \(R\). Since \(R\) is independent of \(\mathop{\mathrm{Key}}\), the key secrecy holds. However, the classical version with key index secrecy is more complicated.

6.2 Definition of classical protocol with key index secrecy↩︎

When the users and servers can only use classical computation and communication in the secure blind decryption protocol, we say that the protocol is classical. The formal definition of the classical secure blind decryption protocol with key index secrecy is shown below. \(\mathop{\mathrm{User}}_1\) has the classical system \(A,B = \mathbb{F}_2^n\) and the servers \(\mathop{\mathrm{Serv}}_1\) and \(\mathop{\mathrm{Serv}}_2\) possess the classical system \(A',B' = \mathbb{F}_2^n\), respectively. The servers and the users are allowed to communicate with each other, but the servers cannot communicate with each other. A protocol for classical two-server protocol is defined as Protocol 5.

For this protocol, we define the correctness, the message secrecy, the sever secrecy, and the key index secrecy in the same way as Protocol 4. The concrete form of Protocol 5 is determined by a \(4\)-tuple \((\mathop{\mathrm{Enc}}_{\mathop{\mathrm{User}}},\mathop{\mathrm{Enc}}_{\mathop{\mathrm{Serv}}_1},\mathop{\mathrm{Enc}}_{\mathop{\mathrm{Serv}}_2}, \mathop{\mathrm{Dec}})\), which is called a code \(\Phi_{n,c}\).

6.3 Construction of our code with two servers↩︎

We consider the following code a \(4\)-tuple \((\mathop{\mathrm{Enc}}_{\mathop{\mathrm{User}}},\mathop{\mathrm{Enc}}_{\mathop{\mathrm{Serv}}_1},\mathop{\mathrm{Enc}}_{\mathop{\mathrm{Serv}}_2}, \mathop{\mathrm{Dec}})\). Assume that \(R_1\) is composed of uniform random numbers \(R_{1,1}\in \mathbb{F}_2^n\) and \(R_{1,2}\in \mathbb{F}_2^f\). We define \((X_1, X_2, Q_1, Q_2) \coloneq \mathop{\mathrm{Enc}}_{\mathop{\mathrm{User}}} (E,K,R_1)\) as \[\begin{align} X_1:= R_{1,1}, \quad X_2:= E\oplus R_{1,1}, \quad Q_1:= R_{1,2} \end{align}\] and \[\begin{align} Q_{2,j}:= \left\{ \begin{array}{ll} Q_{1,j} \oplus 1 &whenj=K \\ Q_{1,j} &whenj \neq K . \end{array} \right. \end{align}\] Then, we define \(g_t \coloneq \mathop{\mathrm{Enc}}_{\mathop{\mathrm{Serv}}_t} (Q_t,Key)\) and \(\mathop{\mathrm{Dec}}\) as \[\begin{align} g_t(X_t) &:=\Big(\bigoplus_{j=1}^f Q_{t,j} \mathop{\mathrm{Key}}_j\Big)\oplus X_t \\ \mathop{\mathrm{Dec}}(X_1', X_2')&:=X_1'\oplus X_2'. \end{align}\]

6.4 Analysis of our code with key index secrecy↩︎

We show the following theorem in this section.

6.5 Classical version of post-specious-attack model↩︎

Next, we define the classical version of the post-specious-attack model. We model the classical post-attack as follows, using the same symbols as in Protocol 2:

Under the above definition, we establish the following lemma:

In the classical case, we do not use the term “specious" because Definition 2 prohibits the servers from deviating from the prescribed procedure. As demonstrated in Lemma 7, even when the servers strictly follow the protocol, they can still succeed the post-attack. Thus, if the servers are allowed to communicate with each other after the protocol’s completion, they do not need to employ a specious attack to extract information. This is why the concept of a post-specious-attack model is not introduced for classical protocols.

Theorem 5 and Lemma 7 collectively highlight the superiority of the quantum secure blind decryption protocol over its classical counterpart under the post-attack model.

7 Conclusion↩︎

We have proposed two types of new protocols for quantum secure blind decryption and constructed codes to realize these protocols. This paper presents three main results: The first and second results are the proposals of protocols for the two newly introduced quantum tasks, quantum secure blind decryption without/with key index secrecy. The first protocol ensures both user and key secrecy. The second protocol extends this security by incorporating the key index secrecy. We have formally defined these protocols and their associated secrecy requirements and have constructed concrete codes to achieve them. As the third result, we have demonstrated that our second protocol satisfies secrecy against post-specious attacks, whereas its classical counterpart does not.

We note that both codes for both protocols achieve the optimal transmission rate, as follows: The upper bound of the transmission rate for the first protocol is derived by considering the entanglement-assisted channel [10]–[12]. For the second protocol, the upper bound is determined by analyzing the channel between the two servers and \(\mathop{\mathrm{User}}_2\). In both cases, the transmission rates of our codes match these upper bounds.

Finally, we explain the relation with quantum symmetric private information retrieval (QSPIR), which is a similar task to quantum two-server protocol. Here, we highlight the differences between the two tasks. Private information retrieval (PIR) [13], [14] allows a user to retrieve a file from a database stored by servers, such that the server learns no information about the file index. SPIR extends PIR by ensuring that the user gains no information about other files. Quantum extensions of SPIR, such as quantum symmetric PIR (QSPIR), have been studied in [8], [15], [16].

While the second setting, quantum two-server protocol shares similarities with QSPIR, simply applying QSPIR to the transmission of the key used for the encryption is insufficient due to the following reason. In this case, \(\mathop{\mathrm{User}}_2\) will obtain the key used for the encryption. However, quantum two-server protocol requires the secrecy of the key used for the encryption. Hence, this application of QSPIR does not work for quantum secure blind decryption with the index secrecy.

There are several future studies.

References↩︎