# Post-Quantum Cheating Detectable Private Information Retrieval

Lin Zhu, Changlu Lin, Fuchun Lin, Liang Feng Zhang

► To cite this version:

Lin Zhu, Changlu Lin, Fuchun Lin, Liang Feng Zhang. Post-Quantum Cheating Detectable Private Information Retrieval. 37th IFIP International Conference on ICT Systems Security and Privacy Protection (SEC), Jun 2022, Copenhagen, Denmark. pp.431-448, 10.1007/978-3-031-06975-8_25 hal-05319920

HAL Id: hal-05319920

https://inria.hal.science/hal-05319920v1

Submitted on 17 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Post-Quantum Cheating Detectable
Private Information Retrieval

Lin Zhu<fnref n="1" />, Changlu Lin<fnref n="2" />, Fuchun Lin<fnref n="3" />(✉), and Liang Feng Zhang<fnref n="1" />

flin@ic.ac.uk

**Abstract.** Private Information Retrieval (PIR) allows a user to privately retrieve any item from a database such that the server(s) holding the database cannot learn any information about the user's choice. Most existing PIR protocols focus on minimizing the communication cost for retrieving one bit from the database, in an honest-but-curious server model. Dishonest servers were studied in an ad-hoc fashion including the robust PIR and verifiable PIR for cheater identification, where the former further guarantees error correction but only works when the number of dishonest servers are bounded and the latter works for any number of dishonest servers but has to rely on the intractability assumption of certain computational hard problems and a tag published by the honest data owner. We initiate a systematic study of the fundamental problem of cheating detection for PIR (cd-PIR). We first show a theoretic result that rules out the possibility of information-theoretically secure cd-PIR against arbitrary number of cheaters (even allowing the data owner to publish a tag and lifting cheater identification), which justifies our study of computational cd-PIR. On the positive side, we show that computational cd-PIR against arbitrary number of cheaters can be achieved much more efficiently than all previous constructions and with weaker cryptography hardness assumptions. In particular, we obtain efficient cheating detection for PIR with more than one server that resists quantum algorithm for the first time.

**Keywords:** PIR · Cheating detection · Merkle tree · Verifiability

# 1 Introduction

Private information retrieval (PIR) allows a user to retrieve an item $x_i$ from a database $x = (x_0, x_1, \dots, x_{n-1})$ such that the server/servers storing the database cannot gain any information about the user's choice of $\{0, 1, \dots, n-1\}$. It is a fundamental privacy-preserving primitive in cryptography and has applications in many systems such as friend discovery [23], publish-subscribe [6], private media browsing [14], private messaging [3,25], privacy preserving ad targeting [12,17], certificate transparency [21], online anonymity [20,22], and location-based services for smartphones [18,31].

<footnote n="1">¹ ShanghaiTech University, Shanghai, China</footnote>

<footnote n="2">² Fujian Normal University, Fujian, China</footnote>

<footnote n="3">³ Imperial College London, London, UK</footnote>
The notion of PIR was introduced by Chor, Goldreich, Kushilevitz and Sudan [7]. In a trivial PIR protocol, the user may simply download the entire database and then locally extract the item of his/her interest. Although the protocol achieves perfect secrecy, it incurs a prohibitive communication complexity of $O(n)$. In general, the communication complexity of a PIR protocol is the total number of bits that have to be exchanged by the user, for the sake of retrieving one bit from the database. Reducing the communication complexity has been the most challenging problem in PIR-related research. Chor et al. [7] showed that if there is only one server and perfect secrecy is needed, then $O(n)$ communication is unavoidable. In order to have a protocol with $o(n)$ communication complexity, we have to work in a multi-server information-theoretic setting [9, 10, 32], where the user's index $i$ is still perfectly secret as long as the servers do not collude, or in a single-server computational setting [5, 19], where the secrecy of $i$ is based on cryptographic assumptions. In particular, the communication complexity of the best protocols in both settings can be as small as $\exp(O(\sqrt{\log n \log \log n}))$ (using two servers) [9] and $O(\log n)$, respectively.

Most of the existing PIR protocols consider only honest-but-curious servers, which strictly follow the protocols' specifications. A dishonest server may arbitrarily deviate from the protocols and thus cause the user to output a wrong value of the retrieved database item. In fact, it has been an interesting and challenging problem to design PIR protocols that allow the user to detect a wrong output. Such protocols have particular interest in the modern age of cloud computing because they allow the PIR servers to be implemented by the untrustworthy cloud services, i.e., outsource the PIR servers' computations to the cloud. The multi-server robust PIR (RPIR) protocols of [4, 8, 11] allow the user to reconstruct the correct value of $x_i$, even if some of the Byzantine servers (called cheaters) [8] provide wrong answers. These protocols provide information-theoretic security of error correction and cheater identification (so that cheaters can be avoided in the future) by using error-correcting techniques, but the number of cheaters tolerated must be bounded. For a "t-private $\tau$-Byzantine robust $k$-out-of-$\ell$ PIR", there exists a protocol that will always output to the client the unique correct block (called unique decoding) if $\tau \le t < k/3$; and there exists a protocol that will always output to the client a small number of blocks including the correct block (called list decoding) if $t < k$ and $\tau < k - t - 1$.

The verifiable PIR (VPIR) protocols of [29, 33] are constructed either in the multi-server model or the single-server model such that any number of servers providing wrong answers will be detected and identified (but there is no guarantee of recovering the correct block, or even a small list containing it). These protocols have communication complexities that are comparable to the best known protocols in an honest-but-curious server model and allow all servers to be Byzantine. Different from RPIR, where the robustness does not rely on computational assumptions, the VPIR assumes the hardness of certain computational problems, and more importantly, the data owner who is supposed to be honest must publish a short tag (similar as in the PIR-Tor [20]) that can be used by the user for verifying the servers.
Allowing all the servers to be Byzantine make the model one big step closer to being practical and cheater identification seems no much weaker than error correction (one could exclude the cheaters and run a basic PIR with remaining honest servers if there are enough number of honest servers). Nevertheless, the multi-server VPIR constructed in [33] relies on the strong Bilinear Diffie-Hellman (SBDH) assumption, which is no longer true in front of quantum attacks [16, 24], and it is not known if SBDH can be replaced by any post-quantum assumptions. On the other hand, the VPIR protocol of [29] is based on latticed-related cryptographic assumptions, which is post-quantum secure. But it is not clear if the construction can be efficiently extended to more than one party. Another drawback of these protocols is that to facilitate cheater identification, both the user and servers in these protocols have to do a lot of public-key operations such as pairing computations and lattice-related computations. For example, in the VPIR protocols of [29, 33], the user has to take thousands of seconds to retrieve an item from a database of 1G bits.

It can be argued that identification of cheating servers may be overly strong in many scenarios, such as private media browsing [14], where a large database of movies is stored on several non-Byzantine servers and the client hides its media diet by using PIR to retrieve a movie. In such scenarios, it may suffice for the client to detect the existence of wrong responses (or cheating servers) and then refuse to pay for the browsing. It is then an interesting problem to consider the relaxed security requirement of detecting the existence of wrong responses (or cheating servers) in exchange for obtain significant improvements of efficiency and weaker hardness assumptions. Given the recent trend of reducing the computational cost of PIR, it may be more appealing to obtain PIR protocols that have both relaxed security and better efficiency than the protocols that have overly strong security but very poor efficiency. On the other hand, given that the quantum computing is making great strides [15, 26], the rule of thumb in designing cryptographic protocol is to avoid basing the security on assumptions that are vulnerable in the face of a quantum computer. There have been two well-performed quantum algorithms that can solve the problem of integer factorization (by Shor's algorithm [28]) and elliptic curve encryption algorithm (by Grover's algorithm [13]), respectively. Note that cheating detection is equivalent to cheater identification in single server special case and hence [29] already gives a post-quantum tampering detection protocol. It is not known if one can realize post-quantum tampering detection for the high-performing PIR protocols for more than one server.

## 1.1 Our Contributions

We initiate a systematic study of the fundamental problem of cheating detection for PIR. In this work, we aim at providing practical solutions that assumes the existence of dishonest servers, which captures real-life adversary. We note that investigating what is the minimum number of honest servers required for enabling cheating detection in a *t*-private *τ*-Byzantine robust *k*-out-of-*ℓ* PIR is an interesting theoretic open question.
We begin with showing negative results on cheating detection for PIR against arbitrary number of Byzantine servers. Our negative results consist of two arguments of different flavours (see the beginning of Sect. 3 for details).

The first negative result rules out the possibility of cheating detection for PIR against arbitrary number of Byzantine servers in the setting without the involvement of the data owner, who is supposed to be honest and publishes a tag of the database for verification. This is shown by relating PIR to secure Multi-Party Computation (MPC) (PIR can be seen as a weaker form of MPC where only the privacy of the user is required). In the case that no tag of the database is published by the data owner, we can consider a variant that we dub *data-private PIR*, where the privacy of the database of the servers are also required instead of only the privacy of the input of the user. It can be observed that data-private PIR is equivalent to secure MPC against passive adversary (no information is revealed to a participant in the computation beyond that can be inferred from the participant's input and output). We then argue that the robustness of secure MPC against active adversary (by definition must allow input substitution of corrupt servers) renders cheating detection for data-private PIR against arbitrary number of Byzantine servers impossible. The impossibility result holds for both information-theoretic security and computational security, which makes it necessary for one to involve the data owner and his/her tag.

Our second negative result only holds when one imposes information-theoretic security. We argue that if the mapping from database to its tag is not injective, then there exist two distinct databases that are mapped to the same tag value. In this case, when one of the two databases is the database of the data owner, the servers can replace it with the other database and execute the protocol honestly after the substitution of the database. Since the correctness of the protocol guarantees that for any choice of database, honest execution should always lead to acceptance of the retrieved block by the user, we conclude that this substitution attack is not detectable at least for one block index. This argument leaves us with the only possible information-theoretic cheating detection PIR, whose tag must be as long as the database. But in that case, the user could as well download the original database (locally retrieve the desired block) and circumvent running the protocol by downloading the tag and communicate with the servers before verifying against the tag.

The above two negative results justify our following cheating detectable PIR (cd-PIR) model. Intuitively, we want to achieve cheating detection that is resistant to quantum attacks at the cost of communicating a small amount of verification information (logarithmic in $n$, the number of items) and conducting an efficient verification taking no more time than the query. Moreover, it is of practical importance that the protocol should come with a communicational low-cost update algorithm that allows the data owner to modify a specific item while maintaining the cheating detection capability.

**cd-PIR Model.** For any integer $k \ge 1$, our $k$-server cd-PIR model consists of a *database owner* who has a database $x = (x_0, x_1, \dots, x_{n-1})$ of $n$ items, a *user* who wants to retrieve an item $x_i$ of the database, and $k$ servers $S_1, S_2, \dots, S_k$.
The database owner prepares both a public encoding $X$ of the database and a public tag Tag for verification. Each server keeps an identical copy of the encoding $X$. To retrieve $x_i$, the user may use Tag to convert its retrieval index $i \in \mathbb{Z}_n$ to $k$ queries $\{q_j\}_{j=1}^k$ and possibly a private auxiliary information aux for reconstruction. For every $j \in [k]$, the server $S_j$ uses $(X, q_j)$ to generate an answer $a_j$ to the user. Finally, the user makes use of $(\text{Tag}, i, \text{aux}, \{a_j\}_{j=1}^k)$ to locally reconstruct and verify the value of $x_i$. As a useful extension, we also include an update algorithm in the model that allows the database owner to dynamically update the value of any database item with $(\text{Tag}, X)$. A cd-PIR protocol is said to be *t-private* if any $t$ of the $k$ servers cannot learn the user's index $i$. For $k > 1$ and $k = 1$, we consider information-theoretic and computational privacy, respectively. A cd-PIR protocol is said to be *secure* (i.e., cheating detectable) against active adversary if the user is able to detect the existence of wrong server answers, even when all servers are Byzantine servers.

<figure><img src="image_3.png" /><figcaption>Fig. 1. PIR model</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. cd-PIR model</figcaption></figure>

The PIR model and cd-PIR model can be depicted by the Fig. 1 and Fig. 2. Following the standard PIR literature, the communication complexity $\mathbb{C}\mathbb{C}_{\Gamma}(n)$ of a cd-PIR protocol $\Gamma$ will be defined as $\sum_{j=1}^k (|q_j| + |a_j|)$, maximized over all possible choices of $x, i$ and underlying randomness.

**Merkle Tree-Based Transformation.** In this paper, we propose a method of using Merkle tree to transform PIR into cd-PIR. Specifically, if we are given a $k$-server PIR protocol $\Pi$ with communication complexity $\mathbb{C}\mathbb{C}_{\Pi}(n)$, then the transformation will give a $k$-server cd-PIR protocol $\Gamma$ with $\mathbb{C}\mathbb{C}_{\Gamma}(n) = 2\mathbb{C}\mathbb{C}_{\Pi}(n) + \sum_{\ell=1}^{\log n-1} \mathbb{C}\mathbb{C}_{\Pi}(n/2^{\ell})$, where $w$ is the length of the digests under a hash $H$ and $H$ is used for constructing a Merkle tree encoding of the database $x$. If the underlying PIR protocol $\Pi$ is *t*-private, then the cd-PIR protocol will be *t*-private as well. As long as $H$ is collision-resistant, the cd-PIR protocol $\Gamma$ will be secure such that a user will never output a wrong value (see Definition 4 for details). As cryptographic hash functions are believed better immune to quantum attacks [1], our protocols are post-quantum secure.
By instantiating with the SHA-256 and applying the Merkle tree-based transformation to [2,30], we obtain both a 2-server cd-PIR protocol $\Gamma_{WY}$ with communication complexity $O(n^{1/3})$ and a single-server cd-PIR protocol $\Gamma_{SL}$ with communication complexity $O(Nd[\sqrt[4]{n}/N])$. See the following Table 1 for a comparison between VPIR and our cd-PIR protocols in terms of quantum resistance and communication complexity.

<table><caption>**Table 1.** Comparison between VPIR and cd-PIR protocols</caption><thead><tr><th>Protocol</th><th></th><th>Post-quantum</th><th>Communication complexity</th></tr></thead><tbody><tr><td rowspan="2">Multi-server</td><td>$\Gamma_{WY}^a$</td><td>✓</td><td>$O(2^{\lfloor \log n \rfloor / \lfloor \frac{2k-1}{t} \rfloor})$</td></tr><tr><td>$\Gamma_{ZSN}$ [33]</td><td>×</td><td>$O(2^{\lfloor \log n \rfloor / \lfloor \frac{2k-1}{t} \rfloor})$</td></tr><tr><td rowspan="2">Single-server</td><td>$\Gamma_{SL}$</td><td>✓</td><td>$O(Nd[\sqrt[4]{n}/N])$</td></tr><tr><td>$\Gamma_{WZ}$ [29]</td><td>✓</td><td>$\Theta(c \cdot \text{poly}(n) \cdot \log n)$</td></tr></tbody></table>

The 2-server protocol $\Gamma_{ZSN}$ in [33] achieves the unconditional 1-privacy and computational security, under the strong Bilinear Diffie-Hellman (SBDH) assumption. Our 2-server protocol has comparable communication cost with [33] and is computationally much more efficient. In the cd-PIR protocol $\Gamma_{WY}$, the user spends less than 1.2s to retrieve an item from a 1G bits database, which gains significant practical improvement compared with [33].

The single-server protocol $\Gamma_{WZ}$ in [29] is based on the LWE with binary errors. It is computationally private and secure, and the communication complexity is $CC_{\Gamma_{WZ}}(n) = \Theta(c \cdot \text{poly}(n) \cdot \log n)$. Our single-server cd-PIR protocol $\Gamma_{SL}$ requires strictly less communication than that. The user in $\Gamma_{SL}$ only spends about 0.044s retrieving the data from a 1G bits database, more than 28000 times less than $\Gamma_{WZ}$. Furthermore, the computation time of user of increases very slightly, whereas that in $\Gamma_{WZ}$ grows almost twice as fast. The computer time of the server of $\Gamma_{SL}$ is also very small, but as the computation time of the server in $\Gamma_{WZ}$ is too long to show, we do not make more comparisons.

## 1.2 Our Techniques

A Merkle tree (see Fig. 3) is a binary tree such that the value of every internal node is the hash value of its two children. It allows a prover to convince a verifier of the value of any leaf node $i$. In particular, the prover only needs to provide the values of the nodes along the *authentication path* of $i$, where the authentication path consists of the siblings of all nodes on the path from $i$ to the root. In our transformation, a collision-resistant hash function $H: \{0, 1\}^* \rightarrow \{0, 1\}^w$ will be chosen, which maps two siblings to their parent (e.g., $H(\cdot|\cdot) \in \{0, 1\}^w$). The owner of a database $x = (x_0, x_1, \dots, x_{n-1})$ will construct a Merkle tree $X$ out of $(H, x)$ such that the $n$ data items $x_0, x_1, \dots, x_{n-1}$ are sequentially taken as $n$ leaf nodes of $X$ and values of other $\lfloor \log n \rfloor$ levels are hash values. The value

<footnote>a Set $(k, t) = (2, 1)$ in $\Gamma_{WY}$</footnote>
of the root of $X$ is defined as the **Tag**. Note that $X$ has exactly $\lceil \log n \rceil + 1$ levels with the root being level 0.

The $\lceil \log n \rceil$-th level is the original database for a $k$-server PIR. For $\ell = \lceil \log n \rceil - 1, \lceil \log n \rceil - 2, \dots, 1$, the $\ell$-th level is considered as a database for a distinct $k$-server PIR (of different database size). For the purpose of retrieving the value of a leaf node $i$, the user firstly simply runs the $\lceil \log n \rceil$-th PIR to retrieve $x_i$. Secondly, in order to check the correctness of this invocation, the user needs to retrieve the authentication path of $i$, which is indicated by an integer sequence of the form $(v_{\lceil \log n \rceil}, v_{\lceil \log n \rceil - 1}, \dots, v_1)$. For every $\ell \in \{\lceil \log n \rceil, \lceil \log n \rceil - 1, \dots, 1\}$, invoke the $\ell$-th PIR to retrieve $v_\ell$-th data. Finally, the user may determine the correctness of the retrieved database item (i.e., $x_i$), by simply re-computing the root of $X$ with that item and the $\lceil \log n \rceil$ path values on the authentication path, and then compare with the **Tag** (i.e., the Merkle root published by the database owner). Note that in the re-computation of the root of $X$, it is computationally infeasible to use an authentication path for $i' \neq i$ to replace the authentication path for $i$, even when $i$ and $i'$ are siblings (in this case, the same collection of values are retrieved). This is because the re-computation of the root from the $i$-th item and $\lceil \log n \rceil$ path values uses an ordering specific to $i$, which is a $\lceil \log n \rceil$-bit string, each bit indicating on either “left” or “right” side, the path value appears in the two inputs to the hash function.

Merkle tree also allows one to efficiently update the value of every leaf node, yielding an updatable cd-PIR. An update algorithm for the data owner to modify a specific item can be realized by updating the corresponding path, which only cost $\log n$ times of computing of hash function. The cost for update is much less than a naive approach of making the data owner signing each data item and publish the public key of the signature scheme, and the user privately retrieving the data item together with the corresponding signature. To avoid the servers reusing an old data item and corresponding signature to fool the user, a new pair of public key and secret key must be used, rendering the data owner replacing all the signatures.

## 1.3 Organization

In Sect. 2, we give explanations for some symbols, and introduce the basics about Merkle trees; In Sect. 3, we formally define the model of cd-PIR. In Sect. 4, we show the Merkle tree based transformation from PIR protocol to cd-PIR protocol; In Sect. 5, we instantiate the transformation to obtain two concrete cd-PIR protocols, implement them to show their performance by experimental results; Finally, Sect. 6 contains our concluding remarks.

# 2 Preliminaries

## 2.1 Notation

For any integer $m > 0$, we denote with $\mathbb{Z}_m = \{0, 1, \dots, m-1\}$ the ring of integers modulo $m$ and denote $[m] = \{1, 2, \dots, m\}$. For any integer $n > 0$, we denote with $\lceil n \rceil$ the least integer $\ge n$ and denote with $\log n$ the logarithm of $n$ to the base
2. For any integers $i \ge 0$ and $\ell \ge \lceil \log i \rceil$, the $\ell$-bit binary representation of $i$ is an $\ell$-bit string $\langle i \rangle_\ell = i_1 \| i_2 \| \dots \| i_\ell \in \{0,1\}^\ell$ such that $i = \sum_{j=1}^\ell i_j \cdot 2^{\ell-j}$. We say that a function $\epsilon(\lambda)$ is negligible in $\lambda$ and denote $\epsilon(\lambda) = \text{negl}(\lambda)$, if for any $c > 0$, there exists $\lambda_c > 0$ such that $\epsilon(\lambda) < \lambda^{-c}$ for all $\lambda \ge \lambda_c$.

## 2.2 Merkle Tree

A Merkle tree is a complete binary tree where the value of every internal node is the hash value of its two children's values. Let $n = 2^m$ and $x = (x_0, x_1, \dots, x_{n-1})$. Let $H$ be a cryptographic hash function. The labels and values of the nodes in a Merkle tree $\text{MT}_{x,H}$ of depth $m$ can be defined as follows:

<figure><img src="image_5.png" /><figcaption>Fig. 3. Merkle tree for a database of length 8</figcaption></figure>

**Labels.** Nodes of $\text{MT}_{x,H}$ (see Fig. 3 for an example) are labeled such that:

- For $1 \le \ell \le m$, the $2^\ell$ nodes at depth $\ell$ are labeled (from left to right) with $\langle 0 \rangle_\ell, \langle 1 \rangle_\ell, \dots, \langle 2^\ell - 1 \rangle_\ell$, respectively. The node at depth 0 is labeled as Root.

- For $1 < \ell \le m$ and $0 \le j < 2^\ell$, the parent of $\langle j \rangle_\ell$ is $j_1 \| j_2 \| \dots \| j_{\ell-1}$. The parent of the nodes at the depth 1 is Root;

- For $1 \le \ell < m$ and $0 \le j < 2^\ell$, the left child of $\langle j \rangle_\ell$ is $\langle 2j \rangle_{\ell+1}$, and the right child of $\langle j \rangle_\ell$ is $\langle 2j+1 \rangle_{\ell+1}$. The left and right child of Root are $\langle 0 \rangle_1$ and $\langle 1 \rangle_1$, respectively.

- For $1 \le \ell \le m$ and $0 \le j < 2^\ell$, the sibling of $\langle j \rangle_\ell$ is $j_1 \| j_2 \| \dots \|(j_\ell \oplus 1)$.

**Values.** Every node $\langle j \rangle_\ell$ in $\text{MT}_{x,H}$ is assigned a value $h_{\langle j \rangle_\ell}$ such that:

- $h_{\langle j \rangle_m} = x_j$ for $0 \le j < 2^\ell$;

- $h_{\langle j \rangle_\ell} = H(h_{\langle 2j \rangle_{\ell+1}} \| h_{\langle 2j+1 \rangle_{\ell+1}})$ for $1 \le \ell < m$ and $0 \le j < 2^\ell$;

- $h_{\text{Root}} = H(h_0 \| h_1)$.

In our definition, values of the $n$ leaf nodes are $x_0, x_1, \dots, x_{n-1}$ sequentially. This is slightly different from the traditional definition of Merkle trees where the values of leaves are defined as the hash values of $x_0, x_1, \dots, x_{n-1}$. This change is made to obtain a more efficient transformation (see Sect. 4 for details).
**Verification.** Merkle tree allows a prover to convince a verifier of the value of any leaf node. For any $i \in \mathbb{Z}_n$, the nodes on the path from Root to $\langle i \rangle_m$ are

$$ (\text{Root}, i_1, i_1 \| i_2, \dots, i_1 \| i_2 \| \dots \| i_m). \qquad (1) $$

The authentication path for the leaf node $\langle i \rangle_m$ is defined as $\rho(i) = (v_1, v_2, \dots, v_m)$, where $v_\ell = i_1 \| i_2 \| \dots \| i_{\ell-1} \|(i_\ell \oplus 1)$ for all $\ell \in [m]$. The proof $\pi$ for the value of $\langle i \rangle_m$ consists of the values of the nodes on its authentication path. In order to verify $h_{\langle i \rangle_m} = \alpha$, the verifier simply recomputes the root value with $\alpha$ and the proof. The verification algorithm MTVer($h_{\text{Root}}$, $i$, $\alpha$, $\pi$) outputs 1 if the re-computed value equals $h_{\text{Root}}$; otherwise it outputs 0.

**Update.** Merkle tree also allows one to update the value of any leaf node. In the cause of changing $h_{\langle i \rangle_m}$ to $\alpha$, the update algorithm MTUpd($i$, $\alpha$, $\text{MT}_{x,H}$) only needs to recompute the values of the nodes on path (1) with the new leaf value $\alpha$. The output of this algorithm consists of the new Merkle tree and the new root value.

## 3 The cd-PIR Model

**Negative Result 1.** Assume the user only receive information about the database $x$ from the servers (in the form of answers to his/her queries) as indicated in Fig. 1. Then the servers can replace $x$ with some prefixed $x_0$ and execute the rest of the protocol honestly. According to the correctness of the protocol, which says that for any given database if all parties execute the protocol honestly, the user will output the correct $i$th data item, this substitution attack succeeds in replacing the $i$th data item of $x$ with $i$th data item of $x_0$. In the case $x = x_0$, this attack is vacuous. For all $x \neq x_0$, this attack is effective and renders cheating detection impossible. Note that in this attack, the servers are not required to do extra computation, as the substitution $x_0$ is prefixed. This means that the negative result is true for both computationally limited and unlimited servers.

**Negative Result 2.** Assume the user also receives a Tag containing information about the database $x$, which is published by the database owner, on top of receiving information about the database $x$ from the servers (in the form of answers to his/her queries) as indicated in Fig. 2. Assume the servers have unlimited computation power. We argue that the tag size has to be at least as big as the database, which undermines the motivation of using a PIR protocol (if the user were to download a tag as big as the database itself, he/she could just as well download the database and locally retrieve the desired data item). Indeed, assume by contradiction that the map from the databases to tags is not injective. Then there exist at least two databases $x$ and $x'$ that are mapped to the same tag. The servers can compute such a pair of databases $x$ and $x'$, then launch a substitution attack using, e.g. the database $x'$. Similarly to negative result 1, in the case $x = x'$, this attack is vacuous. For all $x \neq x'$, this attack is effective and renders cheating detection impossible. Unlike in negative result 1, this attack requires the servers to be capable of finding a pair of collision $x$ and
$x'$. In particular, this negative result does not hold in the case when the map from databases to tags is defined by a *collision-resistant hash function*.

**Definition 1 (cd-PIR).** A t-private k-server cd-PIR protocol $\Gamma = (\mathcal{G}, \mathcal{Q}, \mathcal{A}, \mathcal{R}, \mathcal{U})$ consists of five polynomial-time algorithms as follows:

- (Tag, X) ← $\mathcal{G}(x, \lambda)$: It is a deterministic algorithm. The inputs are a database $x$ and a security parameter $\lambda$, and the outputs are a database encoding $X$ and a public tag Tag.

- $(q_1, q_2, \dots, q_k, \text{aux}) \leftarrow \mathcal{Q}(i)$: It is a probabilistic algorithm. It takes a retrieval index $i \in \{0, 1, \dots, n-1\}$ as input, and outputs the query $q_j$ to the j-th server. It also computes an auxiliary information aux.

- $a_j \leftarrow \mathcal{A}(X, q_j)$: It is a deterministic algorithm. For every $j \in [k]$, it takes the database encoding $X$ and the query $q_j$ as input, and outputs an answer $a_j$ as a response to the user.

- $\{x_i, \perp\} \leftarrow \mathcal{R}(\text{Tag}, i, \text{aux}, (a_1, a_2, \dots, a_k))$: It is a deterministic algorithm. The user uses Tag, $i$, aux and $(a_1, a_2, \dots, a_k)$ to do reconstruction and verification. It outputs either the correct value of $x_i$ or a rejection symbol $\perp$.

- (Tag', X') ← $\mathcal{U}(x', X)$: It is a deterministic algorithm. With $X$ and the new database $x'$ being the input, it outputs a new tag Tag' and the new encoded database $X'$.

**Definition 2 (Correctness).** The protocol $\Gamma$ is said to be correct if for any $k, n \in \mathbb{N}$, any $x \in (0, 1)^n$, any $\lambda$, any $i \in \mathbb{Z}_n$, any $(q_1, q_2, \dots, q_k, \text{aux}) \leftarrow \mathcal{Q}(i)$ and any $\{a_j \leftarrow \mathcal{A}(X, q_j)\}_{j=1}^k$, it always holds that $\mathcal{R}(\text{Tag}, i, \text{aux}, (a_1, a_2, \dots, a_k)) = x_i$.

**Definition 3 (t-Privacy).** Any $t$ servers cannot learn information about the user's input. Formally, the protocol $\Gamma$ is information-theoretically (resp. computationally) t-private if for any $k, n, i, i' \in \mathbb{Z}_n$, and any set $T \subseteq [k]$ of cardinality $\le t$, the random variables $Q_T(i)$ and $Q_T(i')$ are identically distributed (resp. computationally indistinguishable), where $Q_T$ denotes the concatenation of j-th outputs of $\mathcal{Q}$ for $j \in T$.

**Definition 4 (τ-Security).** The protocol $\Gamma$ is τ-secure if for any $T \subseteq [k]$ of cardinality $\tau$, for all probabilistic polynomial-time adversaries $\mathcal{B}$, there is a negligible function $\text{negl}$ such that $\Pr[\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 1] \le \text{negl}(\lambda)$, where $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda)$ is performed between $\mathcal{B}$ and its challenger, as defined in Fig. 4.

# 4 A Merkle Tree Based Construction

In this section, we describe a transformation from PIR protocols to cd-PIR protocols. For all $\ell \in [m]$, let $V_\ell = \{(0)_{\ell}, \dots, (2^\ell - 1)_{\ell}\}$ and $H_\ell = \{(h_{\langle 0 \rangle_\ell}, \dots, h_{\langle 2^\ell - 1 \rangle_\ell})\}$. Let $V_{(0)} = \{\text{Root}\}$ and $H_0 = \{h_{\text{Root}}\}$. In our construction, we denote $\text{MT}_{x,H} = (V, H)$ with $V = \bigcup_{\ell=0}^m V_\ell$ and $H = \bigcup_{\ell=0}^m H_\ell$. Any t-private k-server PIR protocol $\Pi = (\mathcal{Q}, \mathcal{A}, \mathcal{R})$, can be transformed into a cd-PIR protocol $\Gamma = (\mathcal{G}, \mathcal{Q}, \mathcal{A}, \mathcal{R}, \mathcal{U})$ as follows:
1. The adversary $\mathcal{B}$ chooses a database $x$ and an index $i$, and outputs $(x, i)$.

2. The challenger computes $(\mathbf{Tag}, X) \leftarrow \mathcal{G}(x, \lambda)$ and $(q_1, q_2, \dots, q_k, \text{aux}) \leftarrow \mathcal{Q}(i)$. It gives $(X, \{q_j\}_{j \in T})$ to the adversary $\mathcal{B}$.

3. The adversary $\mathcal{B}$ chooses $t$ answers $\{\tilde{a}_j\}_{j \in T}$ to the challenger.

4. The challenger computes $\tilde{a}_j \leftarrow \mathcal{A}(X, q_j)$ for every $j \in [k] \setminus T$. It executes the algorithm $\mathcal{R}(\mathbf{Tag}, i, \text{aux}, (\tilde{a}_1, \tilde{a}_2, \dots, \tilde{a}_k))$ and learns its output $y$.

5. If $y \notin \{x_i, \perp\}$, then $\text{EXP}_{\mathcal{B},T}^{\text{Ver}}(T, \lambda)$ is defined as 1; $\text{EXP}_{\mathcal{B},T}^{\text{Ver}}(T, \lambda) = 0$ otherwise.

<caption>Fig. 4. Experiment $\text{EXP}_{\mathcal{B},T}^{\text{Ver}}(T, \lambda)$</caption>

- $(\mathbf{Tag}, X) \leftarrow \mathcal{G}(x, \lambda)$: Let $m = \lceil \log n \rceil$. (If $\log n < m$, fill the empty leaf nodes with 0.) The database owner constructs $\text{MT}_{x,H} = (V, H)$. It outputs a public tag $\mathbf{Tag} = h_{\text{Root}}$ and the database encoding $\bar{X} = \text{MT}_{x,H}$.

- $(q_1, q_2, \dots, q_k, \text{aux}) \leftarrow \mathcal{Q}(i)$: The user computes the authentication path

$$ \varrho(i) = (v_1, v_2, \dots, v_m) \in V_1 \times V_2 \times \dots \times V_m \quad (2) $$

with $v_\ell = i_1 \|i_2\| \dots \|i_{\ell-1}\|(i_\ell \oplus 1)$, for all $\ell \in [m]$, where $i_j \in \{0, 1\}$ for all $j \in [m]$ and $i = \sum_{j=1}^m i_j \cdot 2^{m+1-j}$. It then generates $(q_1^\ell, q_2^\ell, \dots, q_k^\ell, \text{aux}_\ell) \leftarrow \Pi.\mathcal{Q}(v_\ell)$, for every $\ell \in [m]$, and $(\zeta_1, \zeta_2, \dots, \zeta_k, \text{a}\bar{\text{ux}}) \leftarrow \Pi.\mathcal{Q}(i)$. The outputs are $\{q_j = (q_1^\ell, q_2^\ell, \dots, q_j^m, \zeta_j)\}_{j=1}^k$ and $\text{aux} = (\{\text{aux}_j\}_{j=1}^k, \text{a}\bar{\text{ux}}, \varrho(i))$.

- $a_j \leftarrow \mathcal{A}(X, q_j)$: This $j$-th server computes $\alpha_j = \Pi.\mathcal{A}(x, \zeta_j)$ and $a_j^\ell = \Pi.\mathcal{A}(H_\ell, q_j^\ell), \forall \ell \in [m]$. It responds with $a_j = (a_j^1, a_j^2, \dots, a_j^m, \alpha_j)$.

- $\{x_i, \perp\} \leftarrow \mathcal{R}(\mathbf{Tag}, i, \text{aux}, (a_1, a_2, \dots, a_k))$: The user computes $\alpha = \Pi.\mathcal{R}(i, \text{a}\bar{\text{ux}}, (\alpha_1, \alpha_2, \dots, \alpha_k))$ and $z_\ell = \Pi.\mathcal{R}(v_\ell, \text{aux}_\ell, (a_1^\ell, a_2^\ell, \dots, a_k^\ell))$ for all $\ell \in [m]$. If the verification algorithm $\text{MTVer}(h_{\text{Root}}, i, \alpha, (z_1, z_2, \dots, z_m)) = 1$ (as discussed in Sect. 2), it outputs $\alpha$; o.w., it outputs $\perp$.

- $(\mathbf{Tag}', X') \leftarrow \mathcal{U}(j, x_j', X)$: It runs $\text{MTUpd}(j, x_j', X)$ with $X$ and then outputs both a new tag $\mathbf{Tag}'$ and the updated encoded database $X'$. In particular, $X'$ is identical to $X$ except that the values of the nodes on the path from the root to the $j$-th leaf are recomputed with $x_j'$. The $\mathbf{Tag}'$ is essentially the value of the root of the new Merkle tree $X'$.

**Remark 1.** For the sake of reduction of both communication and computation, if $v_m$ is on the right of $\langle n-1 \rangle_m$, that is the value of the node $v_m$ is 0 by default according to the construction, we substitute the original database $x$ for $H_\ell$ in the PIR invocation during the cd-PIR execution, then the user randomly chooses $v_m \in \{\langle 0 \rangle_m, \langle 1 \rangle_m, \dots, \langle n-1 \rangle_m\}$ to run the query algorithm. Therefore, in the reconstruction phase, the user can write $z_m = 0$ directly, which circumvents dealing with the related answers and saves some computation.

**Remark 2.** Besides $x_i$, the value of $x_i$'s sibling in the Merkle tree could be revealed to the user as a part of the proof. Revealing more information than $x_i$ to the user is allowed in PIR (including the cd-PIR of this paper), because
what the PIR protocols protect is the user's privacy rather than the server's privacy.

**Communication Complexity.** In the execution of cd-PIR $\Gamma$, the underlying PIR protocol will be invoked for $[\log n] + 1$ times with database of different size. If the communication complexity of the PIR protocol $\Pi$ is $CC_{\Pi}(w, n)$ for any database $x \in ((0, 1)^w)^n$ and the outputs of the hash function $H$ are $w$-bit long, then the communication complexity of our protocol $\Gamma$ will be $CC_{\Gamma}(w, n) = 2CC_{\Pi}(w, n) + \sum_{\ell=1}^{m-1} CC_{\Pi}(w, 2^{\lfloor \log n \rfloor - \ell})$.

**Theorem 1.** Our cd-PIR protocol $\Gamma$ satisfies the following:

- **Correctness:** $\Gamma$ is correct if the PIR protocol $\Pi = (Q, A, \mathcal{R})$ is correct.

- **t-Privacy:** $\Gamma$ is information-theoretically t-private (resp. computationally private) if the PIR protocol $\Pi = (Q, A, \mathcal{R})$ is information-theoretically t-private (resp. computationally private).

- **k-Security:** $\Gamma$ is k-secure if the hash function $H$ is collision-resistant.

The output of our cd-PIR protocol will always be true due to the correctness of the underlying PIR protocol. The privacy, inherited from the PIR protocol, guarantees that any $k$ honest-but-curious servers are not able to learn $i$. The security of our cd-PIR protocol comes from the collision resistance of the hash function. The properties of correctness and privacy can be easily proved and omitted from this version. Below we only prove the k-security.

*Proof.* Because $H$ is collision-resistant, for any PPT adversary $\mathcal{D}$, there is a negligible function $\text{negl}(\lambda)$ such that

$$ \Pr[(\delta, \delta') \leftarrow \mathcal{D}(H) : \delta \neq \delta', H(\delta) = H(\delta')] \leq \text{negl}(\lambda). \quad (3) $$

Let $T = [k]$. For any Probabilistic Polynomial Time (PPT) adversary $\mathcal{B}$, we consider the experiment $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda)$ between $\mathcal{B}$ and its challenger, which is shown in Fig. 5. We need to show that

$$ \epsilon(\lambda) := \Pr[\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 1] $$

is negligible. Assume for contradiction that $\epsilon(\lambda)$ is non-negligible. When $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 1$, we have that $\tilde{y} \notin \{x_i, \perp\}$. Let $\tilde{z}_\ell = \Pi.R(v_\ell, \text{aux}_\ell$, ($\tilde{a}_1^\ell, \tilde{a}_2^\ell, \dots, \tilde{a}_k^\ell$)) for all $\ell \in [m]$ and let $\tilde{\alpha} = \Pi.R(i, \text{a}\bar{\text{u}}x$, ($\tilde{\alpha}_1, \tilde{\alpha}_2, \dots, \tilde{\alpha}_k$)). Due to the specification of $\Gamma.R$, the event $\tilde{y} \notin \{x_i, \perp\}$ occurs if and only if $\tilde{\alpha} \neq x_i$ but

$$ \text{MTVer}(h_{\text{Root}}, i, \tilde{\alpha}, (\tilde{z}_1, \tilde{z}_2, \dots, \tilde{z}_m)) = 1. \quad (4) $$

For every $j \in [k]$, let $a_j = (a_j^1, a_j^2, \dots, a_j^m, \alpha_j) \leftarrow \Gamma.A(X, q_j)$ be the correct answer. Let $z_\ell = \Pi.R(v_\ell, \text{aux}_\ell$, ($a_1^\ell, a_2^\ell, \dots, a_k^\ell$)) for all $\ell \in [m]$ and let $\alpha = \Pi.R(i, \text{a}\bar{\text{u}}x$, ($\alpha_1, \alpha_2, \dots, \alpha_k$)). We have $\alpha = x_i$ since $\Pi$ is correct. The correctness of $\Gamma$ implies that

$$ \text{MTVer}(h_{\text{Root}}, i, \alpha, (z_1, z_2, \dots, z_m)) = 1. \quad (5) $$
1. The adversary $\mathcal{B}$ chooses a database $x$ and an index $i$, then outputs $(x, i)$.

2. The challenger computes $(\text{Tag}, X) \leftarrow \Gamma.G(x, \lambda)$ and $(q_1, q_2, \dots, q_k, \text{aux}) \leftarrow \Gamma.Q(i)$, where $\text{Tag} = h_{\text{Root}}$ and $\text{aux} = (\{\text{aux}_\ell\}_{\ell=1}^m, \text{a}\bar{\text{u}}\text{x}, \theta(i))$. For all $\ell \in [m]$, $v_\ell$ is the $\ell$-th element of $v(i)$. It gives $(X, \{q_j\}_{j=1}^k)$ to $\mathcal{B}$.

3. The adversary $\mathcal{B}$ chooses $k$ answers $\{\tilde{a}_j\}_{j=1}^k$, where $\tilde{a}_j = (\tilde{a}_j^1, \tilde{a}_j^2, \dots, \tilde{a}_j^m, \tilde{a}_j)$ for all $j \in [k]$, and gives them to the challenger.

4. The challenger executes $\Gamma.R(\text{Tag}, i, \text{aux}, (\tilde{a}_1, \tilde{a}_2, \dots, \tilde{a}_k))$ and learns its output $\tilde{y}$.

5. If $\tilde{y} \notin \{x_i, \perp\}$, then $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda)$ is defined as 1; $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 0$ otherwise.

<caption>Fig. 5. Experiment $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda)$</caption>

For all $\ell \in [m]$, let $\tilde{\gamma}_\ell$ (resp. $\gamma_\ell$) be the value of the $\ell$-th node on the path from the root to the $i$-th leaf that is computed with (4) (resp. (5)), then

$$ \left\{ \begin{array}{l} \gamma_{\ell} = \mathbf{H}(z_{m+1-\ell}\|\gamma_{\ell-1}), \\ \tilde{\gamma}_{\ell} = \mathbf{H}(\tilde{z}_{m+1-\ell}\|\tilde{\gamma}_{\ell-1}), \end{array} \right. \quad \text{or} \quad \left\{ \begin{array}{l} \gamma_{\ell} = \mathbf{H}(\gamma_{\ell-1}\|z_{m+1-\ell}), \\ \tilde{\gamma}_{\ell} = \mathbf{H}(\tilde{\gamma}_{\ell-1}\|\tilde{z}_{m+1-\ell}), \end{array} \right. \qquad (6) $$

for every $\ell \in [m]$. It follows that $\tilde{\gamma}_m = h_{\text{Root}} = \gamma_m$. If $(\tilde{z}_1, \tilde{\gamma}_{m-1}) \neq (z_1, \gamma_{m-1})$, then (6) indicates that either $(\tilde{z}_1\|\tilde{\gamma}_{m-1}, z_1\|\gamma_{m-1})$ or $(\tilde{\gamma}_{m-1}\|\tilde{z}_1, \gamma_{m-1}\|z_1)$ will be a collision of $\mathbf{H}$. Otherwise, $\tilde{\gamma}_{m-1} = \gamma_{m-1}$. With a similar argument, a collision of $\mathbf{H}$ of the form $(\tilde{z}_2\|\tilde{\gamma}_{m-2}, z_2\|\gamma_{m-2})$ or $(\tilde{\gamma}_{m-2}\|\tilde{z}_2, \gamma_{m-2}\|z_2)$, or $\tilde{\gamma}_{m-2} = \gamma_{m-2}$ will be found. In general, we may find an index $1 < \ell' \le m$ such that $\mathbf{H}$ has a collision being $(\tilde{z}_{m+1-\ell'}\|\tilde{\gamma}_{\ell'-1}, z_{m+1-\ell'}\|\gamma_{\ell'-1})$ or $(\tilde{\gamma}_{\ell'-1}\|\tilde{z}_{m+1-\ell'}, \gamma_{\ell'-1}\|z_{m+1-\ell'})$, or $\tilde{\gamma}_1 = \Gamma_1$. If $\tilde{\gamma}_1 = \Gamma_1$, then here comes $\mathbf{H}(\tilde{z}_m\|\tilde{\alpha}) = \mathbf{H}(z_m\|x_i)$ or $\mathbf{H}(\tilde{\alpha}\|\tilde{z}_m) = \mathbf{H}(x_i\|z_m)$. Either $(\tilde{z}_m\|\tilde{\alpha}, z_m\|x_i)$ or $(\tilde{\alpha}\|\tilde{z}_m, x_i\|z_m)$ will be a collision of $\mathbf{H}$, as $\tilde{\alpha} \neq x_i$.

The above process shows that when $\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 1$, we can always find a collision of $\mathbf{H}$. That is, there is a PPT algorithm that uses $\mathcal{B}$ to find a collision with probability $\ge \text{Pr}[\text{EXP}_{\mathcal{B},\Gamma}^{\text{Ver}}(T, \lambda) = 1] = \epsilon(\lambda)$, which is non-negligible in $\lambda$. Therefore, the assumption is incorrect and the cd-PIR protocol $\Gamma$ is $k$-secure when $\mathbf{H}$ is collision-resistant. $\square$

# 5 Performance Evaluation

In this section, we instantiate the transformation of Sect. 4 with both multi-server PIR and single-server PIR protocols from the literature, and evaluate the obtained cd-PIR protocols with implementations in C++ with the FLINT library. We measure the computational performance of these protocols on the Ubuntu 20.04 with 64GB RAM and 6-cores 4.00GHz Intel(R) Xeon(R) E-2286G CPU made by GenuineIntel. The hash function $\mathbf{H}$ is chosen as SHA-256.

## 5.1 Multi-Server cd-PIR Protocol $\Gamma_{\text{WY}}$

By applying the transformation of Sect. 4 to the $t$-private $k$-server PIR protocol $\Pi_{\text{WY}} = (\mathcal{Q}_{\text{WY}}, \mathcal{A}_{\text{WY}}, \mathcal{R}_{\text{WY}})$ in [30], we obtain a cd-PIR protocol $\Gamma_{\text{WY}} =$
($\mathcal{G}$, $\mathcal{Q}$, $\mathcal{A}$, $\mathcal{R}$, $\mathcal{U}$). As the communication complexity of $\Pi_{WY}$ is $O(\frac{k^2}{t} \log k n^{\lfloor \frac{2k-1}{t} \rfloor})$ for a database $x \in (0, 1)^n$. For the database $x \in ((0, 1)^w)^n$, the communication complexity of using our cd-PIR protocol to retrieve a $w$-bit block from $x$ is

$$CC_{\Gamma_{WY}}(n) = O(2n^{1/\lfloor \frac{2k-1}{t} \rfloor}) + \sum_{\ell=1}^{m-1} O(2^{(m-\ell)/\lfloor \frac{2k-1}{t} \rfloor}) = O(2^{\lceil \log n \rceil/\lfloor \frac{2k-1}{t} \rfloor}).$$

**Experimental Results.** In the experiment, the database $x \in ((0, 1)^w)^n$ consists of $n$ blocks, each having $w$ bits, and we set $(k, t) = (2, 1)$ as an example to demonstrate the efficiency. We execute each protocol for 100 times and fetch the average results as the final results and the user chooses the private index randomly in each of the 100 iterations to avoid occasionality.

The Fig. 6 shows the comparison of computation time of the cd-PIR protocol $\Gamma_{WY}$ and the PIR protocol $\Pi_{WY}$. In order to achieve the verification compared with the underlying PIR protocol, the cd-PIR protocol needs to spend some extra time, even so, the computation time should not be too large, and it should be almost linear with the computation time of the underlying PIR protocol. The experimental results show that the server's computation time in $\Gamma_{WY}$ is no more than 3 times of that in the PIR protocol $\Pi_{WY}$, and the user's computation time in $\Gamma_{WY}$ is about 6 to 7 times longer than that of $\Pi_{WY}$, which are in good agreement with our analysis.

<figure><img src="image_6.png" /><figcaption>Fig. 6. Comparison of Computation Time between $\Gamma_{WY}$ and $\Pi_{WY}$</figcaption></figure>

## 5.2 Single-Server cd-PIR Protocol $\Gamma_{SL}$

The single-server PIR protocol [2] $\Pi_{SL} = (\mathcal{Q}_{SL}, \mathcal{A}_{SL}, \mathcal{R}_{SL})$ uses the Microsoft SEAL homomorphic library [27], based on the Fan-Vercauteren(FV) cryptosystem. The user sends $d$ ciphertexts containing the information of the desired index as queries, the server expands them into ciphertext vectors by a homomorphic method to work out the answer.

By applying the PIR protocol $\Pi_{SL}$, we get a single-server cd-PIR protocol $\Gamma_{SL} = (\mathcal{G}, \mathcal{Q}, \mathcal{A}, \mathcal{R}, \mathcal{U})$. The communication complexity of $\Pi_{SL}$ is $O(Nd^{\lceil \sqrt{d}/\sqrt{n} \rceil})$ for a database $x \in (0, 1)^n$, where $d$ is the number of the ciphertext tuple and $N$ decides size of the ciphertexts, as ciphertexts consist of polynomials in $R_q =$
$Z_q[x] \setminus (x^N + 1)$. So the communication complexity of retrieving any $w$-bit block from $x \in ((0, 1)^w)^n$ is computed as

$$CC_{\Gamma_{SL}}(n) = 2O(Nd^{\lfloor \sqrt[d]{n}/N \rfloor}) + \sum_{\ell=1}^{m-1} O(Nd^{\lfloor 2^{\lceil \log n \rceil}/d \rfloor/N}) = O(Nd^{\lfloor \sqrt[d]{n}/N \rfloor}).$$

**Experimental Results.** In the experiment, the database $x \in ((0, 1)^w)^n$ consists of $n$ blocks, each having $w$ bits. We execute each protocol for 100 times and fetch the average results as the final results and the user chooses the private index randomly in each of the 100 iterations to avoid occasionality.

The Fig. 7 shows the comparison of computation time of the cd-PIR protocol $\Gamma_{SL}$ and the PIR protocol $\Pi_{SL}$. In order to achieve the verification compared with the underlying PIR protocol, the cd-PIR protocol needs to spend some extra time, even so, the computation time should not be too large, and it should be almost linear with the computation time of the underlying PIR protocol. The experimental results show that the server's computation time in $\Gamma_{SL}$ is around 3 times of that in the PIR protocol $\Pi_{SL}$, and the user's computation time in $\Gamma_{SL}$ is around 15 times longer than that of $\Pi_{SL}$, which meets our expected analysis.

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7. Comparison of Computation Time between $\Gamma_{SL}$ and $\Pi_{SL}$</figcaption></figure>

## 6 Conclusion

This paper initiated the fundamental problem of cheating detection for PIR protocol and introduced a new variant of PIR, *cheating detection for PIR* (cd-PIR). It also demonstrated the impossibility of the information-theoretic cd-PIR protocol and the inevitability of the database owner in the computational cd-PIR protocol, to justify the cd-PIR model.

With the Merkle tree, we proposed a construction that enables any PIR protocol to be transformed into a cd-PIR protocol. Moreover, our proposed cd-PIR protocol can be resistant to quantum attacks, as the security is derived from the collision resistance of the hash function. We further implemented two cd-PIR protocols obtained by the transformation. For the multi-server setting, the experiment results display the efficient computation and the practicality
compared with the existing multi-server VPIR protocol. For the single-server setting, the cd-PIR protocol can be viewed as a VPIR protocol, the experiment results show a large scale improvements compared with the latest VPIR protocol. In addition, we pose an open question about the PIR with Byzantine servers.

**Acknowledgments.** The authors would like to thank the anonymous referees for helpful comments to improve the presentation of this paper.

Liang Feng Zhang's research was supported by Natural Science Foundation of Shanghai under grant 21ZR1443000 and Singapore Ministry of Education under grant RG12/19. Changlu Lin's research was supported in part by National Natural Science Foundation of China under grant U1705264. Fuchun Lin's research was supported by EPSRC grant EP/S021043/1.

## References

1. Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595–605 (2004)

2. Angel, S., Chen, H., Laine, K., Setty, S.: PIR with compressed queries and amortized query processing. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 962–979 (2018)

3. Angel, S., Setty, S.: Unobservable communication over fully untrusted infrastructure. In: 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2016), pp. 551–569 (2016)

4. Beimel, A., Stahl, Y.: Robust information-theoretic private information retrieval. J. Cryptol. 20(3), 295–321 (2007)

5. Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X.28

6. Cheng, R., et al.: Talek: private group messaging with hidden access patterns. In: Annual Computer Security Applications Conference, pp. 84–99 (2020)

7. Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 41–50 (1995)

8. Devet, C., Goldberg, I., Heninger, N.: Optimally robust private information retrieval. In: Presented as part of the 21st USENIX Security Symposium (USENIX Security 2012), pp. 269–283 (2012)

9. Dvir, Z., Gopi, S.: 2-server PIR with subpolynomial communication. J. ACM 63(4), 1–15 (2016)

10. Efremenko, K.: 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41(6), 1694–1703 (2012)

11. Goldberg, I.: Improving the robustness of private information retrieval. In: 2007 IEEE Symposium on Security and Privacy (SP 2007), pp. 131–148 (2007)

12. Green, M., Ladd, W., Miers, I.: A protocol for privately reporting ad impressions at scale. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1591–1601 (2016)

13. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC 1996, Association for Computing Machinery, pp. 212–219 (1996)
14. Gupta, T., Crooks, N., Mulhern, W., Setty, S., Alvisi, L., Walfish, M.: Scalable and private media consumption with popcorn. In: 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2016), pp. 91–107 (2016)

15. Gyongyosi, L., Imre, S.: A survey on quantum computing technology. Comput. Sci. Rev. 31, 51–71 (2019)

16. Häner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quantum circuits for elliptic curve discrete logarithms. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 425–444. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_23

17. Juels, A.: Targeted advertising ... and privacy too. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 408–424. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_30

18. Khoshgozaran, A., Shahabi, C.: Private information retrieval techniques for enabling location privacy in location-based services. In: Bettini, C., Jajodia, S., Samarati, P., Wang, X.S. (eds.) Privacy in Location-Based Applications. LNCS, vol. 5599, pp. 59–83. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03511-1_3

19. Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 364–373 (1997)

20. Kwon, A., Lazar, D., Devadas, S., Ford, B.: Riffle: an efficient communication system with strong anonymity. Proc. Priv. Enhancing Technol. 2016(2), 115–134 (2016)

21. Lueks, W., Goldberg, I.: Sublinear scaling for multi-client private information retrieval. In: Böhme, R., Okamoto, T. (eds.) FC 2015. LNCS, vol. 8975, pp. 168–186. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47854-7_10

22. Mittal, P., Olumofin, F., Troncoso, C., Borisov, N., Goldberg, I.: PIR-Tor: scalable anonymous communication using private information retrieval. In: Proceedings of the 20th USENIX Conference on Security (SEC 2011), p. 31 (2011)

23. Borisov, N., Danezis, G., Goldberg, I.: Dp5: a private presence service. Proc. Priv. Enhancing Technol. 2015(2), 4–24 (2015)

24. Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 241–270. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_9

25. Sassaman, L., Cohen, B., Mathewson, N.: The pynchon gate: a secure method of pseudonymous mail retrieval. In: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, pp. 1–9 (2005)

26. National Academies of Sciences, Engineering, and Medicine: Quantum computing: progress and prospects. National Academies Press, Washington, DC (2019)

27. Microsoft SEAL (release 3.2) Microsoft Research, Redmond (2019). https://github.com/microsoft/SEAL

28. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

29. Wang, X., Zhao, L.: Verifiable single-server private information retrieval. In: Naccache, D., Xu, S., Qing, S., Samarati, P., Blanc, G., Lu, R., Zhang, Z., Meddahi, A. (eds.) ICICS 2018. LNCS, vol. 11149, pp. 478–493. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01950-1_28

30. Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), pp. 275–284 (2005)
31. Yannuzzi, M., Milito, R.A., Serral-Graciá, R., Montero, D., Nemirovsky, M.: Key ingredients in an IoT recipe: Fog computing, Cloud computing, and more Fog computing. In: 2014 IEEE 19th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), pp. 325–329 (2014)

32. Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1), 1–16 (2008)

33. Zhang, L.F., Safavi-Naini, R.: Verifiable multi-server private information retrieval. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 62–79. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07536-5_5