11institutetext: RMIT University, Melbourne, Australia
11email: {nhat.quang.cao2, sonhoang.dau<EMAIL_ADDRESS>
22institutetext: The University of New South Wales, Canberra, Australia
22email<EMAIL_ADDRESS>
33institutetext: Monash University, Melbourne, Australia
33email<EMAIL_ADDRESS>
44institutetext: The University of British Columbia, Kelowna, Canada
44email<EMAIL_ADDRESS>
55institutetext: NYCU University, Hsinchu, Taiwan
55email<EMAIL_ADDRESS>
66institutetext: The University of Melbourne, Melbourne, Australia
66email<EMAIL_ADDRESS>
77institutetext: Nanyang Technological University, Singapore
77email: {stanislav.kruglik<EMAIL_ADDRESS>
# Committed Private Information Retrieval††thanks: Supported by the Australian
Research Council through the Discovery Project under Grant DP200100731. The
work of Hong Yen Tran was partly done when she was with RMIT University.

Quang Cao 11 0000-0001-9649-943X Hong Yen Tran 22 Son Hoang Dau 11 Xun Yi 11
Emanuele Viterbo 33 Chen Feng 44 Yu-Chih Huang 55 Jingge Zhu 66 Stanislav
Kruglik 77 Han Mao Kiah 77

###### Abstract

A private information retrieval (PIR) scheme allows a client to retrieve a
data item $x_{i}$ among $n$ items $x_{1},x_{2},\ldots,x_{n}$ from $k$ servers,
without revealing what $i$ is even when $t<k$ servers collude and try to learn
$i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is
$v$-verifiable if the client can verify the correctness of the retrieved
$x_{i}$ even when $v\leq k$ servers collude and try to fool the client by
sending manipulated data. Most of the previous works in the literature on PIR
assumed that $v<k$, leaving the case of all-colluding servers open. We propose
a generic construction that combines a linear map commitment (LMC) and an
arbitrary linear PIR scheme to produce a $k$-verifiable PIR scheme, termed a
committed PIR scheme. Such a scheme guarantees that even in the worst
scenario, when all servers are under the control of an attacker, although the
privacy is unavoidably lost, the client won’t be fooled into accepting an
incorrect $x_{i}$. We demonstrate the practicality of our proposal by
implementing the committed PIR schemes based on the Lai-Malavolta LMC and
three well-known PIR schemes using the GMP library and blst, the current
fastest C library for elliptic curve pairings.

###### Keywords:

Private information retrieval verifiability malicious server commitment scheme
pairing elliptic curve.

##  1 Introduction

In this work, we revisit private information retrieval (PIR), a classic tool
in cryptography, and investigate the extent that PIR can be used in a
trustless system in which participants can be corrupted. While the basic PIR
only provides privacy, i.e., making sure that a client can privately retrieve
a data item of interest without revealing it to any server that stores the
collection of data, we are interested in three extra security111In the PIR
literature, ‘security’ was often used to refer to the concept of
‘verifiability’ defined in this work. However, in our opinion, ‘security’ is a
rather broad term and should not be used as the name of a specific property.
We make an effort to fix that terminology issue in this work, using ‘security’
as an umbrella term instead. requirements, namely, verifiability,
accountability, and Byzantine-robustness. These requirements are made under
the assumption that a group of malicious servers are not only keen on learning
the retrieved data but also on making the client recover incorrect data to
achieve certain purposes. This type of security requirements are crucial to
extend the usage of PIR beyond trusted systems, which make sense mostly in
theory, to the more practical trustless systems, which are capable of
governing both trusted and malicious parties. Note that ‘trusted’ is also a
very shaky status: even a supposedly trusted party like a well-established
bank or a government agency can still be attacked and temporarily become a
malicious party, which may cause severe damage to the customers (see, e.g.
devastating attacks on Australian universities, Medibank, Optus, and Fire
Rescue Victoria in 2022 [1, 2]).

A basic private information retrieval (PIR) scheme allows a client to download
a data item $x_{i}$ among a collection of $n$ items $x_{1},x_{2},\ldots,x_{n}$
from $k\geq 1$ servers without revealing the index $i$ to any curious server.
The very first private information retrieval (PIR) scheme with two servers was
introduced in the seminal work of Chor-Kushilevitz-Goldreich-Sudan [3], which
works as follows. The two servers both store $x_{1},x_{2},\ldots,x_{n}$, which
are elements from a finite field ${\mathbb{F}}$ of characteristic 2. To
privately retrieve $x_{i}$, the client selects a random set
$J\subseteq\\{1,2,\ldots,n\\}$ and requests $\sum_{j\in J}x_{j}$ from Server 1
and $x_{i}+\big{(}\sum_{j\in J}x_{j}\big{)}$ from Server 2. As ${\mathbb{F}}$
has characteristic 2, the client can simply add the two answers to extract
$x_{i}$. Moreover, as $J$ is a random set, from the query, each server
achieves no information (in Shannon’s sense) about $i$. We refer to this as
the CKGS scheme and use it as a toy example to demonstrate our approach below.

The CKGS scheme, while providing privacy against an honest-but-curious server,
doesn’t protect the client against a malicious one: if the malicious server
sends an incorrect answer, the client will end up with an incorrect data item
$\hat{x}_{i}\neq x_{i}$. To construct a secure PIR scheme that can deal with
malicious servers, there are two approaches: the joint-design approach (a PIR
scheme is designed with built-in security) and the modular approach (combining
a PIR and another cryptographic primitive, both of which are separately
designed). As far as we know, most related works in the literature [4, 5, 6,
7, 8, 9, 10, 11] (except for [12]) followed the former. While the first
approach requires more tailor-made designs, which are harder to develop but
potentially achieve better performance, the second provides greater simplicity
and flexibility: an arbitrary PIR scheme and an arbitrary commitment scheme
will work together to achieve a secure PIR scheme. Moreover, any improvement
in either PIR or commitment schemes will automatically translate to an
improvement to this approach. In the cope of this work, we focus on the second
approach, applying a commitment scheme on top of a PIR. The gist of this
approach is to publish a digest of the data, referred to as the commitment,
before the PIR session starts. Once the commitment has been produced and made
public, the client can use the commitment to confirm the correctness of its
desired data item, even when all servers are malicious.

An obvious commitment-based solution that allows the client to verify the
correctness of its derived data is using (cryptographic) hashes of the data as
the commitment: the hashes $h_{j}=h(x_{j})$, $j=1,2,\ldots,n$ are made public
before the PIR session starts, and then the client can download all the
hashes222The client can gather the hashes by downloading them from the data
owner, or from a few random servers in a decentralized system (e.g. a
blockchain) and using a majority vote to determine the correct $h_{i}$. and
perform a hash verification on the derived $\hat{x}_{i}$ and accepts it if
$h(\hat{x}_{i})=h_{i}$. This solution, however, increases the download cost
for the client due to the extra $sn$ hashes coming from $s$ servers for some
constant $s$. More importantly, this makes the PIR protocol cumbersome and
unsuitable to systems requiring compact data-commitments such as the
blockchains, where the commitment to the data (transactions, chain states) is
often a single 256-bit hash (the Merkle proof) stored in a small block header
of a rather limited size, e.g. 80 bytes in Bitcoin and around 500 bytes in
Ethereum. Here, a potential application in this context is for a client to
privately retrieve a transaction in a block.

Figure 1: An example of a 2-server committed PIR scheme based on an LMC and
the CKGS PIR scheme [3] (see Example 1 for more details). The client privately
requests both $x_{1}$ and $h_{1}=h(x_{1})$, where the correctness of the
retrieved hash $\hat{h}_{1}$ can be verified thanks to the LMC. It can then
verify the correctness of the retrieved data $\hat{x}_{1}$ by performing a
hash verification $h(\hat{x}_{1})\overset{?}{=}\hat{h}_{1}$. The size of the
$x_{j}$’s can be arbitrarily large. The commitment $C({\bm{h}})$ and the
witnesses $w_{1}(a_{1}({\bm{h}})),w_{2}(a_{2}({\bm{h}}))$ are of size only 384
bits (equivalent to 1.5$\times$ SHA3-256 hash) if the Lai-Malavolta LMC [13]
is used.

We address the aforementioned drawback of the hash-based solution by using
linear map commitments with a constant-size commitment on top of linear PIR
schemes to provide verifiability. A linear map commitment (LMC) [14, 15, 13,
16] allows the prover to generate a commitment $C({\bm{x}})$ to a vector
${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})\in{\mathbb{F}}^{n}$ and a witness
$w_{\bm{a}}({\bm{x}})$ based on which the verifier can verify that a retrieved
value $y\in{\mathbb{F}}$ is indeed the value of the linear combination
${\bm{a}}\cdot{\bm{x}}=\sum_{j=1}^{n}a_{j}x_{j}$. In a compact LMC, e.g. [13],
the sizes of the commitment $C({\bm{x}})$ and the witness
$w_{\bm{a}}({\bm{x}})$ (in bits) are constant, i.e. together their sizes are
equivalent to a couple of field elements only. To make the PIR scheme suitable
to a database with large-size data items, we let $x_{i}\in\mathbb{F}^{m}$
where $m$ can be arbitrarily large and the LMC can be applied instead to the
hashes ${\bm{h}}=(h_{1},h_{2},\ldots,h_{n})$ of
${\bm{x}}\in\mathbb{F}^{m\times n}$ (see Fig. 1 for a toy example). Our
proposed scheme, referred to as the committed PIR scheme, provides
$k$-verifiability: even in the extreme case where all servers are attacked and
controlled by a malicious attacker, although the privacy is unavoidably lost,
the scheme is still capable of protecting the client from accepting fault
data.

Our main contributions are summarized below.

  * •

We propose a novel modular approach that combines a linear map commitment
scheme and a linear PIR scheme to construct a committed PIR scheme that
provides verifiability on top of the traditional privacy. Our proposed scheme
is capable of preventing the client from accepting an incorrect data item,
even when all $k$ servers are malicious and send manipulated data. Most
previous works can only tolerate up to $k-1$ malicious servers.

  * •

We carry out three case studies discussing the constructions of committed PIR
schemes using a specific linear map commitment on top of the three well-known
representative PIR schemes: the CKGS scheme [3] (the very first PIR scheme),
the WY scheme [17] (lowest upload cost, aka query size), and the BE scheme
[18] (lowest download cost, aka answer size). The LMC primitive incurs only a
constant-size communication overhead.

  * •

We implemented all three schemes in C on top of the GMP library (for efficient
handling of large numbers) and the blst library (the current fastest library
for elliptic curve operations and pairings). Two out of three achieved
reasonably fast running times, e.g. less than one second of computation for
the client to retrieve 3MB from a 3GB-database, demonstrating the practicality
of our proposal.

We want to highlight another advantage of LMCs as the primitive for the
committed PIR: as more advanced LMCs are developed, new features will be
automatically added to the proposed scheme with no modifications to the
underlying PIR schemes. For example, the LMC introduced in [16] allows
updatability, or the lattice-based LMC developed in [15] provides post-quantum
security.

The remainder of the paper is organized as follows. We first define formally
the PIR and committed PIR schemes as well as their performance metrics in
Section 2. We then introduce a generic construction for a committed PIR in
Section 3. In Section 4, we demonstrate the proposed method with three case
studies in which a linear map commitment is applied to three well-known PIR
schemes. Section 5 is devoted to implementations and evaluations.

##  2 Committed Private Information Retrieval

###  2.1 Basic Notations

We use ${\mathbb{F}}$ to denote a general finite field and $\mathbb{F}_{p}$ to
denote a finite field of $p$ elements, where $p$ is a prime power. Within the
scope of this work, we usually assume that $p$ is a prime and hence,
$\mathbb{F}_{p}\equiv Z_{p}$, the integers mod $p$. For implementation, we use
a specific prime $p$ of size about 256 bits (following the parameter of the
BLS12-381 elliptic curve). We use $[n]$ to denote the set
$\\{1,2,\ldots,n\\}$. The data is represented by
${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})$, where $x_{j}\in\mathbb{F}^{m}$,
$j\in[m]$, and $m\geq 1$ represents the size of each data item $x_{j}$ (in
field elements). We call $n$ the number of items or the size of the data. The
data can also be regarded as an $m\times n$ matrix
${\bm{x}}\in\mathbb{F}^{m\times n}$ and each data item $x_{j}$ corresponds to
the $j$-th column of the matrix.

Throughout this work we denote by $\lambda\in{\mathbb{N}}$ the security
parameter, e.g. $\lambda=128$, and ${\sf{negl}}(\lambda)$ the set of
negligible functions in $\lambda$. A positive-valued function
$\varepsilon(\lambda)$ belongs to ${\sf{negl}}(\lambda)$ if for every $c>0$,
there exists a $\lambda_{0}\in{\mathbb{N}}$ such that
$\varepsilon(\lambda)<1/\lambda^{c}$ for all $\lambda>\lambda_{0}$. We use
${\sf{poly}}(\lambda)$ for the set of polynomials in $\lambda$.

Before introducing the notation of a committed PIR scheme, we discuss the
basic PIR and its performance metrics below.

###  2.2 Private Information Retrieval

A (replicated) PIR scheme has $k$ servers, each of which stores the data
${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})$, and one client, who is interested in
retrieving $x_{i}$ for some $i\in[n]$.

######  Definition 1 (PIR)

A $k$-server $n$-dimensional PIR scheme $\Pi_{0}$ over a field ${\mathbb{F}}$
consists of three algorithms $(\sf{QueriesGen},\sf{AnswerGen},\sf{Extract})$
defined as follows.

  * •

$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}(n,k,i)$:
run by the client, this randomized algorithm takes as input $n>1$, $k\geq 1$,
an index $i\in[n]$, and outputs $k$ queries to be sent to $k$ servers and an
auxiliary information ${\sf{aux}}$.

  * •

$a_{j}\leftarrow{\sf{AnswerGen}}({\bm{x}},q_{j})$: run by a server, this
deterministic algorithm takes as input the data ${\bm{x}}\in{\mathbb{F}}^{n}$,
the query $q_{j}$, and outputs an answer $a_{j}$ to be sent to the client.

  * •

$\\{x_{i}\\}\leftarrow{\sf{Extract}}\big{(}n,i,\\{a_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
run by the client, this deterministic algorithm takes as input $n$, $i$, the
auxiliary information ${\sf{aux}}$, the answers from all $k$ servers, and
outputs $x_{i}$.

A PIR scheme is called linear if each answer $a_{j}$ is a linear combination
of ${\bm{x}}$. We define below the correctness and privacy of a PIR scheme.

######  Definition 2 (Correctness of PIR)

The $k$-server $n$-dimensional PIR scheme defined in Definition 1 is correct
if for any $i\in[n]$, ${\bm{x}}\in{\mathbb{F}}^{n}$,
$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}(n,i)$,
and $a_{j}\leftarrow{\sf{AnswersGen}}({\bm{x}},q_{j})$, $j\in[k]$, it holds
that

${\sf{Extract}}\big{(}n,i,\\{a_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}=x_{i}.$

######  Definition 3 (Privacy of PIR)

The $k$-server $n$-dimensional PIR scheme defined in Definition 1 is
(unconditionally) $t$-private if no collusion of up to $t$ servers can learn
any information about $i$, or more formally, for any $i,i^{\prime}\in[n]$, and
any subset $T\subsetneq[k]$ of size $|T|\leq t$, the distributions of
${\sf{QueriesGen}}_{T}(n,k,i)$ and ${\sf{QueriesGen}}_{T}(n,k,i^{\prime})$ are
identical, where ${\sf{QueriesGen}}_{T}(n,k,i)$ denotes the concatenation of
the $|T|$ output queries $\\{q_{j}\\}_{j\in T}$ generated by
${\sf{QueriesGen}}(n,k,i)$.

###  2.3 Communication and Computation Costs of PIR

The efficiency of a PIR scheme can be measured based on its communication and
computation costs. We first discuss the communication cost, which can be
formally defined as follows.

######  Definition 4 (Communication Cost of PIR)

The communication cost of a PIR scheme $\Pi_{0}$ over a field $\mathbb{F}$
given in Definition 1 is defined as

${\sf{comm}}(\Pi_{0})={\sf{up}}(\Pi_{0})+{\sf{down}}(\Pi_{0})\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\max_{i}\sum_{j\in[k]}|q_{j}|+\max_{i}\sum_{j\in[k]}|a_{j}|,$

where $|q_{j}|$ and $|a_{j}|$ denote the sizes (in field elements) of $q_{j}$
and $a_{j}$. The first term is the upload cost whereas the second is the
download cost.

For instance, in the aforementioned CKGS scheme [3], to represent a random
subset of $\\{1,2,\ldots,n\\}$, the client must use a vector of $n$ bits,
which means that the upload cost is $kn$ bits. Straightforward generalizations
of this scheme to $k>2$ servers (see, e.g. [19]) require an upload cost of
$kn$ ${\mathbb{F}}$-elements, which is already significant for large $n$. The
main goal of the majority of early works on PIR was to optimize the
communication cost. The lowest known communication cost, namely,
$O(kn^{1/d})$, for any $d\geq 1$, was achieved in the work of Woodruff and
Yekhanin [17]. Their idea is to transform the PIR problem into the secret
sharing problem while representing an index $i\in\\{1,2,\ldots,n\\}$ by a
vector of length $O(n^{1/d})$ of Hamming weight $d$. We refer to this as the
WY scheme.

Download Rate. Another approach to reduce the communication cost is to
optimize the download cost, assuming that the data items are of large size and
hence the upload cost will be overshadowed by the download cost (see, e.g. Sun
and Jafar [20]). More precisely, one can aim for maximizing the download rate,
defined as $\max_{i\in[n]}\frac{|x_{i}|}{\sum_{j\in[k]}|a_{j}|}$, which is the
ratio of the size of the desirable data to the total amount of data downloaded
by the client. Note that in the CKGS scheme, as the client downloads $k$ field
elements from $k$ servers to recover one element, the download rate is $1/k$,
which is quite small. PIR schemes such as BE [18] can achieve an
asymptotically optimal rate of $(k-1)/k$.

Computation Cost. The computation cost of a PIR scheme typically consists of
the computation time required by the client in generating the request and in
recovering the desired data $x_{i}$, and the computation time required by the
servers in producing the answers (taking the average or maximum among all
servers). In general, as the client often has low computational capacity, its
computation load, ideally, should be much less than that of the servers.

###  2.4 Committed Private Information Retrieval

Apart from the large amount of research aiming for optimizing the upload or
the download costs of a PIR scheme, there have also been a number of proposals
in the literature that seek to extend the basic setting of the PIR problem
(see, e.g. [21] for a survey). In the scope of this work, we are interested in
the verifiablity, accountability, and Byzantine-robustness of a PIR scheme.

A $k$-server PIR scheme is $v$-verifiable if the client can verify the
correctness of the retrieved $x_{i}$ even when $v\leq k$ servers are colluding
and try to fool the client by sending manipulated data. A scheme is
$a$-accountable if the client can identify all servers that sent incorrect
data when at most $a\leq k$ servers did so. A scheme is $b$-Byzantine-robust
if the client can recover the correct desired item $x_{i}$ when at most $b<k$
servers sent incorrect data. It is clear that Byzantine-robustness implies
accountability, which in turn implies verifiability. The converse is not true.
However, it seems that a $b$-Byzantine-robust scheme can be obtained from a
$b$-accountable scheme by increasing the number of servers communicated to
obtain extra data for recovery (discarding the data received from identified
malicious servers). Readers who are familiar with coding theory may notice
that the concepts of verifiability, accountability, and Byzantine-robustness
defined above correspond to the classical concepts of error detection, error-
location identification, and error correction, respectively, in the study of
channel coding.

Following the notations of [12], we consider three types of participants: a
data owner333In PIR’s original setting, the servers are (implicitly) identical
to the data owner. With the ubiquity of cloud computing and the various
benefits they offer, outsourcing storage/computing tasks to hired servers has
become the trend. Thus, it is more practical to explicitly separate the data
owner and the storage servers., $k$ servers $S_{1},\ldots,S_{k}$, and a
client. The data owner owns the data ${\bm{x}}$. Although treated as a single
trusted entity in theory, the data owner may also consist of multiple
decentralized entities, e.g. a blockchain, which is maintained by a large
number of miners. Although each individual miner should not be trusted, the
whole miner group are collectively trusted to produce valid commitments to the
data, i.e., the block headers or the Merkle roots of transactions inside the
block headers. The servers, on the other hand, are considered untrusted.

We formally define the Committed Private Information Retrieval (Com-PIR)
scheme in Definition 5. Compared to the basic PIR (see Definition 1), we also
include one more dimension, $m$, to explicitly include the size of each data
item.

######  Definition 5 (Com-PIR)

A $k$-server $m\times n$-dimensional committed PIR scheme $\Pi$ over a field
$\mathbb{F}$ consists of six algorithms defined as follows.

  * •

${\sf{pp}}\leftarrow{\sf{Setup}}(1^{\lambda},k,m,n)$: run by the data owner or
a trusted setup444In practice, a trusted setup can be run by a group of many
participants (the power-of-$\tau$ ceremony [22]), and as long as one person
discards their piece of data, the secret key used in the setup remains secret
and unrecoverable), this randomized algorithm takes as input $\lambda$,
$k,m,n$, where $\lambda$ is the security parameter, $k$ is the number of
servers, $m$ is the size of each data item, $n$ is the number of data items,
and outputs a public parameter ${\sf{pp}}$ known to everyone.

  * •

$C(\bm{x})\leftarrow{\sf{CommitmentGen}}({\sf{pp}},{\bm{x}})$: run by the data
owner, this deterministic algorithm takes as input the public parameter and
the data ${\bm{x}}\in\mathbb{F}^{m\times n}$ and outputs the commitment
$C(\bm{x})$.

  * •

$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$:
run by the client, this randomized algorithm takes as input the public
parameter, $k$, $m$, $n$, $i\in[n]$, and outputs $k$ queries to be sent to $k$
servers and an auxiliary information ${\sf{aux}}$.

  * •

$a_{j}\leftarrow{\sf{AnswerGen}}({\sf{pp}},{\bm{x}},q_{j})$: run by a server,
this deterministic algorithm takes as input the public parameter, the data
${\bm{x}}$, the query $q_{j}$, and outputs an answer $a_{j}$ to be sent to the
client.

  * •

$w_{j}\leftarrow{\sf{WitnessGen}}({\sf{pp}},{\bm{x}},q_{j})$: run by a server,
this deterministic algorithm takes as input the public parameter, the data
${\bm{x}}$, and the query $q_{j}$, and outputs a witness $w_{j}$ to be sent to
the client.

  * •

$\\{x_{i},\perp\\}\leftarrow{\sf{Extract}}\big{(}{\sf{pp}},C,m,n,i,\\{a_{j},w_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
run by the client, this deterministic algorithm takes as input the public
parameter, a commitment $C$, $m$, $n$, $i\in[n]$, the answers and witnesses
from all servers, the auxiliary information ${\sf{aux}}$, and outputs either
$x_{i}$ (successful) or $\perp$ (unsuccessful). Note that $x_{i}$ denotes the
$i$th column of the matrix ${\bm{x}}$.

A Com-PIR works as follows. First, the data owner or a trusted setup generates
the public parameter ${\sf{pp}}$, which is available to everyone. Next, the
data owner generates the commitment $C(\bm{x})$, which is made publicly
available to everyone, e.g. by being embedded into a block header in a
blockchain. The client, who wants to retrieve $x_{i}$ privately, generates and
sends queries to all servers. The servers generate and send the answers and
the witnesses of the answers back to the client. Finally, the client recovers
$x_{i}$ and also performs the verification of the result using the commitment
and the witnesses. The correctness, privacy, and verifiability of a Com-PIR
scheme are formally defined below.

######  Definition 6 (Correctness of Com-PIR)

The $k$-server $m\times n$-dimensional Com-PIR scheme defined in Definition 5
is correct if the client can recover $x_{i}$ when all servers are honest, or
more formally, for any $i\in[n]$, ${\bm{x}}\in\mathbb{F}^{m\times n}$, and
${\sf{pp}}\leftarrow{\sf{Setup}}(1^{\lambda},k,m,n)$, and
$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$,
and $a_{j}\leftarrow{\sf{AnswersGen}}({\sf{pp}},{\bm{x}},q_{j})$,
$w_{j}\leftarrow{\sf{WitnessGen}}({\sf{pp}},{\bm{x}},q_{j})$, $j\in[k]$, it
holds that

${\sf{Extract}}\big{(}C(\bm{x}),m,n,i,\\{a_{j},w_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}=x_{i}.$

######  Definition 7 (Privacy of Com-PIR)

The $k$-server $m\times n$-dimensional Com-PIR scheme defined in Definition 5
is (unconditionally) $t$-private if no collusion of up to $t$ servers can
learn any information about $i$, or more formally, for any
$i,i^{\prime}\in[n]$, and any subset $T\subsetneq[k]$ of size $|T|\leq t$, the
distributions of ${\sf{QueriesGen}}_{T}({\sf{pp}},k,m,n,i)$ and
${\sf{QueriesGen}}_{T}({\sf{pp}},k,m,n,i^{\prime})$ are identical, where
${\sf{QueriesGen}}_{T}({\sf{pp}},k,m,n,i)$ denotes the concatenation of the
$|T|$ queries $\\{q_{j}\\}_{j\in T}$ output by
${\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$.

The verifiability property of a Com-PIR is defined through the notion of a
security experiment, in which an adversary ${\mathcal{A}}$ controls a group of
Byzantine servers $\\{S_{j}\\}_{j\in B}$, $B\subseteq[k]$, knows the data
${\bm{x}}$, the index $i$ (which means the privacy can be lost), and crafts
the answers $\\{\hat{a}_{j}\\}_{j\in B}$ after receiving the queries
$\\{q_{j}\\}_{j\in B}$. The goal of the adversary is to make the client accept
an output $\hat{x}_{i}\notin\\{x_{i},\perp\\}$.

######  Definition 8 (Security Experiment for Verifiability)

The Com-PIR sche-me $\Pi$ defined in Definition 5 is $v$-verifiable if for any
probabilistic polynomial time (PPT) adversary ${\mathcal{A}}$, there exists a
negligible function $\varepsilon(\lambda)\in{\sf{negl}}(\lambda)$ such that
for any $i\in[n]$, any ${\bm{x}}\in\mathbb{F}_{q}^{m\times n}$, and any subset
$B\subseteq[k]$, $|B|\leq v$, it holds that

${\sf{Pr}}\big{[}{\sf{EXP}}_{{\mathcal{A}},\Pi}(k,m,n,{\bm{x}},i,B)=1\big{]}\leq\varepsilon(\lambda),$

where the security experiment
${\sf{EXP}}_{{\mathcal{A}},\Pi}(k,m,n,{\bm{x}},i,B)$ between an adversary and
a challenger is described as follows.

  * •

The challenger picks
$({\sf{sk}},{\sf{pp}})\leftarrow{\sf{Setup}}(1^{\lambda},k,m,n)$ and gives
${\sf{pp}}$ to ${\mathcal{A}}$.

  * •

The adversary picks an ${\bm{x}}\in\mathbb{F}_{q}^{m\times n}$, an $i\in[n]$,
and a set $B\subseteq[k]$, $|B|\leq v$, and gives ${\bm{x}}$, $i$, and $B$ to
the challenger.

  * •

The challenger generates
$C(\bm{x})\leftarrow{\sf{CommitmentGen}}({\sf{pp}},{\bm{x}})$ and
$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$
$\leftarrow{\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$ and gives $\\{q_{j}\\}_{j\in
B}$ to ${\mathcal{A}}$.

  * •

The adversary crafts and gives $|B|$ answers and witnesses to the challenger

$\\{\hat{a}_{j},\hat{w}_{j}\\}_{j\in
B}\leftarrow{\mathcal{A}}({\sf{pp}},k,\mathbf{x},i,B,\\{q_{j}\\}_{j\in B}).$

  * •

The challenger computes $\\{a_{j}\\}_{j\in[k]\setminus
B}\leftarrow{\sf{AnswerGen}}({\sf{pp}},{\bm{x}},\\{q_{j}\\}_{j\in[k]\setminus
B})$ and $\\{w_{j}\\}_{j\in[k]\setminus
B}\leftarrow{\sf{WitnessGen}}({\sf{pp}},{\bm{x}},\\{q_{j}\\}_{j\in[k]\setminus
B})$.

  * •

The challenger runs the extraction algorithm

$\hat{x}_{i}\leftarrow{\sf{Extract}}\big{(}{\sf{pp}},C(\bm{x}),m,n,i,\\{\hat{a}_{j},\hat{w}_{j}\\}_{j\in
B},\\{a_{j},w_{j}\\}_{j\in[k]\setminus B},{\sf{aux}}\big{)}.$

  * •

If $\hat{x}_{i}\notin\\{x_{i},\perp\\}$ then set
${\sf{EXP}}_{{\mathcal{A}},\Pi}(k,m,n,{\bm{x}},i,B)=1$, and $0$, for
otherwise.

Note that to allow accountability and Byzantine-robustness for Com-PIR, one
can include a set $B\subseteq[k]$ in the output of the algorithm
${\sf{Extract}}(\cdot)$ to list identified Byzantine servers and then define
corresponding security experiments. We omit the details and focus on
verifiability only.

##  3 A Generic Construction of $k$-Verifiable Committed Private Information
Retrieval Schemes

We propose a generic construction for $k$-verifiable committed PIR schemes
based on linear map commitment schemes and linear PIR schemes. The key idea is
for the client to privately retrieve both $x_{i}$ and it hash $h_{i}$ using
the same PIR scheme, where the correctness of the hash can be guaranteed by
the linear map commitment. The client then verifies if the hash matches the
data in the verification step. We first discuss the linear map commitment.

###  3.1 Linear Map Commitments

An $n$-dimensional linear map commitment allows a prover to first commit to a
vector ${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})$ and then prove to a verifier that
a linear combination of $x_{i}$’s is correct, i.e. consistent with the
commitment. We formally define the linear map commitment schemes below,
following [13], [23].

######  Definition 9 (Linear Map Commitments)

An $n$-dimensional linear map commitment (LMC) scheme $\Lambda$ over a field
$\mathbb{F}$ consists of four algorithms defined as follows.

  * •

${\sf{pp}}\leftarrow{\sf{Setup}}(1^{\lambda},n;\omega)$: this randomized
algorithm takes as input $\lambda$, $n$, and $\omega$, where $\lambda$ is the
security parameter, $n$ is the number of data items, $\omega$ is a random
tape, and outputs a public parameter ${\sf{pp}}$ known to all parties.

  * •

$C\leftarrow{\sf{CommitmentGen}}({\sf{pp}},{\bm{x}})$: run by the prover, this
deterministic algorithm takes as input the public parameter ${\sf{pp}}$ and
the data ${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})$ $\in\mathbb{F}^{n}$ and outputs
the commitment $C=C(\bm{x})$.

  * •

$w_{j}\leftarrow{\sf{WitnessGen}}({\sf{pp}},{\bm{x}},{\bm{c}},y)$: run by a
prover, this deterministic algorithm takes as input the public parameter
${\sf{pp}}$, the data ${\bm{x}}=(x_{1},x_{2},\ldots,x_{n})$
$\in\mathbb{F}^{n}$, the vector of coefficients
${\bm{c}}=(c_{1},c_{2},\ldots,c_{n})\in\mathbb{F}^{n}$, a value
$y\in\mathbb{F}$, and outputs a witness $w$ that proves that
$y={\bm{c}}\cdot{\bm{x}}=\sum_{j\in[n]}c_{j}x_{j}$.

  * •

$\\{0,1\\}\leftarrow{\sf{Verify}}\big{(}{\sf{pp}},C,{\bm{c}},y,w\big{)}$: run
by the verifier, this deterministic algorithm takes as input the public
parameter ${\sf{pp}}$, a commitment $C$, a coefficient vector ${\bm{c}}$, an
element $y$, a witness $w$, and outputs either 1 or 0 to accept or reject that
$y={\bm{c}}\cdot{\bm{x}}$, respectively.

There have been a few different constructions of LMC and variants/extensions
recently proposed in the literature [14], [13], [23], [15], [16]. The LMC in
[14] is based on a ring and may not work immediately with a linear PIR scheme,
which is often based on a finite field. We use in this work the version of LMC
introduced in the work of Lai and Malavolta [13], [23], which is the most
straightforward to implement and sufficient for our purpose. We refer to it as
the Lai-Malavolta (LM) linear map commitment. This LMC is based on an
observation that the inner product of ${\bm{c}}$ and ${\bm{x}}$ is equal to
the coefficient of $z^{n+1}$ in the product of the polynomials
$f_{{\bm{c}}}(z)\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\sum_{j\in[n]}c_{j}z^{n+1-j}$
and
$f_{{\bm{x}}}(z)\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\sum_{j\in[n]}x_{j}z^{j}$.

Setup$(1^{\lambda},n;\omega)$
${\sf{BG}}\leftarrow{\sf{BGGen}}(1^{\lambda};\omega)$
where
${\sf{BG}}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}(p,\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},G_{1},G_{2},e)$
$\alpha\leftarrow{\mathbb{Z}}_{p}$
${\sf{pp}}=\big{(}{\sf{BG}},\\{G_{1}^{\alpha^{j}}\\}_{j\in[n]},\\{G_{2}^{\alpha^{j}}\\}_{j\in[2n]\setminus\\{n+1\\}}\big{)}$
return pp

CommitmentGen$({\sf{pp}},{\bm{x}})$ return
$C\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\prod_{j\in[n]}\big{(}G_{1}^{\alpha^{j}}\big{)}^{x_{j}}$

WitnessGen$({\sf{pp}},{\bm{x}},{\bm{c}})$
$w\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\prod_{j\in[n]}\prod_{j^{\prime}\in[n]\setminus\\{j\\}}\big{(}G_{2}^{\alpha^{n+1+j-j^{\prime}}}\big{)}^{c_{j}x_{j^{\prime}}}$
return  $w$

Verify$({\sf{pp}},C,{\bm{c}},y,w)$
$b_{0}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\big{(}y\in{\mathbb{Z}}_{p}\big{)}$
$b_{1}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\begin{pmatrix}e\bigg{(}C,\prod_{j\in[n]}\big{(}G_{2}^{\alpha^{n+1-j}}\big{)}^{c_{j}}\bigg{)}\\\
=e\bigg{(}\big{(}G_{1}^{\alpha}\big{)}^{y},G_{2}^{\alpha^{n}}\bigg{)}e(G_{1},w)\end{pmatrix}$
return $b_{0}$ AND $b_{1}$

Algorithm 1 The Lai-Malavolta linear map commitment scheme [13, 23].

Lai-Malavolta Linear Map Commitment (Algorithm 1). ${\sf{Setup}}$ takes as
input the security parameter $\lambda$, the vector length $n$, and a (private)
random tape $\omega$ and outputs the public parameter ${\sf{pp}}$. First,
BGGen generates a bilinear group BG, which includes a prime $p$, three cyclic
groups $\mathbb{G}_{1}$, $\mathbb{G}_{2}$, $\mathbb{G}_{T}$ of order $p$
(written multiplicatively), where $G_{1}$ and $G_{2}$ are generators of
$\mathbb{G}_{1}$ and $\mathbb{G}_{2}$, respectively, and
$e\colon\mathbb{G}_{1}\times\mathbb{G}_{2}\to\mathbb{G}_{T}$ is a pairing
satisfying the following properties:

  * •

$e$ is efficiently computable,

  * •

$e$ is non-degenerate: $e(G_{1},G_{2})\neq 1_{\mathbb{G}_{T}}$,

  * •

$e$ is bilinear: $e(A^{x},B^{y})=e(A,B)^{xy}$, for every $A\in\mathbb{G}_{1}$,
$B\in\mathbb{G}_{2}$, and $x,y\in{\mathbb{Z}}$.

Next, a random element $\alpha$ is sampled from $\mathbb{Z}_{p}$. The output
${\sf{pp}}$ consists of the bilinear group,
$\\{G_{1}^{\alpha^{j}}\\}_{j\in[n]}$, and
$\\{G_{2}^{\alpha^{j}}\\}_{j\in[2n]\setminus\\{n+1\\}}$. The commitment of
${\bm{x}}$ and the witness for a linear combination $y={\bm{c}}\cdot{\bm{x}}$
are computed as illustrated in Algorithm 1 (note that $y$ is not used in
${\sf{WitnessGen}}$ in this scheme). Finally, ${\sf{Verify}}$ checks if $y$ is
an element in $\mathbb{Z}_{p}$ and verify if the first pairing is equal to the
product of the other two. It accepts that $y={\bm{c}}\cdot{\bm{x}}$ if both
checks pass.

Computational complexity of Lai-Malavolta LMC. The LMC scales linearly for the
verifier and quadratically in $n$ for the server. More specifically, in our
implementation, the prover performs $O(n)$ elliptic curve operations and
$O(n^{2})$ field operations (cheaper) per linear combination. The verifier
performs $O(n)$ elliptic curve operations and three pairings per linear
combinations. Note that elliptic curve pairing $e(G,H)$ is more expensive than
exponentiation $G^{x}$, which is more expensive than product $GH$, which in
turn is more expensive than operations on finite fields. The Lai-Malavolta LMC
requires a trusted setup and a linear-size public parameter, but provides a
constant-size commitment and witness. Others constructions of LMC bring in
different trade-offs, e.g. no trusted setup but $\log$-size
commitment/witness, and additional properties [14, 15, 16].

###  3.2 A Generic Construction of Com-PIR

We now introduce a generic construction that combines an $n$-dimensional LMC
and a linear $k$-server $m\times n$-dimensional PIR to produce a
$k$-verifiable Com-PIR (see Fig. 2 for an illustration). The construction
first applies a cryptographic hash function $h^{*}(\cdot)$ followed by a
modulo operation to each column of the database ${\bm{x}}$ to achieve
$h_{j}=h^{*}(x_{j})\pmod{p}$, where $x_{j}$ denotes the $j$th column of
${\bm{x}}\in\mathbb{F}^{m\times n}=\mathbb{Z}_{p}^{m\times n}$. It then
applies an LMC to the vector
${\bm{h}}=(h_{1},h_{2},\ldots,h_{n})\in\mathbb{F}^{n}$. The client performs
PIR requests for both $x_{i}$ and $h_{i}$. As the correctness of the received
$h_{i}$ is guaranteed by the LMC, the verification
$h_{i}\overset{?}{=}h(\hat{x}_{i})$ is reliable.

Figure 2: Illustration of a generic construction of Com-PIR using an LMC and a
linear PIR. When using SHA3-256 and the BLS12-381, each $x_{j}$ is first
hashed by SHA3-256 to generate a 256-bit digest $h^{*}(x_{j})$, which in turn
is taken modulo $p$, a 255-bit prime, to produce $h_{j}\in\mathbb{Z}_{p}$.
This only reduces the security of SHA3-256 by at most one bit. The modulo
operation is necessary to turn the hashes into valid input to the LMC. The LMC
computation is carried out over the $n$ hashes only, making it independent of
the data item size $m$.

A Generic Construction of Com-PIR. Let $\Pi$ be the target Com-PIR scheme,
which will be constructed based on an LMC and a linear PIR scheme. We use the
‘.’ sign to refer to the algorithm of each scheme, e.g.
PIR.${\sf{QueriesGen}}()$.

  * •

${\sf{pp}}\leftarrow\Pi.{\sf{Setup}}(1^{\lambda},k,m,n)$: The algorithm
invokes $\text{LMC}.{\sf{Setup}}(1^{\lambda},n)$, the setup algorithm of the
LMC.

  * •

$C\leftarrow\Pi.{\sf{CommitmentGen}}({\sf{pp}},{\bm{x}})$: The algorithm first
computes $h_{j}=h^{*}(x_{j})\pmod{p},j\in[n]$, where $h^{*}(\cdot)$ is a
cryptographic hash function, e.g. SHA3-256, and $p$ is the order of the cyclic
groups as part of ${\sf{pp}}$. It then computes
$C=C({\bm{h}})\leftarrow\text{LMC}.{\sf{CommitmentGen}}({\sf{pp}},{\bm{h}})$,
where ${\bm{h}}=(h_{1},h_{2},\ldots,h_{n})$.

  * •

$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow\Pi.{\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$:
The algorithm invokes the corresponding PIR algorithm, namely,
$\text{PIR}.{\sf{QueriesGen}}({\sf{pp}},k,m,n,i)$.

  * •

$a_{j}\leftarrow\Pi.{\sf{AnswersGen}}({\sf{pp}},{\bm{x}},q_{j})$: The
algorithm invokes the corresponding PIR algorithm on both ${\bm{x}}$ and
${\bm{h}}$, i.e.
$a_{j}({\bm{x}})\leftarrow\text{PIR}.{\sf{AnswersGen}}({\sf{pp}},{\bm{x}},q_{j})$
and
$a_{j}({\bm{h}})\leftarrow\text{PIR}.{\sf{AnswersGen}}({\sf{pp}},{\bm{h}},q_{j})$,
and outputs
$a_{j}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}(a_{j}({\bm{x}}),a_{j}({\bm{h}}))$.
Note that each server can compute ${\bm{h}}$ from ${\bm{x}}$ on its own just
once.

  * •

$w_{j}\leftarrow\Pi.{\sf{WitnessGen}}({\sf{pp}},{\bm{x}},q_{j})$: The
algorithm first converts $q_{j}$ into a coefficient vector
${\bm{c}}(q_{j})\in\mathbb{Z}_{p}^{n}$ such that
$a_{j}({\bm{h}})={\bm{c}}(q_{j})\cdot{\bm{h}}$. Then, it invokes
$w_{j}\leftarrow\text{LMC}.{\sf{WitnessGen}}({\sf{pp}},{\bm{h}},{\bm{c}},y)$,
where
$y\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}{\bm{c}}\cdot{\bm{h}}$.

  * •

$\\{x_{i},\perp\\}\leftarrow\Pi.{\sf{Extract}}\big{(}{\sf{pp}},C,m,n,i,\\{a_{j},w_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
The algorithm first parses each answer $a_{j}$ as
$\big{(}a_{j}({\bm{x}}),a_{j}({\bm{h}})\big{)}$. Next, it converts $q_{j}$
into a coefficient vector ${\bm{c}}(q_{j})\in\mathbb{Z}_{p}^{n}$ such that
$a_{j}({\bm{h}})={\bm{c}}(q_{j})\cdot{\bm{h}}$. Then, it verifies
$a_{j}({\bm{h}})$ by running
$\text{LMC}.{\sf{Verify}}({\sf{pp}},C,{\bm{c}}(q_{j}),a_{j}({\bm{h}}),w_{j}),j\in[k]$.
If the verification fails for $j\in[k]$, it returns $\perp$. Otherwise, it
calls
$\text{PIR}.{\sf{Extract}}\big{(}n,i,\\{a_{j}({\bm{h}})\\}_{j\in[k]},{\sf{aux}}\big{)}$
and
$\text{PIR}.{\sf{Extract}}\big{(}n,i,\\{a_{j}({\bm{x}})\\}_{j\in[k]},{\sf{aux}}\big{)}$
to obtain $\hat{h}_{i}$ and $\hat{x}_{i}$. It then performs the final hash
verification $h(\hat{x}_{i})\overset{?}{=}\hat{h}_{i}$ and returns
$\hat{x}_{i}$ if passes and $\perp$ if fails.

Note that in the generic construction above, the PIR scheme is applied to
${\bm{x}}\in\mathbb{Z}_{p}^{m\times n}$ instead of $\mathbb{Z}_{p}^{n}$ as in
Definition 1. This can be done in a straightforward manner in which the PIR
scheme on $\mathbb{Z}_{p}^{n}$ is applied repeatedly $m$ times to the $m$ rows
of ${\bm{x}}\in\mathbb{Z}_{p}^{m\times n}$ using the same set of queries. The
communication and computation costs of a Com-PIR scheme based on the generic
construction can be calculated easily based on the costs of the underlying PIR
and LMC. Note that the LMC doesn’t depend on $m$. Although the final hash
check $h(\hat{x}_{i})\overset{?}{=}\hat{h}_{i}$ depends on $m$ because
$|\hat{x}_{i}|=m$, $h(\cdot)$ is very efficient and its cost is negligible.

######  Lemma 1 (Correctness/Privacy)

The Com-PIR constructed by the generic construction is correct and $t$-private
if the underlying LMC scheme is correct and the underlying PIR scheme is both
correct and $t$-private.

Proof.  The correctness of the constructed Com-PIR scheme can be proved in a
straightforward manner, implied directly from the correctness of the
underlying LMC and PIR schemes. The privacy of the Com-PIR follows from the
privacy of the underlying PIR scheme because the queries sent from the client
are identical to those in the original PIR scheme.

Next, we prove (see Appendix A) that the generic construction generates a
$k$-server $m\times n$-dimensional Com-PIR that is $k$-verifiable, assuming
that the Lai-Malavolta LMC is used in conjunction with an arbitrary linear PIR
scheme.

######  Lemma 2 (Verifiability)

Let $k,m,n\in{\sf{poly}}(\lambda)$ and $1/p\in{\sf{negl}}(\lambda)$. Then the
$k$-server $m\times n$-dimensional Com-PIR using the Lai-Malavolta LMC is
$k$-verifiable in the generic bilinear group model.

##  4 Three Case Studies

We discuss in detail how the generic construction proposed in Section 3.2
performs for the Lai-Malavolta LMC and the three representative linear PIR
schemes with respect to the communication and computation costs.

Chor-Kushilevitz-Goldreich-Sudan (CKGS) Scheme ([3]). This is a linear
2-server $n$-dimensional PIR scheme working over an arbitrary finite field
${\mathbb{F}}$. We also use 2-CKGS to refer to this scheme, while using
$k$-CKGS to refer to its straighforward generalization to the $k$-server
setting (see [19, Section 3.2.1]).

  * •

$\big{(}\\{q_{1},q_{2}\\},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}(n,2,i)$:
the algorithm first picks a random subset $J\subseteq[n]$ and let
$q_{1}\in{\mathbb{F}}^{n}$ be the characteristic vector for $J$, i.e., $q_{1}$
has a ‘1’ at the the $j$th component if $j\in J$, and $0$ otherwise. Next,
$q_{2}$ is obtained from $q_{1}$ by flipping its $i$th component ($0\to 1$ or
$1\to 0$). Then either $e_{i}=q_{1}-q_{2}$ or $e_{i}=q_{2}-q_{1}$, where
$e_{i}\in\mathbb{F}^{n}$ is the unit vector with a ‘1’ at the $i$th component.
Set ${\sf{aux}}=1$ or ${\sf{aux}}=2$, respectively.

  * •

$a_{j}\leftarrow{\sf{AnswerGen}}({\bm{x}},q_{j})$: The algorithm returns
$a_{j}=q_{j}\cdot{\bm{x}}$.

  * •

$\\{x_{i}\\}\leftarrow{\sf{Extract}}\big{(}n,i,\\{a_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
The algorithm returns $a_{1}-a_{2}$ if ${\sf{aux}}=1$ or $a_{2}-a_{1}$ if
${\sf{aux}}=2$.

The CKGS scheme and the Lai-Malavolta LMC scheme work together in a
straightforward manner.

###### Example 1

We consider in Fig. 1 a toy example of a 2-server $m\times 5$-dimensional Com-
PIR based on an LMC and CKGS PIR scheme [3] (see Fig. 1 for an illustration).
The client, who wants $x_{1}$, picks a random subset
$J=\\{1,3,4\\}\subseteq[5]$ and creates the corresponding queries
$q_{1}=(1,0,1,1,0)$ and $q_{2}=(0,0,1,1,0)$. Server 1, if acting honestly,
sends back the answers $a_{1}({\bm{h}})=h_{1}+h_{3}+h_{4}$,
$a_{1}({\bm{x}})=x_{1}+x_{3}+x_{4}$, and the witness $w_{1}(a_{1}({\bm{h}}))$,
which allows the client to verify the correctness of $a_{1}({\bm{h}})$. Server
2, if acting honestly, sends back the answers $a_{2}({\bm{h}})=h_{3}+h_{4}$,
$a_{2}({\bm{x}})=x_{3}+x_{4}$, and the witness $w_{2}(a_{2}({\bm{h}}))$, which
allows the client to verify the correctness of $a_{2}({\bm{h}})$. The client,
knowing the LMC commitment $C({\bm{h}})$, can verify the correctness of both
$a_{1}({\bm{h}})$ and $a_{2}({\bm{h}})$ and then extract the (verifiably
correct) $\hat{h}_{1}=a_{1}({\bm{h}})-a_{2}({\bm{h}})$. It can also extract
$\hat{x}_{1}=a_{1}({\bm{x}})-a_{2}({\bm{x}})$ and verify the correctness of
the result by performing a hash verification
$h(\hat{x}_{1})\overset{?}{=}\hat{h}_{1}$.

Woodruff-Yekhanin (WY) Scheme ([17]). This is a linear $k$-server
$n$-dimensional PIR scheme working over an arbitrary finite field
${\mathbb{F}}$. See Appendix B for the detail. Note that each server generates
$\ell\in O(n^{1/d})$ linear combinations of ${\bm{x}}$. Although in Algorithm
1, we let the LMC verify just one linear combination of ${\bm{x}}$ for
simplicity, in its original form, Lai-Malavolta LMC can produce a single
witness for and verify multiple linear combinations.

Bitar-El Rouayheb (BE) Scheme ([18]). We present a simplified version of this
scheme (dropping unnecessary properties like universality) in Appendix B (see,
also Goldberg [11]). Note that the LMC is applied on $(k-t)n$ hashes instead
of $n$ like in other schemes.

|  Upload Cost (#$\mathbb{Z}_{p}$-elts) |  Download Rate |  Server (#operations) |  Client (#operations)
---|---|---|---|---
Com-PIR |  $2n$ bits |  $1/2$ |  $mn+$ |  $m+$
(2-CKGS) |  |  |  $n^{2}+$, $n^{2}\times$, $n\boxplus$, $n\boxtimes$ |  $2n\boxplus$, $2n\boxtimes$, $6\boxdot$
Com-PIR |  $kn$ |  $1/k$ |  $mn+$, $mn\times$ |  $km+$
($k$-CKGS) |  |  |  $n^{2}+$, $n^{2}\times$, $n\boxplus$, $n\boxtimes$ |  $kn\boxplus$, $kn\boxtimes$, $3k\boxdot$
Com-PIR |  $k\ell$ |  $1/k$ |  $\ell mn+$, $\ell mnd\times$ |  $mt(k\ell+d^{3}t^{2})+$, $mt(k\ell+d^{3}t^{2})\times$
(WY) |  |  |  $\ell n^{2}+$, $\ell n^{2}\times$, $\ell n\boxplus$, $\ell n\boxtimes$ |  $k\ell n\boxplus$, $k\ell n\boxtimes$, $3k\boxdot$
Com-PIR |  $k(k-t)n$ |  $(k-t)/k$ |  $(k-t)mn+$, $(k-t)mn\times$ |  $k((k-t)(kn+m)+km)+$, $k^{2}((k-t)n+m)\times$
(BE) |  |  |  $(k-t)^{2}n^{2}+$, $(k-t)^{2}n^{2}\times$, $(k-t)n\boxplus$, $(k-t)n\boxtimes$ |  $k(k-t)n\boxplus$, $k(k-t)n\boxtimes$, $3k\boxdot$
Table 1: Comparisons of different Com-PIR schemes with $k$-verifiability. For
the computation costs at each server and client, we count the number of field
additions ‘$+$’ and multiplications ‘$\times$’, elliptic curve additions
‘$\boxplus$’ and multiplications ‘$\boxtimes$’, and pairings ‘$\boxdot$’ in
big-O notation (with $\ell\in O(n^{1/d})$ for the WY-based scheme). The top
sub-row counts the operations on data while the bottom sub-row counts the
operations related to verification. The verification time of the proposed Com-
PIR schemes (mostly) doesn’t depend on the size of the retrieved data $m$ but
on the size of the database $n$ and the number of servers $k$.

Comparison of the three Com-PIR schemes. We compare these schemes based on
their communication and computation complexities (Table 1).

  * •

LM-CKGS: this scheme has the lowest computation time among the three for both
servers and client. The reason is that each server only performs cheap field
additions for the data part and generates LMC witness for a single linear
combination of hashes. The client performs one LMC verification per server.

  * •

LM-WY: although having the lowest upload cost, the computation cost of this
scheme is the highest among the three. The reason is that its running time
also depends on $\ell\in O(n^{1/d})$. See Appendix C for more details.

  * •

LM-BE: this scheme achieves the optimal download rate and has computation cost
lying in between the other two. Computation-wise, the smaller the difference
$k-t$, the lower the running time of both servers and client. The reason is
that the LMC has to run not on $n$ but on $(k-t)n$ hashes.

Comparisons with related works. The work of Zhang-Safavi Naini [12] is the
closest to ours and provides $k$-accountability. Their idea is to apply a
verifiable computing scheme [24] on top of WY [17], followed by several
optimization steps to improve the performance. Originally designed for a
$1\times n$ database ($m=1$), the verification time of their main scheme
$\Gamma_{1}$ is in $O\big{(}kmn^{1/d}\big{)}$, which becomes very slow for
large $m$. Moreover, while our scheme has a constant witness size (from each
server), their witness size is in $O\big{(}mn^{1/d}\big{)}$. All other works
in the literature, to our best knowledge, do not provide $k$-verifiability.
For instance, Ke and Zhang [4] constructed a 2-server PIR scheme that can
(information theoretically) verify the correctness of the result given at most
one malicious server. Zhang and Wang [6] introduced $k$-server PIR schemes
that are privately and publicly $v$-verifiable for $v<k$. These schemes were
also designed for $m=1$. Zhao et al. [5] proposed a construction of verifiable
PIR scheme based on the Learning with Errors problem. The main issue in their
construction is that the server can pass the client’s verification if using
the same incorrect database in generating the answer for the query and the
response to the challenge (see [5, Def. 7]). PIR schemes with Byzantine-
robustness were investigated in [7, 8, 9, 11].

##  5 Experiments & Evaluations

Experiment setup. We implemented three Com-PIR schemes in C using the
libraries GMP 6.2.1, OpenSSL 2022, and blst v.0.3.10. We compiled the code
with GCC 11.3.0 and ran our experiments on Ubuntu 22.04.1 environment (Intel
Core i5-1035G1 CPU @1.00GHz×8, 15GB System memory). The code is available on
GitHub at https://github.com/PIR-PIXR/CPIR.

Evaluations. The LMC component in the Com-PIR schemes incurs an extra
communication/computation overhead on top of the original PIR schemes [3, 17,
18]. However, the LMC communication overhead is only $O(k)$ while the
computation overhead doesn’t grow with $m$, the size of each data item. Hence,
as the size of each data item increases, the LMC overhead becomes smaller and
smaller compared to the computation time of the PIR scheme (see Fig. 3). The
computation time of LM-WY is significantly higher than the other two schemes
(see Fig. 3, Fig. 4), hence consistent with the theoretical analysis presented
earlier. Fig. 4 also demonstrates a trade-off between the download rate and
the computation time for LM-BE: larger $t$ leads to smaller download rate but
cheaper computation. More evaluations of these Com-PIR schemes are in Appendix
C.

Figure 3: The average server and client computation times of LM-CKGS, LM-WY,
and LM-BE for $k=2$, $t=1$, $n=2^{10}$, and
$m\in\\{2^{0},2^{10},2^{12},2^{14},2^{16}\\}$. Figure 4: The average server
and client computation times of LM-CKGS and LM-BE for $n=2^{10}$, $m=2^{12}$,
$k\in\\{3,4,5,6\\}$, and $t=1$ or $k-1$.

##  6 Conclusions

We proposed a modular approach to combine a linear map commitment and a linear
PIR scheme to achieve a $k$-verifiable PIR scheme, which guarantees that the
client will never accept wrong data even in the extreme case when all servers
are malicious. By applying the commitment scheme on hashes of data rather than
on data themselves, the construction is reasonably practical, taking less than
one second to privately retrieve 3MB of data from a database of size 3GB. A
drawback of our approach is that the commitment scheme may incur a significant
computation overhead on top of the PIR scheme if the database consists of a
large number of small-sized items.

## Acknowledgement

We thank Russell W. F. Lai and Liangfeng Zhang for helpful discussions.

## References

  * [1] A. Uribe, “Cyberattack on optus potentially exposes millions of customer accounts; australian telecoms company says mass breach could have exposed birth dates, phone numbers and other personal data,” _The Wall Street journal. Eastern edition_ , 2022.
  * [2] N. Biddle, M. Gray, and S. McEachern, “Public exposure and responses to data breaches in australia: October 2022,” 2022.
  * [3] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” _Journal of the ACM (JACM)_ , vol. 45, no. 6, pp. 965–981, 1998\.
  * [4] P. Ke and L. F. Zhang, “Two-server private information retrieval with result verification,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 408–413.
  * [5] L. Zhao, X. Wang, and X. Huang, “Verifiable single-server private information retrieval from lwe with binary errors,” _Information Sciences_ , vol. 546, pp. 897–923, 2021.
  * [6] L. F. Zhang and H. Wang, “Multi-server verifiable computation of low-degree polynomials,” in _Proceedings of the IEEE Symposium on Security and Privacy (S &P)_, 2022, pp. 596–613.
  * [7] C. Devet, I. Goldberg, and N. Heninger, “Optimally robust private information retrieval,” in _Proceedings of the 21st USENIX Security Symposium_ , 2012, pp. 269–283.
  * [8] E. Y. Yang, J. Xu, and K. H. Bennett, “Private information retrieval in the presence of malicious failures,” in _Proceedings of the 26th Annual International Computer Software and Applications_ , 2002, pp. 805–810.
  * [9] A. Beimel and Y. Stahl, “Robust information-theoretic private information retrieval,” in _Proceedings of the Third International Conference on Security in Communication Networks_ , 2003, pp. 326–341.
  * [10] ——, “Robust information-theoretic private information retrieval,” _Journal of Cryptology_ , vol. 20, pp. 295–321, 2007.
  * [11] I. Goldberg, “Improving the robustness of private information retrieval,” in _2007 IEEE Symposium on Security and Privacy (SP’07)_. IEEE, 2007, pp. 131–148.
  * [12] L. F. Zhang and R. Safavi-Naini, “Verifiable multi-server private information retrieval,” in _Proceedings of the International Conference on Applied Cryptography and Network Security (ANCS)_ , 2014, pp. 62–79.
  * [13] R. W. Lai and G. Malavolta, “Subvector commitments with application to succinct arguments,” in _Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part I 39_. Springer, 2019, pp. 530–560.
  * [14] B. Libert, S. C. Ramanna _et al._ , “Functional commitment schemes: From polynomial commitments to pairing-based accumulators from simple assumptions,” in _43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)_ , 2016.
  * [15] C. Peikert, Z. Pepin, and C. Sharp, “Vector and functional commitments from lattices,” in _Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part III 19_. Springer, 2021, pp. 480–511.
  * [16] M. Campanelli, A. Nitulescu, C. Ràfols, A. Zacharakis, and A. Zapico, “Linear-map vector commitments and their practical applications,” in _International Conference on the Theory and Application of Cryptology and Information Security_. Springer, 2022, pp. 189–219.
  * [17] D. Woodruff and S. Yekhanin, “A geometric approach to information-theoretic private information retrieval,” in _20th Annual IEEE Conference on Computational Complexity (CCC’05)_. IEEE, 2005, pp. 275–284.
  * [18] R. Bitar and S. El Rouayheb, “Staircase-pir: Universally robust private information retrieval,” in _2018 IEEE Information Theory Workshop (ITW)_. IEEE, 2018, pp. 1–5.
  * [19] D. Demmler, A. Herzberg, and T. Schneider, “Raid-pir: practical multi-server pir,” in _Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security_ , 2014, pp. 45–56.
  * [20] H. Sun and S. A. Jafar, “The capacity of robust private information retrieval with colluding databases,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 2361–2370, 2017.
  * [21] S. Ulukus, S. Avestimehr, M. Gastpar, S. A. Jafar, R. Tandon, and C. Tian, “Private retrieval, computing, and learning: Recent progress and future challenges,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 3, pp. 729–748, 2022.
  * [22] V. Nikolaenko, S. Ragsdale, J. Bonneau, and D. Boneh, “Powers-of-tau to the people: Decentralizing setup ceremonies,” _Cryptology ePrint Archive_ , 2022\.
  * [23] R. W. Lai, “Succinct arguments: Constructions and applications,” Ph.D. dissertation, Friedrich-Alexander-Universitaet Erlangen-Nuernberg (Germany), 2022\.
  * [24] C. Papamanthou, E. Shi, and R. Tamassia, “Signatures of correct computation,” in _Theory of Cryptography Conference_. Springer, 2013, pp. 222–242.

## Appendix A: Verifiability Proof of Com-PIR

For simplicity, we consider one linear combination of ${\bm{x}}$ in the
definition below.

######  Definition 10 (Function Binding for LMC)

[13] An LMC over $\mathbb{F}$ is function binding if for any PPT adversary
${\mathcal{A}}$, any positive integer $n\in{\sf{poly}}(\lambda)$, there exists
a negligible function $\varepsilon(\lambda)$ such that

${\sf{Pr}}\left[\begin{array}[]{c|c}y\in\mathbb{F}&\omega\mbox{
}{}{\leftarrow}\vbox{\hbox{\tiny\$}}{}\mbox{ }\\{0,1\\}^{\lambda}\\\ \mbox{
}{\sf{Verify}}(C,{\bm{c}},y,w)=1&\mbox{
}{\sf{pp}}\leftarrow{\sf{Setup}}(1^{\lambda},n;\omega)\\\
\not\exists{\bm{x}}\in\mathbb{F}^{n}\text{ s.t.
}\sum_{j\in[n]}c_{j}x_{j}=y&(C,{\bm{c}},y,w)\leftarrow{\mathcal{A}}({\sf{pp}})\\\
\end{array}\right]\leq\varepsilon(\lambda).$

######  Lemma 3 ([13])

Let $n\in{\sf{poly}}(\lambda)$ and $1/p\in{\sf{negl}}(\lambda)$. Then Lai-
Malavolta LMC is function binding in the generic bilinear group model.

Proof. [Proof of Lemma 2] According to the generic construction, the adversary
wins the security experiment, i.e.,
${\sf{EXP}}_{{\mathcal{A}},\Pi}(k,m,n,{\bm{x}},i,B)=1$, if and only if the
challenger extracts $\hat{x}_{i}\notin\\{x_{i},\perp\\}$. This happens only
when one of the following two independent events occur: either
$\hat{h}_{i}=h_{i}$, i.e., the adversary finds a hash collision
$h(\hat{x}_{i})=h(x_{i})=h_{i}$, or $\hat{h}_{i}\neq h_{i}$ but the adversary
manages to fool $\text{LMC}.{\sf{Verify}}()$ with at least one wrong linear
combination of $h_{i}$’s. Therefore,

$\begin{split}&{\sf{Pr}}[{\sf{EXP}}_{{\mathcal{A}},\Pi}(k,m,n,{\bm{x}},i,B)=1]={\sf{Pr}}[\hat{x}_{i}\neq
x_{i}\wedge h(\hat{x}_{i})=h(x_{i})]\\\ &+{\sf{Pr}}[\text{At least one linear
combination is wrong but still passes LMC.{\sf{Verify}}()}]\\\
&\leq\varepsilon_{1}(\lambda)+\varepsilon_{2}(\lambda)\in{\sf{negl}}(\lambda),\vspace{-5pt}\end{split}$

as both events happen with probabilities negligible in $\lambda$ assuming that
$1/p$ is negligible in $\lambda$ and that the security is considered under the
generic bilinear group model (Lemma 3).

## Appendix B: WY and BE PIR Schemes

Woodruff-Yekhanin (WY) Scheme ([17]). This is a linear $k$-server $n$-dimensi-
onal PIR scheme working over an arbitrary finite field ${\mathbb{F}}$. Let
$1\leq t<k$ and $d=\lfloor(2k-1)/t\rfloor$. Let $\ell\in
O\big{(}n^{1/d}\big{)}$ be the smallest integer satisfying
$\binom{\ell}{d}\geq n$ and $E\colon[n]\to\mathbb{F}^{\ell}$ a 1-to-1 mapping
that maps an index $j\in[n]$ to a vector in $\mathbb{F}^{\ell}$ of Hamming
weight $d$. Each ${\bm{x}}\in\mathbb{F}^{n}$ is encoded by a multivariate
polynomial $F_{{\bm{x}}}({\bm{z}})$, where ${\bm{z}}=(z_{1},\ldots,z_{\ell})$,
defined as follows.

$F_{{\bm{x}}}({\bm{z}})\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\sum_{j\in[n]}x_{j}\prod_{u\in[\ell]\colon
E(j)_{u}=1}z_{u}.\vspace{-5pt}$

Then, $\deg(F)=d$ and $x_{i}=F_{{\bm{x}}}(E(i))$. Fix $k$ distinct elements
$\\{\beta_{j}\\}_{j\in[k]}\subseteq\mathbb{F}_{p}^{*}$.

  * •

$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}(n,k,i)$:
The algorithm picks $t$ random vectors
$\\{v^{(s)}\\}_{s\in[t]}\subseteq\mathbb{F}^{\ell}$ and outputs
$q_{j}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}E(i)+\sum_{s\in[t]}\beta_{j}^{s}v_{s}$
and ${\sf{aux}}=\\{v^{(s)}\\}_{s\in[t]}$.

  * •

$a_{j}\leftarrow{\sf{AnswerGen}}({\bm{x}},q_{j})$: The algorithm computes
$a_{j}=(a_{j,0},a_{j,1},\ldots,a_{j,\ell})$, where
$a_{j,0}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}F_{{\bm{x}}}(q_{j})$
and
$a_{j,u}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\frac{\partial
F_{{\bm{x}}}}{z_{u}}\rvert_{q_{j}}$, $u\in[\ell]$.

  * •

$\\{x_{i}\\}\leftarrow{\sf{Extract}}\big{(}n,i,\\{a_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
The algorithm reconstructs the polynomial
$f(y)\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}F_{{\bm{x}}}\big{(}E(i)+\sum_{s\in[t]}y^{s}v^{(s)}\big{)}$
and outputs $f(0)=F_{{\bm{x}}}(E(i))=x_{i}$. The reconstruction of $f$ is
possible because $\deg(f)\leq dt\leq 2k-1$ while $2k$ linear combinations of
its coefficients, namely,
$\\{f(\beta_{j}),f^{\prime}(\beta_{j})\\}_{j\in[k]}$, can be extracted from
the answers $\\{a_{j}\\}_{j\in[k]}$ and ${\sf{aux}}=\\{v^{(s)}\\}_{s\in[t]}$
as follows. For $j\in[k]$, $f(\beta_{j})=F_{{\bm{x}}}(q_{j})=a_{j,0}$, and

$f^{\prime}(\beta_{j})=\sum_{u\in[\ell]}\frac{\partial F}{\partial
z_{u}}\bigg{\rvert}_{q_{j}}\frac{\partial}{\partial
y}\bigg{(}E(i)_{u}+\sum_{s\in[t]}y^{s}v^{(s)}_{u}\bigg{)}\bigg{\rvert}_{\beta_{j}}=\sum_{u\in[\ell]}a_{j,u}\frac{\partial}{\partial
y}\bigg{(}E(i)_{u}+\sum_{s\in[t]}y^{s}v^{(s)}_{u}\bigg{)}\bigg{\rvert}_{\beta_{j}}.\vspace{-5pt}$

Note that each server generates $\ell\in O(n^{1/d})$ linear combinations of
${\bm{x}}$. Although in Algorithm 1 we let the LMC verify just one linear
combination of ${\bm{x}}$ for simplicity, in its original form, Lai-Malavolta
LMC can verify multiple linear combinations using a single witness.

Bitar-El Rouayheb (BE) Scheme ([18]). This scheme works slightly different
from the previous ones in that the client retrieves a fixed block of $k-t$
components of ${\bm{x}}$ instead of a single component. All definitions of a
PIR scheme can be generalized to this block form in a straightforward manner.
Let ${\bm{x}}=(x_{1},\ldots,x_{(k-t)n})\in\mathbb{F}^{(k-t)n}$ and assume the
client wants to retrieve the $i$th block
$\big{(}x_{(i-1)(k-t)+1},\ldots,x_{i(k-t)}\big{)}$ for some $i\in[n]$.

  * •

$\big{(}\\{q_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}\leftarrow{\sf{QueriesGen}}(n,k,i)$:
The algorithm picks a $k\times k$ Vandermonde matrix
$\bm{V}=\big{(}\beta_{a}^{b-1}\big{)}_{a,b\in[k]}$, where
$\\{\beta_{s}\\}_{s\in[t]}$ is a set of $k$ distinct elements in
${\mathbb{F}}$. It also picks $t$ random vectors
$\\{v^{(s)}\\}_{s\in[t]}\subseteq\mathbb{F}^{(k-t)n}$ and set the queries to
be the rows of the matrix ${\bm{Q}}=\bm{V}{\bm{M}}$ given as follows.

${\bm{Q}}=\begin{pmatrix}q_{1}\\\ \hline\cr q_{2}\\\ \hline\cr\vdots\\\
\hline\cr
q_{k}\end{pmatrix}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\bm{V}{\bm{M}}=\bm{V}\begin{pmatrix}v^{(1)}\\\
\hline\cr\vdots\\\ \hline\cr v^{(t)}\\\ \hline\cr{\bm{e}}_{(i-1)(k-t)+1}\\\
\hline\cr\vdots\\\ \hline\cr{\bm{e}}_{i(k-t)}\end{pmatrix}.$

  * •

$a_{j}\leftarrow{\sf{AnswerGen}}({\bm{x}},q_{j})$: The algorithm outputs
$a_{j}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}q_{j}\cdot{\bm{x}}$.

  * •

$\\{x_{i}\\}\leftarrow{\sf{Extract}}\big{(}n,i,\\{a_{j}\\}_{j\in[k]},{\sf{aux}}\big{)}$:
The algorithm calculates $\bm{V}^{-1}{\bm{Q}}{\bm{x}}={\bm{M}}{\bm{x}}$, which
gives $\big{(}x_{(i-1)(k-t)+1},\ldots,x_{i(k-t)}\big{)}$.

The $t$-privacy is guaranteed because any set of $t$ queries has $t$ random
vectors $\\{v^{(s)}\\}_{s\in[t]}$ well mixed (the submatrix of ${\bm{Q}}$
formed by any $t$ rows and the first $t$ columns is always invertible) and
hence appears completely random.

## Appendix C: Extra Performance Evaluations of Com-PIR

In Fig. 5, with a medium $m$ and a growing $n$, the computation time of Com-
PIR is dominated by the LMC. Note that LMC on its own scales linearly for the
verifier and quadratically in $n$ for the server. More specifically, in our
implementation, $O(n)$ elliptic curve operations (expensive) and $O(n^{2})$
field operations (cheaper) are required for the server. Applied on top of a
PIR, the LMC-related running time also depends on $k$, $t$, and $\ell\in
O(n^{1/d})$. Lai-Malavolta LMC runs reasonably fast on small and medium $n$
(thousands) but slow on larger $n$. In Fig. 6, we plot the running times of
LM-WY as $d$ increases, which means that $k$ increases (to satisfy $2k-1\geq
td$ for a fixed $t$) and $\ell$ decreases. While the PIR time increases for
both servers and clients, the LMC time for servers (depending on $\ell$)
decreases as $d$ grows. For the client, the LMC time fluctuates as it depends
on $k\ell$.

Figure 5: The comparison of the average server and client computation times of
LM-CKGS, LM-WY, and LM-BE for $k=2$, $t=1$, $m=2^{10}$, and
$n\in\\{2^{8},2^{10},2^{12}\\}$. Figure 6: The comparison of the average
server and client computation times of LM-WY for $t=1$, $n=2^{10}$,
$m\in\\{2^{10},2^{12}\\}$, and $(d,k)\in\\{(3,2),(4,3),(5,3),(6,4)\\}$.


# The FFSVC 2020 Evaluation Plan

##  1 Introduction

Speaker verification is a key technology in speech processing and biometric
authentication, which has broad impact on our daily lives, e.g. security,
customer service, mobile devices, smart speakers. Recently, speech based human
computer interaction has become more and more popular in far-field smart home
and smart city applications, e.g. mobile devices, smart speakers, smart TVs,
automobiles. Due to the usage of deep learning methods, the performances of
speaker verification in telephone channel and close-talking microphone channel
have been enhanced dramatically. However, there are still some open research
questions that can be further explored for speaker verification in the far-
field and complex environments, including but not limited to

  * •

Far-field text-dependent speaker verification for wake up control

  * •

Far-field text-independent speaker verification with complex environments

  * •

Far-field speaker verification with cross-channel enrollment and test

  * •

Far-field speaker verification with single multi-channel microphone array

  * •

Far-field speaker verification with multiple distributed microphone arrays

  * •

Far-field speaker verification with front-end speech enhancement methods

  * •

Far-field speaker verification with end-to-end modeling using data
augmentation

  * •

Far-field speaker verification with front-end and back-end joint modeling

  * •

Far-field speaker verification with transfer learning and domain adaptation

The Far-Field Speaker Verification Challenge 2020 (FFSVC20) is designed to
boost the speaker verification research with special focus on far-field
distributed microphone arrays under noisy conditions in real scenarios. The
objectives of this challenge are to: 1) benchmark the current speech
verification technology under this challenging condition, 2) promote the
development of new ideas and technologies in speaker verification, 3) provide
an open, free, and large scale speech database to the community that exhibits
the far-field characteristics in real scenes.

The challenge has three tasks in different scenes.

  * •

Task 1: Far-Field Text-Dependent Speaker Verification from single microphone
array

  * •

Task 2: Far-Field Text-Independent Speaker Verification from single microphone
array

  * •

Task 3: Far-Field Text-Dependent Speaker Verification from distributed
microphone arrays

All three tasks follow the cross-channel setup. The recordings of close-
talking cellphone will be selected as enrollment and the recordings of far-
field microphone array will be used for test.

##  2 Database

Table 1: The details of the FFSVC20 challenge data Utterence ID | Content | Noise
---|---|---
001-030 | ni hao, mi ya | F - TV/Office + electric fan
(text-dependent) | T - electric fan
091- | text independent | S - clean

###  2.1 The FFSVC20 Challenge Database

####  2.1.1 The DMASH Database

Figure 1: The setup of the recording environment

The Distributed Microphone Arrays in Smart Home (DMASH) database is recorded
in real smart home scenarios with two different rooms. The detail information
of room sizes will be released after the challenge. Figure 1 shows the
recording environment setup of DMASH, includes one close-talking microphone;
one iPhone, one Android phone, one iPad, one microphone and one circular
microphone array (named PCM) placed at 25cm, 1m,3m,5m, left 3m, right 3m and
-1.5m distances, respectively.

####  2.1.2 FFSVC20 Challenge Data Description

The FFSVC20 challenge database is part of the DMASH Database. The recording
devices include one close-talking microphone (48kHz, 16 bit), one iPhone
(48kHz, 16 bit) at 25cm distance and 6 circular microphone arrays (16kHz,
16bit, 16 microphones, 5cm radius). The language is Mandarin. Text content
include ni hao mi ya as text dependent utterances as well as other text
independent ones.

The data collection setup of the challenge database is shown in Figure 2. Red
arrow points to channel 0 of microphone arrays. Each speaker visits 3 times
with 7-15 days gap.

The first letter of the file name denotes the visit index. F stands for the
speaker’s first visit, S denotes the speaker’s second visit and T means the
speaker’s third visit.

####  2.1.3 Named structure

Here is an example of speaker files.

T0003/
003MIC/
003I0.25M/
003PCM5M/
003PCML3M/
003PCM3M/
......
T0003_003PCM3M_recorded14_0308_normal.wav
......

The corresponding structure is as follows,

$<$visit$><$spk_id$>$/
$<$spk_id$><$device_and_distance$>$/
$<$visit$><$spk_id$>$_$<$spk_id$><$device_distance$>$

_$<$channel_id$>$_$<$utt_id$>$_$<$speed$>$.wav

In PCM (microphone array), recorded 2 stand for channel 0, recorded 6 denotes
channel 4 and so on (in total there are 18 channels in each PCM, recorded 0,1
is empty).

Here we provide three examples.

  * •

F0148_148I0.25M_1_0218_normal.wav means this audio is the utterance 218 in the
first visit of speaker 148, the recorded device is iPhone at a distance of
25cm. 1 stands for channel 1, which is meaningless since iPhone at 25cm
distance only contains one channel.

  * •

S0183_183MIC_Tr2_0138_normal.wav means this audio is the utterance 138 in the
second visit of speaker 183, the recorded device is a close-talking MIC, Tr2
stands for close-talking. In this challenge, we just provide one close-talking
microphone.

  * •

T0003_003PCML3M_recorded14_0308_normal.wav means this audio is the utterance
308 in the third visit of speaker 3, the recorded device is a microphone array
(this audio is channel 12 in this array), located at 3m distance in front of
the speaker, on the left side with a 30 degrees angle.

In this challenge database, we provide three randomly selected microphone
arrays out of the total six arrays in the training and development set; for
each microphone array, we only provide 4 channels’ data (channel 0,4,8,12,
denoted by recorded 2,6,10,14) due to the large size of the whole database.

###  2.2 The SLR-85 HI-MIA database

The original HI-MIA database includes two sub databases, which are the
AISHELL- wakeup1 with 254 speakers and the AISHELL-2019B-eval with 86
speakers. The content of utterances covers two wake-up words, ‘ni hao, mi ya’
in chinese and ‘Hi, Mia’ in English.

During the recording process, seven recording devices (one close-talking
microphone and six 16-channel circular microphone arrays) were set in a real
smart home environment. The 16-channel circular microphone array records
signals in the 16kHz, 16 bit format, and the close-talking microphone records
waveforms in the 44.1kHz, 16 bit format.

111http://openslr.org/85/

The SLR-85 HI-MIA open source database is the 2019 AISHELL Speaker
Verification Challenge database which is a subset of the original HI-MIA
database. It contains one close-talking microphone and three microphone arrays
located at 1m, 3m and 5m distance right in front of speaker. The SLR-85 HI-MIA
database covers all the 254 speakers, but only includes the mandarin
utterances.

For more details, please refer to the latest version (v3) of [1].

Figure 2: The setup of the FFSVC20 challenge data

##  3 Task Description

###  3.1 Task 1:Far-Field Text-Dependent Speaker Verification from single
microphone array

####  3.1.1 Training data

The training data includes 120 speakers and each speaker has 3 visits. In each
visit, there are multiple (‘ni hao, mi ya’) text-dependent utterances as well
as multiple text-independent utterances. The recording from five recording
devices for each utterance are provided for training. These five recording
devices include one close-talk microphone, one 25cm distance cellphone, and
three randomly selected microphone arrays (4 channels per array).

Any publicly open and freely accessible speech database shared on openslr.org
before Feb 1st 2020 (including SLR-85 HI-MIA) can be used in this challenge.

####  3.1.2 Development Data

The Development data includes 35 speakers and each speaker has 3 visits. In
each visit, there are multiple (‘ni hao, mi ya’ ) text-dependent utterances as
well as multiple text-independent utterances. The recording from five
recording devices for each utterance are provided. These five recording
devices include one close-talk microphone, one 25cm distance cellphone, and
three randomly selected microphone arrays (4 channels per array).

####  3.1.3 Evaluation Data

The evaluation data includes 80 speakers and each speaker has 3 visits. In
each visit, there are multiple (‘ni hao, mi ya’ ) utterances, The recording
from two recording devices for each utterance are provided. These two
recording devices include one 25cm distance cellphone and one randomly
selected microphone arrays (4 channels per array).

The recording from 25cm distance cellphone will be selected as enrollment and
recording from single far-field microphone array will be used for test. For
any true trial, the enrollment and the testing utterances are from different
visits of the same speaker.

###  3.2 Task 2: Far-Field Text-Independent Speaker Verification from single
microphone array

####  3.2.1 Training data

The same as the training data for task 1.

####  3.2.2 Development Data

The same as the development data for task 1.

####  3.2.3 Evaluation Data

The evaluation data includes 80 speakers and each speaker has 3 visits. In
each visit, there are multiple text-independent utterances, The recording from
two recording devices for each utterance are provided. These two recording
devices include one 25cm distance cellphone and one randomly selected
microphone arrays (4 channels per array).

The recording from 25cm distance cellphone will be selected as enrollment and
recording from single far-field microphone array will be used for test. For
any true trial, the enrollment and the testing utterances are from different
visits of the same speaker.

###  3.3 Task 3: Far-Field Text-Dependent Speaker Verification from
distributed microphone arrays

####  3.3.1 Training data

The same as the training data for task 1.

####  3.3.2 Development Data

The same as the development data for task 1.

####  3.3.3 Evaluation Data

The evaluation data includes 80 speakers and each speaker has 3 visits. In
each visit, there are multiple (‘ni hao, mi ya’ ) utterances. For each
utterance, its corresponding recordings from one 25cm distance cellphone and
2-4 randomly selected microphone arrays are provided. For each microphone
array, the selected four microphones are equally distributed along the circle
with a random start channel index to simulate the scenarios with unknown array
orientation angles. (e.g. channel 0, 4, 8, 12; channel 1, 5, 9, 13; channel 6,
10, 14, 2, etc.)

Recording from 25cm distance cellphone will be selected as enrollment and the
recordings from 2-4 randomly selected far-field microphone arrays will be used
for test. For any true trial, the enrollment and the testing utterances are
from different visits of the same speaker.

There is no overlapping among the speakers in the training data, development
data, evaluation data in task 1, task 2, and task 3.

##  4 Evaluation Rules

###  4.1 Evaluation Results

Before the mid-term deadline of score submission, each team have 5 times to
submit the result. We sincerely suggest each team to test the system
performance on the development set due to limited opportunities for
submission. The evaluation set and the development set are from the same
database, the only difference is that the development set only has 35
speakers, while the evaluation set for each task has 80 speakers.

After the mid-term deadline and before the final deadline, each team has
another 5 times to submit the final score file.

For the results on the evaluation set, we will release the results calculated
based on a fixed 30% of the trials in the leaderboard. So ranking on the
leaderboard is not the final ranking. We will announce the official result in
the Interspeech 2020 FFSVC special session. We encourage each team to explore
more novel ideas, not just for the first place.

###  4.2 The trials

The trial file consists of three segments: enrollment audio ID, test audio ID
and label. Label denotes that the trial is target or non-target. The 25cm
distance iPhone signal is selected as the enrollment data, and the microphone
array audio is considered as the testing data.

###  4.3 Performance Measures

In this challenge, we will use several metric to evaluate the system
performance. The primary metric we adopt is the min $C_{det}$ cost value. In
addition, Equal Error Rate (EER) and Cllr will be provided to participant as
auxiliary metrics.

####  4.3.1 Primary measures

The primary metric is based on the following detection cost function which is
the same function as used in the NIST 2010 SRE, but with modified parameters
[2]. It is a weighted sum of miss and false alarm error probabilities in the
form:

$C_{det}=C_{miss}\times P_{miss}\times P_{tar}+C_{fa}\times
P_{fa}\times(1-P_{tar})$ (1)

We assume a prior target probability, Ptar of 0.01 and equal costs between
misses and false alarms. The model parameters are 1.0 for both Cmiss and Cfa.
The Cdet will be normalized by Ptar the same way as in [2].

We use the minimum Cdet as our primary metric.

####  4.3.2 Alternate Performance Metrics

The EER and Cllr will be provided as alternate performance metrics and a brief
description of Cllr is provided as follows:

To analyze how well a system performs and is calibrated across different
operating points, a log-likelihood ratio based cost metric, Cllr, is
suggested. Assuming trials scores are represented as LLRs, then Cllr can be
calculated as [3],

$C_{llr}=\frac{1}{2\times\log(2)}\times\Bigg{(}\frac{\sum\log(1+1/s)}{N_{tar}}+\frac{\sum\log(1+s)}{N_{non}}\Bigg{)}$
(2)

where $s$ is the likelihood ratio for a trial, and Ntar and Nnon represent the
number of target and non-target trials, respectively.

##  5 Registration and Submission

###  5.1 Registration

First, please create an account if you do not have one. We kindly request you
to associate your account to an institutional e-mail. The organizing committee
reserves the right to revoke your access to the challenge sites otherwise,
please read the evaluation plan carefully. If you are part of a team, at least
one person in your team will need an account to participate. Make sure to set
the name of your team in the user’s profile, or it will not be visible on the
leaderboard.

Participants can register in one or more tasks. If your team participates in
multiple tasks, we kindly request you to use the same user account to
participate in all tasks.

Please note that any deliberate attempts to bypass the submission limit (for
instance, by creating multiple accounts and using them to submit) will lead to
automatic disqualification.

In case of any issues, the final interpretation right belongs to the
organizing committee.

###  5.2 Submission

####  5.2.1 Score submission

Participants are required to submit at least one valid score file for each
participating task to the FFSVC 2020 platform. The score files need to follow
the following rules:

$<$TeamName$>$_$<$Task$>$_$<$SystemNumber$>$.txt

The score files should be in UTF-8 format with one line per trial. Each line
must include two space-delimited fields:

$<$enrol_data$><$space$><$test_data$><$space$><$score$>$

We will provided a sample in the challenge website.

####  5.2.2 System description submission

Each registered team is required to submit a technical system description
report. Please submit this report using the Interspeech 2020 paper template.
All reports must be a minimum of 2 pages (including references). Reports must
be written in English. The system description does not need to repeat the
content of the evaluation plan, such as the introduction of database,
evaluation metric, etc. The system description must include the following
items:

  * •

a complete description of the system components, including front-end (e.g.,
speech activity detection, features, normalization, front-end speech
enhancement) and back-end (e.g., background models, i-vector/embedding
extractor, Probabilistic Linear Discriminant Analysis (PLDA), speaker features
fusion) modules along with their configurations (i.e., filterbank
configuration, dimensionality and type of the acoustic feature parameters, as
well as the acoustic model and the backend model configurations).

  * •

a complete description of the data partitions used to train the various
models.

  * •

performance of the submission systems on the development dataset (calculated
based on the provided tools) and the evaluation dataset (calculated by the
challenge platform). Teams are encouraged to quantify the contribution of
their major system components that they believe resulted in significant
performance gains.222https://www.nist.gov/system/files/documents/2019/
07/22/2019_nist_speaker_recognition_challenge_v8.pdf

  * •

novel ideas, strategies and methods are strongly recommended to be shared.

  * •

a report of the model size, CPU (single threaded) and GPU execution times as
well as the amount of memory used to process a single trial (i.e., the time
and memory used for creating a speaker model from enrollment data as well as
processing a test segment to compute the score).

####  5.2.3 Paper submission

The organizing committee highly encourages the participating teams to submit a
paper to the INTERSPEECH 2020 Far-Field Speaker Verification Challenge special
session. However, paper contributions within the scope are also welcome if the
authors do not intend to participate in the Challenge itself. In any case,
please submit your paper until 30 March 2020 (and final results by 15 June
2020) using the standard style info and respecting length limits, and submit
to the Interspeech 2020 paper submission system. Important: as topic you
should choose only this Special Session (FFSVC 2020). The papers will undergo
the normal review process similar to the regular session papers.

##  6 Schedule

  * •

Feb 1st: Releasing the training and development data as well as the evaluation
plan

  * •

March 1st: Releasing the evaluation data and launching the leaderboard (30% of
the trials)

  * •

March 15th: Challenge registration deadline

  * •

March 23th: Mid-term deadline of score submission (up to 5 chances)

  * •

March 30th: Interspeech 2020 paper submission deadline

  * •

June 15th: Final deadline of score submission (another 5 chances)

  * •

Interspeech 2020 Camera Ready Paper deadline: System description submission
deadline

  * •

Interspeech 2020 special session: Official results announcement

## References

  * [1] X. Qin, H. Bu, and M. Li, “HI-MIA : A Far-field Text-Dependent Speaker Verification Database and the Baselines,” in _Proc. of ICASSP_ , 2020, arXiv:1912.01231.
  * [2] M. K. Nandwana, J. van Hout, M. McLaren, C. Richey, A. Lawson, and M. A. Barrios, “The voices from a distance challenge 2019 evaluation plan,” _arXiv:1902.10828_ , 2019.
  * [3] N. Brummer and J. Preez, “Application-independent evaluation of speaker detection,” _Computer Speech & Language_, vol. 20, pp. 230–275, 04 2006\.