#  $k$-server Byzantine-Resistant PIR Scheme with Optimal Download Rate and
Optimal File Size

Stanislav Kruglik1, Son Hoang Dau2, Han Mao Kiah1, Huaxiong Wang1
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>1 School of Physical and Mathematical Sciences, Nanyang
Technological University, Singapore  2 School of Computing Technologies, STEM
College, RMIT University, Melbourne, Australia

###### Abstract

We consider the problem of designing a Private Information Retrieval (PIR)
scheme on $m$ files replicated on $k$ servers that can collude or, even worse,
can return incorrect answers. Our goal is to correctly retrieve a specific
message while keeping its identity private from the database servers. We
consider the asymptotic information-theoretic capacity of this problem defined
as the maximum ratio of the number of correctly retrieved symbols to the
downloaded one for a large enough number of stored files. We propose an
achievable scheme with a small file size and prove that such a file size is
minimal, solving the problem pointed out by Banawan and Ulukus.

##  I Introduction

A Private Information Retrieval (PIR) scheme is a tool to retrieve a given
file $f_{\iota}$ from a database $\mathbf{x}=(f^{(1)},\ldots,f^{(m)})$, while
keeping its identity $\iota\in[m]$ private for the database servers [1, 2].
The setup has many related practical applications, including protecting the
identity of stock market records reviewed by investment funds because showing
specific interest may negatively affect the stock price. The first PIR scheme
was proposed in the pioneering paper by Chor et. al. [3]. In the case of a
single server, the authors also showed that to guarantee information-
theoretical privacy of retrieved file index, it is necessary for the user to
download the entire database. Thus, to reduce the communication cost in an
information-theoretical setting, we have to move to a multi-server setup. In
this model, the client queries each of $k$ servers once, while keeping the
identity of the retrieved file private from up to $t$ honest-but-curious
servers. In PIR literature, such a scheme is called $t$-private $k$-server PIR
scheme and such property is known as $t$-privacy.

The computer science formulation of the PIR problem assumes files of size one
and measures the performance by the sum of the lengths of queries (upload
cost) and the sum of the length of responses (download cost) [4, 5, 6].
Motivated by practical applications, in which the size of the message can be
arbitrarily large, the problem of PIR was revisited by the information-theory
community. Download cost became the dominant performance metric, and the
maximum achievable download rate, defined as a ratio of the retrieved file
size to the amount of information downloaded by the user, became a focus of
the pleiad of the research papers [7, 8, 9, 10].

Most of the current PIR schemes assume that servers are honest-but-curious and
provide correct answers. However, such an assumption cannot be guaranteed in
the cloud environment. This fact poses an interesting question about responses
to wrong server answers. Here we provide three different interpretation of
this question and their formal definition.

  * •

$s$-verifiability [referred as $s$-security in [11]]. The client can detect
the presence of up to $s$ servers that persuade the client to output a wrong
result.

  * •

$a$-accountability. The client can identify each of up to $a$ servers that
persuade the client to output a wrong result.

  * •

$b$-byzantine resistance/$b$-byzantine robustness. The client can retrieve the
correct result in presence of up to $b$ servers that persuade the client to
output a wrong result.

It is clear that $a$-accountability implies $a$-verifiability, while
$b$-byzantine resistance implies both $b$-accountability and $b$-verifiability
[11]. However, in some practical applications, the user needs to be able to
correctly reconstruct the desired message irrespective of the adversarial
actions of servers. This fact motivates us to consider the strongest notion of
$b$-byzantine resistant PIR [12, 13, 14, 15].

The capacity of $b$-byzantine resistant PIR scheme for the case of $2b+t<k$ is
shown in [12] to be equal to

$C_{m}(t,b,k)=\frac{k-2b}{k}\cdot\frac{1-\frac{t}{k-2b}}{1-\left(\frac{t}{k-2b}\right)^{m}}.$
(1)

Authors of [12] also proposed a general achievable scheme based on MDS codes.
It utilizes the division of each file into multiple sub-packets whose number
is denoted as sub-packetization. In [12], the scheme has sub-packetization
value $(k-2b)^{m}$, while the problem of obtaining its minimum capacity-
achieving quantity is left as an open one. We do note that each sub-packet
usually corresponds to some finite field element, and the size of the latter
drastically affects the implementation costs [16]. Thus, in this paper, we
focus on the total file size. Since the number of files is high, we are
interested in asymptotic capacity values, where the size of the file in scheme
from [12] is tremendous. So, we let $m\to\infty$, and for the case of $2b+t<k$
we have

$C(t,b,k)\triangleq\lim_{m\to\infty}C_{m}(t,b,k)=\frac{k-2b}{k}\cdot\left(1-\frac{t}{k-2b}\right).$
(2)

In this paper, we propose $b$-byzantine resistant $k$-server PIR with optimal
download rate and small file size. We also formally prove that the latter is
minimal among all capacity-achieving schemes. The key ingredients of our
method are the recently proposed communication-efficient secret sharing scheme
based on trace recovery framework [17] and the technique to repair Reed-
Solomon code in presence of erroneous traces [18].

##  II Preliminaries

###  II-A Notations

For any integer $n>0$ we denote $[n]=\\{1,\ldots,n\\}$. For any prime power
$q$, we denote an extended finite field with $q^{s}$ elements as
$\mathbb{F}_{q^{s}}$. The base field with $q$ elements is denoted as
$\mathbb{F}_{q}$. For any $\xi\in\mathbb{F}_{q^{s}}$ we define the trace
function from $\mathbb{F}_{q^{s}}$ to $\mathbb{F}_{q}$ as
$\textrm{Tr}(\xi)=\sum_{i=0}^{s-1}\xi^{q^{i}}$. We note that it is
$\mathbb{F}_{q}$-linear function. By $\mathbb{F}_{q^{s}}[\xi]$ we denote the
ring of polynomials over $\mathbb{F}_{q^{s}}$. By superscript $T$, we denote
the transpose of a vector. By $\mathbf{M}_{ij}$ we denote $(i,j)$th entry of
matrix $\mathbf{M}$. By $\langle\mathbf{M},\mathbf{N}\rangle$ we denote the
Frobenius inner product of $\mathbf{M}$ and $\mathbf{N}$, i.e.
$\langle\mathbf{M},\mathbf{N}\rangle=\sum_{i,j}M_{ij}N_{ij}$. By $H(X)$ \- we
denote the entropy of discrete random variable $X$ and by $I(X;Y)$ the mutual
information between discrete random variables $X$ and $Y$.

###  II-B $k$-Server PIR Schemes

Let us formally define $k$-server PIR schemes. Let the database $\mathbf{x}$
be formed of $m$ files $f^{(1)},\ldots,f^{(m)}$ and replicated on each server.
The user wants to retrieve the file $\iota$ by sending the queries
$\textbf{q}_{1},\ldots,\textbf{q}_{k}$ to each server. Let $F$ be the random
variable representing the file of interest and $N$ be the random variable
representing its number. Let $Q_{j}$ be the random variable representing the
query to the server $j$ and $Q_{\mathcal{S}}$ the set of queries to servers in
the set $\mathcal{S}\subseteq[k]$. Based on the received query
$\textbf{q}_{j}$, each server $j\in[k]$ computes the answer $\textbf{a}_{j}$
and sends it back to the user. Let $A_{j}$ be the random variable representing
the answer to the query $\mathbf{q}_{j}$ by the server $j\in[k]$ and
$A_{\mathcal{S}}$ the set of answers from servers in the set
$\mathcal{S}\subseteq[k]$. In the byzantine PIR setting, there exists a set
$\mathcal{B}\subset[k]$ of servers that can provide incorrect answers to
queries. This set has a cardinality up to $b$ and is unknown to the user.
After this introduction, we can define $k$-server $t$-private $b$-byzantine
resistant PIR.

######  Definition 1 ($k$-server $t$-private $b$-byzantine resistant PIR).

A $k$-server $t$-private $b$-byzantine resistant PIR is a scheme that
satisfies the following properties:

  1. 1.

(Privacy) The scheme is $t$-private, i.e., $\forall\mathcal{T}\subset[k]$ with
$|\mathcal{T}|\leq t$ it holds that

$I(N;Q_{\mathcal{T}})=0.$ (3)

  2. 2.

(Correctness) The scheme is correct and $b$-byzantine resistant, i.e.,
$\forall\mathcal{B}\subset[k]$ with $|\mathcal{B}|\leq b$ and
$\mathcal{S}=[k]$ it holds that

$H(F|A_{\mathcal{S}})=0,$ (4)

even if servers from the set $\mathcal{B}$ unknown to the user provide
incorrect responses to queries.

######  Remark 2.

By setting $b=0$ this definition is transformed to $k$-server $t$-private PIR
scheme.

######  Definition 3 (retrieval threshold).

For $k$-server $t$-private $b$-byzantine resistant PIR scheme from Definition
1 the retrieval threshold $r$ is the minimum number of servers so that
$\forall\mathcal{R}\subseteq[k]$ with $|\mathcal{R}|=r$ and
$\forall\mathcal{B}\subset[k]$ with $|\mathcal{B}|\leq b$ it holds that

$H(F|A_{\mathcal{R}})=0$ (5)

even if servers from the unknown to the user set $\mathcal{B}$ provide
incorrect responses to queries.

###  II-C A Communication-Efficient PIR Scheme

Let us adopt a communication-efficient secret-sharing scheme from [17] to
obtain $k$-server $t$-private PIR scheme with optimal download rate. For
simplicity, we consider a non-universal case when we request responses from
exactly $k\geq r$ servers, where $r$ is the recovery threshold.

Scheme $\Pi_{1}$: $k$-server $t$-private PIR

Let $t$, $r$, $k$ be positive integers satisfying $t<r<k\leq q$, $\Delta=r-t$
and $\Delta|(k-t)$. Denote by $s\triangleq\frac{k-t}{\Delta}$. Let
$\Omega_{\alpha}=\\{\alpha_{1},\ldots,\alpha_{\Delta}\\}\subset\mathbb{F}_{q^{s}}$,
$\Omega_{\chi}=\\{\chi_{1},\ldots,\chi_{t}\\}\subset\mathbb{F}_{q^{s}}$ and
$\Omega_{\beta}=\\{\beta_{1},\ldots,\beta_{k}\\}\subseteq\mathbb{F}_{q}$ be
publicly known non-intersecting sets such that all elements of
$\Omega_{\alpha}$ are roots of distinct monic irreducible polynomials of
degree $s$ over $\mathbb{F}_{q}$.

Let us represent the database $\mathbf{x}$ with $m$ files as a
$m\times\Delta$-array. Let the $(i,j)$-th entry of $\mathbf{x}$ be
$x^{(i)}_{j}$. Then we set the file
$f^{(i)}\triangleq[x^{(i)}_{1},\ldots,x^{(i)}_{\Delta}]$. Therefore,

$\mathbf{x}=\begin{bmatrix}x^{(1)}_{1}&x^{(1)}_{2}&\cdots&x^{(1)}_{\Delta}\\\
x^{(2)}_{1}&x^{(2)}_{2}&\cdots&x^{(2)}_{\Delta}\\\
\vdots&\vdots&\ddots&\vdots\\\
x^{(m)}_{1}&x^{(m)}_{2}&\cdots&x^{(m)}_{\Delta}\end{bmatrix}=\begin{bmatrix}f^{(1)}\\\
f^{(2)}\\\ \vdots\\\ f^{(m)}\end{bmatrix}\,.$

Then we define $\mathbf{e}_{(i,j)}$ to be the $m\times\Delta$ indicator array
for the database components. In other words, the $(i,j)$th entry of
$\mathbf{e}_{(i,j)}$ is one, while all other entries of $\mathbf{e}_{(i,j)}$
are zero. We replicate the database $\mathbf{x}$ on $k$ servers.

  * •

Query generation algorithm: To retrieve the file $\iota\in[m]$ user randomly
generates $t$ $(m\times\Delta)$-arrays
$\mathbf{r}^{(1)},\ldots,\mathbf{r}^{(t)}$ and draw a random
degree-$t+\Delta-1$ curve

$\displaystyle\mathbf{g}(\xi)$
$\displaystyle\triangleq\sum_{j=1}^{\Delta}\prod_{\ell\in[\Delta]\setminus\\{j\\}}\left(\frac{\xi-\alpha_{\ell}}{\alpha_{j}-\alpha_{\ell}}\right)\prod_{\ell=1}^{t}\left(\frac{\xi-\chi_{\ell}}{\alpha_{j}-\chi_{\ell}}\right)\mathbf{e}_{(\iota,j)}$
$\displaystyle+\sum_{h=1}^{t}\prod_{\ell=1}^{\Delta}\left(\frac{\xi-\alpha_{\ell}}{\chi_{h}-\alpha_{\ell}}\right)\prod_{\ell\in[t]\setminus\\{h\\}}\left(\frac{\xi-\chi_{\ell}}{\chi_{h}-\chi_{\ell}}\right)\mathbf{r}^{(h)}$
(6)

that resides in $\mathbb{F}_{q^{s}}^{m\times\Delta}$ and passes through points
$(\alpha_{1},\mathbf{e}_{(\iota,1)}),\ldots,(\alpha_{\Delta},\mathbf{e}_{(\iota,\Delta)})$.
Query to server $j\in[k]$ is $\mathbf{g}(\beta_{j})$. We note that both
$\mathbf{g}$ and $\mathbf{r}^{(h)}$ depend on retrieved index $\iota$, but we
omit the subscript $\iota$ for readability.

  * •

Answer generation algorithm: Upon receive the query $\mathbf{g}(\beta_{j})$,
server $j\in[k]$ computes the Frobenius inner product
$\langle\mathbf{g}(\beta_{j}),\mathbf{x}\rangle$. We can observe that

$\displaystyle\langle\mathbf{g}(\xi),\mathbf{x}\rangle=\sum_{j=1}^{\Delta}\prod_{\ell\in[\Delta]\neq\\{j\\}}\left(\frac{\xi-\alpha_{\ell}}{\alpha_{j}-\alpha_{\ell}}\right)\prod_{\ell=1}^{t}\left(\frac{\xi-\chi_{\ell}}{\alpha_{j}-\chi_{\ell}}\right)x^{(\iota)}_{j}$
$\displaystyle+\sum_{h=1}^{t}\prod_{\ell=1}^{\Delta}\left(\frac{\xi-\alpha_{\ell}}{\chi_{h}-\alpha_{\ell}}\right)\prod_{\ell\in[t]\setminus\\{h\\}}\left(\frac{\xi-\chi_{\ell}}{\chi_{h}-\chi_{\ell}}\right)\langle\mathbf{r}^{(h)},\mathbf{x}\rangle,$

which is a polynomial in $\xi$ of degree $\Delta+t-1=r-1$. We call this
polynomial $\phi(\xi)$ and observe further that
$\phi(\alpha_{i})=x^{(\iota)}_{i}$ for $i\in[\Delta]$.

    * –

For retrieval from answers from $r$ servers, server $j$ responds with value of
$\mathbf{a}_{j}=\phi(\beta_{j})\in\mathbb{F}_{q^{s}}$.

    * –

For retrieval from answers from $k$ servers, server responds with

$\mathbf{a}_{j}=\textrm{Tr}(v_{j}\phi(\beta_{j}))\in\mathbb{F}_{q},$ (7)

where

$v_{j}=\prod_{\ell=1}^{\Delta}(\beta_{j}-\alpha_{\ell})^{-1}\times\prod_{\ell\in[k]\setminus\\{j\\}}(\beta_{j}-\beta_{\ell})^{-1}.$
(8)

  * •

File retrieval algorithm

    * –

For retrieval from answers from $r$ servers, the user applies the Lagrange
interpolation formula.

    * –

For retrieval from answers from $k$ servers, the user prepares a basis
$\\{\theta_{1},\ldots,\theta_{s}\\}$ for $\mathbb{F}_{q^{s}}$ over
$\mathbb{F}_{q}$ and its trace-orthogonal basis
$\\{\eta_{1},\ldots,\eta_{s}\\}$. After that, the user chooses polynomials
$h_{i\delta}\in\mathbb{F}_{q}[\xi]$ of degree less than $s$ for all
$i\in[\Delta]$ and $\delta\in[s]$ so that

$h_{i\delta}(\alpha_{i})=u_{i}^{-1}\eta_{\delta}\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}^{-1}(\alpha_{i}),$
(9)

where $\tilde{f}_{\ell}(\xi)$ is the minimal polynomial of $\alpha_{\ell}$
over $\mathbb{F}_{q}$ and

$u_{i}=\prod_{\ell\in[\Delta]\setminus\\{i\\}}(\alpha_{i}-\alpha_{\ell})^{-1}\times\prod_{j=1}^{k}(\alpha_{i}-\beta_{j})^{-1}.$
(10)

The user retrieves the file of interest by

$\displaystyle
x_{i}^{(\iota)}=\phi(\alpha_{i})=-\sum_{\delta=1}^{s}\theta_{\delta}\Bigg{(}\sum_{j=1}^{k}h_{i\delta}(\beta_{j})\textrm{Tr}(v_{j}\phi(\beta_{j}))\cdot$
$\displaystyle\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\Bigg{)},$
(11)

for all $i\in[\Delta]$.

######  Theorem 1.

Scheme $\Pi_{1}$ is $k$-server $t$-private PIR over $\mathbb{F}_{q^{s}}$ with
file size $(k-t)\log(q)$ and a recovery threshold $r$ that achieves the
asymptotic capacity (2) for $b=0$ and any given $\Delta$ and $r$ so that

$t<r<k\leq q,\;\Delta=r-t\;\;\textrm{and}\;\;\Delta|(k-t),$

and $s=\frac{k-t}{\Delta}$.

###### Proof.

According to the definition of $k$-server $t$-private PIR, we will prove
privacy and correctness properties and show that responses from $r$ servers
are enough for file retrieval. The proof is very similar to the proof from
[17]. To make the paper self-contained, we present the proof here in all the
details.

To prove the security, we need to show that

$I(\mathbf{g}(\beta_{l_{1}}),\ldots,\mathbf{g}(\beta_{l_{t}});\mathbf{e}_{\iota,1},\ldots,\mathbf{e}_{\iota,\Delta})=0,$
(12)

for any subset $\\{l_{1},\ldots,l_{t}\\}\subset[k]$ of servers and any file
index $\iota\in[m]$.

As each element of the matrix $\mathbf{g}(\xi)$ is encoded separately from
other elements and corresponding random symbols are independent, $(i,j)$th
entry of $\mathbf{g}(\xi)$ depends only on $\mathbf{e}_{(i,j)}$ and
conditionally independent of everything else. Hence, our scheme is equivalent
to the transmission over $m\Delta$ independent channels [19] and, as a result,
we have

$\displaystyle
I(\mathbf{g}(\beta_{l_{1}}),\ldots,\mathbf{g}(\beta_{l_{t}});\mathbf{e}_{\iota,1},\ldots,\mathbf{e}_{\iota,\Delta})$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{j=1}^{\Delta}I(\mathbf{g}(\beta_{l_{1}})_{(ij)},\ldots,\mathbf{g}(\beta_{l_{t}})_{(ij)};(\mathbf{e}_{\iota,1})_{(ij)},\ldots,(\mathbf{e}_{\iota,\Delta})_{(ij)}).$
(13)

It can be easily seen that for each $i,j$,
$\mathbf{g}(\beta_{l_{1}})_{(ij)},\ldots,\mathbf{g}(\beta_{l_{t}})_{(ij)}$ are
$t$ evaluations of random polynomial $\psi_{(ij)}$ of degree $t+\Delta-1$ over
$\mathbb{F}_{q^{s}}$ at points $\beta_{l_{1}},\ldots,\beta_{l_{t}}$. For any
given values of
$(\mathbf{e}_{\iota,1})_{ij},\ldots,(\mathbf{e}_{\iota,\Delta})_{ij}$ by
Lagrange interpolating formula we can obtain a unique polynomial $\psi_{(ij)}$
over $\mathbb{F}_{q^{s}}$ such that
$\psi_{(ij)}(\alpha_{1})=(\mathbf{e}_{\iota,1})_{(ij)},\ldots,\psi_{(ij)}(\alpha_{\Delta})=(\mathbf{e}_{\iota,\Delta})_{(ij)}$
and
$\psi_{(ij)}(\beta_{l_{1}})=\mathbf{g}(\beta_{l_{1}})_{(ij)},\ldots,\psi_{(ij)}(\beta_{l_{t}})=\mathbf{g}(\beta_{l_{t}})_{(ij)}$.
This implies that
$I(\mathbf{g}(\beta_{l_{1}})_{(ij)},\ldots,\mathbf{g}(\beta_{l_{t}})_{(ij)};(\mathbf{e}_{\iota,1})_{(ij)},\ldots,(\mathbf{e}_{\iota,\Delta})_{(ij)})=0$
and by (II-C), the privacy property holds.

The property that responses from $r$ servers are enough for file retrieval
trivially follows from the facts - that servers responses are values of
polynomial $\phi$ over $\mathbb{F}_{q^{s}}$ of degree $r-1$ so that
$\phi(\alpha_{j})=x_{j}^{(\iota)}$ for $j\in[\Delta]$ and we can use a
Lagrange interpolation formula to retrieve them.

Let us prove the correctness of scheme $\Pi_{1}$. It is clear that values
$(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),\ldots,\phi(\beta_{k}))$
can be seen as a codeword of Reed-Solomon code

$\displaystyle\textrm{RS}_{r}$
$\displaystyle(\Omega_{\alpha}\cup\Omega_{\beta})=\\{(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),$
$\displaystyle\ldots,\phi(\beta_{k}))|\phi\in\mathbb{F}_{q^{s}}[\xi],\deg(\phi)<r\\}.$
(14)

Dual of $\textrm{RS}_{r}$ is a Generalized-Reed Solomon code [20] defined as

$\displaystyle\textrm{GRS}_{k+\Delta-r}(\Omega_{\alpha}\cup\Omega_{\beta})=\\{u_{1}h(\alpha_{1}),\ldots,u_{\Delta}h(\alpha_{\Delta}),v_{1}h(\beta_{1}),$
$\displaystyle\ldots,v_{k}h(\beta_{k}))|h\in\mathbb{F}_{q^{s}}[\xi],\deg(h)<k+\Delta-r=k-t\\},$
(15)

where
$u_{i}=\prod_{\ell\in[\Delta]\setminus\\{i\\}}(\alpha_{i}-\alpha_{\ell})^{-1}\times\prod_{j=1}^{k}(\alpha_{i}-\beta_{j})^{-1}$
and
$v_{j}=\prod_{\ell=1}^{\Delta}(\beta_{j}-\alpha_{\ell})^{-1}\times\prod_{\ell\in[k]\setminus\\{j\\}}(\beta_{j}-\beta_{\ell})^{-1}$
for $i\in[\Delta]$ and $j\in[k]$.

As each $\alpha_{j},j\in[\Delta]$ is a root of different monic irreducible
polynomial $\tilde{f}_{j}$ of degree $s$ over $\mathbb{F}_{q}$ we have that

$\tilde{f}_{j}(\alpha_{j})=0\;\;\;\tilde{f}_{j}(\alpha_{i})\neq
0\;\;\;\textrm{for}\;\;i\in[\Delta],j\neq i$ (16) $\prod_{j\in[\Delta],j\neq
i}\tilde{f}_{j}(\alpha_{n})=0\;\;\;\textrm{for}\;\;n\in[\Delta],n\neq i.$ (17)

Let $\\{\theta_{1},\ldots,\theta_{s}\\}$ be the basis of $\mathbb{F}_{q^{s}}$
over $\mathbb{F}_{q}$ and $\\{\eta_{1},\ldots,\eta_{s}\\}$ is its trace-
orthogonal basis. For each $\delta\in[s]$ and $i\in[\Delta]$, we can represent
the element $u_{i}^{-1}\eta_{\delta}\prod_{\ell\in[\Delta],\ell\neq
i}\tilde{f}_{\ell}^{-1}(\alpha_{i})$ as the value of function
$h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$ of degree less than $s$ at point
$\alpha_{i}$. It is clear that
$\deg(h_{i\delta}\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell})<\Delta
s\leq k-t$ and hence such functions belong to the dual Generalized Reed-
Solomon code (II-C). Also, we have that

$h_{i\delta}(\alpha_{i})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{i})=u_{i}^{-1}\eta_{\delta}$
(18)

and

$h_{i\delta}(\alpha_{n})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{n})=0\;\;\;\textrm{for
all}\;\;n\in[\Delta],n\neq i.$ (19)

Consequently,

$\displaystyle\big{(}u_{1}h_{i\delta}(\alpha_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{1}),\ldots,u_{\Delta}h_{i\delta}(\alpha_{\Delta})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{\Delta}),$
$\displaystyle
v_{1}h_{i\delta}(\beta_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{1}),\ldots,v_{k}h_{i\delta}(\beta_{k})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{k})\big{)}$
$\displaystyle\cdot(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),\ldots,\phi(\beta_{k}))^{T}=0.$
(20)

Utilizing the properties of function $h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$
we have

$\displaystyle\eta_{\delta}\phi(\alpha_{i})+v_{1}h_{i\delta}\phi(\beta_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{1})+\ldots+$
$\displaystyle
v_{k}h_{i\delta}\phi(\beta_{k})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{k})=0$
(21)

and

$\eta_{\delta}\phi(\alpha_{i})=-\sum_{j=1}^{k}\left(v_{j}h_{i\delta}(\beta_{j})\phi(\beta_{j})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right).$
(22)

Applying trace-mapping function to both sides of equation (22) and utilizing
the facts that $h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$,
$\tilde{f}_{\ell}(\xi)\in\mathbb{F}_{q}[\xi]$ and $\beta_{j}\in\mathbb{F}_{q}$
for all $i,\ell\in[\Delta]$, $\delta\in[s]$, $j\in[k]$ together with the
linearity of trace-mapping function we obtain that

$\displaystyle\textrm{Tr}(\eta_{\delta}\phi(\alpha_{i}))=-\sum_{j=1}^{k}\textrm{Tr}\left(v_{j}\phi(\beta_{j})h_{i\delta}(\beta_{j})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right)=$
$\displaystyle-\sum_{j=1}^{k}h_{i\delta}(\beta_{j})\left(\textrm{Tr}\left(v_{j}\phi(\beta_{j})\right)\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right)$
(23)

From the fact that $\\{\theta_{1},\ldots,\theta_{s}\\}$ and
$\\{\eta_{1},\ldots,\eta_{s}\\}$ are trace-orthogonal bases of
$\mathbb{F}_{q^{s}}$ over $\mathbb{F}_{q}$ it is clear (see, for example,
[21][Ch. $2$]) that

$x_{i}^{(\iota)}=\phi(\alpha_{i})=\sum_{\delta=1}^{s}\theta_{\delta}\textrm{Tr}(\eta_{\delta}\phi(\alpha_{i}))$
(24)

and hence all $\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta})$ can be recovered
by accessing $\textrm{Tr}(v_{j}\phi(\beta_{j}))$ from all involved servers
$j=1,\ldots,k$.

The observations that each file consists of $\Delta$ elements of
$\mathbb{F}_{q^{s}}$ for $s=\frac{k-t}{\Delta}$ and download rate is equal to
$\frac{k-t}{k}$ finish the proof.

∎

##  III Byzantine-Resistant PIR scheme

Let us construct a $k$-server PIR scheme with $t$-colluding and $b$-byzantine
servers by modifying the construction from Section II-C. For simplicity, we
consider a non-universal case when we request responses from exactly $k\geq r$
servers, where $r$ is the recovery threshold and employ the idea of [18] to
include error-correction capability in our PIR scheme.  Scheme $\Pi_{2}$:
$k$-server $t$-private $b$-byzantine resistant PIR

Let $t$, $r$, $k$ be positive integers satisfying $t<r-2b<k-2b\leq k\leq q$,
$\Delta=r-2b-t$ and $\Delta|(k-2b-t)$. Denote by
$s\triangleq\frac{k-2b-t}{\Delta}$. Let
$\Omega_{\alpha}=\\{\alpha_{1},\ldots,\alpha_{\Delta}\\}\subset\mathbb{F}_{q^{s}}$,
$\Omega_{\chi}=\\{\chi_{1},\ldots,\chi_{t}\\}\subset\mathbb{F}_{q^{s}}$ and
$\Omega_{\beta}=\\{\beta_{1},\ldots,\beta_{k}\\}\subseteq\mathbb{F}_{q}$ be
publicly known non-intersecting sets such that all elements of
$\Omega_{\alpha}$ are roots of distinct monic irreducible polynomials of
degree $s$ over $\mathbb{F}_{q}$.

Let us represent the database $\mathbf{x}$ with $m$ files as a
$m\times\Delta$-array. Let the $(i,j)$-th entry of $\mathbf{x}$ be
$x^{(i)}_{j}$. Then we set the file
$f^{(i)}\triangleq[x^{(i)}_{1},\ldots,x^{(i)}_{\Delta}]$. Therefore,

$\mathbf{x}=\begin{bmatrix}x^{(1)}_{1}&x^{(1)}_{2}&\cdots&x^{(1)}_{\Delta}\\\
x^{(2)}_{1}&x^{(2)}_{2}&\cdots&x^{(2)}_{\Delta}\\\
\vdots&\vdots&\ddots&\vdots\\\
x^{(m)}_{1}&x^{(m)}_{2}&\cdots&x^{(m)}_{\Delta}\end{bmatrix}=\begin{bmatrix}f^{(1)}\\\
f^{(2)}\\\ \vdots\\\ f^{(m)}\end{bmatrix}\,.$

Then we define $\mathbf{e}_{(i,j)}$ be the $m\times\Delta$ indicator array for
the database components. In other words, the $(i,j)$th entry of
$\mathbf{e}_{(i,j)}$ is one, while all other entries of $\mathbf{e}_{(i,j)}$
are zero. We replicate the database $\mathbf{x}$ on $k$ servers.

  * •

Query generation algorithm: To retrieve the file $\iota\in[m]$ user randomly
generates $t$ $(m\times\Delta)$-arrays
$\mathbf{r}^{(1)},\ldots,\mathbf{r}^{(t)}$ and draw a random
degree-$t+\Delta-1$ curve

$\displaystyle\mathbf{g}(\xi)$
$\displaystyle\triangleq\sum_{j=1}^{\Delta}\prod_{\ell\in[\Delta]\setminus\\{j\\}}\left(\frac{\xi-\alpha_{\ell}}{\alpha_{j}-\alpha_{\ell}}\right)\prod_{\ell=1}^{t}\left(\frac{\xi-\chi_{\ell}}{\alpha_{j}-\chi_{\ell}}\right)\mathbf{e}_{(i,j)}$
$\displaystyle+\sum_{h=1}^{t}\prod_{\ell=1}^{\Delta}\left(\frac{\xi-\alpha_{\ell}}{\chi_{h}-\alpha_{\ell}}\right)\prod_{\ell\in[t]\setminus\\{h\\}}\left(\frac{\xi-\chi_{\ell}}{\chi_{h}-\chi_{\ell}}\right)\mathbf{r}^{(h)}$
(25)

that resides in $\mathbb{F}_{q^{s}}^{m\times\Delta}$ and passes through points
$(\alpha_{1},\mathbf{e}_{(\iota,1)}),\ldots,(\alpha_{\Delta},\mathbf{e}_{(\iota,\Delta)})$.
Query to server $j\in[k]$ is $\mathbf{g}(\beta_{j})$. We note that both
$\mathbf{g}$ and $\mathbf{r}^{(h)}$ depend on retrieved index $\iota$, but we
omit the subscript $\iota$ for readability.

  * •

Answer generation algorithm: Upon receive the query $\mathbf{g}(\beta_{j})$,
server $j\in[k]$ computes the Frobenius inner product
$\langle\mathbf{g}(\beta_{j}),\mathbf{x}\rangle$. We can observe that

$\displaystyle\langle\mathbf{g}(\xi),\mathbf{x}\rangle=\sum_{j=1}^{\Delta}\prod_{\ell\in[\Delta]\neq\\{j\\}}\left(\frac{\xi-\alpha_{\ell}}{\alpha_{j}-\alpha_{\ell}}\right)\prod_{\ell=1}^{t}\left(\frac{\xi-\chi_{\ell}}{\alpha_{j}-\chi_{\ell}}\right)x^{(\iota)}_{j}$
$\displaystyle+\sum_{h=1}^{t}\prod_{\ell=1}^{\Delta}\left(\frac{\xi-\alpha_{\ell}}{\chi_{h}-\alpha_{\ell}}\right)\prod_{\ell\in[t]\setminus\\{h\\}}\left(\frac{\xi-\chi_{\ell}}{\chi_{h}-\chi_{\ell}}\right)\langle\mathbf{r}^{(h)},\mathbf{x}\rangle,$

which is a polynomial in $\xi$ of degree $\Delta+t-1=r-2b-1$. We call this
polynomial $\phi(\xi)$ and observe further that
$\phi(\alpha_{i})=x^{(\iota)}_{i}$ for $i\in[\Delta]$.

    * –

For retrieval from answers from $r$ servers, server $j$ responds with value of
$\mathbf{a}_{j}=\phi(\beta_{j})\in\mathbb{F}_{q^{s}}$.

    * –

For retrieval from answers from $k$ servers, server responds with

$\mathbf{a}_{j}=\textrm{Tr}(v_{j}\phi(\beta_{j}))\in\mathbb{F}_{q},$ (26)

where

$v_{j}=\prod_{\ell=1}^{\Delta}(\beta_{j}-\alpha_{\ell})^{-1}\times\prod_{\ell\in[k]\setminus\\{j\\}}(\beta_{j}-\beta_{\ell})^{-1}.$
(27)

  * •

File retrieval algorithm

    * –

For retrieval from answers from $r$ servers, the user applies any Reed-Solomon
code decoding algorithm (see, for example, [20]).

    * –

For retrieval from answers from $k$ servers, the user decodes the vector

$\left(\prod_{\ell=1}^{\Delta}\tilde{f}_{\ell}(\beta_{1})\textrm{Tr}(v_{1}\phi(\beta_{1})),\ldots,\prod_{\ell=1}^{\Delta}\tilde{f}_{\ell}(\beta_{k})\textrm{Tr}(v_{k}\phi(\beta_{k}))\right),$
(28)

where $\tilde{f}_{\ell}(\xi)$ is the minimal polynomial of $\alpha_{\ell}$
over $\mathbb{F}_{q}$, as a codeword of Generalized Reed-Solomon code over
$\mathbb{F}_{q}$ by any decoding algorithm (see, for example, [20]) and
extract the values

$\textrm{Tr}(v_{j}\phi(\beta_{j})),\;\;\textrm{for}\;\;j\in[k].$ (29)

After it, user prepares a basis $\\{\theta_{1},\ldots,\theta_{s}\\}$ for
$\mathbb{F}_{q^{s}}$ over $\mathbb{F}_{q}$ and its trace-orthogonal basis
$\\{\eta_{1},\ldots,\eta_{s}\\}$. After it, the user chooses polynomials
$h_{i\delta}\in\mathbb{F}_{q}[\xi]$ of degree less than $s$ for all
$i\in[\Delta]$ and $\delta\in[s]$ so that

$h_{i\delta}(\alpha_{i})=u_{i}^{-1}\eta_{\delta}\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}^{-1}(\alpha_{i}),$
(30)

and

$u_{i}=\prod_{\ell\in[\Delta]\setminus\\{i\\}}(\alpha_{i}-\alpha_{\ell})^{-1}\times\prod_{j=1}^{k}(\alpha_{i}-\beta_{j})^{-1}.$
(31)

The user retrieves the file of interest by

$\displaystyle
x_{i}^{(\iota)}=\phi(\alpha_{i})=-\sum_{\delta=1}^{s}\theta_{\delta}\Bigg{(}\sum_{j=1}^{k}h_{i\delta}(\beta_{j})\textrm{Tr}(v_{j}\phi(\beta_{j}))\cdot$
$\displaystyle\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\Bigg{)},$
(32)

for all $i\in[\Delta]$.

######  Theorem 2.

Scheme $\Pi_{2}$ is $k$-server $t$-private $b$-byzantine PIR over
$\mathbb{F}_{q^{s}}$ with file size $(k-2b-t)\log(q)$ and recovery threshold
$r$ that achieves the asymptotic capacity (2) for any given $\Delta$ and $r$
so that

$t<r-2b<k-2b\leq q,\;\Delta=r-2b-t\;\;\textrm{and}\;\;\Delta|(k-2b-t),$

and $s=\frac{k-2b-t}{\Delta}$.

###### Proof.

According to the definition of $k$-server $t$-private $b$-byzantine resistant
PIR, we will prove privacy and correctness properties and show that responses
from $r$ servers are enough for file retrieval in presence of up to $b$
incorrect responses. The proof of privacy coincides with privacy proof for
Theorem 1 and is omitted here.

The property that responses from $r$ servers are enough for file retrieval
follows from the fact that values
$(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),\ldots,\phi(\beta_{k}))$
can be seen as a codeword of Reed-Solomon code

$\displaystyle\textrm{RS}_{r-2b}$
$\displaystyle(\Omega_{\alpha}\cup\Omega_{\beta})=\\{(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),$
$\displaystyle\ldots,\phi(\beta_{k}))|\phi\in\mathbb{F}_{q^{s}}[\xi],\deg(\phi)<r-2b\\}.$
(33)

As a result, by values of polynomial $\phi$ in any $r$ points, we can
correctly interpolate it in the presence of $b$ incorrect value utilizing any
Reed-Solomon decoding algorithm (see, for example, [20]).

Let us prove the correctness of scheme $\Pi_{2}$. It is clear that dual of
$\textrm{RS}_{r-2b}$ is a Generalized-Reed Solomon code [20] defined as

$\displaystyle\textrm{GRS}_{k+\Delta-(r-2b)}(\Omega_{\alpha}\cup\Omega_{\beta})=\\{u_{1}h(\alpha_{1}),\ldots,u_{\Delta}h(\alpha_{\Delta}),v_{1}h(\beta_{1}),$
$\displaystyle\ldots,v_{k}h(\beta_{k}))|h\in\mathbb{F}_{q^{s}}[\xi],\deg(h)<k+\Delta-r+2b=k-t\\},$
(34)

where
$u_{i}=\prod_{\ell\in[\Delta]\setminus\\{i\\}}(\alpha_{i}-\alpha_{\ell})^{-1}\times\prod_{j=1}^{k}(\alpha_{i}-\beta_{j})^{-1}$
and
$v_{j}=\prod_{\ell=1}^{\Delta}(\beta_{j}-\alpha_{\ell})^{-1}\times\prod_{\ell\in[k]\setminus\\{j\\}}(\beta_{j}-\beta_{\ell})^{-1}$
for $i\in[\Delta]$ and $j\in[k]$.

As each $\alpha_{j},j\in[\Delta]$ is a root of different monic irreducible
polynomial $\tilde{f}_{j}$ of degree $s$ over $\mathbb{F}_{q}$ we have that

$\tilde{f}_{j}(\alpha_{j})=0\;\;\;\tilde{f}_{j}(\alpha_{i})\neq
0\;\;\;\textrm{for}\;\;i\in[\Delta],j\neq i$ (35)
$\prod_{j\in[\Delta]\setminus\\{i\\}}\tilde{f}_{j}(\alpha_{n})=0\;\;\;\textrm{for}\;\;n\in[\Delta],n\neq
i.$ (36)

Let $\\{\theta_{1},\ldots,\theta_{s}\\}$ be the basis of $\mathbb{F}_{q^{s}}$
over $\mathbb{F}_{q}$ and $\\{\eta_{1},\ldots,\eta_{s}\\}$ is its trace-
orthogonal basis. For each $\delta\in[s]$ and $i\in[\Delta]$, we can represent
the element
$u_{i}^{-1}\eta_{\delta}\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}^{-1}(\alpha_{i})$
as the value of function $h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$ of degree
less than $s$ at point $\alpha_{i}$. It is clear that
$\deg(h_{i\delta}\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell})<\Delta
s<k-t$ and hence such functions belong to the dual Generalized Reed-Solomon
code (III). Also, we have that

$h_{i\delta}(\alpha_{i})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{i})=u_{i}^{-1}\eta_{\delta}$
(37)

and

$h_{i\delta}(\alpha_{n})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{n})=0\;\;\;\textrm{for
all}\;\;n\in[\Delta],n\neq i.$ (38)

Consequently,

$\displaystyle\big{(}u_{1}h_{i\delta}(\alpha_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{1}),\ldots,u_{\Delta}h_{i\delta}(\alpha_{\Delta})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\alpha_{\Delta}),$
$\displaystyle
v_{1}h_{i\delta}(\beta_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{1}),\ldots,v_{k}h_{i\delta}(\beta_{k})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{k})\big{)}$
$\displaystyle\cdot(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),\ldots,\phi(\beta_{k}))^{T}=0.$
(39)

Utilizing the properties of function $h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$
we can write down that

$\displaystyle\eta_{\delta}\phi(\alpha_{i})+v_{1}h_{i\delta}\phi(\beta_{1})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{1})+\ldots+$
$\displaystyle
v_{k}h_{i\delta}\phi(\beta_{k})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{k})=0$
(40)

and

$\eta_{\delta}\phi(\alpha_{i})=-\sum_{j=1}^{k}\left(v_{j}h_{i\delta}(\beta_{j})\phi(\beta_{j})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right).$
(41)

Applying trace-mapping function to both sides of equation (41) and utilizing
the facts that $h_{i\delta}(\xi)\in\mathbb{F}_{q}[\xi]$,
$\tilde{f}_{\ell}(\xi)\in\mathbb{F}_{q}[\xi]$ and $\beta_{j}\in\mathbb{F}_{q}$
for all $i,\ell\in[\Delta]$, $\delta\in[s]$, $j\in[k]$ together with the
linearity of trace-mapping function we obtain that

$\displaystyle\textrm{Tr}(\eta_{\delta}\phi(\alpha_{i}))=-\sum_{j=1}^{k}\textrm{Tr}\left(v_{j}\phi(\beta_{j})h_{i\delta}(\beta_{j})\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right)=$
$\displaystyle-\sum_{j=1}^{k}h_{i\delta}(\beta_{j})\left(\textrm{Tr}\left(v_{j}\phi(\beta_{j})\right)\prod_{\ell\in[\Delta]\setminus\\{i\\}}\tilde{f}_{\ell}(\beta_{j})\right)$
(42)

From the fact that $\\{\theta_{1},\ldots,\theta_{s}\\}$ and
$\\{\eta_{1},\ldots,\eta_{s}\\}$ are trace-orthogonal bases of
$\mathbb{F}_{q^{s}}$ over $\mathbb{F}_{q}$ it is clear (see, for example,
[21][Ch. $2$]) that

$x_{i}^{(\iota)}=\phi(\alpha_{i})=\sum_{\delta=1}^{s}\theta_{\delta}\textrm{Tr}(\eta_{\delta}\phi(\alpha_{i}))$
(43)

an hence all $\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta})$ can be recovered
by accessing $\textrm{Tr}(v_{j}\phi(\beta_{j}))$ from all involved servers
$j=1,\ldots,k$.

Let us show that we can correctly recover
$\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta})$ even in case of at most $b$
incorrect values of $\textrm{Tr}(v_{j}\phi(\beta_{j}))$. Following the ideas
from [18], let us replace the functions $h_{i\delta}$ in derivations above by
functions

$\tilde{h}_{e}(\xi)=\xi^{e}\prod_{\ell\in[\Delta]}\tilde{f}_{e}(\xi)\in\mathbb{F}_{q}[\xi].$
(44)

It is clear that $\tilde{h}_{e}(\alpha_{i})=0$ for all $i\in[\Delta]$ and
$\deg(h_{e}(\xi))<\Delta s+e$. Hence, for all $e<2b$, we have that
$\deg(h_{e}(\xi))<k-t$ and, as a result, these functions belong to the dual
Generalized Reed-Solomon code (III). Consequently,

$\displaystyle(u_{1}\tilde{h}_{e}(\alpha_{1}),\ldots,u_{\Delta}\tilde{h}_{e}(\alpha_{\Delta}),v_{1}\tilde{h}_{e}(\beta_{1}),\ldots,v_{k}\tilde{h}_{e}(\beta_{k}))\cdot$
$\displaystyle(\phi(\alpha_{1}),\ldots,\phi(\alpha_{\Delta}),\phi(\beta_{1}),\ldots,\phi(\beta_{k}))^{T}=$
$\displaystyle
v_{1}\tilde{h}_{e}(\beta_{1})\phi(\beta_{1})+\ldots+v_{k}\tilde{h}_{e}(\beta_{k})\phi(\beta_{k})=0.$
(45)

As $\tilde{h}_{e}(\xi)\in\mathbb{F}_{q}[\xi]$ and
$\\{\beta_{1},\ldots,\beta_{k}\\}\subseteq\mathbb{F}_{q}$, applying the trace-
mapping function to both sides of equation (III) and utilizing its linearity,
we have

$\displaystyle\beta_{1}^{e}\prod_{\ell\in[\Delta]}\tilde{f}_{\ell}(\beta_{1})\textrm{Tr}(v_{1}\phi(\beta_{1}))+\ldots$
$\displaystyle+\beta_{k}^{e}\prod_{\ell\in[\Delta]}\tilde{f}_{\ell}(\beta_{k})\textrm{Tr}(v_{k}\phi(\beta_{k}))=0,$
(46)

where $e=0,1,\ldots,2b-1$, and $\beta_{j}$,
$\prod_{\ell\in[\Delta]}\tilde{f}_{\ell}(\beta_{k})$,
$\textrm{Tr}(v_{j}\phi(\beta_{j}))$ belong to $\mathbb{F}_{q}$ for all
$j\in[k]$. Hence, elements
$\prod_{\ell\in[\Delta]}\tilde{f}_{\ell}(\beta_{k})\textrm{Tr}(v_{k}\phi(\beta_{k}))$
form a codeword of Generalized Reed-Solomon code over $\mathbb{F}_{q}$ of
length $k$ and dimension $k-2b$. This code can correct up to $b$ errors, and
user can retrieve the correct values of $\textrm{Tr}(v_{j}f(\beta_{j}))$ from
server responses for all $j\in[k]$ [20].

The observations that each file consists of $\Delta$ elements of
$\mathbb{F}_{q^{s}}$ for $s=\frac{k-t-2b}{\Delta}$ and download rate is equal
to $\frac{k-t-2b}{k}$ finish the proof.

∎

##  IV Lower bound on the file size

For any given base field $\mathbb{F}_{q}$ of size $q\geq k$, the size of file
$\Delta s\log_{2}q$ bits depends on the parameter $\Delta s$. In this section,
following the derivations of [17, Section V], we describe the class of
byzantine-resistant PIR schemes for an asymptotically large number of files,
and then show that the size of the file in our scheme is optimal.

######  Definition 4 (Balanced byzantine-resistant PIR).

The byzantine-resistant PIR scheme is balanced if the client downloads a
single element of the same subfield $\mathbb{F}_{q^{R}}$ from each involved
server.

######  Definition 5 (Rate optimal byzantine-resistant PIR).

Byzantine-resistant PIR scheme is rate optimal if
$H(f^{(i)})=(r-2b-t)s=s\Delta$, where $f^{(i)}$ is the $i$-th file.

After introducing the necessary definitions, we can formulate the main theorem
of this section.

######  Theorem 3.

For a balanced rate-optimal byzantine-resistant PIR scheme that achieves the
minimum download rate for a large enough number of files, the following hold:

$(r-2b-t)|(k-2b-t)$ (47) $s\Delta\geq k-2b-t$ (48)

###### Proof.

As the considered scheme is rate-optimal, $\Delta=r-2b-t$. Let us consider the
scenario in which the client downloads a single element of
$\mathbb{F}_{q^{R}}$ from each of $k$ servers, and the scheme achieves the
asymptotic capacity. It follows that

$k\log_{q^{s}}q^{R}=\frac{k}{k-2b-t}\Delta s.$ (49)

As a result $\Delta s=R(k-2b-t)$. Since $s$ is a positive integer and
$\mathbb{F}_{q^{R}}$ is a subfield of $\mathbb{F}_{q^{s}}$, then $R$ divides
$s$ and hence theorem statement follows. ∎

######  Corollary 4.

The scheme $\Pi_{2}$ is a balanced rate-optimal byzantine-resistant PIR with
optimal file size.

##  V Comparison

In this section, we give a comparison of PIR schemes $\Pi_{1}$ and $\Pi_{2}$
with Staircase-PIR from [22]. We denote the latter as scheme $\mathbb{A}_{1}$
and formulate its parameters in form of the following theorem.

######  Theorem 5.

Scheme $\mathbb{A}_{1}$ is $k$-server $t$-private PIR over $\mathbb{F}_{q}$
with file size $(r-t)(k-t)\log(q)$ and recovery threshold $r$ that achieves
the asymptotic capacity (2) for $b=0$ and any given r so that

$t<r<k\leq q.$

Scheme $\mathbb{A}_{1}$ assumes that servers are honest-but-curious and
provide correct answers. To add the $b$-byzantine resistance, we can utilize
error-correction capabilities of underlined staircase codes in the same way as
it was done in [23]. We present the parameters of resulted scheme
$\mathbb{A}_{2}$ in the following theorem.

######  Theorem 6.

Scheme $\mathbb{A}_{2}$ is $k$-server $t$-private $b$-byzantine resistant PIR
over $\mathbb{F}_{q}$ with file size $(r-2b-t)(k-2b-t)\log(q)$ and recovery
threshold $r$ that achieves the asymptotic capacity (2) for any given $r$ so
that

$t<r-2b<k-2b<k\leq q.$

To justify ignoring the upload cost, we repeat each scheme $l$ times and
summarize the parameters in Table 1. We note that our schemes work over the
extended field, while schemes $\mathcal{A}_{1}$ and $\mathbb{A}_{2}$ work over
the base field. Nevertheless, in $\mathbb{A}_{1}$ and $\mathbb{A}_{2}$, each
component of the file consists of multiple field symbols that result in a big
file size and retrieval delay.

TABLE 1: Parameters of PIR scheme with optimal download rate. All parameters
are measured in bits.

| $\Pi_{1}$ | $\Pi_{2}$ | $\mathbb{A}_{1}$ | $\mathbb{A}_{2}$
---|---|---|---|---
File size | $l(k-t)\log(q)$ | $l(k-2b-t)\log(q)$ | $l(r-t)(k-t)\log(q)$ | $l(r-2b-t)(k-2b-t)\log(q)$
Field |  $\mathbb{F}_{q^{s}}$, where $s=\frac{k-t}{r-t}$ |  $\mathbb{F}_{q^{s}}$, where $s=\frac{k-2b-t}{r-2b-t}$ | $\mathbb{F}_{q}$ | $\mathbb{F}_{q}$
Download cost | $lk\log(q)$ | $lk\log(q)$ | $lk(r-t)\log(q)$ | $lk(r-2b-t)\log(q)$
Download rate | $1-\frac{t}{k}$ | $1-\frac{2b+t}{k}$ | $1-\frac{t}{k}$ | $1-\frac{2b+t}{k}$
Capacity | $1-\frac{t}{k}$ | $1-\frac{2b+t}{k}$ | $1-\frac{t}{k}$ | $1-\frac{2b+t}{k}$
Byzantine-resistance | $0$ | $b\neq 0$ | $0$ | $b\neq 0$

##  VI Conclusion

We considered the problem of designing a Private Information Retrieval scheme
resistant to the adversarial behavior of servers. We focused on download cost
minimization and proposed a capacity-achieving scheme with a small file size.
We also formally proved that such a file size is optimal solving the problem
pointed out by Banawan and Ulukus in [12].

## References

  * [1] Sennur Ulukus et al.  “Private Retrieval, Computing, and Learning: Recent Progress and Future Challenges”  In _IEEE Journal on Selected Areas in Communications_ 40.3, 2022, pp. 729–748
  * [2] Rafail Ostrovsky and William E. Skeith  “A Survey of Single-Database Private Information Retrieval: Techniques and Applications”, 2007, pp. 393–411
  * [3] B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan  “Private information retrieval”  In _Proceedings of IEEE 36th Annual Foundations of Computer Science_ , 1995, pp. 41–50
  * [4] David Woodruff and Sergey Yekhanin  “A Geometric Approach to Information-Theoretic Private Information Retrieval”  In _SIAM Journal on Computing_ 37.4, 2007, pp. 1046–1056
  * [5] Sergey Yekhanin  “Towards 3-Query Locally Decodable Codes of Subexponential Length”  In _J. ACM_ 55.1 New York, NY, USA: Association for Computing Machinery, 2008
  * [6] Zeev Dvir and Sivakanth Gopi  “2-Server PIR with Subpolynomial Communication”  In _J. ACM_ 63.4 New York, NY, USA: Association for Computing Machinery, 2016
  * [7] Nihar B. Shah, K.. Rashmi and Kannan Ramchandran  “One extra bit of download ensures perfectly private information retrieval”  In _2014 IEEE International Symposium on Information Theory_ , 2014, pp. 856–860
  * [8] Terence H. Chan, Siu-Wai Ho and Hirosuke Yamamoto  “Private information retrieval for coded storage”  In _2015 IEEE International Symposium on Information Theory (ISIT)_ , 2015, pp. 2842–2846
  * [9] Razane Tajeddine, Oliver W. Gnilke and Salim El Rouayheb  “Private Information Retrieval From MDS Coded Data in Distributed Storage Systems”  In _IEEE Transactions on Information Theory_ 64.11, 2018, pp. 7081–7093
  * [10] Hua Sun and Syed Ali Jafar  “The Capacity of Robust Private Information Retrieval With Colluding Databases”  In _IEEE Transactions on Information Theory_ 64.4, 2018, pp. 2361–2370
  * [11] Liang Feng Zhang and Huaxiong Wang  “Multi-Server Verifiable Computation of Low-Degree Polynomials”  In _2022 IEEE Symposium on Security and Privacy (SP)_ , 2022, pp. 596–613
  * [12] Karim Banawan and Sennur Ulukus  “The Capacity of Private Information Retrieval from Byzantine and Colluding Databases”  In _IEEE Transactions on Information Theory_ 65.2, 2019, pp. 1206–1219
  * [13] Kaoru Kurosawa  “How to Correct Errors in Multi-server PIR”  In _Advances in Cryptology – ASIACRYPT 2019_ , 2019, pp. 564–574
  * [14] K Devet, I Goldberg and N Heninger  “Optimally Robust Private Information Retrieval”  In _21st USENIX Security Symposium (USENIX Security 12)_ , 2012, pp. 269–283
  * [15] Amos Beimel  “Robust Private Information Retrieval”  In _Encyclopedia of Cryptography, Security and Privacy_ Springer Berlin Heidelberg, 2019, pp. 1–3
  * [16] J. Plank, K. Greenan and E.. Miller  “Screaming Fast Galois Field Arithmetic Using Intel SIMD Extensions”  In _11th USENIX Conference on File and Storage Technologies (FAST ’13)_ , 2013
  * [17] Jian Ding, Changlu Lin, Huaxiong Wang and Chaoping Xing  “Communication Efficient Secret Sharing With Small Share Size”  In _IEEE Transactions on Information Theory_ 68.1, 2022, pp. 659–669
  * [18] Zitan Chen, Min Ye and Alexander Barg  “Enabling Optimal Access and Error Correction for the Repair of Reed–Solomon Codes”  In _IEEE Transactions on Information Theory_ 66.12, 2020, pp. 7439–7456
  * [19] Thomas M. Cover and Joy A. Thomas  “Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)”  Wiley-Interscience, 2006
  * [20] Ron.. Roth  “Introduction to Coding Theory”  Cambridge University Press, 2006
  * [21] Rudolf Lidl and Harald Niederreiter  “Finite Fields”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 1996
  * [22] Rawad Bitar and Salim El Rouayheb  “Staircase-PIR: Universally Robust Private Information Retrieval”  In _2018 IEEE Information Theory Workshop (ITW)_ , 2018, pp. 1–5
  * [23] Rawad Bitar and Sidharth Jaggi  “Communication Efficient Secret Sharing in the Presence of Malicious Adversary”  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 548–553


$\displaystyle\;\;+{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}\right)}\Pi_{\mathrm{safe}}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}\right)}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert\Pi_{\mathrm{safe}}Q_{m,[m-\ell-1,m],k}f\right\rVert}_{2}$
(Lemma 66) $\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,R_{m,[m-1],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}$
$\displaystyle+{\left|\left\langle
f,Q_{m,[m-1],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-\ell-1,m],k}f\right\rangle\right|}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\mathinner{\\!\left\lVert
f\right\rVert}_{2}\mathinner{\\!\left\lVert{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-\ell-1,m],k}\right\rVert}_{2}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell/2-10}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}+\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}.$ (Equation 8 below)

To establish Equation 8 we compute

$\displaystyle\mathinner{\\!\left\lVert{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-1],k}f\right\rVert}_{2}^{2}$
$\displaystyle=$ $\displaystyle\left\langle
f,Q_{m,[m-1],k}{\left(\mathrm{Id}-\Pi_{\mathrm{safe}}\right)}Q_{m,[m-1],k}f\right\rangle$
(self-adjointness (55) $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
Q_{m,[m-1],k}f\right\rVert}_{2}\mathinner{\\!\left\lVert
R_{m,[m-1],k}f\right\rVert}_{2}$ $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell-1}}\mathinner{\\!\left\lVert
f\right\rVert}_{2}^{2}.$ (8)

The first inequality follows from Lemma 41 the fact that
$\mathrm{Supp}(f)\subseteq B_{\geq 1}^{\mathrm{safe}}$ and for any $X\in
B_{\geq 1}^{\mathrm{safe}}$, we have $\operatorname{{\bf
Pr}}_{\mathbf{Y}\sim\mathcal{C}^{m,[m-\ell-1,m],k}_{X}}{\left[\mathbf{Y}\not\in
B_{\geq 1}^{\mathrm{safe}}\right]}\leq\frac{k^{2}}{2^{\ell-1}}$ (using the
same proof as Lemma 62). The second term in the sum Equation 7 follows from
the same argument. ∎

######  Corollary 68.

Let $k\geq 2$ and $f\mathrel{\mathop{\mathchar 58\relax}}\\{\pm
1\\}^{mk}\to\mathbb{R}$ be supported on $B_{\geq 1}^{\mathrm{safe}}$. Then

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}\leq\frac{k^{2}}{2^{\ell/2-50}}\langle
f,f\rangle.$

###### Proof.

We directly compute

$\displaystyle{\left|\left\langle
f,R_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}+$
$\displaystyle\;\;{\left|\left\langle
f,{\left(R_{m,[m-\ell-1,m],k}-Q_{m,[m-\ell-1,m],k}\right)}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-R_{m,[m],k}\right)}f\right\rangle\right|}+\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle$ (Lemma 67, first part) $\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle+{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(Q_{m,[m-1],k}-Q_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle\;\;\;+{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}-R_{m,[m],k}+Q_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle=$ $\displaystyle\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle+{\left|\left\langle
f,Q_{m,[m-\ell-1,m],k}{\left(R_{m,[m-1],k}-Q_{m,[m-1],k}-R_{m,[m],k}+Q_{m,[m],k}\right)}f\right\rangle\right|}$
$\displaystyle=$ $\displaystyle\frac{k^{2}}{2^{\ell/2-20}}\langle
f,f\rangle+\frac{k^{2}}{2^{\ell/2-20}}\langle f,f\rangle.$ (Lemma 67, second
part)

For the second-to-last equality we used that
$Q_{m,[m-\ell-1,m],k}{\left(Q_{m,[m-1],k}-Q_{m,[m],k}\right)}=0$ because
$Q_{m,S,k}Q_{m,T,k}=Q_{m,S\cup T,k}$ for any $S,T\subseteq[m]$. ∎

##  7 Computational Hardness of Inverting Block Ciphers

In this section we show a connection between the existence of one-way
functions (OWFs) and the hardness of inverting classes of block ciphers. We
view the problem of inverting block ciphers as equivalent to the problem of
learning a reversible circuit that computes a permutation using query access
to the permutation, which frames the problem as a minimum (reversible) circuit
size problem (MRCSP).

The idea is essentially the same as that of Kabanets and Cai [KC00], who
showed that the analogous result about the minimum circuit size problem
(MCSP). In that paper, it is observed that pseudorandom function ensembles
computed by small circuits are exactly the type of input distributions to the
MCSP problem that “fool” algorithms for MCSP running in polynomial time. So
the existence of OWFs (which by [GGM86, HILL99] implies the existence of such
pseudorandom function ensembles) precludes the existence of polynomial time
algorithms for MCSP.

Thus, to prove the result for MRCSP, we would like to construct pseudorandom
permutations implementable by small reversible circuits. It is known how to
construct pseudorandom permutations implementable by small circuits by the
Feistel cipher construction Luby and Rackoff [LR88], but these circuits are
not necessarily reversible. We build on this construction by simulating these
circuits using reversible circuits, as one often does in the context of
quantum computing, for example. The problem with this is that such simulation
requires ancilla bits (let’s say $n^{d}$ total bits are required), which may
reveal information about the computation, so naively simulating the Feistel
cipher does not yield a pseudorandom permutation. At this point we are viewing
our ciphers as acting on $\\{0,1\\}^{n^{d}}$. Our solution is to simply hide
away the ancilla bits with another round of the Feistel cipher, this time
applied to the ancilla bits. We iterate this a polynomial number of times, and
find that this is sufficient for pseudorandomness.

We note here that the construction of Luby-Rackoff can be made reversible when
the underlying pseudorandom function is computable in $\mathsf{NL}$ with no
extra ancillas by a construction of Cleve [Cle90].

###  7.1 Pseudorandom Permutations Implementable Using Reversible Circuits

Throughout this section we use $\\{0,1\\}$-notation and interpret $\\{0,1\\}$
as the field $\mathbb{F}_{2}$ with two elements.

######  Definition 69.

Fix $\kappa\mathrel{\mathop{\mathchar 58\relax}}\mathbb{N}\to\mathbb{N}$ and
$\varepsilon\mathrel{\mathop{\mathchar 58\relax}}\mathbb{N}\to[0,1]$. A family
(indexed by $n$) of maps map $f_{(\cdot)}^{n}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{\kappa(n)}\to{\left\\{f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}\right\\}}$ is an
$\varepsilon$-pseudorandom function ensemble against a class of adversaries
$\mathcal{C}$999Here $\mathcal{C}$ actually defines a set $\mathcal{C}_{n}$ of
adversaries for each $n$. We will commonly take $\mathcal{C}$ to be the class
of circuits with size restricted by some function $r\mathrel{\mathop{\mathchar
58\relax}}\mathbb{N}\to\mathbb{N}$, so that $\mathcal{C}_{n}$ consists of the
set of all circuits of size at most $r(n)$. with key length $\kappa$ if for
all large enough $n$ and $\mathcal{A}\in\mathcal{C}_{n}$, we have

$\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathsf{key}\in\\{0,1\\}^{\kappa(n)}}{\left[\mathcal{A}^{f^{n}_{\mathsf{key}}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{\\{0,1\\}^{n}}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}\right|}\leq\varepsilon(n).$

Here (and throughout this section) $\mathcal{A}^{f}$ denotes the circuit
$\mathcal{A}$ with nonadaptive oracle gates computing $f$ (all oracles are at
the bottom of the circuit).

Given the existence of OWFs, we can construct efficiently-implementable
ensembles of pseudorandom functions by constructing pseudorandom generators.

######  Theorem 70 ([HILL99] \+ [GGM86]).

If OWFs exist, then there exists constants $c,d>0$ such that for any large
enough $n$ there exists a $\delta>0$ and $2^{-n^{\delta}}$-pseudorandom
function ensemble against $\mathsf{P}/\mathrm{poly}$ implementable by a family
of Boolean circuits with size at most $n^{d}$.101010The family $f_{(\cdot)}$
is implementable by circuits of size at most $s$ if every
$f^{n}_{\mathsf{key}}$ is computed using Boolean circuits of size at most
$s(n)$. By Boolean circuits we mean circuits with fan-in at most 2 and
$(\mathsf{AND},\mathsf{OR},\mathsf{NOT})$ gates.

We first show how to get pseudorandom permutation ensembles implemented by
short reversible circuits from pseudorandom function ensembles implemented by
small Boolean circuits. Throughout this section reversible circuits are those
with arbitrary 3-bit gates, and Boolean circuits have 2-bit gates computing
$\mathsf{AND}$ and $\mathsf{OR}$ and 1-bit gates computing $\mathsf{NOT}$. The
specific gate set is not important, since we can simulate universal gate sets
with other universal gate sets using constant overhead.

##### Implementing Luby-Rackoff Reversibly.

Fix any positive integer $N$, and assume that $N=ns$ for some $s$, so that we
regard strings in $\\{0,1\\}^{N}$ as $s$-tuples of $n$-bit strings. That is,
we write $x\in\\{0,1\\}^{N}$ as $x=(x_{1},\dots,x_{s})$ where each
$x_{i}\in\\{0,1\\}^{n}$.

Figure 2: An illustration of
$p^{N}_{{\left(f_{{(1,2)}},\dots,f_{{s(n)}}^{2}\right)}}$. Here each wire
carries a single $n$-bit string, and there are $s(n)$ wires. The first layer
applies the operation $\mathsf{Ctr}_{f_{(1,2)}^{(1,2)}}$, the second layer
applies $\mathsf{Ctr}_{f_{(1,3)}^{(1,3)}}$, etc. We apply the operations in
two phases. The first phase consists of the operations
$\mathsf{Ctr}_{f_{(i,j)}^{(i,j)}}$ for $i\neq j\in[s(n)]$. The second phase
applies the operations $\mathsf{Ctr}_{f_{i}^{1}}^{(i,i+1)}$ and
$\mathsf{Ctr}_{f_{i}^{2}}^{(i+1,i)}$.

######  Definition 71.

For each $a,b\in[s]$ and a function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ define the following permutation
$\mathsf{Ctr}_{f}^{(i,j)}$ on $\\{0,1\\}^{N}$:

$\displaystyle\mathsf{Ctr}_{f}^{(a,b)}(x_{1},\dots,x_{s})={\left(x_{1},\dots,x_{a-1},x_{a},x_{a+1},\dots,x_{b-1},x_{j}+f(x_{a}),x_{b+1},\dots,x_{s}\right)}.$

The notation $\mathsf{Ctr}$ refers to “controlled”, so
$\mathsf{Ctr}_{f}^{(a,b)}$ is a “controlled $f$” with control string $a$ and
target string $b$, since such functions can be thought of as generalization of
$\mathsf{CNOT}$s.

We now describe our pseudorandom ensemble of functions
${\left\\{p^{N}_{(\cdot)}\right\\}}_{N\in\mathbb{N}}$ implemented using
reversible circuits. Let ${\left\\{f^{n}_{(\cdot)}\right\\}}_{n\in\mathbb{N}}$
be a $\varepsilon$-pseudorandom function ensemble with key length $\kappa$
implementable using Boolean circuits of size at most $s(n)$. We will prove
that the ensemble resulting from our construction, when instantiated with
$f$111111$f$ here really denotes the ensemble
${\left\\{f^{n}_{(\cdot)}\right\\}}_{n\in\mathbb{N}}$. We employ this abuse of
notation throughout this section., is pseudorandom against
$\mathsf{P}/\mathrm{poly}$.

To begin, define for functions
$f_{(1,2)},f_{(1,3)},\dots,f_{(s(n),s(n)-1)},f_{1}^{1},f_{1}^{2},\dots,f_{s(n)}^{1},f_{s(n)}^{2}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ the permutation

$\displaystyle
p^{N}_{{\left(f_{{(1,2)}},\dots,f_{{s(n)}}^{2}\right)}}=\prod_{i\in[s(n)],i\text{
odd}}{\left(\mathsf{Ctr}_{f_{a}}^{(a+1,a)}\mathsf{Ctr}_{f_{a}}^{(a,a+1)}\right)}\cdot\prod_{a\in[s(n)]}{\left(\prod_{b\in[s(n)]\setminus\\{a\\}}\mathsf{Ctr}_{f_{{(a,b)}}}^{(a,b)}\right)}.$

Here the order of factors in the product is given by
$\prod_{a\in[s]}x_{a}=x_{s}x_{s-1}\dots x_{1}$. Here we can think of the
permutation as acting in two phases: the first phase consists of
$s(n)(s(n)-1)$ many controlled $f$ permutation from each $a\in[s(n)]$ to each
$b\in[s(n)]\setminus\\{a\\}$. Then the second phase consists of a sequence of
permutations from each $a$ to one of its adjacent bits. We will show that
applying the first phase to any $x\in\\{0,1\\}^{Nq(n)}$ will make all of its
matrix entries pairwise distinct with high probability. Then the second phase
will leverage this distinctness to make all of the entries close to i.i.d.
uniform on $\\{0,1\\}^{n}$.

To construct our ensemble, we construct $p^{N}_{\mathsf{key}}$ for each
$\mathsf{key}\in\\{0,1\\}^{\kappa^{\prime}(N)}=\\{0,1\\}^{s(n)^{2}\kappa(n)}$
(recalling that $N=s(n)n$). Given $\mathsf{key}$, interpret it as

$\displaystyle\mathsf{key}=$
$\displaystyle{\left({\left(\mathsf{key}_{(a,b)}\right)}_{a\neq
b\in[s(n)]},{\left(\mathsf{key}_{a}^{1},\mathsf{key}_{a}^{2}\right)}_{a\in[s(n)]}\right)},$

where each
$\mathsf{key}_{i,1},\mathsf{key}_{i,2},\mathsf{key}_{(i,j)}\in\\{0,1\\}^{\kappa(n)}$.
Then define

$\displaystyle
p^{N}_{\mathsf{key}}=p^{N}_{{\left(f_{\mathsf{key}_{(1,2)}},\dots,f_{\mathsf{key}_{s(n),2}}\right)}}.$

Here the order of factors in the product is given by
$\prod_{i\in[t]}x_{i}=x_{t}x_{t-1}\dots x_{1}$.

######  Proposition 72.

Let $c>0$ be fixed. Assume
${\left\\{f^{n}_{(\cdot)}\right\\}}_{n\in\mathbb{N}}$ is
$\varepsilon$-pseudorandom against circuits of size at most
$100n^{c+1}s(n)^{3}$. Fix $n\in\mathbb{N}$ large enough and let $s(n)$ be as
above. Let $N=s(n)n$. Then for any adversary circuit $\mathcal{A}$ of size at
most $n^{c}$ that makes $q(n)$ black box nonadaptive queries, we have

$\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{\\{0,1\\}^{N}}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathsf{key}\in\\{0,1\\}^{s(n)^{2}\kappa(n)}}{\left[\mathcal{A}^{p^{N}_{\mathsf{key}}}\right]}=1\right|}\leq
s(n)^{2}\varepsilon(n)+\frac{q(n)^{2}s(n)^{2}}{2^{n-10}}.$

###### Proof.

We proceed by a hybrid argument. The first step is to replace the pseudorandom
function ensemble given by the $f$’s with completely random permutations. By
the triangle inequality,

$\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathsf{key}\in\\{0,1\\}^{s(n)^{2}\kappa(n)}}{\left[\mathcal{A}^{p^{N}_{\mathsf{key}}}\right]}=1\right|}$
$\displaystyle\leq$ $\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}}{\left[\mathcal{A}^{p^{N}_{{\left(\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\right)}}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathsf{key}}{\left[\mathcal{A}^{p^{N}_{\mathsf{key}}}\right]}=1\right|}$
$\displaystyle+{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{\\{0,1\\}^{N}}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}}{\left[\mathcal{A}^{p^{N}_{{\left(\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\right)}}}=1\right]}\right|}$
$\displaystyle\leq$ $\displaystyle
s(n)^{2}\varepsilon(n)+{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{\\{0,1\\}^{N}}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}}{\left[\mathcal{A}^{p^{N}_{{\left(\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\right)}}}=1\right]}\right|}.$

This last inequality follows from a standard hybrid argument in 74 and the
$\varepsilon$-pseudorandomness of $f$ against adversaries with size at most
$100n^{c+1}s(n)^{3}$.

We now work to bound the difference between these two probabilities. We do so
by proving that the total variation distance between the distributions on
$\\{0,1\\}^{Nq(n)}$ induced by applying a fully random permutation of
$\\{0,1\\}^{N}$ to all the elements in a fixed $q(n)$-tuple
$x\in(\\{0,1\\}^{N})^{q(n)}$ and by applying the product of the $s(n)^{2}+1$
permutations as in the second experiment to the same tuple is small. Without
loss of generality we may assume that $x_{i}\neq x_{j}$ for all $i\neq j$.

We view elements
$x\in\\{0,1\\}^{Nq(n)}\cong{\left({\left(\\{0,1\\}^{n}\right)}^{s(n)}\right)}^{q(n)}$
as $q(n)$-by-$s(n)$ matrices of elements of $\\{0,1\\}^{n}$:

$\displaystyle x=\begin{bmatrix}x^{1}_{1}&\dots&x^{1}_{s(n)}\\\ &\vdots&\\\
x^{q(n)}_{1}&\dots&x^{q(n)}_{s(n)}\end{bmatrix}.$

Here each $x^{i}_{a}$ is an element of $\\{0,1\\}^{n}$.

######  Claim 73.

Fix any $x\in\\{0,1\\}^{Nq(n)}$ such that $x^{i}\neq x^{j}$ if $i\neq j$.
Except with probability at most $\frac{q(n)^{2}s(n)^{2}}{2^{n-1}}$, we have
that

$\displaystyle
y={\left(\prod_{a\in[s(n)]}\prod_{b\in[s(n)]\setminus\\{a\\}}\mathsf{Ctr}_{\mathbf{g}_{{(a,b)}}}^{(a,b)}\right)}{\left(x\right)}$

has $y^{i}_{a}\neq y^{j}_{b}$ if $(i,a)\neq(j,b)$, where each
$\mathbf{g}_{(a,b)}$ is a uniformly random function
$\\{0,1\\}^{n}\to\\{0,1\\}^{n}$.

###### Proof.

We bound $\operatorname{{\bf Pr}}{\left[y^{i}_{a}=y^{j}_{b}\right]}$ for each
$(i,a)\neq(j,b)$. First assume that $a\neq b$. Then (addition and subtraction
are the same because operations are over $\mathbb{F}_{2}$) we have

$\displaystyle y^{i}_{a}-y^{j}_{b}$ $\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{b}+\sum_{a^{\prime}\neq
a}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\sum_{b^{\prime}\neq
b}\mathbf{g}_{(b^{\prime},b)}{\left(F_{b^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{b^{\prime}-1}\right)}+x_{b^{\prime}}^{j}\right)}$
$\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{b}+\mathbf{g}_{(b,a)}{\left(F_{b}{\left(x^{i}_{1},\dots,x^{i}_{b-1}\right)}+x^{i}_{b}\right)}+\mathbf{g}_{(a,b)}{\left(F_{a}{\left(x^{j}_{1},\dots,x^{j}_{a-1}\right)}+x^{j}_{a}\right)}$
$\displaystyle+x^{i}_{a}+x^{j}_{b}+\sum_{a^{\prime}\neq
a,b}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\sum_{b^{\prime}\neq
a,b}\mathbf{g}_{(b^{\prime},b)}{\left(F_{b^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{b^{\prime}-1}\right)}+x_{b^{\prime}}^{j}\right)}.$

The $F_{a^{\prime}}$ are arbitrary functions that depend on the
$\mathbf{g}_{(a^{\prime\prime},a^{\prime})}$ for $a^{\prime\prime}\leq
a^{\prime}$. The right-hand side is of this is therefore the sum of a
uniformly random element $\\{0,1\\}^{n}$, given by
$\mathbf{g}_{(b,a)}{\left(F_{b}{\left(x^{i}_{1},\dots,x^{i}_{s(n)}\right)}\right)}$,
with independent random elements of $\\{0,1\\}^{n}$, which is a uniformly
random element of $\\{0,1\\}^{n}$. As a result we have that
$\operatorname{{\bf Pr}}{\left[y_{a}^{i}=y_{b}^{j}\right]}=2^{-n}$.

Now assume that $a=b$; this means that $i\neq j$. Because $x^{i}\neq x^{j}$,
it must be that $x^{i}_{a^{\prime}}\neq x^{j}_{a^{\prime}}$ for some
$a^{*}\in[s(n)]$. Let $a^{*}$ be the least such index. Then if $a^{*}\neq a$,
we have

$\displaystyle y^{i}_{a}-y^{j}_{b}$ $\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{a}+\sum_{a^{\prime}\neq
a}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\sum_{a^{\prime}\neq
a}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{a^{\prime}-1}\right)}+x_{a^{\prime}}^{j}\right)}$
$\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{a}+\mathbf{g}_{(a^{*},a)}{\left(F_{a^{*}}{\left(x^{i}_{1},\dots,x^{i}_{a^{*}-1}\right)}+x^{i}_{a^{*}}\right)}+\mathbf{g}_{(a^{*},a)}{\left(F_{a^{*}}{\left(x^{j}_{1},\dots,x^{j}_{a^{*}-1}\right)}+x^{j}_{a^{*}}\right)}$
$\displaystyle+x^{i}_{a}+x^{j}_{a}+\sum_{a^{\prime}\neq
a,a^{*}}{\left(\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{a^{\prime}-1}\right)}+x_{a^{\prime}}^{j}\right)}\right)}.$

Again the $F_{a^{\prime}}$ are arbitrary functions that depend on the
$\mathbf{g}_{(a^{\prime\prime},a^{\prime})}$ for $a^{\prime\prime}\leq
a^{\prime}$. Since $x^{i}_{a^{*}}\neq x^{j}_{a^{*}}$ and
$x^{i}_{a^{\prime\prime}}\neq x^{j}_{a^{\prime\prime}}$ for all
$a^{\prime\prime}\leq a^{*}$, the above random variable is the sum of the
images under a uniformly random permutation of two distinct elements, which is
a uniformly random nonzero element of $\\{0,1\\}^{n}$, so we have
$\operatorname{{\bf Pr}}{\left[y_{a}^{i}=y_{b}^{j}\right]}\leq 2^{-n+1}$.

If $a^{*}=a$ then

$\displaystyle y^{i}_{a}-y^{j}_{b}$ $\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{a}+\sum_{a^{\prime}\neq
a}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\sum_{a^{\prime}\neq
a}\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{a^{\prime}-1}\right)}+x_{a^{\prime}}^{j}\right)}$
$\displaystyle=$ $\displaystyle
x^{i}_{a}+x^{j}_{a}+\mathbf{g}_{(a+1,a)}{\left(F_{a+1}{\left(x^{i}_{1},\dots,x^{i}_{a}\right)}+x^{i}_{a+1}\right)}+\mathbf{g}_{(a+1,a)}{\left(F_{a+1}{\left(x^{j}_{1},\dots,x^{j}_{a^{*}}\right)}+x^{j}_{a+1}\right)}$
$\displaystyle+x^{i}_{a}+x^{j}_{a}+\sum_{a^{\prime}\neq
a,a+1}{\left(\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{i}_{1},\dots,x^{i}_{a^{\prime}-1}\right)}+x^{i}_{a^{\prime}}\right)}+\mathbf{g}_{(a^{\prime},a)}{\left(F_{a^{\prime}}{\left(x^{j}_{1},\dots,x^{j}_{a^{\prime}-1}\right)}+x_{a^{\prime}}^{j}\right)}\right)}.$

We know that
$F_{a+1}{\left(x^{i}_{1},\dots,x^{i}_{a}\right)}=\mathbf{g}_{(a,a+1)}{\left(F_{a}{\left(x^{i}_{1},\dots,x^{i}_{a-1}\right)}+x^{i}_{a}\right)}$
for some function $F_{a}$ depending on $\mathbf{g}_{(a^{\prime\prime},a)}$ for
$a^{\prime\prime}\leq a$. Because $x^{i}_{a}\neq x^{j}_{a}$, we know
$F_{a+1}{\left(x^{i}_{1},\dots,x^{i}_{a}\right)}$ and
$F_{a+1}{\left(x^{j}_{1},\dots,x^{j}_{a}\right)}$ are two uniform elements
sampled without replacement from $\\{0,1\\}^{n}$. With probability at least
$1-\frac{1}{2^{n}-1}$ we have

$\displaystyle F_{a+1}{\left(x^{i}_{1},\dots,x^{i}_{a}\right)}+x^{i}_{a+1}\neq
F_{a+1}{\left(x^{j}_{1},\dots,x^{j}_{a}\right)}+x^{j}_{a+1}.$

If this occurs, then $y^{i}_{a}-y^{j}_{b}=y^{i}_{a}-y^{j}_{a}$ is the sum of a
uniformly random element of $\\{0,1\\}^{n}$ with an arbitrary independent
element of $\\{0,1\\}^{n}$, which is uniformly random. Thus,

$\displaystyle\operatorname{{\bf
Pr}}{\left[y^{i}_{a}=y^{j}_{b}\right]}\leq\frac{1}{2^{n}-1}+\frac{1}{2^{n}}\leq\frac{1}{2^{n-1}}.$

To complete the proof let the event that $y^{i}_{a}\neq y^{j}_{b}$ for all
$(i,a)\neq(j,b)$ be denoted by $\mathcal{E}$. Then

$\displaystyle\operatorname{{\bf
Pr}}{\left[\overline{\mathcal{E}}\right]}\leq\sum_{(i,a)\neq(j,b)}\operatorname{{\bf
Pr}}{\left[y^{i}_{a}=y^{j}_{b}\right]}\leq\frac{q(n)^{2}s(n)^{2}}{2^{n-1}}.\qed$

Conditioned on the event $\mathcal{E}$ (so that $y^{i}_{a}\neq y^{j}_{b}$ for
$(i,a)\neq(j,b)$), the distribution

$\displaystyle{\left(\prod_{a\in[s(n)],a\text{
odd}}\mathsf{Ctr}_{\mathbf{g}_{{a}}^{1}}^{(a,a+1)}\mathsf{Ctr}_{\mathbf{g}_{{a}}^{2}}^{(a+1,a)}\right)}{\left(y\right)}$

$\frac{q(n)^{2}s(n)^{2}}{2^{n-1}}$-close to uniform on $\\{0,1\\}^{Nq(n)}$. To
see this, we prove that every two columns of the form $\\{a,a+1\\}$ for $a$
odd ends up close to uniform on $\\{0,1\\}^{2nq(n)}$. WLOG assume that $a=1$.
Then because $y^{i}_{2}\neq y^{j}_{2}$ for all $i\neq j$, we have that
${\left(\mathbf{g}(y^{i}_{1})\right)}_{i\in q(n)}$ is uniformly distributed on
$\\{0,1\\}^{nq(n)}$, independently of the $n$-bit strings occupying the
entries not in the second column of
$\mathsf{Ctr}_{\mathbf{g}_{{1}}^{2}}^{(2,1)}{\left(y\right)}$. By a union
bound, with probability at least $1-\frac{q(n)^{2}}{2^{n}}$ all of the strings
in the second column are distinct, and if this occurs then the first column of
$\mathsf{Ctr}_{\mathbf{g}_{{1}}^{1}}^{(1,2)}\mathsf{Ctr}_{\mathbf{g}_{{1}}^{2}}^{(2,1)}{\left(y\right)}$
is uniformly distributed on $\\{0,1\\}^{nq(n)}$ independently of the strings
in the entries not in the first column. Repeating this argument for $s(n)/2$
other pairs of columns and using a union bound gives that the resulting
distribution is $\frac{q(n)^{2}s(n)}{2^{n-2}}$-close to uniform on
$\\{0,1\\}^{Nq(n)}$.

The uniform distribution on $\\{0,1\\}^{Nq(n)}$ has distance at most
$\frac{q(n)^{2}}{2^{n}}$ from the uniform distribution on $B_{\geq
1}={\left\\{z\in\\{0,1\\}^{Nq(n)}\mathrel{\mathop{\mathchar
58\relax}}z^{i}\neq z^{j}\iff i\neq j\right\\}}$, so if we let $\mathcal{D}$
denote the distribution induced by applying the local permutations given above
to a matrix $x\in\\{0,1\\}^{Nq(n)}$, we have by the previous paragraph that

$\displaystyle\mathinner{\\!\left\lVert\mathcal{D}-\mathrm{Unif}{\left(B_{\geq
1}\right)}\right\rVert}_{1}\leq$
$\displaystyle\mathinner{\\!\left\lVert\mathcal{D}-\mathrm{Unif}{\left(\\{0,1\\}^{Nq(n)}\right)}\right\rVert}_{1}+\mathinner{\\!\left\lVert\mathrm{Unif}{\left(B_{\geq
1}\right)}-\mathrm{Unif}{\left(\\{0,1\\}^{Nq(n)}\right)}\right\rVert}_{1}$
$\displaystyle\leq$
$\displaystyle{\left(\frac{q(n)^{2}s(n)}{2^{n-2}}+\frac{q(n)^{2}s(n)^{2}}{2^{n-1}}\right)}+\frac{q(n)^{2}}{2^{n}}\leq\frac{q(n)^{2}s(n)^{2}}{2^{n-3}}.$

Since $\mathrm{Unif}(B_{\geq 1})$ is exactly the distribution induced by
applying a uniformly random permutation from $\mathfrak{S}_{\\{0,1\\}^{N}}$ to
$x$, this completes our proof. ∎

######  Claim 74.

Let $c>0$ be fixed. Assume
${\left\\{f^{n}_{(\cdot)}\right\\}}_{n\in\mathbb{N}}$ is
$\varepsilon$-pseudorandom against circuits of size at most
$100n^{c+1}s(n)^{3}$ and implementable by circuits of size at most $s(n)$.
Then for any adversary circuit $\mathcal{A}$ of size at most $n^{c}$, we have

$\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}}{\left[\mathcal{A}^{p^{N}_{{\left(\mathbf{g}_{(1,2)},\dots,\mathbf{g}_{s(n),2}\right)}}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathsf{key}}{\left[\mathcal{A}^{p^{N}_{\mathsf{key}}}\right]}=1\right|}\leq
s(n)^{2}\varepsilon(n).$

###### Proof.

Let $\mathcal{A}$ be a circuit of size at most $n^{c}$. We replace the
pseudorandom functions in $p^{N}_{(\cdot)}$ with completely random functions
one-by-one, so that the quantity we intend to bound can be written as
${\left|\operatorname{{\bf Pr}}^{s(n)^{2}}-\operatorname{{\bf
Pr}}^{0}\right|}$, where for each $\ell\in[s(n)^{2}]$ we define

$\displaystyle\operatorname{{\bf Pr}}^{\ell}=$
$\displaystyle\operatorname{{\bf
Pr}}_{\begin{subarray}{c}\mathsf{key}_{\ell+1},\dots,\mathsf{key}_{s(n)^{2}}\\\
\mathbf{g}_{1},\dots,\mathbf{g}_{\ell}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}\\\
\mathbf{g}_{t+1}=f^{n}_{\mathsf{key_{t}}}\forall
t\in[\ell+1,s(n)^{2}]\end{subarray}}{\left[\mathcal{A}^{p^{N}_{{\left(\mathbf{g}_{1},\dots,\mathbf{g}_{s(n)^{2}}\right)}}}=1\right]}.$

It suffices to show that ${\left|\operatorname{{\bf
Pr}}^{\ell}-\operatorname{{\bf Pr}}^{\ell-1}\right|}\leq\varepsilon(n)$ for
all $\ell\in[s(n)^{2}-1]$. Assume otherwise, so that this does not hold for a
particular value of $\ell$. Then we can build an adversary
$\mathcal{A}^{\prime}$ breaking pseudorandomness of $f$ by simulating oracle
to access to $p$ using oracle access to $f$. To do this, we build a randomized
adversary $\mathcal{R}$ that is the same circuit as $\mathcal{A}$, but each
oracle gate $\mathcal{A}$ has is replaced with the following random circuit
$\mathcal{P}$. The circuit $\mathcal{P}$ randomly draws
$\mathsf{key}_{1},\dots,\mathsf{key}_{\ell-1}$ uniformly at random. It then
implements the function

$\displaystyle
p^{N}_{f_{\mathsf{key_{1}}}^{n},\dots,f_{\mathsf{key_{\ell-1}}}^{n},\mathcal{O},\mathbf{g}_{\ell+1},\dots,\mathbf{g}_{s(n)^{2}}},$

where $\mathcal{O}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ is the oracle gate (which is either a
pseudorandom $f^{n}_{\mathsf{key}_{\ell}}$ or a completely random function
$\mathbf{g}_{\ell}$) and each $\mathbf{g}_{t}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ is a completely random function. To
implement the completely random functions, $\mathcal{P}$ just draws uniformly
random elements each time it is asked for the output of a random function, and
remembers which input it has been queried on.

If we run $\mathcal{A}$ with its oracle calls replaced by these circuits
$\mathcal{P}$, we get a distinguisher $\mathcal{R}$ with oracle access to a
function $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$
that distinguishes the case where $f$ is chosen completely randomly and the
case where $f$ is chosen according to ${\left\\{f^{n}_{(\cdot)}\right\\}}$
with advantage equal to ${\left|\operatorname{{\bf
Pr}}^{\ell}-\operatorname{{\bf Pr}}^{\ell-1}\right|}$.

The circuit $\mathcal{P}$ has size at most $s(n)^{2}\cdot s(n)+100s(n)\cdot n$
(the $100s(n)\cdot n$ comes from the size required for the memorization of
queried strings). There are a fixed set of random strings so that
$\mathcal{R}$ has the largest distinguishing advantage on that set of strings,
so we just let $\mathcal{A}^{\prime}$ be $\mathcal{R}$ equipped with those
random strings, and $\mathcal{A}^{\prime}$ has size at most
$\mathrm{size}(\mathcal{A})+\mathrm{size}(\mathcal{A})+\mathrm{size}(\mathcal{P})\leq
n^{c}+100n\cdot s(n)^{3}$. Thus, we have a contradiction, since
$\mathcal{A}^{\prime}$ has distinguishing advantage at least
${\left|\operatorname{{\bf Pr}}^{\ell}-\operatorname{{\bf
Pr}}^{\ell-1}\right|}>\varepsilon(n)$ against $f$. ∎

When we instantiate this construction with the pseudorandom $f$ ensembles
given by [HILL99] and [GGM86], we get pseudorandom permutations implementable
by small reversible circuits.

######  Corollary 75.

If OWFs exist then for some $\delta>0$ there exists an
$2^{-n^{\delta}}$-pseudorandom function ensemble
${\left\\{p^{n}_{(\cdot)}\right\\}}$ against $\mathsf{P}/\mathrm{poly}$
implementable by reversible circuits of size at most $n^{3}$.

###### Proof.

If OWFs exist then by Theorem 70, for some constants $\delta$ and $d$ and any
$c>0$, there exists a $2^{-n^{\delta}}$-pseudorandom function ensemble
${\left\\{f^{n}_{(\cdot)}\right\\}}$ against circuits of size at most $n^{c}$
implementable using Boolean circuits of size $n^{d}$. Proposition 72 shows
that the ${\left\\{p^{N}_{(\cdot)}\right\\}}$ built from
${\left\\{f^{n}_{(\cdot)}\right\\}}$ as above is $\varepsilon$-pseudorandom
against circuits of size at most $n^{c/(d+1)}/n^{3d+1}100\leq n^{c/d-4d}$,
where (recalling that $N=ns(n)=n^{d+1}$)

$\displaystyle\varepsilon(N)\leq\frac{n^{2c}}{2^{n^{\delta^{\prime}}}}+\frac{n^{2c/d-8d}n^{2d}}{2^{n-10}}\leq
2^{-N^{\delta}},$

where we set $\delta=0.001\delta^{\prime}/d$ and assume $n$ to be large
enough. This applies for any $c$, so the ensemble is pseudorandom against
$\mathsf{P}/\mathrm{poly}$.121212For subexponential-time adversaries, $q(n)$
is subexponential, and this is still exponentially small when $f$ is
subexponentially secure.

Moreover, each $\mathsf{Ctr}_{f_{\mathsf{key}}}^{(i,j)}$ is implementable
using a reversible circuit of size $O(n^{d})\leq O(N)$ by standard simulation
of Boolean circuits with reversible circuits. There are at most $O(N^{2})$
many applications of such a permutation, so there are reversible circuits with
at most $O(N^{3})$ gates capable of implementing this ensemble. ∎

###  7.2 Hardness of MRCSP for Poly-Time Adversaries

As in [KC00], the capability of small reversible circuits to implement
pseudorandom functions implies that their minimization problems are hard.

######  Corollary 76 (Theorem 15, restated).

Fix any constant $d\geq 3$. If one-way functions exist, then there is no
deterministic $\mathrm{poly}(n)$-time algorithm that — given black-box access
to a permutation $\pi$ on $\\{0,1\\}^{n}$ — decides whether $\pi$ is
computable by a reversible circuit of size at most $n^{d}$.

###### Proof.

Given that OWFs exist, by Corollary 75 there exists $\delta>0$ such that there
exists a $2^{-n^{\delta}}$-pseudorandom function ensemble
${\left\\{p^{n}_{(\cdot)}\right\\}}_{n\in\mathbb{N}}$ against
$\mathsf{P}/\mathrm{poly}$ implemented by reversible circuits with at most
$n^{3}$ gates for some constant $\delta>0$. Now assume that there exists such
a deterministic $\mathcal{A}$. Then, by definition we have that for $n$ large
enough,

$\displaystyle{\left|\operatorname{{\bf
Pr}}_{\mathsf{key}\in\\{0,1\\}^{\kappa(n)}}{\left[\mathcal{A}^{p^{n}_{\mathsf{key}}}=1\right]}-\operatorname{{\bf
Pr}}_{\mathbf{g}\in\mathfrak{S}_{\\{0,1\\}^{n}}}{\left[\mathcal{A}^{\mathbf{g}}=1\right]}\right|}\geq{\left|1-\frac{n^{4n^{d}}}{2^{n2^{n}}}\right|}>2^{-n^{\delta}}.$

This is because for large enough $n$, there are at most $n^{4n^{d}}$
permutations of $\\{0,1\\}^{n}$ computable by reversible circuits with at most
$n^{d}$ gates. This contradicts the pseudorandomness of
${\left\\{p_{(\cdot)}^{n}\right\\}}_{n\in\mathbb{N}}$. (When $p$ is
pseudorandom against subexponential algorithms, then this argument gives
subexponential-time hardness.) ∎

This shows that given the existence of OWFs, it is impossible for polynomial-
time adversaries to invert our block ciphers. In fact, the result applies when
one replaces reversible circuits with reversible circuits with nearest-
neighbor gates, with some cost coming from the simulation of arbitrary gates
with nearest-neighbor gates. In fact, our result applies to any restricted set
of reversible circuits that can simulate arbitrary reversible circuits with
3-bit gates with polynomial overhead.

We leave a few directions open:

  * •

Provide more efficient implementations using reversible circuits of the
pseudorandom permutation ensemble of Proposition 72 (as in polynomial-size
circuits with small exponent).

  * •

Show average-case hardness of inverting block ciphers (an average-case version
of Corollary 76) under a well-founded computational hardness assumption.

###  7.3 Hardness of MRCSP for General Adversaries

In Section 7.2 we showed that it is hard for circuits/algorithms running in
time bounded in $\mathrm{poly}(n)$ (or subexponential in $n$) with query-
access to a function to distinguish between functions of large reversible
circuit complexity and those of small reversible circuit complexity. Part of
our proof relied on the fact that such adversaries can query a limited number
of inputs to the function that it receives. However, often we are interested
in the case where the adversary can actually query the entire truth table and
run in time $\mathrm{poly}(2^{n})$. To show that such adversaries still
struggle, we provide a direct reduction from a gapped version of the MCSP
problem, which is known to be hard under the existence of OWFs. For this
reduction we need a less naive simulation of Boolean circuits using reversible
circuits than the one used in the proof of Proposition 72; we get a better
simulation from [Wil10].

######  Definition 77.

Let $a,b\mathrel{\mathop{\mathchar 58\relax}}\mathbb{N}\to\mathbb{N}$. In the
promise problem $\mathsf{gapMCSP}_{a,b}$, the input is a truth-table of a
permutation $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ such that there either exists a
circuit of size at most $a(n)$ computing $f$ or there is no circuit of size
less than $b(n)$ computing $f$. The objective is to decide whether $f$ falls
into the former case or the latter case.

######  Lemma 78.

If OWFs exist then there exists $d$ such that the are no polynomial-size
circuits for $\mathsf{gapMCSP}_{n^{d},n^{100d}}$.

###### Proof.

If OWFs exist then by [HILL99], [GGM86], and [LR88] there exists a
$2^{-n^{\delta}}$-pseudorandom function ensemble against polynomial-time
adversaries computable with circuits with at most $n^{d}$ gates. The existence
of such an ensemble precludes the existence of a polynomial-time algorithm for
$\mathsf{gapMCSP}_{n^{d},n^{100d}}$. ∎

######  Definition 79.

Let $a,b\mathrel{\mathop{\mathchar 58\relax}}\mathbb{N}\to\mathbb{N}$. In the
promise problem $\mathsf{MRCSP}_{a}$, the input is a truth-table of a
permutation $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ such that there either exists a
reversible circuit with at most $a(n)$ gates computing $f$ or there is no
circuit with less than $a(n)$ gates computing $f$. The objective is to decide
whether $f$ falls into the former case or the latter case.

######  Proposition 80.

Let $d<d^{\prime}/10$. If there exist circuits for $\mathsf{MRCSP}_{n^{5d}}$
with size at most $T(2^{n})$ then there exist circuits for
$\mathsf{gapMCSP}_{n^{d},n^{d^{\prime}}}$ with size at most
$T(2^{2n})+O(2^{4n})$.

###### Proof.

Assume the existence of such circuits for $\mathsf{MRCSP}_{n^{d},n^{d}}$. We
present distinguisher circuits $\mathcal{D}_{n}$ for
$\mathsf{gapMCSP}_{n^{5d},n^{d^{\prime}}}$ satisfying the size bound. The
circuit $\mathcal{D}_{n}$ proceeds as follows. Given the input to
$\mathsf{gapMCSP}_{n^{d},n^{d^{\prime}}}$, which is a truth table

$\displaystyle\mathsf{tt}={\left(x_{i},y_{i}\right)}_{i\in[2^{n}]},$

where each $x_{i}$ and $y_{i}$ are elements of $\\{0,1\\}^{n}$. Now form the
truth table $\mathsf{tt}^{\prime}$ which is given by

$\displaystyle\mathsf{tt}^{\prime}={\left(x_{i}\circ z,y_{i}\circ
z\right)}_{i\in[2^{n}],z\in\\{0,1\\}^{n}},$

where $\circ$ denotes concatenation of strings, so that $\mathsf{tt}^{\prime}$
is the truth table of a permutation on $\\{0,1\\}^{2n}$. Then
$\mathcal{D}_{n}$ runs the size $T(2^{2n})$ circuit
$\mathcal{C}^{\prime}_{2n}$ on $\mathsf{tt}^{\prime}$ and returns 1 if
$\mathcal{C}^{\prime}$ returns 1 and 0 otherwise.

First assume that $\mathsf{tt}$ is computable by circuits of size at most
$n^{d}$. Then by 81 $\mathsf{tt}^{\prime}$ is computable by reversible
circuits with at most $n^{5d}\leq(2n)^{5d}$ gates, so that our
$\mathcal{D}_{n}$ is correct on such an input.

######  Claim 81 ([Wil10], Section 2.2.1).

If $f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ is
computable using circuits of size $n^{d}$, then there exists circuits of size
at most $n^{5d}$ computing the function
$f\circ\mathrm{Id}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2n}\to\\{0,1\\}^{2n}$ given by
$(f\circ\mathrm{Id})(x\circ z)=f(x)\circ z$.

Otherwise, $\mathsf{tt}$ (the truth table for the function $f$) has no
circuits of size at most $n^{d^{\prime}}$, and therefore $f\circ\mathrm{Id}$
has no reversible circuits of size at most $n^{d^{\prime}/2}$. This implies
that $f\circ\mathrm{Id}$ has no reversible circuits of size at most
$n^{d}<n^{d^{\prime}/2}$, so that the internal circuit
$\mathcal{C}_{2n}^{\prime}$ returns 0. Therefore $\mathcal{D}_{n}$ returns 0
and is again correct. The size of $\mathcal{D}_{n}$ is at most
$T(2^{2n})+O(2^{4n})$ because it simply builds the size $2^{4n}$ truth table
$\mathsf{tt}^{\prime}$ and runs a size at most $T(2^{2n})$ circuit on it. ∎

Combining Lemma 78 and Proposition 80 results in the conditional (based on the
existence of OWFs) hardness of MRCSP.

######  Corollary 82.

If OWFs exist then there exists $d>0$ such that
$\mathsf{MRCSP}_{n^{d}}\not\in\mathsf{P}/\mathrm{poly}$.

## Acknowledgements

W.H. thanks Angelos Pelecanos and Lucas Gretta for helpful discussions on the
comparison method, and for allowing him to reuse results from their discussion
and in-progress work in Appendix A.

## References

  * [AALV09] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani.  The Detectability Lemma and Quantum Gap Amplification.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pages 417–426, 2009.
  * [Ben73] Charles H. Bennett.  Logical Reversibility of Computation.  IBM Journal of Research and Development, 17(6):525–532, 1973.
  * [BH08] Alex Brodsky and Shlomo Hoory.  Simple Permutations Mix Even Better.  Random Structures & Algorithms, 32(3):274–289, 2008.
  * [BHH16] Fernando G.S.L. Brandao, Aram W. Harrow, and Michał Horodecki.  Local Random Quantum Circuits are Approximate Polynomial-Designs.  Communications in Mathematical Physics, 346:397–434, 2016.
  * [CG75] Don Coppersmith and Edna Grossman.  Generators for Certain Alternating Groups with Applications to Cryptography.  SIAM Journal on Applied Mathematics, 29(4):624–627, 1975.
  * [Cle90] Richard Cleve.  Complexity Theoretic Issues Concerning Block Ciphers Related to DES.  In Conference on the Theory and Application of Cryptography, pages 531–544. Springer, 1990.
  * [EG83] Shimon Even and Oded Goldreich.  DES-like Functions can Generate the Alternating group.  Transactions on Information Theory, 29(6):863–865, 1983.
  * [FT82] Edward Fredkin and Tommaso Toffoli.  Conservative Logic.  International Journal of Theoretical Physics, 21(3):219–253, 1982.
  * [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to Construct Random Functions.  Journal of the ACM (JACM), 33(4):792–807, 1986.
  * [Gow] W. T. Gowers.  Are There Very Strongly Pseudorandom Permutations?  MathOverflow.  URL:https://mathoverflow.net/q/134060 (version: 2013-06-27).
  * [Gow96] W.T. Gowers.  An Almost m-wise Independent Random Permutation of the Cube.  Combinatorics, Probability and Computing, 5(2):119–130, 1996.
  * [HHJ21] Jonas Haferkamp and Nicholas Hunter-Jones.  Improved Spectral Gaps for Random Quantum Circuits: Large Local Dimensions and All-to-All Interactions.  Physical Review A, 104(2):022417, 2021.
  * [HILL99] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby.  A Pseudorandom Generator from any One-Way Function.  SIAM Journal on Computing, 28(4):1364–1396, 1999.
  * [HMMR05] Shlomo Hoory, Avner Magen, Steven Myers, and Charles Rackoff.  Simple Permutations Mix Well.  Theoretical Computer Science, 348(2-3):251–261, 2005.
  * [HP07] Patrick Hayden and John Preskill.  Black Holes as Mirrors: Quantum Information in Random Subsystems.  Journal of High Energy Physics, 2007(09):120, 2007.
  * [Kas07] Martin Kassabov.  Symmetric Groups and Expander Graphs.  Inventiones Mathematicae, 170(2):327–354, 2007.
  * [KC00] Valentine Kabanets and Jin-Yi Cai.  Circuit Minimization Problem.  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 73–79, 2000.
  * [KNR09] Eyal Kaplan, Moni Naor, and Omer Reingold.  Derandomized Constructions of k-wise (almost) Independent Permutations.  Algorithmica, 55(1):113–133, 2009.
  * [Lan] R. Landauer.  Dissipation and Heat Generation in the Computing Process.  IBM Journal of Research and Development, 5.
  * [Lec63] Yves Lecerf.  Machines de Turing réversibles. Récursive insolubilité en $n\in N$ de l’équation $u=\theta^{n}u$, où $\theta\ $est un “isomorphisme de codes”.  Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 257:2597–2600, 1963.
  * [LPTV23] Tianren Liu, Angelos Pelecanos, Stefano Tessaro, and Vinod Vaikuntanathan.  Layout Graphs, Random Walks and the t-Wise Independence of SPN Block Ciphers.  In Annual International Cryptology Conference, pages 694–726. Springer, 2023.
  * [LR88] Michael Luby and Charles Rackoff.  How to Construct Pseudorandom Permutations from Pseudorandom Functions.  SIAM Journal on Computing, 17(2):373–386, 1988.
  * [LTV21] Tianren Liu, Stefano Tessaro, and Vinod Vaikuntanathan.  The t-wise independence of substitution-permutation networks.  In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part IV 41, pages 454–483. Springer, 2021.
  * [MOP20] Sidhanth Mohanty, Ryan O’Donnell, and Pedro Paredes.  Explicit Near-Ramanujan Graphs of Every Degree.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 510–523, 2020.
  * [MP04] Ueli Maurer and Krzysztof Pietrzak.  Composition of Random Systems: When Two Weak Make One Strong.  In Theory of Cryptography Conference, pages 410–427. Springer, 2004.
  * [Nac96] Bruno Nachtergaele.  The Spectral Gap for Some Spin Chains with Discrete Symmetry Breaking.  Communications in Mathematical Physics, 175:565–606, 1996.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [OSP23] Ryan O’Donnell, Rocco A. Servedio, and Pedro Paredes.  Explicit Orthogonal and Unitary Designs.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1240–1260. IEEE, 2023.
  * [Tof80] T. Toffoli.  Reversible Computing/Automata, Languages and Programming, Volume 85 of Lecture Notes in Computer Science, 1980.
  * [Wil10] Colin P Williams.  Explorations in quantum computing.  Springer Science & Business Media, 2010.
  * [WLP09] E.L. Wilmer, David A. Levin, and Yuval Peres.  Markov Chains and Mixing Times.  American Mathematical Soc., Providence, 2009.

##  Appendix A Comparison Method

######  Theorem 83 ([WLP09], Theorem 13.23).

Let $\widetilde{P}$ and $P$ be transition matrices for two ergodic Markov
chains on the same state space $V$. Assume that for each $(x,y)\in V^{2}$
there exists a random path

$\displaystyle\bm{\Delta}(x,y)={\left((x,\bm{u}_{1}),(\bm{u}_{1},\bm{u}_{2}),(\bm{u}_{2},\bm{u}_{3}),\dots,(\bm{u}_{\ell},y)\right)}.$

Then we have that

$\displaystyle\lambda_{2}(L)\geq{\left(\max_{v\in
V}\frac{\pi(v)}{\widetilde{\pi}(v)}\right)}A(\bm{\Delta})\lambda_{2}(\widetilde{L}).$

where the comparison constant of $\bm{\Delta}$ is defined to be

$\displaystyle A(\bm{\Delta})\coloneq\max_{\begin{subarray}{c}(a,b)\in
V^{2}\\\
\widetilde{P}(a,b)>0\end{subarray}}{\left\\{\frac{1}{\widetilde{\pi}(x)\widetilde{P}(a,b)}\sum_{(x,y)\in
V^{2}}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(x,y)}\cdot|\bm{\Delta}(x,y)|\right]}\cdot\pi(x)\cdot
P(x,y)\right\\}}.$

Here $\pi$ and $\widetilde{\pi}$ are the (unique) stationary distributions for
$P$ and $\widetilde{P}$, respectively, and $\mathbf{1}_{(a,b)\in\mathcal{P}}$
is the indicator variable which captures whether $(a,b)$ appears in the
sequence $\mathcal{P}$.

Lemma 32 is a direct consequence of the following Corollary 84, with symmetry
applied.

######  Corollary 84.

Let $\widetilde{P}$ and $P$ be transition matrices for random walks on
undirected (multi)graphs $\widetilde{G}=(V,\widetilde{E})$ and $G=(V,E)$,
respectively. The graph $G$ is $d$-regular, and $\widetilde{G}$ is
$\widetilde{d}$-regular. Assume that for each $e\in E$ there exists a random
path

$\displaystyle\bm{\Gamma}(e)=(\widetilde{\bm{e}}_{1},\dots,\widetilde{\bm{e}}_{T_{e}}),$

where $(\widetilde{\bm{e}}_{1},\dots,\widetilde{\bm{e}}_{T_{e}})$131313Here
$T_{e}$ is a (deterministic) quantity determined by the edge $e$. is drawn
from a distribution on sequences of edges connecting the endpoints of $E$.
Then we have for any $f\mathrel{\mathop{\mathchar 58\relax}}V\to\mathbb{R}$
that

$\displaystyle\lambda_{2}(L)\geq{\left(\max_{v\in
V}\frac{\pi(v)}{\widetilde{\pi}(v)}\right)}B(\bm{\Gamma})\lambda_{2}(\widetilde{L}).$

where the _multigraph comparison constant_ is defined as the maximum
congestion over all edges $\tilde{e}\in\widetilde{E}$ connecting vertices
$a,b\in V$,

$\displaystyle
B(\bm{\Gamma})\coloneq\max_{\widetilde{e}\in\widetilde{E}}{\left\\{\frac{\widetilde{d}}{d}\sum_{e\in
E}\mathop{{\bf
E}\/}_{\bm{\Gamma}}{\left[\mathbf{1}_{\widetilde{e}\in\bm{\Gamma}(e)}\cdot|\bm{\Gamma}(e)|\right]}\right\\}}.$

Here $\pi$ and $\widetilde{\pi}$ are the (unique) stationary distributions for
$P$ and $\widetilde{P}$, respectively.

###### Proof.

We construct a (randomized) map $\bm{\Delta}$ as in Lemma 32 from the map
$\bm{\Gamma}$ as follows. For each $(x,y)\in V^{2}$, if $x$ and $y$ are not
connected by an edge in $E$ then set $\bm{\Delta}(x,y)=()$ (the sequence of
length 0). Otherwise select a random edge $\bm{e}$ from $(E)_{x,y}$ and let
${\left(\bm{\widetilde{e}}_{1},\dots,\bm{\widetilde{e}}_{{T_{e}}}\right)}$ be
the random path $\bm{\Gamma}(\bm{e})$. For each $i\in[T_{e}]$ let
$(\bm{u}_{i},\bm{v}_{i})$ be the vertices connected by
$\widetilde{\bm{e}}_{i}$. Then set

$\displaystyle\bm{\Delta}(x,y)={\left((\bm{u}_{1},\bm{v}_{1}),\dots,(\bm{u}_{\ell},\bm{v}_{T_{e}})\right)}={\left((x,\bm{v}_{1}),\dots,(\bm{u}_{T_{e}},y)\right)}.$

The comparison constant of $\bm{\Delta}$ is

$A(\bm{\Delta})=\max_{(a,b)\in
V^{2}}{\left\\{\frac{1}{\widetilde{\pi}(x)\widetilde{P}(a,b)}\sum_{(x,y)\in
V^{2}}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(x,y)}\cdot|\bm{\Delta}(x,y)|\right]}\cdot\pi_{\mathsf{ref}}(x)\cdot
P(x,y)\right\\}}.$

Since both Markov chains have the same stationary distribution over the same
state space, the $\pi$ terms cancel, so the above is equal to

$\displaystyle\max_{(a,b)\in
V^{2}}{\left\\{\frac{1}{\widetilde{P}(a,b)}\sum_{(x,y)\in V^{2}}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(x,y)}\cdot|\bm{\Delta}(x,y)|\right]}\cdot
P(x,y)\right\\}}$ $\displaystyle=$ $\displaystyle\max_{(a,b)\in
V^{2}}{\left\\{\frac{\widetilde{d}}{{\left|\widetilde{E}_{a,b}\right|}}\sum_{(x,y)\in
V^{2}}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(x,y)}\cdot|\bm{\Delta}(x,y)|\right]}\cdot\frac{{\left|E_{x,y}\right|}}{d}\right\\}}.$

Let us now start translating from pairs of vertices to edges of the
multigraph. Each pair of vertices $(x,y)$ has $\left|E_{x,y}\right|$ edges
connecting them, we can change the summation from pairs of vertices to edges
$e\in E$. Recall that $u(e),v(e)$ are the endpoints of edge $e$. Continuing
the calculation, the above is equal to

$\displaystyle\max_{(a,b)\in
V^{2}}{\left\\{\frac{\widetilde{d}}{d{\left|\widetilde{E}_{a,b}\right|}}\sum_{e\in
E}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(u(e),v(e))}\cdot|\bm{\Delta}(u(e),v(e))|\right]}\right\\}}$
$\displaystyle=$ $\displaystyle\max_{(a,b)\in
V^{2}}{\left\\{\frac{\widetilde{d}}{d}\sum_{e\in
E}\frac{1}{{\left|\widetilde{E}_{a,b}\right|}}\mathop{{\bf
E}\/}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(u(e),v(e))}\cdot|\bm{\Delta}(u(e),v(e))|\right]}\right\\}}$
$\displaystyle=$ $\displaystyle\max_{(a,b)\in
V^{2}}{\left\\{\frac{\widetilde{d}}{d}\sum_{e\in
E}\frac{1}{{\left|\widetilde{E}_{a,b}\right|}}|\bm{\Gamma}(e)|\operatorname{{\bf
Pr}}_{\bm{\Delta}}{\left[\mathbf{1}_{(a,b)\in\bm{\Delta}(u(e),v(e))}\right]}\right\\}}.$

The last equality is because $|\bm{\Delta}(u(e),v(e))|=|\bm{\Gamma}(e)|$ with
certainty, and $|\bm{\Gamma}(e)|$ is a deterministic quantity that only
depends on $e$.

The sum of probabilities that $\widetilde{e}\in(\widetilde{E})_{a,b}$ appears
in the sequence $\bm{\Gamma}(e)$, over all such $\widetilde{e}$, is equal to
the probability that $(a,b)$ appears in $\bm{\Delta}(u(e),v(e))$. By
averaging, we have that the probability that
$\widetilde{e}\in\widetilde{E}_{a,b}$ appears in $\bm{\Gamma}(e)$, where
$\widetilde{e}$ maximizes this quantity, is at least
$\frac{1}{|\widetilde{E}_{a,b}|}$ times the appearance probability of $(a,b)$.
This results in

$\displaystyle A(\bm{\Delta})\leq$
$\displaystyle\max_{\widetilde{e}\in\widetilde{E}}{\left\\{\frac{\widetilde{d}}{d}\sum_{e\in
E}\mathop{{\bf
E}\/}_{\bm{\Gamma}}{\left[\mathbf{1}_{\widetilde{e}\in\bm{\Gamma}(e)}\cdot|\bm{\Gamma}(e)|\right]}\right\\}}=B(\bm{\Gamma}).$

Applying Theorem 83 with this new map $\bm{\Delta}$ completes the proof. ∎