# Two-Server Private Information Retrieval with Optimized Download Rate and
Result Verification

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

Private Information Retrieval (PIR) schemes allow a client to retrieve any
file of interest, while hiding the file identity from the database servers. In
contrast to most existing PIR schemes that assume honest-but-curious servers,
we study the case of dishonest servers. The latter provide incorrect answers
and try to persuade the client to output the wrong result. We introduce
several PIR schemes with information-theoretic privacy and result verification
for the case of two servers. Security guarantees can be information-
theoretical or computational, and the verification keys can be public or
private. In this work, our main performance metric is the download rate.

##  I Introduction

A private information retrieval (PIR) scheme allows a user to retrieve a given
file $x_{i}$ from a database $\textbf{x}^{T}=x_{1}\cdots x_{m}$, while keeping
its identity or index $i\in[m]$ private from the database servers [1]. The
problem is motivated by the necessity to preserve the privacy of not only the
sensitive content downloaded from public databases, but also the identity of
the queried record [2, 3]. Examples include the price of a specific stock or a
specific blockchain transaction. A trivial solution is to simply download the
entire database and this clearly incurs tremendous communication costs.
Unfortunately, in the case of a single server, Chor et al. [1] showed that
this was the best information-theoretically secure solution. Nevertheless, in
the same seminal paper, Chor et al. [1] showed that when the content are
replicated among several servers, the communication cost can be significantly
reduced. Following [1], several authors have introduced PIR schemes that
progressively reduced the communications cost [4, 5, 6]. Formally, in this
model, the client queries each of the $k$ servers (each stores $x_{1}\cdots
x_{m}$) once and retrieves $x_{i}$, while keeping the index $i$ 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 a property is known as
$t$-privacy. Motivated by the large size of stored files, we ignore the upload
cost. In other words, we assume queries are small compared to the downloaded
file. Hence, our main performance metric is the download rate, defined as the
ratio of the retrieved file size to the amount of information downloaded by
the user [7, 8, 9]. The PIR capacity is defined as the maximum achievable
download rate and the capacity is shown in [10] to be equal to

$C_{m}(t,k)=\frac{1-t/k}{1-(t/k)^{m}}.$ (1)

Since the number of files is also large, we are interested in asymptotic
capacity values. So, we let $m\to\infty$, and we have that

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

Most of the current schemes assume that servers are honest-but-curious and
that they provide correct responses. However, such an assumption cannot be
guaranteed within a cloud environment. This poses an interesting question:
what can the user do if servers provide wrong responses? Here, we provide
three different interpretations of this question and their formal definitions.

  * •

$s$-verifiablility [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$-verifiablility, while
$b$-byzantine resistance implies both $b$-accountability and
$b$-verifiablility. We also note that existing verifiable PIR schemes [12],
[13] provide accountability - but rely on computational assumptions and
require a trusted setup. Other previously studied schemes are $b$-byzantine-
resistant PIR schemes [14, 15, 16, 17]. Typically, they rely on error-
correcting techniques and require at least three servers, while protocols
considered in this paper are deployed in the two-server scenario.

Both verifiable $a$-accountable and $b$-byzantine PIR schemes identify
malicious servers. However, in certain low-latency applications, such as
private media browsing, this may be excessive [18]. By simply requiring
$s$-verifiability, we can then have some savings of communication cost.
$s$-verifiable PIR schemes was considered in papers [19, 11]. In these papers,
authors measure the communication cost as the sum of upload and download
costs, while in our case, we ignore the upload cost.

In this paper, we consider the notion of $s$-verifiability and propose a two-
server verifiable PIR scheme with an optimized download rate by modifying a
linear secret-sharing-based PIR scheme that achieves PIR asymptotic capacity
(2) from [20]. We also propose a generalization that allows the PIR scheme to
be publicly verifiable. After which, to reduce the communication cost, we
introduce the use of homomorphic hashing in the verification step [21].

##  II Preliminaries

###  II-A Notation

For any integer $n>0$ we denote $[n]=\\{1,\ldots,n\\}$. For any prime number
$p$, we denote an extended finite field with $p^{t}$ elements as
$\mathbb{F}_{p^{t}}$. The base field with $p$ elements is denoted as
$\mathbb{F}_{p}$. By superscript $T$, we denote the transpose of a vector.

###  II-B PIR Based Secret-Sharing Schemes

In what follows, we focus on the two-server scenario and add a result
verification to the linear secret-sharing-based PIR scheme that achieves PIR
capacity [20, Proposition 2]. Let us formally define it and denote as
$\Pi_{0}$. Each server $S_{1}$ and $S_{2}$ stores $m$ files
$x_{1},\ldots,x_{m}\in\mathbb{F}_{p^{t}}$ that form the data vector
$\mathbf{x}^{T}=(x_{1},\ldots,x_{m})$. Queries from client to servers to
retrieve the file $i$ are formed by Shamir secret sharing scheme as
$\mathbf{f}(u_{1})$ and $\mathbf{f}(u_{2})$, where
$\mathbf{f}(u)=\mathbf{e}_{i}+\mathbf{r}u\in\mathbb{F}_{p}^{m}$,
$\mathbf{e}_{i}$ is all zero vector of length $m$ with a ‘1’ in the position
$i$, $\mathbf{r}$ is a random vector over $\mathbb{F}^{m}_{p}$, $u_{1}$ and
$u_{2}$ are pre-selected points over $\mathbb{F}_{p}$ that correspond to
servers one and two. As a response, server $S_{j}$ computes the scalar product
of data vector $\mathbf{x}$ and query $\mathbf{f}(u_{j})$ that can be written
as
$\mathbf{f}(u)\mathbf{x}^{T}=\mathbf{e}_{i}^{T}\mathbf{x}+\mathbf{r}^{T}\mathbf{x}u=x_{i}+\mathbf{r}^{T}\mathbf{x}u$.
By collecting responses from two servers, the client can retrieve $x_{i}$ from

$\begin{bmatrix}x_{i}\\\
\mathbf{r}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}\mathbf{f}(u_{1})^{T}\mathbf{x}\\\
\mathbf{f}(u_{2})^{T}\mathbf{x}\end{bmatrix}$ (3)

We do note that such a scheme has the download rate $\frac{1}{2}$ and its
$1$-privacy is ensured by the properties of underlined Shamir’s secret sharing
scheme.

###  II-C PIR Model

Before we proceed further, let us formally define two server verifiable PIR.
Our model consist of two servers $S_{1}$ and $S_{2}$. Each server stores $m$
files $x_{1},\ldots,x_{m}\in\mathbb{F}_{p^{t}}$ that form the data vector
$\mathbf{x}^{T}=(x_{1},\ldots,x_{m})$. The client wants to privately retrieve
the correct value of $x_{i}$, while one server can be malicious and provide a
wrong response.

######  Definition 1 (PIR with results verification).

A two-server PIR scheme $\Pi$ with results verification consists of three
algorithms that can be described as follows:

  * •

$(\textrm{vk},\sigma_{1},\sigma_{2},\textrm{aux}_{A},\textrm{aux}_{V})\leftarrow\texttt{QueriesGen}(m,i)$
is a randomized query-generating algorithm for the client. As input, it takes
the database size $m$ and retrieval index $i$ and outputs two queries
$\sigma_{1}$ and $\sigma_{2}$ that will be given to servers $S_{1}$ and
$S_{2}$, value vk further employed by the client for verification purposes
and, if necessary, auxiliary information $\textrm{aux}_{A}$ used in answer-
generation and $\textrm{aux}_{V}$ used in verification.

  * •

$\pi_{j}\leftarrow\texttt{AnswerGen}(j,\sigma_{j},\textbf{x},\textrm{aux}_{A})$
is a deterministic answer-generation algorithm for server $S_{j}$. As input it
takes server number $j$, query $\sigma_{j}$, database x, and, if necessary,
auxiliary information $\textrm{aux}_{A}$, and outputs the query response
$\pi_{j}$ .

  * •

$\\{x_{i},\perp\\}\leftarrow\texttt{Verify}(i,\textrm{vk},\pi_{1},\pi_{2},\textrm{aux}_{V})$
is a deterministic verification algorithm for the client. As input, it takes
the retrieval index $i$, verification key vk, servers answers $\pi_{1}$,
$\pi_{2}$, if necessary, auxiliary information $\textrm{aux}_{V}$, and uses
them to determine if it can reconstruct the correct value of $x_{i}$. If it
cannot do so, it outputs the special symbol $\perp$ indicating that at least
one of the answers is incorrect, otherwise, it reconstructs $x_{i}$ and
outputs it.

A scheme is called publicly verifiable if vk is public. Otherwise, the scheme
is privately verifiable. Public verification is generally preferred, but
usually relies on computational assumptions, while privately verifiable
schemes can be information-theoretically secure. Considered PIR scheme should
satisfy correctness, privacy, and security properties. Let us formally define
them.

######  Definition 2 (Correctness).

The scheme $\Pi$ is correct if for any $m$, $i\in[m]$ and
$\mathbf{x}\in\mathbb{F}_{p^{t}}^{m}$ and any
$(\textrm{vk},\sigma_{1},\sigma_{2},\textrm{aux}_{A},\textrm{aux}_{V})\leftarrow\texttt{QueriesGen}(m,i)$
it holds that
$\texttt{Verify}(i,\textrm{vk},\texttt{AnswerGen}(1,\sigma_{1},\textbf{x},\textrm{aux}_{A}),\texttt{AnswerGen}(2,\sigma_{2},$
$\textbf{x},\textrm{aux}_{V})=x_{i}$.

######  Definition 3 (Privacy).

The scheme $\Pi$ is private if for any $m$, any $i,i^{\prime}\in[m]$ and
$(\textrm{vk},\sigma_{1},\sigma_{2},\textrm{aux}_{A},\textrm{aux}_{V})\leftarrow\texttt{QueriesGen}(m,i)$,
$(\textrm{vk}^{\prime},\sigma^{\prime}_{1},\sigma^{\prime}_{2},\textrm{aux}_{A},\textrm{aux}_{V})\leftarrow\texttt{QueriesGen}(m,i^{\prime})$
and any $j\in[2]$, queries $\sigma_{j}$ and $\sigma^{\prime}_{j}$ are
identically distributed. The latter means that a given server $j$ cannot
distinguish between them.

Following [22] and recent papers on multi-server verifiable computations [11,
19], the verifiablity property can be defined through the notion of security
experiment: an adversary $\mathcal{A}$ controls the dishonest server $S_{j}$,
knows the database $\mathbf{x}$, retrieval index $i$, and, if necessary, the
auxiliary information $\textrm{aux}_{A}$ and crafts an answer $\hat{\pi}_{j}$
after receiving the query $\sigma_{j}$. We consider this setup for the
privately verifiable case and we denote the corresponding experiment as
$\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)$. For the publicly
verifiable case, we borrow the same ideas from [11] and generalize the
security experiment of [23] in a single-server setting to our two-server
setup. The resulting security experiment
$\textrm{EXP}_{\mathcal{A},\Pi}^{PubV}(m,\mathbf{x},i,j)$ is identical to
$\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)$ except that
adversary also knows verification key vk. Let us formally define them.

######  Definition 4 (Security experiment).

An interactive security experiment
$\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)/\textrm{EXP}_{\mathcal{A},\Pi}^{PubV}(m,\mathbf{x},i,j)$
between adversary $\mathcal{A}$ that controls dishonest server $j\in[2]$ and
its challenger in privately/publicly verifiable case can be described as
follows:

  * •

Challenger generates
$(\textrm{vk},\sigma_{1},\sigma_{2},\textrm{aux}_{A},\textrm{aux}_{V})\leftarrow\texttt{QueriesGen}(m,i)$
and sends $\sigma_{j}$ to the adversary $\mathcal{A}$.

  * •

The adversary $\mathcal{A}$ generates a crafted answer
$\hat{\pi}_{i}\leftarrow\mathcal{A}(j,\sigma_{j},\mathbf{x},i,\textrm{aux}_{A})/\hat{\pi}_{i}\leftarrow\mathcal{A}(j,\sigma_{j},\mathbf{x},i,\textrm{vk},\textrm{aux}_{A})$
and sends it to the challenger.

  * •

The challenger computes
$\pi_{3-j}\leftarrow\texttt{AnswerGen}(3-j,\sigma_{3-j},\textbf{x},\textrm{aux}_{A})$

  * •

The challenger runs the verification algorithm Verify with inputs $i$, vk,
$\hat{\pi}_{j}$ and $\pi_{3-j}$, if necessary, $\textrm{aux}_{V}$ and computes
an output $y$.

  * •

If $y\notin\\{x_{i},\perp\\}$ set the outcome
$\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)/\textrm{EXP}_{\mathcal{A},\Pi}^{PubV}(m,\mathbf{x},i,j)$
of the experiment to be $1$, otherwise set it to be $0$.

In what follows, we define the following two notions of verifiablity –
information-theoretical and computational.

######  Definition 5 (Negligible function).

A function from $\mathbb{N}$ to $\mathbb{R}^{+}$ is negligible and denoted as
$\texttt{negl}(.)$ if for all $c>0$ there exists a natural number
$\lambda_{0}$ such that $\texttt{negl}(\lambda)<\frac{1}{\lambda^{c}}$ for all
$\lambda>\lambda_{0}$.

######  Definition 6 (Information-theoretical virifiability).

The protocol $\Pi$ is $(1,\epsilon)$-verifiable if for any adversary
$\mathcal{A}$, any $j\in[2]$, $m$, $\mathbf{x}\in\mathbb{F}_{p^{t}}^{m}$ and
any $i\in[m]$, we have
$\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)=1]\leq\epsilon$.
Here, the probability is taken over the randomness of $\mathcal{A}$ and the
experiment.

######  Definition 7 (Computational verifiability).

The scheme $\Pi$ is $1$-verifiable if for any probabilistic poly-time (PPT)
adversary $\mathcal{A}$, any $j\in[2]$, $m$,
$\mathbf{x}\in\mathbb{F}_{q^{t}}^{m}$ and any $i\in[m]$,
$\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi}^{PriV}(m,\mathbf{x},i,j)/\textrm{EXP}_{\mathcal{A},\Pi}^{PubV}(m,\mathbf{x},i,j)=1]\leq\texttt{negl}(\lambda)$,
where the probability is taken over the randomness of $\mathcal{A}$ and the
experiment.

The notion of computational verifiability relies on certain cryptographic
assumptions. Schemes proposed in this paper rely on the following Discrete
logarithm (DLog) assumption.

######  Definition 8 (DLog assumption).

Let $\mathbb{G}$ be a cyclic group of order $p>2^{\lambda}$. For generator $g$
and $\alpha\in\mathbb{F}_{p}\setminus\\{0\\}$ we define the advantage
$\textrm{Adv}_{\mathcal{A}}^{DLog}$ of adversary $\mathcal{A}$ in solving
discrete logarithm problem in group $\mathbb{G}$ as the probability that he
can find $\alpha$ from values of $g$ and $g^{\alpha}$. We say that discrete
logarithm assumption holds if for any PPT adversary $\mathcal{A}$,
$\textrm{Adv}_{\mathcal{A}}^{DLog}(\lambda)\leq\texttt{negl}(\lambda)$.

##  III Our Constructions

In this section, we introduce two-server PIR schemes in which the client can
verify the result in the presence of one dishonest server. The basic idea is
to provide one more independent set of queries to the servers, so that the
user can compute two versions of $x_{i}$ or $x_{i}$ and $\textrm{v}x_{i}$ for
some secret parameter v and verify that both servers are truthful. If we keep
the verification key in secret and download whole responses to queries, we
obtain an information-theoretical $(1,\epsilon)$-verifiable scheme with
private verification, or shortly $(1,\epsilon)$ privately verifiable scheme
(see section III-A). Later on, we generalize this scheme to a publicly
verifiable setup (see section III-B) and reduce the communication cost by
introducing homomorphic hashes (see section III-C).

###  III-A Information-Theoretical Privately Verifiable Scheme

Let us modify the linear secret-sharing-based PIR scheme $\Pi_{0}$ to the case
of results verification by creating one more set of independent queries. The
resulting two server verifiable PIR scheme $\Pi_{1}$ can be described as
follows.

  * •

$\texttt{QueriesGen}(m,i)$: Choose
$\textrm{v}\leftarrow\mathbb{F}_{p}\setminus\\{0\\}$,
$\textbf{r}\leftarrow\mathbb{F}_{p}^{m}$,
$\textbf{r}_{v}\leftarrow\mathbb{F}_{p}^{m}$. Let
$\mathbf{f}(u)=\mathbf{e}_{i}+\mathbf{r}u\in\mathbb{F}_{p}^{m}$ and
$\mathbf{f}_{v}(u)=\textrm{v}\mathbf{e}_{i}+\mathbf{r}_{v}u\in\mathbb{F}_{p}^{m}$,
$\mathbf{e}_{i}$ is all zero vector of length $m$ with a ‘1’ in the position
$i$. Compute $\sigma_{j}=(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$ for all
$j\in[2]$. Output $\textrm{vk}=\textrm{v}$, $\sigma_{1}$, $\sigma_{2}$, and
$\textrm{aux}_{V}=\\{u_{1},u_{2}\\}$.

  * •

$\texttt{AnswerGen}(j,\sigma_{j},\mathbf{x})$: Parse $\sigma_{j}$ as
$(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$, compute
$z_{j}=\mathbf{f}(u_{j})^{T}\mathbf{x}$,
$w_{j}=\mathbf{f}_{v}(u_{j})^{T}\mathbf{x}$, output $\pi_{j}=(z_{j},w_{j})$.

  * •

$\texttt{Verify}(i,\textrm{vk},\pi_{1},\pi_{2},\textrm{aux}_{V})$: Parse
$\textrm{aux}_{V}$ as $\\{u_{1},u_{2}\\}$. Retrieve $x_{i}$ and
$\textrm{v}x_{i}$ as

$\begin{bmatrix}x_{i}\\\
\mathbf{r}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}z_{1}\\\
z_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}z_{1}\\\ z_{2}\end{bmatrix}$ (4)

and

$\begin{bmatrix}\textrm{v}x_{i}\\\
\mathbf{r}_{v}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}w_{1}\\\ w_{2}\end{bmatrix}$ (5)

If the equation below holds, output $x_{i}$; otherwise, output $\perp$.

$\textrm{v}\left(az_{1}+bz_{2}\right)=aw_{1}+bw_{2}$ (6)

The proofs of correctness of our scheme and proof of privacy are almost
identical to that of [20] and omitted here. The download rate is equal to
$\frac{1}{4}$ and below we show that $\Pi_{1}$ is $(1,\epsilon)$-verifiable.

######  Theorem 1.

The scheme $\Pi_{1}$ is $(1,\epsilon)$-verifiable where
$\epsilon=\frac{1}{p-1}$.

###### Proof.

Without loss of generality, assume that Adversary $\mathcal{A}$ controls the
server $S_{1}$ and set $j=1$. Let $\pi_{1}=(z_{1},w_{1})$ and
$\pi_{2}=(z_{2},w_{2})$ be the answers obtained by correctly executing
algorithm AnswerGen by each server. Let
$\hat{\pi}_{1}=(\hat{z}_{1},\hat{w}_{1})$ be the answer chosen by
$\mathcal{A}$ for $S_{1}$.

From the description of $\Pi_{1}$ it is clear that

$x_{i}=A=az_{1}+bz_{2}$

and

$\textrm{v}x_{i}=V=aw_{1}+bw_{2}$

while

$\hat{x}_{i}=\hat{A}=a\hat{z}_{1}+bz_{2}$

and

$\hat{\textrm{v}}\hat{x}_{i}=\hat{V}=a\hat{w}_{1}+bw_{2}.$

$\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)$ if the
$\hat{A}\neq A$ and $\hat{V}=\textrm{v}\hat{A}$. It is clear that
$V=\textrm{v}A$. Hence, in this case,

$\hat{V}-V=\textrm{v}(\hat{A}-A).$

From equations (4), (5) and the fact that server $S_{2}$ is honest, it is
clear that

$\hat{A}-A=a\left(\hat{z}_{1}-z_{1}\right)=a\Delta_{0}\neq 0$ (7)
$\hat{V}-V=a\left(\hat{w}_{1}-w_{1}\right)=a\Delta_{1}$ (8)

Hence $\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)$ iff it finds the
solution for the equation

$G(\textrm{v})=a\Delta_{1}-a\textrm{v}\Delta_{0}=a(\Delta_{1}-\textrm{v}\Delta_{0})=0.$
(9)

From the description of the security experiment, it follows that
$\Delta_{0},\Delta_{1}$ are known to $\mathcal{A}$ and independent from v.
Hence

$\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)=1]\leq\textrm{Pr}[G(\textrm{v})=0],$
(10)

for v chosen independently and uniformly at random from
$\mathbb{F}_{p}\setminus\\{0\\}$. By Schwartz-Zippel Lemma [24, 25] this value
can be estimated from above as $\frac{1}{p-1}$, and the theorem statement
follows. ∎

###  III-B Computational Publicly Verifiable Scheme

Next, we modify information-theoretical privately verifiable scheme $\Pi_{1}$
to a publicly verifiable setup. To do so, we choose a cyclic group
$\mathbb{G}$ with generator $g$ of prime order $p\geq 2^{\lambda}$ and made
$\textrm{vk}=g^{\textrm{v}}$ public. The resulting PIR scheme $\Pi_{2}$ can be
described as follows.

  * •

$\texttt{QueriesGen}(m,i)$: Choose
$\textrm{x}\leftarrow\mathbb{F}_{p}\setminus\\{0\\}$,
$\textbf{r}\leftarrow\mathbb{F}_{p}^{m}$,
$\textbf{r}_{v}\leftarrow\mathbb{F}_{p}^{m}$. Let
$\mathbf{f}(u)=\mathbf{e}_{i}+\mathbf{r}u\in\mathbb{F}_{p}^{m}$ and
$\mathbf{f}_{v}(u)=\textrm{v}\mathbf{e}_{i}+\mathbf{r}_{v}u\in\mathbb{F}_{p}^{m}$.
Compute $\sigma_{j}=(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$ for all
$j\in[2]$. Choose a cyclic group $\mathbb{G}$ of prime order $p$ with
generator $g$. Output $\textrm{vk}=g^{\textrm{v}}$, $\sigma_{1}$, $\sigma_{2}$
and $\textrm{aux}_{V}=\\{u_{1},u_{2}\\}$.

  * •

$\texttt{AnswerGen}(j,\sigma_{j},\mathbf{x})$: Parse $\sigma_{j}$ as
$(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$, compute
$z_{j}=\mathbf{f}(u_{j})^{T}\mathbf{x}$,
$w_{j}=\mathbf{f}_{v}(u_{j})^{T}\mathbf{x}$, output $\pi_{j}=(z_{j},w_{j})$.

  * •

$\texttt{Verify}(i,\textrm{vk},\pi_{1},\pi_{2},\textrm{aux}_{V})$: Parse
$\textrm{aux}_{V}$ as $\\{u_{1},u_{2}\\}$. Retrieve $x_{i}$ and
$\textrm{v}x_{i}$ as

$\begin{bmatrix}x_{i}\\\
\mathbf{r}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}z_{1}\\\
z_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}z_{1}\\\ z_{2}\end{bmatrix}$ (11)

and

$\begin{bmatrix}\textrm{v}x_{i}\\\
\mathbf{r}_{v}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}w_{1}\\\ w_{2}\end{bmatrix}$ (12)

If the equation below holds, output $x_{i}$; otherwise, output $\perp$:

$(g^{\textrm{v}})^{\left(az_{1}+bz_{2}\right)}=g^{aw_{1}+bw_{2}}.$ (13)

The proofs of correctness of our scheme and proof of privacy are almost
identical to that of [20] and omitted here. The download rate is equal to
$\frac{1}{4}$.

######  Theorem 2.

The scheme $\Pi_{2}$ is $1$-verifiable under DLog assumption in $\mathbb{G}$.

###### Proof.

Without loss of generality, assume that Adversary $\mathcal{A}$ controls the
server $S_{1}$ and set $j=1$. Let
$\pi_{1}=(\mathbf{f}(u_{1})^{T}\mathbf{x},\mathbf{f}_{v}(u_{1})^{T}\mathbf{x})=(z_{1},w_{1})$
and
$\pi_{2}=(\mathbf{f}(u_{2})^{T}\mathbf{x},\mathbf{f}_{v}(u_{2})^{T}\mathbf{x})=(z_{2},w_{2})$
be the answers obtained by correctly executing algorithm AnswerGen by each
server. Let $\hat{\pi}_{1}=(\hat{z}_{1},\hat{w}_{1})$ is answers chosen by
$\mathcal{A}$ for $S_{1}$.

From the description of $\Pi_{1}$ it is clear that

$x_{i}=A=az_{1}+bz_{2}$

and

$\textrm{v}x_{i}=V=aw_{1}+bw_{2}$

while

$\hat{x}_{i}=\hat{A}=a\hat{z}_{1}+bz_{2}$

and

$\hat{\textrm{v}}\hat{x}_{i}=\hat{V}=a\hat{w}_{1}+bw_{2}.$

$\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\Pi_{2}}^{PubV}(m,\mathbf{x},i,j)$ if the
$\hat{A}\neq A$ and $g^{\hat{V}}=g^{\textrm{v}\hat{A}}$. From equations
(11),(12) and the fact that server $2$ is honest it is clear that

$\hat{A}-A=a\left(\hat{z}_{1}-z_{1}\right)=a\Delta_{0}\neq 0$ (14)
$\hat{V}-V=a\left(\hat{w}_{1}-w_{1}\right)=a\Delta_{1}.$ (15)

As $g^{V}=(g^{\textrm{v}})^{A}$, $\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\Pi_{2}}^{PubV}(m,\mathbf{x},i,j)$ iff

$g^{a\Delta_{0}}=(g^{\textrm{v}})^{a\Delta_{1}}.$ (16)

From the description of security experiment it follows that $\Delta_{0}$,
$\Delta_{1}$ are known to $\mathcal{A}$ and independent from v and
$g^{\textrm{v}}$. Hence
$\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)=1]$
can be estimated from above as probability of learning the value
$\textrm{v}=\frac{a\Delta_{0}}{a\Delta_{1}}=\frac{\Delta_{0}}{\Delta_{1}}$
where $\Delta_{0}\neq 0$ from the discrete-logarithm relationship in the group
$\mathbb{G}$. As a result, the theorem statement follows. ∎

###  III-C Computational Privately Verifiable Scheme

The main drawback of scheme $\Pi_{1}$ is that it doubles the download cost in
comparison to capacity-achieving scheme $\Pi_{0}$. The possible solution to a
problem of this kind is to apply homomorphic hashes to the second part of
responses $\pi_{1}$ and $\pi_{2}$. The construction of homomorphic hashes is
based on DLog assumption in the multiplicative group of order $p\geq
2^{\lambda}$ in the finite field and was introduced for the first time for
verification of digital content distributed by rateless erasure codes in [26]
and further applied for network coding in [21]. Resulted PIR scheme $\Pi_{3}$
can be described as follows.

  * •

$\texttt{QueriesGen}(m,i)$: Choose
$\textrm{x}\leftarrow\mathbb{F}_{p}\setminus\\{0\\}$,
$\textbf{r}\leftarrow\mathbb{F}_{p}^{m}$,
$\textbf{r}_{v}\leftarrow\mathbb{F}_{p}^{m}$. Let
$\mathbf{f}(u)=\mathbf{e}_{i}+\mathbf{r}u\in\mathbb{F}_{p}^{m}$ and
$\mathbf{f}_{v}(u)=\textrm{v}\mathbf{e}_{i}+\mathbf{r}_{v}u\in\mathbb{F}_{p}^{m}$.
Compute $\sigma_{j}=(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$ for all
$j\in[2]$. Choose a prime number $r$ so that $r-1$ is divisible by $p$ and
random elements $g_{1},\ldots,g_{t}$ of $\mathbb{Z}_{r}$ of order $p$. Choose
a basis $\mathcal{B}$ of $\mathbb{F}_{p^{t}}$ over $\mathbb{F}_{p}$. Output
$\textrm{vk}=\textrm{v}$, $\sigma_{1}$, $\sigma_{2}$,
$\textrm{aux}_{A}=\\{g_{1},\ldots,g_{t},\mathcal{B}\\}$ and
$\textrm{aux}_{V}=\\{g_{1},\ldots,g_{t},\mathcal{B},u_{1},u_{2}\\}$.

  * •

$\texttt{AnswerGen}(j,\sigma_{j},\mathbf{x},\textrm{aux}_{A})$: Parse
$\sigma_{j}$ as $(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$,
$\textrm{aux}_{A}$ as $\\{g_{1},\ldots,g_{t},\mathcal{B}\\}$, compute
$z_{j}=\mathbf{f}(u_{j})^{T}\mathbf{x}$,
$w_{j}=\mathbf{f}_{v}(u_{j})^{T}\mathbf{x}$. Represent $w_{j}$ in basis
$\mathcal{B}$ of $\mathbb{F}_{p^{t}}$ over $\mathbb{F}_{p}$ as
$(w_{j,1},\ldots,w_{j,t})^{T}$ and compute
$h(w_{j})=\prod_{l=1}^{t}g_{l}^{w_{j,l}}\;\;\textrm{mod}\;r$. Output
$\pi_{j}=(z_{j},h(w_{j}))$.

  * •

$\texttt{Verify}(i,\textrm{vk},\pi_{1},\pi_{2},\textrm{aux}_{V})$: Parse
$\textrm{aux}_{V}$ as $\\{g_{1},\ldots,g_{t},\mathcal{B},u_{1},u_{2}\\}$.
Retrieve $x_{i}$ as

$\begin{bmatrix}x_{i}\\\
\mathbf{r}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}z_{1}\\\
z_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}z_{1}\\\ z_{2}\end{bmatrix}$ (17)

Represent $x_{i}$ in basis $\mathcal{B}$ of $\mathbb{F}_{p^{t}}$ over
$\mathbb{F}_{p}$ as $(x_{i,1},\ldots,x_{i,t})^{T}$ and compute
$h(x_{i})=\prod_{l=1}^{t}g_{l}^{x_{i,l}}\;\;\textrm{mod}\;r$.

If the equation below holds, output $x_{i}$; otherwise, output $\perp$.

$h(x_{i})^{\textrm{v}}=h(w_{1})^{a}h(w_{2})^{b}\;\;\textrm{mod}\;r.$ (18)

The proofs of correctness of our scheme and proof of privacy are almost
identical to that of [20] and omitted here. The download rate is equal to
$\frac{t\log p}{2(t\log p+\log r)}$ that can be arbitrarily close to
$\frac{1}{2}$.

######  Theorem 3.

The scheme $\Pi_{3}$ is $1$-verifiable under DLog assumption in a
multiplicative group of order $p$ in a finite field.

###### Proof.

Without loss of generality, assume that Adversary $\mathcal{A}$ controls the
server $S_{1}$ and set $j=1$. Let
$\pi_{1}=(\mathbf{f}(u_{1})^{T}\mathbf{x},h(\mathbf{f}_{v}(u_{1})^{T}\mathbf{x}))=(z_{1},h(w_{1}))$
and $\pi_{2}=(z_{2},h(w_{2}))$ be the answers obtained by correctly executing
algorithm AnswerGen by each server. Let
$\hat{\pi}_{1}=(\hat{z}_{1},h(\hat{w}_{1})$ be the answer chosen by
$\mathcal{A}$ for $S_{1}$.

Let $HC$ and $HC^{c}$ denote the event of hash collision and its complement,
respectively. From the description of $\Pi_{3}$ and the law of total
probability, it is clear that

$\displaystyle\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{3}}^{PriV}(m,\mathbf{x},i,j)=1]$
$\displaystyle=\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{3}}^{PriV}(m,\mathbf{x},i,j)=1|HC]\textrm{Pr}[HC]$
$\displaystyle~{}+\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{3}}^{PriV}(m,\mathbf{x},i,j)=1|HC^{c}]\textrm{Pr}[HC^{c}]$
$\displaystyle\leq\textrm{Pr}[HC]+\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{3}}^{PriV}(m,\mathbf{x},i,j)=1|HC^{c}]\textrm{Pr}[HC^{c}]$
$\displaystyle\leq\textrm{Pr}[HC]+\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)=1]\leq\texttt{negl}(\lambda).$
(19)

The final inequality (19) follows from the collision resistance of homomorphic
hash functions under the DLog assumption in a multiplicative group of order
$p\geq 2^{\lambda}$. ∎

######  Remark 9.

We can replace homomorphic hashes construction based on DLog assumption with
homomorphic hashes construction based on t-poly DH assumption in the group of
points of an elliptic curve [27, 28]. Despite the latter requiring a smaller
field size to deploy, it requires the existence of a trusted setup that can be
impossible in some scenarios.

##  IV Comparisons

Let us consider setup when we have $m$ files over a finite field
$\mathbb{F}_{p^{t}}$ and possible solutions to the problem of verifiable PIR
with optimized download cost. By Pr we denote the probability that an
adversary with access to one server wins in the security experiment. We
measure the file size, upload cost (UP), and download cost (DC) in bits. Also,
we differentiate schemes by the notion of 1-verifiablity (1-verif.), 1-privacy
(1-priv.), and presence of verifiability (verif.). The comparison is presented
in Table 1.

| $\Pi_{0}$ | [11, Scheme 3] | $\mathbb{A}$ | $\Pi_{1}$ | $\Pi_{2}$ | $\Pi_{3}$
---|---|---|---|---|---|---
File size | $t\cdot\log(p)$ | $t\cdot\log(p)$ | $t\cdot\log(p)$ | $t\cdot\log(p)$ | $t\cdot\log(p)$ | $t\cdot\log(p)$
UC | $2m\cdot\log(p)$ | $4m\cdot\log(p)$ | $4m\cdot\log(p)$ | $4m\cdot\log(p)$ | $4m\cdot\log(p)$ | $4m\cdot\log(p)$
DC | $2t\cdot\log(p)$ | $4t\cdot\log(p)$ | $4t\cdot\log(p)$ | $4t\cdot\log(p)$ | $4t\cdot\log(p)$ | $2t\cdot\log(p)+2\cdot\log(r)$
Pr | $1$ | $\frac{p-1}{p^{2}-3}$ | $\frac{2(p-1)}{(p-2)^{2}}$ | $\frac{1}{p-1}$ | $\texttt{negl}(\lambda)$ | $\texttt{negl}(\lambda)$
1-verif. | no | IT | IT | IT | DLog | DLog
1-priv. | IT | IT | IT | IT | IT | IT
verif. | no | private | private | private | public | private
TABLE 1: Comparison of two-server PIR schemes that optimize the download rate

For comparison we take schemes $\Pi_{0}$, $\Pi_{1}$, $\Pi_{2}$ and $\Pi_{3}$
decribed in this paper. Also, we apply a two-server verifiable computation
scheme of low-degree polynomials from [11, Scheme 3] at the top of scheme
$\Pi_{0}$ to construct the two-server verifiable scheme. We note that this is
the only scheme from [11] that can be deployed in two server scenarios. It
cannot be generalized to publicly verifiable cases, and we cannot apply
homomorphic hashing schemes to it as we cannot separate server responses into
two parts (one is responsible for the retrieval, and one is for the
verification). The parameters of the resulting scheme are presented in column
$3$.

Two server-verifiable schemes can also be created from scheme $\Pi_{0}$ by
forming two independent queries for each server. The important thing here is
that in comparison to previously described schemes, points of evaluation must
be kept secret. Such an approach offers a higher probability that an adversary
with access to one server wins in the security experiment. Let us formally
describe it below and prove its $(1,\epsilon)$-verifiability. In that follows,
we denote this scheme as $\mathbb{A}$.

  * •

$\texttt{QueriesGen}(m,i)$: Choose $u_{1},u_{2}\leftarrow\mathbb{F}_{p}$,
$u_{1}\neq u_{2}$, $\tilde{u}_{1},\tilde{u}_{2}\leftarrow\mathbb{F}_{p}$,
$\tilde{u}_{1}\neq\tilde{u}_{2}$, $\textbf{r}\leftarrow\mathbb{F}_{p}^{m}$,
$\textbf{r}_{v}\leftarrow\mathbb{F}_{p}^{m}$. Let
$\mathbf{f}(u)=\mathbf{e}_{i}+\mathbf{r}u\in\mathbb{F}_{p}^{m}$ and
$\mathbf{f}_{v}(u)=\mathbf{e}_{i}+\mathbf{r}_{v}u\in\mathbb{F}_{p}^{m}$.
Compute $\sigma_{j}=(\mathbf{f}(u_{j}),\mathbf{f}_{v}(\tilde{u}_{j}))$ for all
$j\in[2]$. Output
$\textrm{vk}=\textrm{aux}_{V}=\\{u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2}\\}$,
$\sigma_{1}$ and $\sigma_{2}$.

  * •

$\texttt{AnswerGen}(j,\sigma_{j},\mathbf{x})$: Parse $\sigma_{j}$ as
$(\mathbf{f}(u_{j}),\mathbf{f}_{v}(u_{j}))$, compute
$z_{j}=\mathbf{f}(u_{j})^{T}\mathbf{x}$,
$w_{j}=\mathbf{f}_{v}(u_{j})^{T}\mathbf{x}$, output $\pi_{j}=(z_{j},w_{j})$.

  * •

$\texttt{Verify}(i,\textrm{vk},\pi_{1},\pi_{2},\textrm{aux}_{V})$: Parse
$\textrm{vk}=\textrm{aux}_{V}=\\{u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2}\\}$.
Retrieve $x_{i}$ as

$\begin{bmatrix}x_{i}\\\
\mathbf{r}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&u_{1}\\\
1&u_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}z_{1}\\\
z_{2}\end{bmatrix}=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\cdot\begin{bmatrix}z_{1}\\\ z_{2}\end{bmatrix}$ (20)

and

$\begin{bmatrix}x_{i}\\\
\mathbf{r}_{v}^{T}\mathbf{x}\end{bmatrix}=\begin{bmatrix}1&\tilde{u}_{1}\\\
1&\tilde{u}_{2}\end{bmatrix}^{-1}\cdot\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}=\begin{bmatrix}\tilde{a}&\tilde{b}\\\
\tilde{c}&\tilde{d}\end{bmatrix}\cdot\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}$ (21)

If the equation below holds, output $x_{i}$; otherwise, output $\perp$.

$az_{1}+bz_{2}=\tilde{a}w_{1}+\tilde{b}w_{2}$ (22)

The proofs of correctness of this scheme and proof of privacy are almost
identical to that of [20] and omitted here. The download rate is equal to
$\frac{1}{4}$.

######  Theorem 4.

The scheme $\mathbb{A}$ is $(1,\epsilon)$-verifiable where
$\epsilon=\frac{2(p-1)}{(p-2)^{2}}$.

###### Proof.

Without loss of generality, assume that Adversary $\mathcal{A}$ controls the
server $S_{1}$ and set $j=1$. Let $\pi_{1}=(z_{1},w_{1})$ and
$\pi_{2}=(z_{2},w_{2})$ be the answers obtained by correctly executing
algorithm AnswerGen by each server. Let
$\hat{\pi}_{1}=(\hat{z}_{1},\hat{w}_{1})$ be the answer chosen by
$\mathcal{A}$ for $S_{1}$.

From the description of $\mathbb{A}$ it is clear that

$x_{i}=A=az_{1}+bz_{2}$

and

$x_{i}=V=\tilde{a}w_{1}+\tilde{b}w_{2}$

while

$\hat{x}_{i}=\hat{A}=a\cdot\hat{z}_{1}+bz_{2}$

and

$\tilde{x}_{i}=\hat{V}=\tilde{a}\hat{w}_{1}+\tilde{b}w_{2}.$

$\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\mathbb{A}}^{PriV}(m,\mathbf{x},i,j)$ if the
$\hat{A}\neq A$ and $\hat{V}=\hat{A}$. It is clear that $A=V$. Hence,

$\hat{V}-V=\hat{A}-A.$

From equations (20), (21) and the fact that server $2$ is honest it is clear
that

$\hat{A}-A=a\left(\hat{z}_{1}-z_{2}\right)=a\Delta_{0}\neq 0$ (23)
$\hat{V}-V=\tilde{a}\left(\hat{w}_{1}-w_{2}\right)=\tilde{a}\Delta_{1},$ (24)

where $a=\frac{u_{2}}{u_{2}-u_{1}}$ and
$\tilde{a}=\frac{\tilde{u}_{2}}{\tilde{u}_{2}-\tilde{u}_{1}}$. Hence
$\mathcal{A}$ wins the security experiment
$\textrm{EXP}_{\mathcal{A},\Pi_{1}}^{PriV}(m,\mathbf{x},i,j)$ iff it finds the
solution for the equation

$\displaystyle
G(u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2})=\frac{\tilde{u}_{2}}{\tilde{u}_{2}-\tilde{u}_{1}}\Delta_{1}-\frac{u_{2}}{u_{2}-u_{1}}\Delta_{0}$
$\displaystyle=\frac{\tilde{u}_{2}(u_{2}-u_{1})\Delta_{1}-u_{2}(\tilde{u}_{2}-\tilde{u}_{1})\Delta_{0}}{(\tilde{u}_{2}-\tilde{u}_{1})(u_{2}-u_{1})}=0.$
(25)

From the description of security experiment, it follows that
$\Delta_{0},\Delta_{1}$ are known to $\mathcal{A}$ and independent from
$u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2}$. Hence,

$\displaystyle\textrm{Pr}[\textrm{EXP}_{\mathcal{A},\mathbb{A}}^{PriV}(m,\mathbf{x},i,j)=1]$
$\displaystyle\leq\textrm{Pr}(G(u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2})=0|\Delta_{1}\neq\Delta_{0}\neq
0)$ $\displaystyle=\sum_{(c_{1},c_{2},c_{3},c_{4})\in
L}\textrm{Pr}(G(c_{1},c_{2},c_{3},c_{4})=0|\Delta_{1}\neq\Delta_{0}\neq 0)$
$\displaystyle~{}\cdot\textrm{Pr}[(u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2})=(c_{1},c_{2},c_{3},c_{4})]=\frac{g}{(q-1)^{2}(q-2)^{2}},$
(26)

where
$L=\\{(c_{1},c_{2},c_{3},c_{4})|c_{1},c_{2},c_{3},c_{4}\in\mathbb{F}_{q}\setminus\\{0\\},c_{1}\neq
c_{2},c_{3}\neq c_{4}\\}$ and $g$ is the number of
$(c_{1},c_{2},c_{3},c_{4})\in L$ so that $G(c_{1},c_{2},c_{3},c_{4})=0$. Since
the denominator of $G$ is non-zero, we can estimate $g$ as number of zeros of
$H(u_{1},u_{2},\tilde{u}_{1},\tilde{u}_{2})=\tilde{u}_{2}(u_{2}-u_{1})\Delta_{1}-u_{2}(\tilde{u}_{2}-\tilde{u}_{1})\Delta_{0}$.
Let
$L^{\prime}=\\{(c_{1},c_{2},c_{3},c_{4})|c_{1},c_{2},c_{3},c_{4}\in\mathbb{F}_{q}\setminus\\{0\\}\\}$.
It is clear that $L\subseteq L^{\prime}$ and we can estimate $g$ from above as
number of zeros of $H(\tau_{1},\tau_{2},\tau_{3},\tau_{4})$ where
$\tau_{1},\tau_{2},\tau_{3},\tau_{4}$ are chosen uniformly from $L^{\prime}$.
By Schwartz-Zippel Lemma [24, 25] this value can be estimated from above as
$\frac{2}{q-1}$. As a result, we have that $g\leq 2(q-1)^{3}$, and the theorem
statement follows. ∎

##  V Conclusion

We considered the problem of reflecting malicious server behavior in private
information retrieval schemes with optimized download rates. We focused on the
extreme two-server case and propose generalizations of linear secret-sharing-
based PIR schemes to verifiable setups. Considered schemes can detect the
presence of one cheating server and offers information-theoretical private
verifiability, computational public verifiability, and computational private
verifiability with download rate close to those of non-verifiable scheme.

## Acknowledgment

Authors thank L. F. Zhang from ShanghaiTech University for numerous fruitful
discussions during the preparation of this paper.

## References

  * [1] 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
  * [2] 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
  * [3] Rafail Ostrovsky and William E. Skeith  “A Survey of Single-Database Private Information Retrieval: Techniques and Applications”, 2007, pp. 393–411
  * [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] Liang Feng Zhang and Reihaneh Safavi-Naini  “Verifiable Multi-server Private Information Retrieval”  In _Applied Cryptography and Network Security_ , 2014
  * [13] Liang Zhao, Xingfeng Wang and Xinyi Huang  “Verifiable single-server private information retrieval from LWE with binary errors”  In _Information Sciences_ 546, 2021, pp. 897–923
  * [14] 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
  * [15] Kaoru Kurosawa  “How to Correct Errors in Multi-server PIR”  In _Advances in Cryptology – ASIACRYPT 2019_ , 2019, pp. 564–574
  * [16] K Devet, I Goldberg and N Heninger  “Optimally Robust Private Information Retrieval”  In _21st USENIX Security Symposium (USENIX Security 12)_ , 2012, pp. 269–283
  * [17] Amos Beimel  “Robust Private Information Retrieval”  In _Encyclopedia of Cryptography, Security and Privacy_ Springer Berlin Heidelberg, 2019, pp. 1–3
  * [18] Trinabh Gupta et al.  “Scalable and Private Media Consumption with Popcorn”  In _13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)_ , 2016
  * [19] Pengzhen Ke and Liang Feng Zhang  “Two-Server Private Information Retrieval with Result Verification”  In _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 408–413
  * [20] Rawad Bitar and Salim El Rouayheb  “Staircase-PIR: Universally Robust Private Information Retrieval”  In _2018 IEEE Information Theory Workshop (ITW)_ , 2018, pp. 1–5
  * [21] C. Gkantsidis and P. Rodriguez Rodriguez  “Cooperative Security for Network Coding File Distribution”  In _Proceedings of 25th IEEE International Conference on Computer Communications_ , 2006, pp. 1–13
  * [22] Mira Belenkiy et al.  “Incentivizing Outsourced Computation”  In _Proceedings of the 3rd International Workshop on Economics of Networked Systems_ , 2008, pp. 85–90
  * [23] Bryan Parno, Mariana Raykova and Vinod Vaikuntanathan  “How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption”  In _Theory of Cryptography_ , 2012, pp. 422–439
  * [24] J.. Schwartz  “Fast Probabilistic Algorithms for Verification of Polynomial Identities”  In _J. ACM_ 27.4 New York, NY, USA: Association for Computing Machinery, 1980, pp. 701–717
  * [25] Richard Zippel  “Probabilistic algorithms for sparse polynomials”  In _Symbolic and Algebraic Computation_ , 1979, pp. 216–226
  * [26] M.N. Krohn, M.J. Freedman and D. Mazieres  “On-the-fly verification of rateless erasure codes for efficient content distribution”  In _IEEE Symposium on Security and Privacy_ , 2004, pp. 226–240
  * [27] Man Ho Au, Qianhong Wu, Willy Susilo and Yi Mu  “Compact E-Cash from Bounded Accumulator”  In _Topics in Cryptology_ , 2006, pp. 178–195
  * [28] Man Ho Au, Willy Susilo and Yi Mu  “Practical Anonymous Divisible E-Cash from Bounded Accumulators”  In _Financial Cryptography and Data Security_ , 2008, pp. 287–301


# Batteryless BLE and Light-based IoT Sensor Nodes for Reliable Environmental
Sensing

Jimmy Fernandez Landivar1⋄, Khojiakbar Botirov2⋄, Hazem Sallouha1, Marcos
Katz2 and Sofie Pollin1
The present work has received funding from the European Union’s Horizon 2020
Marie Skłodowska Curie Innovative Training Network Greenedge (GA. No. 953775).
The work of Hazem Sallouha was funded by the Research Foundation – Flanders
(FWO), Postdoctoral Fellowship No. 12ZE222N. 0000-0002-4904-5256
0009-0004-6690-3365 0000-0002-1288-1023 0000-0001-9901-5023
0000-0002-1470-2076 1Department of Electrical Engineering (ESAT) - WaveCoRE,
KU Leuven, 3000 Leuven, Belgium
2Centre for Wireless Communications, University of Oulu, 90570 Oulu, Finland
⋄Authors contributed equally
E-mails: {jfernand, hazem.sallouha<EMAIL_ADDRESS>{khojiakbar.botirov<EMAIL_ADDRESS>
###### Abstract

The sustainable design of Internet of Things (IoT) networks encompasses
considerations related to energy efficiency and autonomy as well as
considerations related to reliable communications, ensuring no energy is
wasted on undelivered data. Under these considerations, this work proposes the
design and implementation of energy-efficient Bluetooth Low Energy (BLE) and
Light-based IoT (LIoT) batteryless IoT sensor nodes powered by an indoor light
Energy Harvesting Unit (EHU). Our design intends to integrate these nodes into
a sensing network to improve its reliability by combining both technologies
and taking advantage of their features. The nodes incorporate state-of-the-art
components, such as low-power sensors and efficient System-on-Chips (SoCs).
Moreover, we design a strategy for adaptive switching between active and sleep
cycles as a function of the available energy, allowing the IoT nodes to
continuously operate without batteries. Our results show that by adapting the
duty cycle of the BLE and LIoT nodes depending on the environment’s light
intensity, we can ensure a continuous and reliable node operation. In
particular, measurements show that our proposed BLE and LIoT node designs are
able to communicate with an IoT gateway in a bidirectional way, every 19.3 and
624.6 seconds, respectively, in an energy-autonomous and reliable manner.

###### Index Terms:

Bluetooth Low Energy, Hybrid RF/VLC Networks, Environmental Sensing, Light-
based IoT, Sustainable Internet of Things, Visible Light Communications.

##  I Introduction

Environmental sensing and monitoring rely on the dense deployment of sensors
that are needed to ensure accurate data acquisition. To guarantee a reliable,
energy and cost-efficient deployment, the focus is on implementing energy-
autonomous devices, efficient low-power communication protocols, and adopting
sustainable design and deployment approaches [1, 2]. Therefore, cutting-edge
technologies such as batteryless Internet of Things (IoT) devices aim to
minimize hardware elements by employing organic electronic materials such as
Printed Electronics (PE) while integrating highly efficient sensors and
alternative environmentally friendly power sources like light or Radio-
Frequency (RF) energy harvesting. This technology aims to establish
sustainable IoT nodes following and spreading the “Expose and Connect”
concept; whenever a node is exposed to an energy source, it connects to the
network and sends information [2]. For instance, Bluetooth Low Energy (BLE)
and Visible Light Communications (VLC) are promising technologies that support
this concept while offering reliable communications.

In particular, BLE is among the most suitable technologies for monitoring
applications for many reasons, such as its ease of integration with multiple
sensor devices, its cost-effectiveness in network deployment, and the
advantage of being integrated into highly efficient System-on-Chips (SoCs)
with low energy consumption features. These reasons allow BLE to be used in
short-range communications with minimal energy consumption through optimized
scanning and advertising cycles [3]. However, in extensive IoT sensor network
deployments, BLE and RF technologies may be subject to congestion and
interference issues [2]. VLC has recently evolved as an IoT low-power
technology capable of tackling the mentioned challenges of BLE networks by
using the light spectrum for wireless data exchange. A Light-based IoT (LIoT)
node can exploit different frequencies of the visible and non-visible light
spectrum for the uplink and downlink, such as Infrared (IR) and Visible Light
(VL) [4, 5]. Thus, implementing an IoT network with BLE and LIoT can enhance
its reliability and node efficiency by leveraging both technologies’ strengths
without mutual interference[6]. In addition to the communication technologies,
integrating low-power sensors and energy-efficient algorithms is essential to
ensure reliable communications despite low-energy constraints [3, 4].

Moreover, environmental sensing is critical to creating a controlled and safe
environment in several use cases such as indoor laboratories, manufacturing
plants, and office buildings [3, 7]. Precisely, sensing parameters such as
temperature, humidity, and Volatile Organic Compounds (VOCs) contribute to
assessing and improving the infrastructure Indoor Air Quality (IAQ) [3, 7]. In
these scenarios, the deployment of monitoring networks with reliable IoT
sensor nodes implementing BLE and LIoT technologies can support these critical
monitoring networks with energy-efficient sensing operations.

Concerning this topic, this paper proposes the design of BLE and LIoT sensor
nodes using state-of-the-art software and components, such as low-power
sensors and SoCs. Our solution follows a sustainable approach by using PE and
avoiding using batteries. These sensor nodes are intended to integrate into an
indoor environmental sensing network, providing a reliable operation under
constant illumination.

Hence, our main contributions are summarized as follows:

  * •

We investigate the design of two batteryless IoT nodes, one based on BLE and
another one on LIoT. The sensor nodes use state-of-the-art components, such as
a sustainable Energy Harvesting Unit (EHU), low-power sensors, and energy-
efficient communication technologies.

  * •

Based on our design, a solution for the sensing, communication, and
batteryless low-power operation is proposed. It includes a detailed analysis
of the nodes’ active and sleep cycles for low-power periodic operation based
on experimental energy consumption measurements.

  * •

Finally, we conducted an eight-hour experimental evaluation to demonstrate the
energy conservation of the nodes during active and sleep cycles and the
stability of the implemented solution in a continuous operational period.

The rest of this paper is organized as follows: Section II presents the
related work. Section III describes the principal components of a batteryless
IoT sensor node. Sections IV and V detail the energy consumption analysis and
implementation of the BLE and LIoT batteryless sensor nodes, respectively.
Section VI presents the experimental performance evaluation of our solution,
and Section VII concludes and outlines future work.

##  II Related work

Energy-efficient IoT devices for sensing have been widely investigated. For
instance, [3] designed a device using BLE, powered by a coin cell battery and
employing the all-in-one sensor BME280 (predecessor of current BME680) to
acquire and advertise environmental data. In the results, the authors
highlight the importance of performing an energy analysis in order to
determine the correct operation of the device in terms of battery lifetime.
Also, in [8], the authors proposed a BLE beacon powered by a light EHU and a
backup battery, capable of advertising air quality data every 60 seconds with
an optimized power management strategy. Despite the advancements, these
solutions still rely on batteries and broadcast the readings in a one-way
connection to the gateways. Different from previous works, [9] implemented a
BLE device for indoor home applications that transmits data every 95 seconds
and turns off when not operating. Furthermore, the work in [10] designed a
batteryless IoT node powered by an indoor solar panel that operates as a Low
Power Node (LPN) node in a BLE mesh network, where the node establishes bi-
directional communication with the gateway. The authors presented a comparison
between different capacitor sizes and harvesting powers and concluded that the
node shows a better performance with an optimal selection of the check
interval for energy-aware communications. Although, it is valid to point out
that BLE mesh may introduce delays in packet delivery due to data exchange
between LPN-Friend nodes. Therefore, not being appropriate for applications
that require high reliability. On this matter, [11] demonstrated that is
feasible to achieve highly reliable communications with BLE by implementing a
low-latency architecture for BLE monitoring systems.

On the other hand, in the context of LIoT communications, [5] proposed the
design of a full-duplex IoT node powered by an indoor solar panel that uses
organic Photovoltaic (PV) cells; with this, the authors demonstrated that
sustainable components could be successfully integrated into IoT devices. In
addition, our previous work [4] implemented a LIoT node in a SoC to transmit
environmental sensing data, powered by an indoor light sustainable EHU. The
results emphasized the relevance of employing SoCs given its many advantages,
such as low-power operation and fast data acquisition.

Despite the significant contribution highlighted in the previous works, the
reliability in batteryless IoT applications, such as monitoring networks,
still has ground to be improved. This motivates our work on reliable
batteryless sensors with bi-directional communication employing BLE and LIoT.

##  III Components of a Batteryless IoT Sensor Node

The block diagram in Fig. 1 presents the principal components of a batteryless
IoT device. The blocks illustrate the EHU, the different low-power sensors,
the low-power SoC and integrated circuits, and the communication technologies.
Next, we present a description of the main characteristics of each of these
components, focusing on enhancing the reliability of the batteryless IoT
sensor nodes.

Figure 1: Principal components of a batteryless IoT sensor node.

###  III-A Energy Harvesting and Storage System

One of the main components of the batteryless node design is the EHU, which
produces and supplies the energy to the system. The first step to be
considered is the selection of the EHU elements. Selecting organic PV cells
and PE circuits can play an important role in offering a sustainable solution
to harvest energy. Next, regarding efficient energy management, the Power
Management Unit (PMU) in the EHU needs to allow the use of the Harvest-
Storage-Use (HSU) approach to follow the “Expose and Connect” concept,
allowing the EHU to power the system immediately after it harvests enough
energy. This is possible with the Maximum Power Point Tracking (MPPT)
approach, which maintains the optimum light energy harvesting point while
transferring energy from the PV cell to a supercapacitor (SCap) as an energy
buffer. Precisely, the use of SCaps instead of batteries is justified by
several features, such as providing almost infinite charging cycles with high
charge-discharge efficiency $(97\%-98\%)$, high power density, and no heat
emission when draining [12].

###  III-B Low-Power ”All-in-one” Environmental Sensors

The condition of IAQ is closely related to the health state of indoor space
occupants, along with the measurement of both temperature and humidity. For
this reason, the selected sensor should be capable of measuring the principal
components related to IAQ, such as temperature, humidity, air pressure, gas,
and/or CO2 [3]. Specifically, gas detection is regulated by the ISO16000-29
standard ”Test methods for VOCs detectors.” VOCs include Isoprene, Ethane,
Acetone, Carbon Monoxide, and Ethanol, which are important to determining IAQ
in laboratories and office buildings. However, all these parameters should be
measured with the least energy consumption as possible. Thus, the sensor for
indoor environmental sensing applications should always follow the state-of-
the-art solution for ultra-low-power IoT applications.

###  III-C Low-power System-on-Chip

A SoC refers to an integrated circuit that unifies a variety of electronic
system peripherals, including memory, connections, and analog and digital
components, all on a single substrate, which is controlled by a
microprocessor. The SoC communication can be carried out through wired
interfaces like I2C, SPI, UART, and wireless technologies such as WiFi or BLE.
Hence, a SoC encapsulates all the necessary electronic components and circuits
for sensing, processing, and communication. One of the most popular solutions
is the ARM Cortex M series-based SoC, given its special design for
applications demanding low-power consumption [4].

###  III-D Reliable RF/Light Energy-Efficient Communication

Wireless RF communication protocols like Bluetooth and BLE, ZigBee, and Wi-Fi
are standard protocols for IoT sensor nodes. In particular, the BLE standard
is the preferred protocol for low-power short-range IoT applications given its
ultra-low-power characteristics when implemented in a SoC [13]. However, it is
essential to exploit alternatives to complement radio communications and
improve the reliability of batteryless IoT nodes. VLC is a prominent low-power
choice to complement short-range radio communications since it covers the
light spectrum from 380$\eta m$ to 780 $\eta m$, offering an alternative that
improves the total reliability of indoor short-range networks.

##  IV Energy Constraints for Continuous Batteryless Operation

The critical energy constraints when designing reliable batteryless IoT
devices with continuous operation are threefold, energy harvesting efficiency,
energy buffer capacity, and power consumption. Our design considers a constant
illumination scenario to guarantee continuous operation and sensor readings at
a fixed amount of time. Moreover, to achieve maximum sensing efficiency with
the available energy, our solution proposes a power management strategy based
on the periodic switching between active and sleep cycles.

The computation of the sleep and active cycles in the considered solution
relies on the energy consumption analysis of the IoT nodes. This analysis
employs the producer-consumer model for autonomous wireless devices presented
in [14]. The model considers all the energy sources and energy consumed by a
wireless IoT node, and based on the energy conservation principle, outlines
that the energy produced in a total operational time $T$ should be equal to or
greater than the energy consumed, which is described in the following
inequality:

$E_{buf}\\!+\\!\underbrace{\int_{0}^{T}\\!P_{harv}(\tau)d\tau}_{E_{harv}(T)}\geq\underbrace{\int_{0}^{T}\\!P_{dev}(\tau)d\tau}_{E_{dev}(T)},$
(1)

where $\tau$ is used as the variable of time, $E_{buf}$ represents the initial
energy in the buffer in Joules, $P_{harv}(\tau)$ is the harvested power for an
instant of time $\tau$ in Watts, and $P_{dev}(\tau)$ is the power consumed by
the device for an instant of time $\tau$ in Watts. In addition, $E_{harv}(T)$
and $E_{dev}(T)$ represent the energy harvested and consumed in Joules during
a complete duty cycle in $T$, respectively. $E_{buf}$ is the minimum amount of
energy needed to ensure that the node stays operational, and our goal is not
to go below it. Accordingly, a simplified version of the energy flow model is

$E_{harv}(T)\geq\\!E_{dev}(T),\forall T\in[0,\infty).$ (2)

In other words, at each duty cycle, we aim to harvest more energy than what
the node consumes for the active and sleep cycles. Therefore, the inequality
described in (2) models the energy of a wireless IoT device that is always
active. However, to show the energy produced during the sleep and active
cycles in our low-power management implementation, we split the duty cycle
time $T$ into the active and sleeping time, $T_{a}$ and $T_{s}$, being $T$ =
$T_{a}$ \+ $T_{s}$. Consequently, we divided the energy consumed by the
wireless node $E_{dev}(T)$ into the energy consumed during the active and
sleeping time, $E_{deva}(T_{a})$ and $E_{devs}(T_{s})$, being
$E_{dev}(T)=E_{deva}(T_{a})+E_{devs}(T_{s})$. Therefore, the energy
conservation of a batteryless IoT node with low-power management is modeled as

$E_{harv}(T_{a}+T_{s})\geq\\!E_{deva}(T_{a})+E_{devs}(T_{s}).$ (3)

The obtained model is applied to design and implement the BLE and LIoT nodes.
Specifically, it allows us to compute the correct sleeping period $T_{s}$ that
satisfies (3), enabling our proposed low-power management strategy for the
batteryless IoT nodes.

##  V Design of Reliable IoT Sensor Nodes

The design and implementation of the BLE and LIoT batteryless sensor nodes are
described in V-A and V-B, respectively. Both subsections presented next are
centered on three main parts: 1. Hardware and software; 2. Communication; 3.
Low-power operation.

###  V-A BLE IoT Environmental Sensor Node

The batteryless BLE IoT node periodically senses and transmits environmental
information such as VoCs for IAQ, air pressure, temperature, and humidity.
After being acquired, those measurements are transmitted to the gateway in a
bi-directional way, which indicates that during a connection, the gateway can
also send instructions to the IoT node.

####  V-A1 Hardware and software

The hardware structure of the BLE IoT node, described in the blocks of Fig. 2
is composed of the Epishine LEH3 EHU, the Bosch BME680 all-in-one sensor, and
the Seeed XIAO BLE board with an ARM-based nRF52840 SoC, which enables
Bluetooth 5.0 for wireless communication. The EHU consists of the e-Peas
AEM10941 with the MPPT feature and of a 400mF SCap CAP-XX GA230F used as an
energy buffer. A BME680 all-in-one low-power sensor is connected to the I2C
port of the SoC board. Regarding the software, the communication and low-power
algorithms are implemented over the manufacturer’s firmware. These algorithms,
based on open-source libraries, execute the sensor data acquisition and
process the obtained information in data array structures, which are
advertised as characteristics of the BLE Environmental Sensing Service (ESS).
The implemented processes are controlled by a timer-based scheduler that
coordinates and controls the node sleep and active cycles.

Figure 2: Hardware block structure of the BLE IoT node.

####  V-A2 Communication

The BLE IoT node enables low-power RF communication to the gateway through the
Bluetooth radio chip incorporated in the SoC. The data exchange process,
depicted in Fig. 3, starts when the BLE node advertises the ESS service
(Channels 37-39) for an interval of maximum 4s, with a transmission power of
4dBm. After the node’s connection, the gateway requests the ESS attributes
(Channels 0-36) that contain the sensor data. Finally, the node awaits a
message from the gateway with configurations or to end the connection and go
into the sleep cycle.

Figure 3: The BLE IoT node data exchange.

####  V-A3 Low-Power operation

To determine the optimal active and sleep cycles, we characterized the energy
consumption of the IoT device by measuring the current consumed in every stage
of the sensing and communication process. The current measurements for this
analysis are carried out with the Nordic Semiconductors PPK II power profiler
tool, which allows us to measure and log the current consumption at a maximum
rate of $10^{5}$ samples per second. Accordingly, the different current
consumption levels, in milliamperes, for every stage of the active and sleep
cycles are shown in the energy consumption profile in Fig.4. Along with the
current consumption, the figure also depicts the sleeping period, the sensor’s
data acquisition, and BLE advertising and data transmission.

Figure 4: BLE IoT node energy consumption profile.

The detailed energy profile of the BLE IoT node allows the computation of the
average current consumption for every stage of the active and sleep cycles.
Consequently, under an operational voltage of $3.3$V, and given the produced
current of the EHU, $E_{harv}(T_{a}+T_{s})$ can be determined for two
different illumination scenarios, with 500lx and 700lx. Next, with the
performed current measurements, we obtain the values for the energy consumed
by the devices in the active cycle $E_{deva}(T_{a})$ and sleep cycle
$E_{devs}(T_{s})$. Finally, replacing the energy variables in (3), as
described in subsection IV, the optimal value of the sleep cycle in seconds is
determined, for both illumination scenarios, as $T_{s}$$=$$12.842$ and
$T_{s}$$=$$20.520$, for 700lx and 500lx, respectively. These results enable
the node to send up to 1491 samples from all sensors in a total operational
period of 8 hours, considering an illumination of 700lx, and 1042 samples for
500lx. Table I summarizes the measured and computed current, time, and energy
for every stage of the BLE IoT node in both illumination scenarios.

TABLE I: BLE IoT Batteryless Node Energy Consumption Profile | Operation Stage | Current (mA) | Time (s) | Energy (J)
---|---|---|---|---
Active Cycle $E_{deva}$ | Sensors Reading | 7.550 | 0.260 | 0.0065
BLE Advertising | 0.310 | 4.000 | 0.0041
Data Exchange | 0.410 | 1.300 | 0.0018
Sleep Cycle $E_{devs}$ 700lx | 0.010 | 12.842 | 0.0004
Sleep Cycle $E_{devs}$ 500lx | 0.010 | 20.520 | 0.0007

###  V-B LIoT Environmental Sensor Node

Like the BLE node, the LIoT node also operates as an environmental sensor for
indoor infrastructures. The main difference between them is the communication
process. For the LIoT node, VLC is employed for downlink and IR for uplink,
establishing bi-directional communication with the gateway.

####  V-B1 Hardware and software

The first version of the LIoT node was introduced in detail in our previous
work [4]. For this current work, the LIoT node is also based on the Seed XIAO
SAMD21 board and powered by the Epishine LEH3 EHU. Additionally, we
incorporated the BME680 low-power sensor for sensing tasks since it adjusts
perfectly with the evaluated use cases. The IoT node also has an additional
transceiver unit for VLC/IR communication, and a Light-Dependent-Resistor
(LDR) to determine the indoor illumination. Based on the obtained
illumination, the node schedules the next sleep and active cycles. The LIoT
transceiver unit comprises a photodiode operating at 525$\eta m$ to receive a
downlink signal, an infrared light emitting diode TSAL6200 IRLED at 940$\eta
m$ for uplink, and the all-in Integrated Circuit (IC) VSOP38388 [4, 5]. The IC
converts the current to voltage and amplifies it with an Automatic Gain
Control (AGC). Finally, a band-pass filter with a 38kHz center frequency
filters the output signal. Both uplink and downlink signals are modulated at
38kHz carrier frequency with Pulse Position Modulation (PPM). Fig. 5 depicts
the components for the sensing and communication features of the implemented
LIoT node. Regarding the software, the implemented algorithms employ open-
source libraries alongside the manufacturer board’s firmware, handling the
transmission modulation/demodulation and sensor readings through a timer-based
scheduler.

Figure 5: Hardware block structure of the LIoT node.

####  V-B2 Communication

The communication process is carried out with the novel protocol depicted in
Fig.6. In our proposal, the LIoT node starts the data exchange by uploading
the node ID and the illumination value over IR to the gateway. After that, the
gateway requests the data from one or multiple sensors via VLC, and the LIoT
node sends the requested readings. Finally, the gateway determines and sends
the time value for the next sleep cycle, and receives the acknowledgment
packet before closing the connection.

Figure 6: The LIoT node data exchange.

####  V-B3 Low-Power operation

The energy consumption measurements are made in the same way as in the BLE IoT
node. The active and sleep cycles are calculated using the measured average
current when transmitting all sensor readings. Thus, following the process
detailed in IV, we determined the optimal sleep period in seconds for 700lx
and 500lx scenarios, being $T_{s}$$=$$620$ and $T_{s}$$=$$1350$, respectively.
These results enable the node to send up to 46 samples in a total operational
time of 8 hours at 700lx, and 21 samples for 500lx. The average current
consumption and times for the active and sleep cycles (when all the sensor
readings are requested) are detailed in Table II. In addition, Fig. 7 shows
the current consumed in the different sensing/communication stages of the
node. Compared to [4], we can observe that the active periods are longer due
to the amount of transmitted data.

Figure 7: LIoT node energy consumption profile. TABLE II: LIoT Batteryless Node Energy Consumption Profile | Operation Stage | Current (mA) | Time (s) | Energy (J)
---|---|---|---|---
Active Cycle | GW Request | 12.69 | 0.428 | 0.0179
Sensor Reading | 17.73 | 0.525 | 0.0307
Data Upload | 14.58 | 3.58 | 0.1722
Sleep Set | 9.81 | 0.078 | 0.0025
Sleep Cycle $E_{devs}$ 700lx | 0.087 | 620 | 0.1780
Sleep Cycle $E_{devs}$ 500lx | 0.087 | 1350 | 0.3876

##  VI Experimental Performance Evaluation

In order to validate the implemented BLE and LIoT nodes, and to test the
system stability, we conducted two experiments of eight hours each. We
consider an office environment with two levels of constant illumination, 700lx
$\pm$5% and 500lx $\pm$5%. In this scenario, the gateway is placed half a
meter from the LIoT node and three meters from the BLE IoT node. During the
experiments, the nodes’ current consumption and the SCap’s charge-discharge
voltage are measured to show the energy conservation during active and sleep
cycles.

In particular, for the BLE node, an additional 5% of time is included in the
duty cycle to compensate for temperature and humidity changes in the
environment. Finally, the timer-based scheduler of the BLE node starts a new
duty cycle every 19.3 and 26.7 seconds for 700lx and 500lx, respectively.

Fig. 8 shows the current consumed by the BLE IoT node (below) and the voltage
charge-discharge of the SCap (above) versus time for 700 and 500lx. Note that
for both illumination scenarios, the SCap experiments a discharge of 0.007V
during the active cycle and recovers during the sleep cycle, highlighting the
energy conservation principle for this implementation. Also, we can observe
that the recovery time is longer for the 500lx illumination scenario, which is
expected given the lower amount of energy harvested.

Figure 8: Energy conservation in the BLE IoT node.

The energy conservation in the LIoT node can be observed in Fig. 9. The LIoT
node can perform a complete sensor measurement every 624.6s at 700lx and
1354.6s at 500lx. Compared to the BLE IoT node, the measurements show a longer
duty cycle and higher current consumption, leading to a 0.17V discharge on the
SCap. This is because of the energy consumed by the external transceivers used
for transmission via IR and VLC. However, the performance of the LIoT node
satisfies the necessities for environmental sensing, establishing continuous
communication with the gateway and complementing the RF transmission of the
BLE IoT node.

Figure 9: Energy conservation in the LIoT node.

Table III summarizes the results obtained in the performed experiments. On
that, PDR stands for packet delivery rate, which corresponds to the ratio of
the successful duty cycles to the failed ones. In the case of BLE, a packet is
successfully delivered when the gateway receives the ESS attributes and closes
a connection, and for the LIoT, a packet is successfully delivered when all
the sensor readings are received and decoded by the gateway. The BLE node
achieved a PDR of 0.991 and 0.912 for the 700 and 500lx scenarios,
respectively. On the other hand, the LIoT node successfully delivered all the
sent packets, having a PDR of 1.000 for both scenarios.

TABLE III: Batteryless IoT Nodes’ Performance Evaluation (8 hours) Node | Illumination |  | Packets
---
Sent
| Packets
---
Received
PDR |  | Avg.
---
SCap (V)
BLE IoT | 700lx | 1491 | 1479 | 0.991 | 4.463
500lx | 1042 | 951 | 0.912 | 4.416
LIoT | 700lx | 46 | 46 | 1.000 | 4.235
500lx | 21 | 21 | 1.000 | 4.353

##  VII Conclusions and future work

In this work, we explored the design and implementation of BLE and LIoT
batteryless devices powered by an indoor light EHU. We analyzed the energy
consumption of the nodes and calculated the optimal sleep period for the
operation based on the energy harvested. The obtained results demonstrate the
feasibility of having an energy-autonomous operation of our proposed IoT node
designs under environments with two different light intensities. In
particular, our design guarantees the transmission of one packet (at 700lx)
every 19.3 and 624.6 seconds for the BLE and LIoT nodes, respectively,
satisfying the measurement frequency requirements for an environmental-sensing
use case. Moreover, our measurements showed that more than 90% of the packets
were successfully delivered for BLE and LIoT. Future research directions
include testing our solution in different scenarios and exploiting the
capacities of the SoC to process the acquired data for intelligent edge
decision-making.

## References

  * [1] H. Sallouha et al., “ulora: Ultra low-power, low-cost and open platform for the lora networks,” in Proceedings of the 4th ACM Workshop on Hot Topics in Wireless, pp. 43–47, 2017.
  * [2] M. Katz and I. Ahmed, “Opportunities and Challenges for Visible Light Communications in 6G,” in 2020 2nd 6G Wireless Summit (6G SUMMIT), pp. 1–5, 2020.
  * [3] T. Santejudean, S. Folea, and G. Mois, “Analysis of Low-Power Operation for an Environmental Monitoring Beacon,” 2020 22nd IEEE International Conference on Automation, Quality and Testing, Robotics - THETA, AQTR 2020 - Proceedings, 5 2020.
  * [4] K. Botirov et al., “Design and Implementation of a Sustainable Light-based IoT Node on a System-on-Chip,” 2nd Workshop on Green and Sustainable Networking, IEEE ICC, 2023.
  * [5] M. A. N. Perera et al., “Light-Based IoT: Developing a Full-Duplex Energy Autonomous IoT Node Using Printed Electronics Technology,” Sensors, vol. 21, no. 23, 2021.
  * [6] H. Abuella et al., “Hybrid RF/VLC Systems: A Comprehensive Survey on Network Topologies, Performance Analyses, Applications, and Future Directions,” IEEE Access, vol. 9, pp. 160402–160436, 2021.
  * [7] Z. Liu et al., “Multi-Points Indoor Air Quality Monitoring Based on Internet of Things,” IEEE Access, vol. 9, pp. 70479–70492, 2021.
  * [8] G. D. Moiş et al., “Performance Evaluation of Energy-Autonomous Sensors Using Power-Harvesting Beacons for Environmental Monitoring in Internet of Things (IoT),” Sensors 2018, Vol. 18, Page 1709, vol. 18, p. 1709, 5 2018.
  * [9] F. Fraternali et al., “Pible: Battery-Free Mote for Perpetual Indoor BLE Applications,” BuildSys 2018 - Proceedings of the 5th Conference on Systems for Built Environments, vol. 18, pp. 168–171, 11 2018.
  * [10] A. K. Sultania and J. Famaey, “Batteryless Bluetooth Low Energy Prototype With Energy-Aware Bidirectional Communication Powered by Ambient Light,” IEEE Sens. J., vol. 22, pp. 6685–6697, 4 2022.
  * [11] F. Battaglia et al., “EEG-Over-BLE: A Low-Latency, Reliable, and Low-Power Architecture for Multichannel EEG Monitoring Systems,” IEEE Trans. Instrum. Meas., vol. 72, pp. 1–10, 2023.
  * [12] U. Alvarado et al., “Energy harvesting technologies for low-power electronics,” Transactions on Emerging Telecommunications Technologies, vol. 23, no. 8, pp. 728–741, 2012.
  * [13] J.-S. Lee, Y.-W. Su, and C.-C. Shen, “A comparative study of wireless protocols: Bluetooth, UWB, ZigBee, and Wi-Fi,” IECON Proceedings (Industrial Electronics Conference), pp. 46 – 51, 12 2007.
  * [14] B. Martinez et al., “The Power of Models: Modeling Power Consumption for IoT Devices,” IEEE Sens. J., vol. 15, pp. 5777–5789, 10 2015.