# Robot Air Hockey: A Manipulation Testbed for Robot Learning with
Reinforcement Learning
††thanks: * denotes equal contribution. For corresponding author and code
requests contact<EMAIL_ADDRESS>
Caleb Chuck1,∗, Carl Qi1,∗, Michael J. Munje1,∗, Shuozhe Li1,∗, Max
Rudolph1,∗,
Chang Shi1,∗, Siddhant Agarwal1,∗, Harshit Sikchi1,∗, Abhinav Peri1, Sarthak
Dayal1,
Evan Kuo1, Kavan Mehta1, Anthony Wang1, Peter Stone1,3, Amy Zhang1, Scott
Niekum2

1 The University of Texas at Austin
2 University of Massachusetts Amherst
3 Sony AI

###### Abstract

Reinforcement Learning is a promising tool for learning complex policies even
in fast-moving and object-interactive domains where human teleoperation or
hard-coded policies might fail. To effectively reflect this challenging
category of tasks, we introduce a dynamic, interactive RL testbed based on
robot air hockey. By augmenting air hockey with a large family of tasks
ranging from easy tasks like reaching, to challenging ones like pushing a
block by hitting it with a puck, as well as goal-based and human-interactive
tasks, our testbed allows a varied assessment of RL capabilities. The robot
air hockey testbed also supports sim-to-real transfer with three domains: two
simulators of increasing fidelity and a real robot system. Using a dataset of
demonstration data gathered through two teleoperation systems: a virtualized
control environment, and human shadowing, we assess the testbed with behavior
cloning, offline RL, and RL from scratch.

###### Index Terms:

Reinforcement Learning, Dynamic robotic manipulation, Skill learning.

Figure 1: (a) Robot Air Hockey is a testbed that contains a large number of
dynamic, interactive Air Hockey tasks in multiple distinct simulators as well
as the real world. It is suitable for evaluating a variety of frameworks from
vanilla RL (both online and offline), learning from demonstrations, to skill
transfer or goal-conditioned RL. (b) Overview of our control pipeline. We use
object detection to get the state of interactive objects, and the UR5 RTDE
controller to transform the task actions into joint forces for the robot.

##  I Introduction

Reinforcement Learning (RL) offers a promising direction for real-world
robotics by allowing robotics to accomplish complex tasks using only a reward
description. Although high-performance demonstrations can sometimes be
collected through tools like teleoperation, it is not always feasible (and
often not possible) to collect large quantities of such “expert” data. Recent
developments in RL [1, 2, 3] offer ever-increasing generalization
capabilities, and improved learning algorithms through goal-conditioned RL [4,
5, 6] or unsupervised skill learning [7, 8, 9, 10, 11], as well as utilization
of human information such as preferences and offline demonstrations [12, 13,
14, 15, 16]. Suitable testbeds for assessing RL in the real world will help
scale RL to real-world robotics.

Real-world environments are challenging because they are often both dynamic
and interactive. For example, objects can roll about the table when cooking or
might fall when cleaning. The world is full of dynamic elements—state features
that are constantly moving. By contrast, quasistatic elements remain
predominantly stationary and only move when being operated on by the robot.
Furthermore, real-world tasks often require the agent to interact with its
environment, i.e. making contact with and even manipulating, elements such as
objects and other agents. In tasks that are both dynamic and interactive, RL
offers a promising direction since human demonstrators can often struggle with
precise, high-speed robot teleoperation, and hard-coded policies can be
brittle when taken out of a controlled context.

To evaluate RL in these settings, a testbed should support the complexity of
the real world while also allowing assessment of the variety of RL settings.
Reinforcement Learning research has introduced a wide gamut of tools, such as
goal-conditioning, model learning, task transfer, skill learning, offline, and
inverse reinforcement learning—to name just a few. While many of these tools
have been applied to simulated environments, even simulated robots, testing
these methods on a physical robot is challenging. Offering a single testbed
that supports these settings both in simulation and with a real-world system
would be an important step for the improved evaluation of RL in robotic
manipulation.

We introduce a novel dynamic, interactive RL testbed that modifies air hockey,
a popular game, with a collection of objects, Figure 1 illustrates some of the
potential of this domain. By focusing on puck-hitting, the domain is
inherently interactive and dynamic. This platform offers several advantages
that facilitate RL training. The puck’s constrained movement allows for
efficient environment resets, while a strictly controlled agent workspace
ensures safe autonomous operations when exploring. By incorporating multiple
objects, both virtual and real, we can describe a wide array of tasks,
illustrated in Figure 3, allowing for the assessment of goal-conditioned,
transfer, or skill learning methods. To evaluate RL without the physical setup
we provide two simulators, illustrated in Figure 1, of increasing fidelity to
the real world and tunable parameters so that sim-to-real transfer algorithms
can be assessed even without the physical system, by proxy of sim-to-sim
transfer. Furthermore, we introduce a human-teleoperated dataset using two
teleoperation systems for the agent which can be used in the simulators and
the real world, allowing the assessment of learning from demonstration and
offline RL algorithms (see Figure 2).

This work not only describes the domain and associated tasks but also assesses
several baseline algorithms and elucidates the key design decisions motivating
the algorithm. We also assess behavior cloning, vanilla RL, and offline RL on
several tasks in simulation and the real world. We demonstrate empirically
that the set of tasks developed has a smooth variation from easy to difficult
for all of these algorithms, both in simulation and the real world. Together,
this testbed provides a dynamic, interactive environment where existing
algorithms tested with other benchmarks could struggle. Algorithms assessed
with quasistatic elements that rely on the slow movement of the robot could be
exposed to the fast-moving dynamics, and those without interactive elements
could struggle to adapt to the sparse puck or object interactions. This
testbed offers a tool for assessing a wide range of RL algorithms on a similar
footing in a real-world setting.

Environment | Method | Robot Air Hockey Tasks
---|---|---
|  | Reach | Reach V. | Touch | Strike | Strike Crowd | Juggle | Puck V. | Block | Hit Goal | Hit Goal V.
Box2D [17] | BC | 0.9 | 0.8 | 1.0 | 0.7 | 0.3 | 0.3 | 0.7 | 0.0 | 0.1 | 0.0
IQL | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.0 | 0.4 | 0.0
RL | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.0 | 0.9 | 0.0
Robosuite [18] | BC | 0.9 | 0.8 | 0.8 | - | - | 0.6 | 0.6 | - | 0.1 | -
IQL | 0.9 | 0.9 | 0.8 | - | - | 0.7 | 0.8 | - | 0.1 | -
RL | 1.0 | 1.0 | 1.0 | - | - | 0.9 | 0.9 | - | 0.2 | -
Real World | BC | 0.9 | 0.1 | 0.3 | - | - | - | 0.1 | - | - | -
IQL | 1.0 | 0.0 | 0.6 | - | - | - | 0.3 | - | - | -
Human | 1.0 | 0.0 | 1.0 | - | - | 0.3 | 1.0 | - | - | -

TABLE I: Quantitative results for the Box2D, robosuite and real robot
environment. A dash (-) indicates that this combination of environment, method
and task was not evaluated. Simulation performances are averaged across 5
seeds. For Box2D, a combination of SAC/HER [19, 20] is used to train the goal-
conditioned RL policies, while PPO [21] is used to train RL policies for the
remaining tasks. For Robosuite, we use PPO for Vanilla RL, following the
implementation of CleanRL library [22]. In simulation, BC and IQL [23] are
used to learn policies offline using the “expert” data collected with trained
PPO policies. On the real robot, we instead use a teleoperated dataset
collected by 8 human players of varying skill of 400 trajectories for BC and
IQL.

##  II Related Works

Agile robots and tasks, distinguished by fast, dynamic motion, have seen
growing interest in the past several years. One instantiation of an agile
robotic task is autonomous air hockey and has been studied in several settings
[24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]. Notably, a recent workshop [35]
highlighted robot air hockey as a competitive robot learning task with several
submissions on model-based and deep learning methods [36, 37, 38].
Specifically, Liu et al.[24] used Bayesian optimization and a slew of other
well-tuned solvers to plan trajectories for striking the puck. While this
hand-crafted technique is successful, it is difficult to generalize across
small variations in air hockey table physical parameters and task
specifications. Most autonomous robotic air hockey systems focus on learning
to play competitive matches with humans. In contrast, our work focuses on a
variety of tasks, from goal conditioned puck hitting to puck juggling.
Furhter, we incorporate of human teleoperation modes to assess learning from
demonstration and other offline methods. The many works on robotic air hockey
cover a wide range of topics and are summarized here:

  1. 1.

Namiki et al [27] uses a hierarchical switching controller to play with
different behaviors according to the robot’s opponent.

  2. 2.

Owgawa et al [28] aims to generate motion plans that take advantage of weak
spots in a human’s vision when switching gaze.

  3. 3.

Bishop et al. [29] demonstrates the difficulty of building a vision-based
autonomous air-hockey system.

  4. 4.

AlAttar et al. [30] presents a state-model-based method to create air hockey-
playing agents against which humans can compete.

  5. 5.

Alizadeh et al. [31] introduces a method to estimate the parameters of air
hockey tables (e.g. coefficient of friction, etc.) automatically so that a
robot may adapt its behavior accordingly.

  6. 6.

Liu et al. [32] demonstrates a fast-hitting, air hockey-playing robot using
analytical controllers that were developed by modeling the air hockey
environment.

  7. 7.

Tadokoro et al. [33] design a high-speed wrist mechanism as an add-on to a
manipulator so that a robot can easily compete with the speed of a human air
hockey player.

  8. 8.

Huang et al. [34] introduces a method to align simulators with real-world
observations using causal relationships.

Robotic air hockey is an active field of research with a diverse set of
reliable solutions, most notably reinforcement learning. Our testbed is well-
positioned to act as a benchmark for learning agile manipulation skills.

##  III Domain Description

###  III-A Components

The common components across environments consist of the table, the paddle,
the pucks, moveable objects such as blocks, and immovable obstacles. A robot
arm is used in the Robosuite and real-world environments to control the
paddle. In the 2D simulator the paddle is manipulated directly. In all
domains, the table workspace is $66$ in $\times 24$ in, the paddle is $3.75$in
in diameter and the puck is $2.5$ in. We maintain consistency between the
domains to leave open the possibility of transfer.

###  III-B Teleoperation

####  III-B1 Mouse-Teleop

The mouse teleoperation setup streams a live video feed of the robot as seen
by the overhead camera after performing an orthographic tomography to
transform the camera coordinate system into the robot coordinate system in 2D.
The mouse $x,y$ position in the image is mapped to a desired robot $x,y$ pose,
using force control to maintain contact with the table. Desired positions are
then projected into the bounded action distances. This simple approach to
teleoperation allows us to easily collect data for various tasks.

Figure 2: Robot Air Hockey supports two types of teleoperations. Mouse-Teleop
(top): The user moves the mouse to control the robot. Shadow-Teleop (bottom):
the user moves a paddle to control the robot. Figure 3: Robot Air Hockey real-
world setup. We use a top-down camera to provide observation and a UR5e robot
to actuate the paddle. Our real-world setup can facilitate many air hockey
tasks, including but not limited to reaching, touching, and hitting.

####  III-B2 Shadow-Teleop

The shadowing setup consists of a flat surface, a paddle, and an above camera.
We utilize color segmentation to track the paddle movement on this surface and
transform these movements to end-effector locations on the robot. This
approach allows the user to play more naturally, as it is in direct control of
a paddle, while bounded by the capabilities of the robot.

###  III-C Environments

A common high-level interface is used for all environments, allowing the same
reward functions to be used across all individual environments. All
environments share a common state and action space.

####  III-C1 2D

Our 2D simulation environment uses the Python implementation of Box2D [17] as
a physics simulation backend. While we are not able to deploy robot arm models
in this environment, we use hand-tuned reward shaping so that sequences of
actions are empirically more realistic for a robot arm. This environment has
many changeable world parameters such as paddle mass, puck mass, dampening,
friction, gravity, starting puck velocities, and many more parameters.

####  III-C2 3D

Our 3D simulation environment is a custom Robosuite [18] setting which builds
on top of a MuJoCo [39] as a simulation backend and allows us to simulate the
robot arm in addition to the other components such as the table, a paddle, and
a puck. For control, the operational space controller [40] is available in
Robosuite, which we modify to maintain stable contact with the table.

####  III-C3 Real World

Our real-world setup consists of a 76in x 34in Wind Chill air hockey table
tilted $5.5$ degrees and a UR5e robot arm. The vision system uses a Sony
Playstation Eye, a high framerate camera, which gathers $640\times 480$ frames
at $60$ FPS, mounted to the ceiling to have a full view of the table. The
robot control operates at $20$ FPS, which is dictated by the cost of vision
processing and computing the desired action from the model while maintaining a
stable control loop. We use hue-saturation-value (HSV) segmentation and a
homography transformation using OpenCV [41] to estimate puck location and
velocity. We visualize puck detection in Figure 10. We use force and operation
space control on the robot to maintain the contact between the paddle and the
table. A picture of our workspace and tasks is described in Fig 3. The control
flow is illustrated in Figure 1b.

###  III-D Tasks

We provide a collection of ten total tasks which vary in difficulty from those
that can be achieved through behavior cloning (reaching) to those where even
humans can struggle in the real world (juggling). Each task includes a
designed reward function, and some can include additional objects beyond the
puck and the end effector, such as target regions or other objects to be
manipulated through the puck. We have five tasks on the real robot, six tasks
in Robosuite, and ten tasks in Box2D. The wide variety of tasks allows us not
only to assess varying difficulty but also leaves room for potential skill
learning and transfer learning.

Below we describe the ten tasks we assessed in this work. In addition to the
reward specified by the task itself, we also provided regularization to ensure
that undesirable behaviors such as jittering and twisting motion, which can
cause the robot to emergency stop (a safety measure on the UR5 that prevents
it from damaging itself or the human), were prevented.

  1. 1.

Reaching: The paddle reaches a random location. When the paddle is within
$\epsilon$ of the goal, the agent receives a positive reward and the episode
is reset.

  2. 2.

Reaching with Velocity: The paddle reaches a random location and velocity
combination. When the paddle is within
$\epsilon_{\text{position}},\epsilon_{\text{velocity}}$ of the goal (both
position and velocity) a reward is given, and the episode is reset.

  3. 3.

Touching: The paddle touches the puck. Upon detection of contact, a reward is
given. The agent is continually rewarded each time it touches the puck.

  4. 4.

Striking a stationary puck: The paddle hits a stationary puck and moves it a
minimum distance. If a sufficient velocity is achieved, a reward is given and
the episode ends.

  5. 5.

Striking a stationary puck into a crowd: The paddle hits a stationary puck
which causes it to collide with blocks, similar to the game of pool. The
reward is dependent on the amount of spread from the blocks from the crowd.

  6. 6.

Juggling: The paddle hits a puck a minimum distance above the paddle at the
time of hitting.

  7. 7.

Puck Velocity: The paddle hits a puck and causes it to move at a minimum
upward velocity.

  8. 8.

Moving a block: The paddles hits a puck into a block, causing it to move a
minimum distance from the block’s initial position.

  9. 9.

Hitting into a goal region: The paddle hits a puck into a goal circle region
with a constant radius.

  10. 10.

Hitting into a goal region with desired velocity: The paddle hits a puck into
a goal circle region with a constant radius with a specified velocity. It is
rewarded based on distance to the goal region’s center, cosine similarity
between the puck’s vector when entering the goal region, and difference in the
puck’s magnitude from the desired velocity’s magnitude.

While not a task we trained models for in this work, our Box2D simulation
environment also supports both collaborative play and adversarial play,
extending these environments as a potential testbed for multi-agent RL.
Furthermore, additional tasks with increasing complexity can be easily
constructed.

###  III-E Offline Data

On the real robot, we provide a dataset of human gameplay using both
teleoperation methods ($350$ mouse-teleop trajectories and $50$ shadow-teleop
trajectories) gathered from 8 participants of varying skill. We visualize some
of the human-gathered demonstrations in Figure 5 and Figure 10. In these, it
is clear that the human demonstrators, while able to hit the puck at least
once, can struggle to achieve multiple hits. In Table I, we assess successful
juggling as hitting the puck at least four times in a trajectory, and we can
see that humans only achieve moderate success. We discuss real-world data
collection and visualize human-gathered policies in Figure 5 and Appendix
VII-C.

##  IV Learning Methods

In our experiments, we evaluate three representative methods: Behavior cloning
(mean squared error loss), Vanilla Reinforcement Learning (SAC [19] and PPO
[21]), and Offline Reinforcement Learning (IQL [23]). Behavior cloning learns
a policy to take desired actions, Reinforcement learning maximizes discounted
reward, and offline RL assumes environment interactions are not available to
the agent.

###  IV-A Preliminaries

A Markov decision process is defined by the tuple
$\mathcal{M}\coloneqq(\mathcal{S},\mathcal{A},p,R)$, where $\mathcal{S}$ is
the state space, $\mathcal{A}$ is the action space and
$s\in\mathcal{S},a\in\mathcal{A}$ are states and actions respectively.
$p(s^{\prime}|s,a)$ is the transition function that gives the probability of
the next state $s^{\prime}$ given the current state and action $(s,a)$. The
reward function $R(s,a)$ maps state and action to a scalar reward. A policy
$\pi(a|s)$ is the probability of an action given the current state.

###  IV-B Behavior Cloning

Behavior cloning [42] is an offline imitation learning approach that learns a
policy using supervised learning. We use the common MSE loss to learn $\pi$:

$\mathcal{L}_{\text{bc}}=\mathbb{E}_{(a,s)\sim\mathcal{D}}[\|\pi(s)-a\|^{2}_{2}].$

Although the performance of behavior cloning is limited by the quality of the
dataset and is plagued by compounding error problems in the limited data
regime, it presents a simple and scalable alternative [12, 43] to the more
complicated yet unstable imitation learning methods [44, 14, 45].

###  IV-C Reinforcement Learning

The goal of Reinforcement Learning is to learn a policy maximizing returns
obtained on any user-specified reward function. Formally, RL aims to learn a
policy $\pi$ that maximizes the cumulative return
$J(\pi)=\mathbb{E}_{\pi}[\sum_{t=0}^{\infty}\gamma_{t}r(s_{t},a_{t}))]$. RL
reduces the effort of designing hand-tuned controllers by proposing general
approaches that learn any behaviors.

Online RL: In our work, we rely on Proximal Policy Optimization (PPO) [21] as
our baseline algorithm. PPO has been extensively used in robotics for its
stability and guarantee of near-monotonic improvement.

Offline RL: Offline RL deals with a specific setting where environment
interactions are not available to the agent, but rather the agent is provided
with data of offline transitions of the form {s,a,r,s’} from the environment.
This setting reduces the burden of exploration considerably and provides a
safe way to learn from previously collected datasets. Offline deep RL
algorithms suffer optimization difficulties due to problems like
overestimation [46], and feature-coadaptation [47] leading to popular
regularizers like pessimism [48, 49, 15]. We use a representative and
performant algorithms for offline RL in this work - IQL [23]. IQL is a
modification on the standard actor-critic learning procedure to replace the
maximization of the state-action value function with a maximization that only
chooses values for actions seen in the dataset.

For all of our experiments, our policies are represented with multi-layer
perceptions with a hidden layer of 256. Further training details are described
in Appendix VII-B.

##  V Experimental Results

In this section, we briefly describe the results of running various learning
algorithms in the three domains. Overall, online RL performs the best among
the baselines in simulation, showing that online interactions are crucial for
solving our dynamic tasks. In the real world, all of our baselines fall short
to human performance, leaving room for potential improvements for future work.
To assess qualitative results, we include several figures in the Appendix
illustrating the robot behavior in Box2D (Figure 4), Robosuite (Figure 6) and
the real world (Figure 5). We also discuss training curves in Appendix VII-B.

###  V-A Behavior Cloning Results

In the real world, using the dataset of approximately 128,000 frames of human-
generated striking behavior gathered through two teleoperation systems, we
train a network that maps puck and proprioceptive state information to
actions. Because humans can struggle to hit using teleoperation, the learned
models likewise struggle, while also being hampered by distribution mismatch.
In the real world, we also experimented with an image-based policy using a
ResNet-18 In the simulated domains, we behavior clone using 1M time steps from
high-performing policies: if the RL policy performs well on a task, we
behavior clone these policies for that task. If it does not, we use hindsight
relabelling to retarget goals from a different task that does have high
performance and use that.

###  V-B Vanilla RL Results

We assess Vanilla RL in simulation providing sufficient reward shaping to
ensure that the agents can perform well, and find good performance in both
simulators, as seen in Table I. In this table, we also describe the specific
RL algorithms we employ. This provides evidence to validate the hypothesis
that RL is an ideal choice in dynamic, interactive tasks where behavior
cloning might struggle to utilize the nuanced distinctions in capabilities. In
the real world, however, the random exploration necessary for RL from scratch
prevents the robot from gathering enough meaningful feedback without wearing
down the robot.

###  V-C Offline RL Results

Offline RL offers a mechanism for utilizing data collected offline from the
agent, such as our teleoperation dataset, to learn a policy. For offline RL,
we use IQL [23]. Because Offline RL does not generate its own environment
interactions, though, it can struggle more with distribution mismatch.
However, this does allow us to assess Offline RL in the real world, where
reward in dynamic, complex tasks outperforms behavior cloning.

##  VI Conclusion

We introduce an air-hockey-based evaluation domain for RL to evaluate RL in
dynamic interactive environments. We provide the initial set of evaluations
that support the hypothesis that in these kinds of domains, RL can outperform
imitation learning in a real-world robotics setting. Most importantly, the
suite of tasks, simulators, and collected human data opens the door for
assessing a wide variety of RL settings from goal-conditioned RL to
unsupervised skill learning to sim-to-real transfer, which we explore more in
Appendix VII-A. Videos describing the project, of learned policies and human
data can be found at RLAirHockey.github.io.

##  VII Appendix

###  VII-A Future Work And Relation with Manipulation Skills

####  VII-A1 Roadmap for Manipulation Skills

Robot manipulation has made tremendous progress in recent years. By creating
Robot Air Hockey, we aim to push the robot manipulation research frontier in
two major ways.

First, we explore the setting of dynamic object manipulation, which is
understudied in the real world relative to quasistatic object manipulation
because of many challenges. Compared to other dynamic robotics tasks (e.g.
learning quadrupedal policies), it can be difficult to collect data for
dynamic manipulation. Mainly, the low latency requirements and frequent (often
human) resets required in these tasks bottleneck data’s quality and quantity.
We hope that our system serves as a potential testbed and provides insights
for future works where we address some of these challenges. Some of the
insights we observed from creating a dynamic manipulation system are: 1)
maintaining low latency is challenging, and 2) playing at a relatively high
frame rate—20Hz or 50ms, even humans can struggle. We hope to follow up with
experiments investigating human capabilities across different modalities of
teleoperation. Furthermore, one of the most significant hurdles is the robot
emergency-stopping, either because a learned policy takes cyclic actions that
result in damaging resonant behavior, or because the robot jerks too quickly
when changing direction, making the robot exceed its acceleration limits.
Further investigation into action smoothing could provide higher-quality human
demonstration data and offline policies.

Furthermore, recent work in robot learning has mostly focused on learning from
demonstrations, where the data provided are usually optimal trajectories from
humans or internet-scale data used to train representations. This optimality
assumption is safe in quasistatic or low interaction environments, but in
dynamic object manipulation, human teleoperators can lack the skill necessary
to provide high-quality demonstrations. Robot air hockey considers one type of
data that is relatively understudied: in-domain low-reward interaction data.
Currently, we have collected robot data via teleoperation, and we are also
planning to collect robot interaction data autonomously soon. As a result,
this will open up avenues for many algorithms that are not limited to learning
from demonstrations. For instance, our system allows us to assess RL
algorithms and offers the opportunity to assess many forms of RL, such as
goal-conditioned, offline or sim-to-real methods, to name a few. Because of
the suboptimality of demonstration data, RL is an ideal tool for this setting,
as suggested by the results in this work where offline RL outperforms other
learning methods such as behavior cloning. Since related work assessing RL
directly on a physical robot, especially in a dynamic manipulation setting, is
limited, this work offers offline RL assessment in a dynamic, interactive
real-world set of tasks.

Our roadmap for future robot manipulation research is to learn from suboptimal
interaction data and solve dynamic manipulation tasks in the real world.
Current approaches have achieved incredible performance in quasistatic
manipulation tasks, thanks to their abilities to harness optimal demonstration
data and understand the task dynamics. However, doing so for dynamic
manipulation is much more difficult. Although the scale of large models and
datasets increases, in-domain data for dynamic tasks is still hard to collect.
Even if one can collect in-domain data for these tasks, collecting optimal
data is difficult, let alone deriving an accurate dynamics model for the task.
Therefore, we believe this system is a powerful potential testbed for applying
RL in the real world where we envision achieving super-human level performance
on challenging, dynamic manipulation tasks.

####  VII-A2 Future Work

Perhaps the most obvious setting for RL in air hockey is goal-conditioned RL.
The inverted table is inherently goal-conditioned in the sense of striking the
puck to a desired position, and one of the most challenging of our existing
tasks is striking the puck to a desired position with a desired velocity.
However, many more goal-conditioned settings exist, including using the puck
to hit an object to a location, achieving a sequence of goals for the end
effector, or getting the puck into a desired goal state relative to other
objects.

Another clear setting for future RL assessment of the robot air hockey
testbed, considering the multiple simulation environments of increasing
fidelity, is to utilize offline data generated by a higher fidelity simulator
to train policies using another simulator [50]. Sim-to-real transfer can be
iterated on quickly through 2D-to-3D sim-to-sim transfer and then tested on
3D-to-real transfer. Similarly, model-based RL can utilize the simpler
simulated environment models and transfer to model more complex real-world
dynamics, especially using the offline data.

Another consequence of the paired simulators is to provide a natural
curriculum for curriculum learning. Within single tasks, depending on the
initialization of target objects tasks can range from easy to hard, as well as
between simulators. Also, because many of the tasks are derivative of each
other, this leaves the room open for transfer learning or meta-learning, where
learning on some tasks will benefit downstream learning. As an extension,
unsupervised learning or skill learning make a lot of sense in many of the
environments since certain strikes and hits will be useful across multiple
tasks. While hard-coding these behaviors would be challenging, learning them
from the offline dataset or from experience could allow agents to perform
complex behaviors like hitting a target block to a desired location.

The air hockey setting itself offers possibilities for object-based
factorization. While this work only provided a few additional objects beyond
the puck and paddle, a wider variety of objects are actively being
incorporated to investigate object-based generalization algorithms. For
example, adding in target objects to push, obstacles for the puck, negative or
positive reward regions, or even regions of different physics are all
possible. Furthermore, by modifying real-world parameters such as table angle
or paddle shape, we can assess causal or model-based RL. Finally, especially
as more objects are added, visual complexity opens the door for more complex
object detection than simple color segmentation.

With many manipulation tasks focusing on tasks that can often be performed
with high precision for human demonstrators, such as pick-and-place, this
system offers the opportunity for superhuman performance, especially on even
more challenging tasks, such as two-puck juggling. RL is an ideal tool for
this setting, as suggested by the results in this work, but RL directly on the
robot is limited.

While the existing system shows a wide range of capabilities, the real-world
system illuminates several insights about running learned policies in a high-
speed setting. In particular, maintaining high latency is challenging, and we
found that even humans playing at 20Hz can struggle. We hope to follow up with
experiments investigating human capabilities in teleoperation. Furthermore,
one of the most significant hurdles is the robot emergency-stopping, either
because a learned policy takes cyclic actions that result in damaging resonant
behavior, or because the robot jerks too quickly when changing direction.
Further investigation into action smoothing could provide higher-quality human
demonstration data and offline policies.

As an immediate direction, the air hockey testbed offers offline RL assessment
in a dynamic, interactive real-world set of tasks. The initial results suggest
that RL is preferable because of the difficulty of gathering high-quality
demonstrations, and further investigation into offline and mixed offline and
online methods can provide substantial benefits.

We are looking into multi-agent settings. Air hockey is itself an adversarial
game. Beyond this, simulators can be modified to include collaborative
settings such as rallying the puck between multiple paddles or multiple puck
juggling with multiple paddles. Furthermore, we can extend the adversarial
setting to more than two goal regions and opposing paddles in a free for all.
On the physical robot, by incorporating an additional UR5 at the opposite end
of the table, we can realize some of these settings. Alternatively, while
humans far outstrip the physical capabilities of the UR5, adversarial play can
be between two humans playing against each other through the robot.

Finally, the teleoperation systems offer several means of assessing human-
robot interaction. Some possible directions for this include simple
assessments of human skill levels over play on the robot or frustrations with
robot capabilities, to more complex assessments of humans being able to detect
or react to another human playing, or a learned policy.

In summation, we believe that the robot air hockey testbed offers ample
opportunities to assess a significant range of RL capabilities across multiple
domains. While there are certainly limitations, a shared interface can
facilitate proof of concept work.

Figure 4: Execution rollouts in Box2D for various tasks. For each first frame
the motion of the puck is downwards. Top row: The task where the policy tries
to hit the puck to reach a minimum amount of upward velocity. Middle row: The
task where the policy hits the puck into a crowd of blocks, causes them to
spread. Bottom row: The task where the policy moves a puck into a goal region,
shown as a green circle. Figure 5: Execution rollouts on the UR5 air hockey
setup for policies trained with behavior cloning, IQL with the touching loss,
and human teleoperation demonstrations. Notice that even though humans are
trying to achieve multiple bounces, they often hit the puck too erratically to
effectively return, so demonstrations can vary significantly in skill, even
after cleaning human failure modes. Figure 6: Execution rollouts in Robosuite
simulator. The puck is circled in red for emphasis. Policies are trying to
touch the puck, hit the puck with a minimum upward velocity, and juggle the
puck.

###  VII-B Training Curves

We illustrate the training curves as normalized reward over the number of
timesteps for Box2D (Figure 7), success rate over 15 episodes over the number
of training timesteps for Robosuite (Figure 8), mean squared error for
behavior cloning on the real robot, and actor loss for IQL over number of
iterations of training (Figure 9). The real robot uses different losses
because we do not evaluate during training, as that would require loading
partial networks onto the real robot, which would greatly extend training
time.

Figure 7: Training curve for all tasks in Box2D. For vanilla RL tasks, the
rewards are averaged across 5 seeds, while for goal-conditioned RL we use 1
seed. Rewards are then normalized to to the [0, 1] range with respect to the
minimum and maximum reward seen for each task. Tasks in which performance
converges quickly indicate that the task is either trivially easy (reaching a
position with the paddle, reaching a position with the paddle with a desired
velocity) or too difficult (moving a block, hitting a puck into a goal
position with desired velocity).

(a)

(b)

(c)

Figure 8: Robosuite Training curves. (a): Vanilla RL with PPO, following the
implementation of CleanRL library [22]. (b) Behavior Cloning with data
collected the ”expert” policy (a trained PPO policy). (c) IQL [23] using the
same offline data, using asymmetric $\tau$ set to 0.6. Figure 9: Loss (MSE of
behavior cloning and Actor Loss for IQL) curves for training using data
collected from the real robot. Since humans did not distinguish puck velocity
and juggling, we only trained a single behavior cloning policy (BC Juggle).

###  VII-C Puck Hitting dataset

This section will describe how we extract the state of the puck on the table
from the collected videos and show exemplary trajectories from our dataset. We
collected videos of several participants attempting to hit the puck after
being dropped from the far end of the table using the various teleoperation
modalities.

Puck state extraction. We use red or green pucks because they are the easiest
to locate on the air hockey table using HSV color segmentation. To find the
location of the puck on the air hockey table, we first apply a homography
transformation to the image to account for the distortions introduced by the
camera. We then apply a mask to each frame that indicates whether a pixel
falls within the color bounds for the red or green puck. Lastly, we find the
median pixel location of all the masked pixels and apply an affine transform
that maps from the pixel location in the image to the robot base’s reference
frame. Puck trajectories In Figure 10, we illustrate the extracted
trajectories from shadow-teleop and mouse-teleop. Gaps in the puck’s
trajectory indicate where the puck was not detected, for example, if it was
occluded by the robot.

(a) Stacked images representing the video of a trajectory collected with
Shadow-teleop

(b) Extracted state trajectory of puck data collected with Shadow-teleop

(c) Stacked images representing the video of a trajectory collected with
Mouse-teleop

(d) Extracted state trajectory of puck data collected with Mouse-teleop

Figure 10: Puck-hitting trajectories collected with teleoperation modalities.
Generally, mouse-teleop is more responsive, and thus participants could strike
the puck more easily. Nonetheless, participant skill was the primary factor
when assessing the quality of a gathered trajectory.

## References

  * [1] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel _et al._ , “Mastering atari, go, chess and shogi by planning with a learned model,” _Nature_ , vol. 588, no. 7839, pp. 604–609, 2020.
  * [2] A. Brohan, N. Brown, J. Carbajal, Y. Chebotar, X. Chen, K. Choromanski, T. Ding, D. Driess, A. Dubey, C. Finn _et al._ , “Rt-2: Vision-language-action models transfer web knowledge to robotic control,” _arXiv preprint arXiv:2307.15818_ , 2023.
  * [3] O. M. Team, D. Ghosh, H. Walke, K. Pertsch, K. Black, O. Mees, S. Dasari, J. Hejna, C. Xu, J. Luo _et al._ , “Octo: An open-source generalist robot policy,” 2023.
  * [4] Y. Chebotar, K. Hausman, Y. Lu, T. Xiao, D. Kalashnikov, J. Varley, A. Irpan, B. Eysenbach, R. Julian, C. Finn _et al._ , “Actionable models: Unsupervised offline reinforcement learning of robotic skills,” _arXiv preprint arXiv:2104.07749_ , 2021.
  * [5] H. Sikchi, R. Chitnis, A. Touati, A. Geramifard, A. Zhang, and S. Niekum, “Score models for offline goal-conditioned reinforcement learning,” _arXiv preprint arXiv:2311.02013_ , 2023.
  * [6] B. Eysenbach, S. Levine, and R. R. Salakhutdinov, “Replacing rewards with examples: Example-based policy search via recursive classification,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 11 541–11 552, 2021.
  * [7] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine, “Diversity is all you need: Learning skills without a reward function,” _arXiv preprint arXiv:1802.06070_ , 2018.
  * [8] S. Park, O. Rybkin, and S. Levine, “Metra: Scalable unsupervised rl with metric-aware abstraction,” _arXiv preprint arXiv:2310.08887_ , 2023.
  * [9] T. Zahavy, Y. Schroecker, F. Behbahani, K. Baumli, S. Flennerhag, S. Hou, and S. Singh, “Discovering policies with domino: Diversity optimization maintaining near optimality,” _arXiv preprint arXiv:2205.13521_ , 2022.
  * [10] C. Chuck, K. Black, A. Arjun, Y. Zhu, and S. Niekum, “Granger-causal hierarchical skill discovery,” _arXiv preprint arXiv:2306.09509_ , 2023.
  * [11] C. Chuck, S. Chockchowwat, and S. Niekum, “Hypothesis-driven skill discovery for hierarchical deep reinforcement learning,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 5572–5579.
  * [12] M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, C. Fu, K. Gopalakrishnan, K. Hausman _et al._ , “Do as i can, not as i say: Grounding language in robotic affordances,” _arXiv preprint arXiv:2204.01691_ , 2022.
  * [13] J. Hejna, R. Rafailov, H. Sikchi, C. Finn, S. Niekum, W. B. Knox, and D. Sadigh, “Contrastive prefence learning: Learning from human feedback without rl,” _arXiv preprint arXiv:2310.13639_ , 2023.
  * [14] H. Sikchi, A. Saran, W. Goo, and S. Niekum, “A ranking game for imitation learning,” _arXiv preprint arXiv:2202.03481_ , 2022.
  * [15] H. Sikchi, Q. Zheng, A. Zhang, and S. Niekum, “Dual rl: Unification and new methods for reinforcement and imitation learning,” _arXiv preprint arXiv:2302.08560_ , 2023.
  * [16] T. Ni, H. Sikchi, Y. Wang, T. Gupta, L. Lee, and B. Eysenbach, “f-irl: Inverse reinforcement learning via state marginal matching,” in _Conference on Robot Learning_. PMLR, 2021, pp. 529–551.
  * [17] E. Catto. [Online]. Available: https://box2d.org/
  * [18] Y. Zhu, J. Wong, A. Mandlekar, R. Martín-Martín, A. Joshi, S. Nasiriany, and Y. Zhu, “robosuite: A modular simulation framework and benchmark for robot learning,” _arXiv preprint arXiv:2009.12293_ , 2020.
  * [19] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” in _International conference on machine learning_. PMLR, 2018, pp. 1861–1870.
  * [20] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. Pieter Abbeel, and W. Zaremba, “Hindsight experience replay,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [21] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017.
  * [22] S. Huang, R. F. J. Dossa, C. Ye, J. Braga, D. Chakraborty, K. Mehta, and J. G. Araújo, “Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms,” _Journal of Machine Learning Research_ , vol. 23, no. 274, pp. 1–18, 2022. [Online]. Available: http://jmlr.org/papers/v23/21-1342.html
  * [23] I. Kostrikov, A. Nair, and S. Levine, “Offline reinforcement learning with implicit q-learning,” _arXiv_ , 2021.
  * [24] P. Liu, D. Tateo, H. Bou-Ammar, and J. Peters, “Efficient and reactive planning for high speed robot air hockey,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 586–593.
  * [25] A. Taitler and N. Shimkin, “Learning control for air hockey striking using deep reinforcement learning,” 2017.
  * [26] J. Jankowski, A. Marić, and S. Calinon, “Airlihockey: Highly reactive contact control and stochastic optimal shooting,” 2024.
  * [27] A. Namiki, S. Matsushita, T. Ozeki, and K. Nonami, “Hierarchical processing architecture for an air-hockey robot system,” in _2013 IEEE International Conference on Robotics and Automation_ , 2013, pp. 1187–1192.
  * [28] M. Ogawa, S. Shimizu, T. Kadogawa, T. Hashizume, S. Kudoh, T. Suehiro, Y. Sato, and K. Ikeuchi, “Development of air hockey robot improving with the human players,” in _IECON 2011 - 37th Annual Conference of the IEEE Industrial Electronics Society_ , 2011, pp. 3364–3369.
  * [29] B. Bishop and M. Spong, “Vision-based control of an air hockey playing robot,” _IEEE Control Systems Magazine_ , vol. 19, no. 3, pp. 23–32, 1999.
  * [30] A. AlAttar, L. Rouillard, and P. Kormushev, “Autonomous air-hockey playing cobot using optimal control and vision-based bayesian tracking,” in _Towards Autonomous Robotic Systems_ , K. Althoefer, J. Konstantinova, and K. Zhang, Eds. Cham: Springer International Publishing, 2019, pp. 358–369.
  * [31] H. Alizadeh, H. Moradi, and M. N. Ahmadabadi, “Automatic calibration of an air hockey robot,” in _2013 First RSI/ISM International Conference on Robotics and Mechatronics (ICRoM)_ , 2013, pp. 107–112.
  * [32] P. Liu, D. Tateo, H. Bou-Ammar, and J. Peters, “Efficient and reactive planning for high speed robot air hockey,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 586–593.
  * [33] K. Tadokoro, S. Fukuda, and A. Namiki, “Development of air hockey robot with high-speed vision and high-speed wrist,” _Journal of Robotics and Mechatronics_ , vol. 34, no. 5, pp. 956–964, 2022.
  * [34] P. Huang, X. Zhang, Z. Cao, S. Liu, M. Xu, W. Ding, J. Francis, B. Chen, and D. Zhao, “What went wrong? closing the sim-to-real gap via differentiable causal discovery,” in _Proceedings of The 7th Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, J. Tan, M. Toussaint, and K. Darvish, Eds., vol. 229. PMLR, 06–09 Nov 2023, pp. 734–760. [Online]. Available: https://proceedings.mlr.press/v229/huang23c.html
  * [35] “Robot air hockey challenge 2023,” https://air-hockey-challenge.robot-learning.net/home, accessed: 2024-03-28.
  * [36] A. Orsula, “Learning to play air hockey with model-based deep reinforcement learning,” _Air Hockey Challenge at Advances in neural information processing systems_ , 2023.
  * [37] M. E. B. V. de Bakker3Atalay, D. Ö. E. Yagmurlu, M. F. Z. J. D. Yang, H. Zhou, X. Jia, O. Celik, F. Otto, R. Lioutikov, and G. Neumann, “Air hockey challenge 2023: Air-hockit team report,” _Air Hockey Challenge at Advances in neural information processing systems_ , 2023.
  * [38] F. Minnucci, “Applying rule-based controllers and reinforcement learning to control a general purpose robot: the air hockey challenge case,” _Air Hockey Challenge at Advances in neural information processing systems_ , 2023.
  * [39] E. Todorov, T. Erez, and Y. Tassa, “Mujoco: A physics engine for model-based control,” in _2012 IEEE/RSJ international conference on intelligent robots and systems_. IEEE, 2012, pp. 5026–5033.
  * [40] O. Khatib, “A unified approach for motion and force control of robot manipulators: The operational space formulation,” _IEEE Journal on Robotics and Automation_ , vol. 3, no. 1, pp. 43–53, 1987.
  * [41] G. Bradski, “The OpenCV Library,” _Dr. Dobb’s Journal of Software Tools_ , 2000.
  * [42] D. A. Pomerleau, “Efficient training of artificial neural networks for autonomous navigation,” _Neural computation_ , vol. 3, no. 1, pp. 88–97, 1991.
  * [43] E. Jang, A. Irpan, M. Khansari, D. Kappler, F. Ebert, C. Lynch, S. Levine, and C. Finn, “Bc-z: Zero-shot task generalization with robotic imitation learning,” in _Conference on Robot Learning_. PMLR, 2022, pp. 991–1002.
  * [44] J. Ho and S. Ermon, “Generative adversarial imitation learning,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [45] S. K. S. Ghasemipour, R. Zemel, and S. Gu, “A divergence minimization perspective on imitation learning methods,” in _Conference on robot learning_. PMLR, 2020, pp. 1259–1277.
  * [46] S. Fujimoto, D. Meger, and D. Precup, “Off-policy deep reinforcement learning without exploration. corr abs/1812.02900 (2018),” _arXiv preprint arXiv:1812.02900_ , 2018.
  * [47] A. Kumar, R. Agarwal, T. Ma, A. Courville, G. Tucker, and S. Levine, “Dr3: Value-based deep reinforcement learning requires explicit regularization,” _arXiv preprint arXiv:2112.04716_ , 2021.
  * [48] S. Fujimoto and S. S. Gu, “A minimalist approach to offline reinforcement learning,” in _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * [49] S. Levine, A. Kumar, G. Tucker, and J. Fu, “Offline reinforcement learning: Tutorial, review, and perspectives on open problems,” _arXiv preprint arXiv:2005.01643_ , 2020.
  * [50] J. P. Hanna, S. Desai, H. Karnan, G. Warnell, and P. Stone, “Grounded action transformation for sim-to-real reinforcement learning,” _Machine Learning_ , vol. 110, no. 9, pp. 2469–2499, 2021.


# Fast Private Location-based Information Retrieval over the Torus

Joon Soo Yoo1, Mi Yeon Hong1, Ji Won Heo2, Kang Hoon Lee1, Ji Won Yoon1
1School of Cybersecurity, Korea University
2Department of Physics, Korea University
{sandiegojs, hachikohmy, hjw4, hoot55<EMAIL_ADDRESS>
###### Abstract

Location-based services offer immense utility, but also pose significant
privacy risks. In response, we propose LocPIR, a novel framework using
homomorphic encryption (HE), specifically the TFHE scheme, to preserve user
location privacy when retrieving data from public clouds. Our system employs
TFHE’s expertise in non-polynomial evaluations, crucial for comparison
operations. LocPIR showcases minimal client-server interaction, reduced memory
overhead, and efficient throughput. Performance tests confirm its
computational speed, making it a viable solution for practical scenarios,
demonstrated via application to a COVID-19 alert model. Thus, LocPIR
effectively addresses privacy concerns in location-based services, enabling
secure data sharing from the public cloud. ††979-8-3503-7428-5/24/$31.00 ©2024
IEEE

##  1 Introduction

Location-based services offer individuals various advantages, including
personalized features like navigation assistance and targeted recommendations.
Nevertheless, these services also carry inherent risks, primarily centered
around the potential compromise of individuals’ privacy and the undesired
consequences of data aggregation and behavioral analysis.

To address these challenges, homomorphic encryption (HE) emerges as a powerful
cryptographic technique that facilitates computations on encrypted data.
Notably, HE offers a distinct advantage over the traditional client-server
model, known as two-party computation, wherein the client submits encrypted
data for private computation that is subsequently evaluated without
decryption. Consequently, the client obtains the computation result while
safeguarding their sensitive information, as all operations are conducted
within the encrypted domain.

In this paper, we introduce a novel framework, called LocPIR, which utilizes
HE to hide user location information during the retrieval of location-
associated data from the public cloud. The core component of our system is
TFHE (Fast Fully Homomorphic Encryption over the Torus) [5], a prominent
branch of HE schemes distinguished by its efficient gate bootstrapping.

Our motivation stems from recognizing the inherent advantage of the TFHE
scheme in facilitating non-polynomial evaluations, particularly in
_comparison_ operations. In contrast, other notable branches of HE schemes,
such as the BGV-family [4], exhibit lower performance in evaluation and thus
rarely employ comparison operations. Consequently, some literature [2, 8]
focusing on the construction of location-based PIR relies on the client’s
computational power or increased communication overhead to address the
challenges posed by non-linear evaluations.

(a) Seoul

(b) Busan

Figure 1: Bounding Box and Boundary Coordinates for Seoul and Busan.

In our study, we develop a homomorphic comparison circuit capable of
processing two ciphertexts and generating a ciphertext that represents either
greater than or less than relation, depending on the context. The primary
objective of this construction is to establish a _red bounding box_ , as
illustrated in Figure 1, that encompasses the geographical regions
corresponding to the designated city for the encrypted service. Subsequently,
upon receiving the user’s encrypted GPS coordinates, the cloud can employ the
LocPIR circuit to homomorphically compare these coordinates with the
boundaries of the bounding box. The output of this computation allows the
cloud to retrieve the _encrypted service_ associated with the relevant
bounding box area. It is important to note that throughout this process, the
server does not have access to the user’s location information, as all
computations are performed within the encrypted domain.

###  1.1 Contribution

  * •

Our model is computationally efficient, enabling fast evaluation of user
services in secure data sharing. It takes $5.12$ seconds for an $80$-bit
security level and $5.67$ seconds for a $128$-bit level.

  * •

The size of GPS ciphertexts in our framework is measured at $39.4$ KBytes, and
the encrypted service result, specifically in our COVID-19 model, amounts to
$22.9$ KBytes. These throughput values demonstrate the efficiency of our
location-based PIR solution compared to other literature.

  * •

Our framework is designed to minimize client-server interaction. At the
preprocessing step, the client shares their public key, after which they only
transmit encrypted GPS coordinates without further interaction.

  * •

We validate the practical feasibility of our model by applying it to a real-
world scenario, specifically the COVID-19 alert model.

###  1.2 Related Work

Jain et al. [8] propose a solution that involves two servers to determine the
user’s location. One server employs the Paillier cryptosystem for homomorphic
addition, while the other server utilizes the Elgamal encryption scheme for
multiplication. By leveraging partial homomorphic encryption, they aim to
alleviate computational burdens. However, the assumption of non-collusion
between the servers must be maintained. Additionally, their approach
demonstrates a throughput of 5,000 data points in 4,600 seconds.

An et al. [2] address location-based private information retrieval using a
single-server setup, focusing on the COVID-19 alert model, which shares
similarities with our problem setting. They employ the BFV scheme (BGV-family)
to implement their model, requiring the user to compute the distance based on
encrypted data received from the server. However, their approach has some
drawbacks. Firstly, the computational overhead on the user’s device consumes
over 50% of the CPU resources. Secondly, the total transfer size of ciphertext
between the client and server amounts to 132.84 MBytes. Lastly, the total
computation time required is approximately 399 seconds.

##  2 Background

###  2.1 Notation

In the subsequent sections of this paper, we adopt the following notation:
$\mathbb{B}$ represents the set $\\{0,1\\}$, while $\mathbb{T}$ denotes the
real Torus $\mathbb{R}/\mathbb{Z}$, which corresponds to the set of real
numbers modulo $1$. The notation
$a\stackrel{{\scriptstyle\$}}{{\leftarrow}}\chi$ denotes uniform random
sampling from the distribution $\chi$. The expression
$\textsf{Enc}_{\mathfrak{K}}(m)$ refers to the encryption of the message $m$
using the secret key $\mathfrak{K}$. Throughout the paper, bold case letters,
such as $\mathbf{a}$, are employed to denote vectors, while normal case
letters are used to represent scalar values unless otherwise specified.

###  2.2 Homomorphic Encryption

Homomorphic encryption (HE) is a powerful encryption technique that enables
the processing of encrypted data. The most promising solution against post-
quantum attacks is LWE-based [9] (or RLWE-based [10]) HE, which relies on the
hardness of the Learning with Error (LWE) problem. The security of LWE-based
encryption schemes heavily relies on introducing noise to the plaintext,
making it computationally difficult to distinguish the encrypted form from
random values (or LWE samples). HE schemes can be classified into two
families: BGV-like [3, 6, 4], and GSW-like [7] schemes.

FHE over the Torus. TFHE [5] stands out as a leading scheme within the GSW-
like family, primarily due to its highly efficient gate bootstrapping
capability, with a single-core execution time of less than $13$ ms. The TFHE
scheme encompasses three distinct types of ciphertexts that operate over the
Torus $\mathbb{T}$. For the purpose of understanding our paper, we will
specifically focus on the TLWE ciphertext type.

  * •

KeyGen($\lambda$): Given security parameter $\lambda$, the key generation
algorithm outputs a pair of keys: a secret key
$\mathfrak{K}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{B}$ and a public
key set PK, which includes a bootstrapping key and a key switching key.
Additionally, the algorithm outputs TLWE parameters $n$ and $\sigma$, where
both paramters are determined by the security paramter $\lambda$.

  * •

Encrypt($m,\mathfrak{K},n,\sigma$): Given a binary message $m\in\mathbb{B}$,
it is encoded to a plaintext $\mu\in\mathbb{T}$ using the function $f:m\mapsto
m/4-1/8$. Next, the algorithm generates a masking vector $\mathbf{a}$ by
uniformly sampling from the set $U(\mathbb{T}^{n})$. The plaintext message
$\mu$ is then encrypted using the secret key $\mathfrak{K}$, resulting in a
TLWE sample denoted as $\mathsf{ct}=\mathbf{a}\cdot\mathfrak{K}+\mu+e$. Here,
$e$ is a noise term drawn from a Gaussian distribution $N(0,\sigma)$.

  * •

Decrypt($\mathsf{ct},\mathfrak{K}$): The decryption algorithm calculates the
phase of the ciphertext $\mathsf{ct}=(\mathbf{a},b)$ by
$\varphi_{\mathfrak{K}}(\mathsf{ct})=b-\mathbf{a}\cdot\mathfrak{K}$. The
resulting phase $\mu+e$ is then rounded to the nearest plaintext message from
the set $\\{-1/8,1/8\\}$. Applying the inverse function $f^{-1}$ to the
obtained plaintext message allows us to recover the original message bit
$m\in\mathbb{B}$. Note that the error term $e$ must have a magnitude smaller
than $1/16$ to guarantee the correctness of the algorithm.

  * •

EvalGate($\mathsf{ct}_{1},\mathsf{ct}_{2}$, PK): We focus on the evaluation of
the HomAND gate as an illustrative example, noting that similar procedures
apply to other basic gates (refer to [5] for details). The evaluation of the
HomAND gate can be described as follows:

$\textsf{HomAND}(\mathsf{ct}_{1},\mathsf{ct}_{2},\textsf{PK})=\textsf{Bootstrap}((\mathbf{0},-\frac{1}{8})+\mathsf{ct}_{1}+\mathsf{ct}_{2}).$

Assuming that the magnitude of errors in both $\mathsf{ct}_{1}$ and
$\mathsf{ct}_{2}$ is less than $1/16$, the aforementioned procedure correctly
produces the AND result. We can verify by applying the phase function to
$\mathsf{ct^{\prime}}=(\mathbf{0},-\frac{1}{8})+\mathsf{ct}_{1}+\mathsf{ct}_{2}$,
resulting in:

$\varphi_{\mathfrak{K}}(\mathsf{ct^{\prime}})=-\frac{1}{8}+\mu_{1}+\mu_{2}+e_{1}+e_{2}.$

If both $\mu_{1}$ and $\mu_{2}$ represent the encoding of $1$, indicating a
result of AND as $1$, we can extract the plaintext message $\mu^{\prime}$ from
$\mathsf{ct^{\prime}}$ when $\mu^{\prime}>0$. On the other hand, if
$\mu^{\prime}$ is less than $0$, we can determine that the result of AND is
$0$.

##  3 Our Model

We present an overview of our model, which involves four distinct parties: a
client, a cloud, a data generator, and a satellite (see Fig. 2). We assume a
_semi-honest_ cloud, which is curious about the client’s information but
adheres to the prescribed protocol.

Figure 2: An Overview Timeline of Our Model.

Preprocessing. The service provider collects data from a data generator,
which, for instance, can be a COVID testing center responsible for aggregating
the number of positive patients in a specific district. Upon receiving data
from each data generating center, the cloud service provider generates service
information, denoted as $S_{i}$, based on the received data and the
corresponding geographical coordinates. For instance, the geographical
coordinates of a city may span from $35.8$ to $38.2$ latitude and $125.2$ to
$127.8$ longitude. The cloud service provider assigns a binary string, such as
”immediate evacuation,” to represent the generated service information $S_{i}$
for the client. Note that the length of the binary service string may vary; we
introduce the parameter $m$ to denote the size of the service string.

The client transmits $N\times m$ freshly generated TLWE samples, represented
as $\mathsf{ct}_{i,j}$, to the cloud encrypting the value of $0$ along side
with the public key PK. These samples are subsequently utilized for encrypting
the binary service string $S_{i}$ through the following steps: (1) encoding
the individual bits of $S_{i}$ into a torus element, and (2) performing the
operation $S_{i}[j]+\mathsf{ct}_{i,j}$. For instance, if the first bit of
$S_{i}$ is $1$, it is encoded as $(0,1/8)$ in the plaintext sample, and the
fresh sample $(\textbf{a}_{i},b_{i})$ is added to it to transform it into a
ciphertext (see Algorithm 1). It should be noted that $\mathsf{ct}_{i,j}$
serves as a public key for the client, enabling the cloud to encrypt their
binary services.

Input: Trivial noiseless plaintext $S_{i}[j]$ and
$\mathsf{ct}_{i,j}=(\mathbf{a}_{i,j},b_{i,j})$ where
$b_{i,j}=\mathbf{a}_{i,j}\cdot\mathfrak{K}+e$

Output: Encryption of $S_{i}[j]$ under secret key $\mathfrak{K}$

1

2for  _$i=1,\dots,N$_ do

3 for  _$j=0,\dots,m-1$_ do

4 $S_{i}[j]\leftarrow S_{i}[j]+\mathsf{ct_{i,j}}$

5

6

7return _$S_{i}[j]$_

Algorithm 1 Preprocess($S_{i}[j],\mathsf{ct_{i,j}}$)

Secure location-based computation. The client obtains GPS data in the form of
a tuple $(x,y)$ representing latitude $x$ and longitude $y$ from satellite
sources. This data is encrypted using the client’s secret key $\mathfrak{K}$
and transmitted to the cloud. The cloud receives the encrypted GPS data
$(\textsf{Enc}_{\mathfrak{K}}(x),\textsf{Enc}_{\mathfrak{K}}(y))$ and performs
an evaluation of the location-based service, denoted as LocPIR, utilizing the
encrypted data and the client’s public key PK. Upon completion of the
evaluation, the cloud sends the encrypted result $S$ back to the client, which
can only be decrypted by the client’s secret key $\mathfrak{K}$.

##  4 LocPIR

###  4.1 Encoding and Encryption

Encoding. We begin by explaining the encoding process for the input GPS data,
denoted as $x$ and $y$. We adopt a fixed-point number representation
methodology, as opposed to using a floating-point representation which
requires more careful consideration. Given that latitude values range from
$-90$ to $90$ degrees and longitude values range from $-180$ to $180$ degrees,
we allocate a fixed $9$-bit representation to accommodate the integer part of
the value. For the fractional part, we employ a flexible length, allowing for
a customizable level of precision. By default, we assign a $7$-bit length for
the fractional part, resulting in a total of $16$ bits for encoding the input
GPS data $x$ and $y$. Note that the input length size is parameterized and
denoted as $l$, indicating that our input has $l$-bit precision.

Encryption. In our encryption process, we adopt a bit-by-bit approach for the
given encoded GPS data. Specifically, given a GPS data $x$, which has been
encoded into a binary string of length $l$, we encrypt each individual bit of
$x$ using the secret key $\mathfrak{K}$, which results in $l$ TLWE ciphertext.

###  4.2 Comparison Gate Design

At the core of our framework lies a fundamental component—HomCompS circuit,
representing a less-than comparison operation. This circuit accepts two
ciphertexts, denoted as $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$, which encrypt
$x_{1}$ and $x_{2}$, each of length $l$ in binary format when encoded. The
circuit produces a ciphertext of length $1$, wherein the encrypted value
represents $1$ if $x_{1}<x_{2}$, and $0$ otherwise.

1

Input: Ciphertext $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ of length $l$,
encrypting $x_{1}$ and $x_{2}$ with secret key $\mathfrak{K}$ and PK

Output: $\textsf{Enc}_{\mathfrak{K}}$($1$) if $x_{1}<x_{2}$,
$\textsf{Enc}_{\mathfrak{K}}$($0$) otherwise

2

3$t_{0}\leftarrow\textsf{Enc}_{\mathfrak{K}}(0)$

4$\mathbf{c}_{1}[l-1]\leftarrow\textsf{HomNOT}(\mathbf{c}_{1}[l-1])$

5$\mathbf{c}_{2}[l-1]\leftarrow\textsf{HomNOT}(\mathbf{c}_{2}[l-1])$

6for  _$i=0,\dots,l-1$_ do

7

8 $t_{1}\leftarrow\textsf{HomXNOR}(\mathbf{c}_{1}[i],\mathbf{c}_{2}[i])$

9 $t_{0}\leftarrow\textsf{HomMUX}(t_{1},t_{0},\mathbf{c}_{2}[i])$

10

11return _$t_{0}$_

Algorithm 2 HomCompS($\mathbf{c}_{1},\mathbf{c}_{2}$, PK)

Correctness. The correctness of the circuit can be attributed to the iterative
utilization of the XNOR gate and MUX gate within the loop defined in Algorithm
2. The XNOR gate assigns $\textsf{Enc}_{\mathfrak{K}}(1)$ to $t_{1}$ when two
bits are equal, while the MUX gate selects $t_{0}$ based on the previous
result. Specifically, if the bits of $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ are
equal, $t_{0}$ is chosen; otherwise, the corresponding bit of $\mathbf{c}_{2}$
is selected.

Considering the scenario where $x_{1}$ and $x_{2}$ are equal, the XNOR gate
yields $t_{0}$ as the output, which is then propagated through the MUX gate,
resulting in the selection of $t_{0}$ once again. Consequently, the initial
value of $t_{0}$ (i.e., $\textsf{Enc}_{\mathfrak{K}}(0)$) is successfully
propagated to the final output of the circuit, satisfying the desired outcome.

In the scenario where $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ differ, the focus
is on the most significant differing position (MSDP), which represents the
highest bit position where the corresponding bits of $\mathbf{c}_{1}$ and
$\mathbf{c}_{2}$ differ. At the MSDP, the MUX gate selects the corresponding
bit of $\mathbf{c}_{2}$ for $t_{0}$. Consequently, if $x_{1}>x_{2}$, the
desired outcome of $\textsf{Enc}_{\mathfrak{K}}(0)$ is achieved, indicating
that $x_{1}$ is not less than $x_{2}$. A similar process applies to the
opposite case.

To address potential issues, bit-flipping is introduced in line $2$ and $3$ of
Algorithm 2. In situations where $x_{1}$ and $x_{2}$ are equal, the iterative
process passes $t_{0}$ from the MSDP bit to the output, ensuring correctness
of the circuit. However, when $x_{1}$ and $x_{2}$ differ, the MSDP corresponds
to the most significant bit (MSB), and the MUX gate selects the MSB of
$\mathbf{c}_{2}$. This selection may yield an opposite result
($\textsf{Enc}_{\mathfrak{K}}(1)$) instead of the desired
$\textsf{Enc}_{\mathfrak{K}}(0)$ when $x_{1}>x_{2}$. Thus, the MSB needs to be
initially reversed. Likewise, HomCompLE can be designed by negating the result
from HomCompS, as it yields the inverse outcome.

###  4.3 LocPIR Circuit

Input: Client’s encrypted GPS coordinate
$(\textsf{Enc}_{\mathfrak{K}}(x),(\textsf{Enc}_{\mathfrak{K}}(y))$ and PK

Output: Requested service $\textsf{Enc}_{\mathfrak{K}}(S)$

1

$S\leftarrow[\textsf{Enc}_{\mathfrak{K}}(0),\cdots,\textsf{Enc}_{\mathfrak{K}}(0)]$
// size $m$

2

3for  _$i=1,\dots,N$_ do

/* compare all intervals */

4
$x_{l}\leftarrow\textsf{HomCompLE}(x_{i,1},\textsf{Enc}_{\mathfrak{K}}(x),\textsf{PK})$

5
$x_{r}\leftarrow\textsf{HomCompS}(\textsf{Enc}_{\mathfrak{K}}(x),x_{i,2},\textsf{PK})$

6
$y_{l}\leftarrow\textsf{HomCompLE}(y_{i,1},\textsf{Enc}_{\mathfrak{K}}(y),\textsf{PK})$

7
$y_{r}\leftarrow\textsf{HomCompS}(\textsf{Enc}_{\mathfrak{K}}(y),y_{i,2},\textsf{PK})$

/* validation #1 */

8 $v_{1}\leftarrow\textsf{HomAND}(x_{l},x_{r},\textsf{PK})$

9 $v_{2}\leftarrow\textsf{HomAND}(y_{l},y_{r},\textsf{PK})$

/* validation #2 */

10 $f\leftarrow\textsf{HomAND}(v_{1},v_{2},\textsf{PK})$

/* service validation */

11 $S_{i}\leftarrow\textsf{bitwiseAND}(f,S_{i},\textsf{PK})$

/* addition of all services */

12 $S\leftarrow\textsf{HomSum}(S,S_{i},\textsf{PK})$

13

14return _$S$_

Algorithm 3
LocPIR($\textsf{Enc}_{\mathfrak{K}}(x),\textsf{Enc}_{\mathfrak{K}}(y)$, PK)

Comparison with bounding boxes. The LocPIR circuit takes the client’s
encrypted GPS coordinates
$(\textsf{Enc}_{\mathfrak{K}}(x),\textsf{Enc}_{\mathfrak{K}}(y))$, along with
their public key PK, as inputs. The circuit then produces the requested
service of the client, represented as $\textsf{Enc}_{\mathfrak{K}}(S)$,
according to the algorithm outlined in Algorithm 3. The underlying concept
behind this circuit is to compare the GPS coordinates with the bounding box
coordinates $(x_{i,1},x_{i,2},y_{i,1},y_{i,2})$, where each coordinate defines
the latitude and longitude range of the $i-$th region. If the values of $x$
and $y$ fall within the boundary of the bounding box, the comparison result,
as shown in line 3-6 of Algorithm 3 will output
$\textsf{Enc}_{\mathfrak{K}}(1)$.

Validation step. The obtained comparison result from line 3-6 allows us to
verify whether the given GPS coordinate falls within the specified bounding
box. This validation step occurs in line 7-10 of Algorithm 3. Utilizing the
property of the homomorphic AND gate (HomAND), which outputs
$\textsf{Enc}_{\mathfrak{K}}(1)$ only when all encrypted values are 1, we can
determine the fulfillment of the bounding box condition. Specifically, if the
GPS coordinates fall within the bounding box, we have
$x_{l}=x_{r}=y_{l}=y_{r}=\textsf{Enc}_{\mathfrak{K}}(1)$. By applying HomAND
gates, we can obtain $\textsf{Enc}_{\mathfrak{K}}(1)$.

Input: 1-bit encryption $\mathsf{ct}$, $\mathbf{c}$ encrypting $m$-bit binary
$x$, and PK

Output: (size $m$) $\mathbf{c}$ encrypting $x$ or $0$

1

2for  _$i=0,\dots,m-1$_ do

3
$\mathbf{c}[i]\leftarrow\textsf{HomAND}(\mathsf{ct},\mathbf{c}[i],\textsf{PK})$

4

5return _$\mathbf{c}$_

Algorithm 4 bitwiseAND($\mathsf{ct},\mathbf{c}$, PK)

Sevice validation. Subsequently, we can perform a bitwise HomAND operation,
denoted by bitwiseAND (see Algorithm 4), on the previous validation result $f$
with $S_{i}[j]$ of length $m$ to obtain $S_{i}$, which represents the
encrypted service $S_{i}$ associated with the $i$-th location or bounding box.
If the validation step yields a result of $\textsf{Enc}_{\mathfrak{K}}(1)$ for
$f$, it indicates that the GPS coordinates $x$ and $y$ fall within the $i$-th
boundary. Consequently, the $i$-th encrypted service $S_{i}$ will be preserved
in the bitwiseAND operation.

Figure 3: Diagram Illustrating Comparison Gate Evaluation and Validation Step.

Illustrative example. Consider the following scenario, illustrated in Fig. 3,
where $x=37.5$ and $y=130.1$ in the plain domain. Initially, we compare $x$
and $y$ with $N$ location boundaries represented by
$x_{i,1},x_{i,2},y_{i,1},y_{i,2}$. For instance, in the case of location 1,
the latitude boundary is defined as $[37.4,37.6)$ and the longitude boundary
as $[126.8,127.1)$. The comparison results output $1$ for $x$ since it falls
within the latitude boundary. Conversely, $y$ does not satisfy the boundary
condition $y<127.1$, resulting in a comparison outcome of $0$. Consequently,
the bitwise AND operation applied to these outcomes yields $0$ as the final
validation result ($f=0$). Thus, performing a bitwise AND of $f$ with the
corresponding service $S_{1}=101$ in binary form yields $000$. In summary, if
the input GPS coordinates fail to satisfy the bounding box condition, the
resulting $S_{i}$ is represented as $000$ in binary. Conversely, if the GPS
coordinates satisfy the bounding condition, the validation result $f$ will be
$1$, preserving the original binary representation of $S_{i}$.

###  4.4 Services Summation: HomAddXOR

In the final step, we combine the results of $N$ services $S_{i}$. Under the
assumption of disjointly distributed bounding boxes, there exists only one
$S_{i}$ (or none) that corresponds to the encryption of its binary
representation, while the remaining $S_{i}$ values are encryption of $0$. This
distinction arises due to the unique matching of the GPS coordinate with a
specific bounding box condition. Consequently, we can sum the $N$ services
$S_{i}$, resulting in the service associated with the bounding box in which
the coordinates $x$ and $y$ reside.

XOR Addition. An appealing approach is to employ HomXOR gates to perform the
addition of the corresponding bits in $S_{i}$. For each bit position
$j\in[0,m)$, we can compute the operation $S_{1}[j]\oplus\dots\oplus S_{N}[j]$
(see Algorithm 5).

Input: $\\{S_{i}\\}_{i=1}^{N}$, where at most one of $S_{i}$’s is not an
encryption of $0$ and PK

Output: $S$ (sum of $S_{i}$’s)

1

$S\leftarrow[\textsf{Enc}_{\mathfrak{K}}(0),\cdots,\textsf{Enc}_{\mathfrak{K}}(0)]$
// size $m$

2

3for  _$i=1,\dots,N$_ do

4 for  _$j=0,\dots,m-1$_ do

5 $S_{i}[j]\leftarrow\textsf{HomXOR}(S[j],S_{i}[j],\textsf{PK})$

6

7

8return _$S$_

Algorithm 5 HomAddXOR($\\{S_{i}\\}_{i=1}^{N}$, PK)

##  5 Experiment

Environment Setting. The experiments were performed on a computer with the
following specifications: an AMD Ryzen 5 3500X 6-Core Processor and 64GB of
RAM. The operating system used was Ubuntu 22.04 LTS. We implemented our model
using the TFHE library version 1.1.

City | Lat1 | Lat2 | Long1 | Long2 | Service
---|---|---|---|---|---
Seoul | 37.4758 | 37.6195 | 126.8831 | 127.1331 | 427
Busan | 35.1692 | 35.2199 | 128.8821 | 129.2104 | 33
Daegu | 35.7467 | 35.9743 | 128.4280 | 128.6909 | 61
Incheon | 37.4127 | 37.5941 | 126.5876 | 126.7894 | 74
Gwangju | 35.0732 | 35.2361 | 126.7050 | 126.9533 | 5
Daejeon | 36.2615 | 36.4508 | 127.2998 | 127.5076 | 13
Ulsan | 35.3710 | 36.6745 | 129.0731 | 129.3644 | 9
Sejong | 36.5018 | 36.6970 | 127.1430 | 127.4080 | 6
Jeju | 33.2948 | 33.5149 | 126.1874 | 126.8493 | 6

Table 1: COVID-19 Dataset for Nine Major Cities: Bounding Box Coordinates and
Patient Incidence (Services).

Dataset. We utilized the publicly available dataset provided by the Korea
Disease Control and Prevention Agency (KDCA), which contains the daily records
of COVID-19 patient incidence for the nine major cities in Korea. The dataset
used in this study specifically focuses on October 26th, 2021. To define the
geographical boundaries of each major city, we obtained the coordinates of the
bounding box region using Google Maps (see Fig. 1). Subsequently, we
associated the COVID-19 patient incidence data for each city with the
corresponding ”Service” information.

TFHE Parameters. Our model utilized standard 80-bit ($\lambda_{80}$) and
128-bit ($\lambda_{128}$) security levels. The selection of parameters $n$ and
$\sigma$, which determine the security level of the LWE scheme, was chosen
based on the lattice estimator [1]. Specifically, for the 80-bit security
level, we set $n=540$ and $\sigma=2^{-20.2}$. Similarly, for the 120-bit
security level, we chose $n=630$ and $\sigma=2^{-13.8}$.

COVID-19 Model Outline. The scenario for the COVID-19 alert model aligns
closely with our previous proposal (See Fig. 2). Based on the aggregated
result of COVID-19 incidences, the cloud system evaluates LocPIR to provide
the user with the encrypted service result, which can only be decrypted with
the user’s secret key.

##  6 Result

###  6.1 Privacy-preserving COVID-19 Alert Model

Precision | Parameter Set | Encrypt | LocPIR | Decrypt
---|---|---|---|---
Comparison | Validation | HomAddXOR | Total Time
$l=13$ | $\lambda_{80}$ | $0.34\,\text{ms}$ | $3.92\,\text{s}$ | $0.32\,\text{s}$ | $0.12\,\text{s}$ | $\mathbf{4.36\,\text{s}}$ | $6.27\,\text{\textmu s}$
$\lambda_{128}$ | $0.38\,\text{ms}$ | $4.40\,\text{s}$ | $0.33\,\text{s}$ | $0.15\,\text{s}$ | $\mathbf{4.88\,\text{s}}$ | $5.55\,\text{\textmu s}$
$l=16$ | $\lambda_{80}$ | $0.41\,\text{ms}$ | $4.69\,\text{s}$ | $0.31\,\text{s}$ | $0.12\,\text{s}$ | $\mathbf{5.12\,\text{s}}$ | $5.57\,\text{\textmu s}$
$\lambda_{128}$ | $0.48\,\text{ms}$ | $5.21\,\text{s}$ | $0.33\,\text{s}$ | $0.13\,\text{s}$ | $\mathbf{5.67\,\text{s}}$ | $4.97\,\text{\textmu s}$
Table 2: Execution Time of LocPIR COVID-19 Alert Model: Fixed Service Length
and Major Cities Number ($m,N=9$).

Time Performance. The evaluation (LocPIR) process took a total of $4.36$
seconds for the 80-bit security level and $4.88$ seconds for the 120-bit
security level when the input length was $13$. Additionally, for an input
length of $16$, the evaluation required $5.12$ seconds for the 80-bit security
level and $5.67$ seconds for the 120-bit security level. It is worth noting
that the encryption and decryption stages each took less than a millisecond,
regardless of the security parameters.

The comparison circuit evaluations, which involved encrypted GPS coordinates
with $N$ bounding boxes, accounted for the majority of the execution time in
the evaluation step. Specifically, for $l=13$ and $\lambda_{80}$, the
comparison circuit evaluations took $3.92$ seconds. In comparison, the
Validation step required $0.32$ seconds, and the HomAddXOR step took $0.12$
seconds. This highlights that the comparison circuit evaluations constituted
approximately $90$ percent of the total evaluation time.

Memory Size. In our parameter setting, a TLWE sample for $\lambda_{80}$
occupies approximately $2.11$ KBytes of memory. As a result, during the
preprocessing stage, the user is required to transmit $N\times m=81$ TLWE
samples for the encryption of services to the public cloud server, totaling
around $171$ KBytes. Subsequently, the user transmits two encrypted GPS
coordinates, which are approximately $27.4$ KBytes and $33.8$ KBytes in size
for lengths $13$ and $16$, respectively. For $\lambda_{128}$, the user
transmits approximately $199$ KBytes of $81$ TLWE samples, along with
approximately $32$ KBytes and $39.4$ KBytes for size $13$ and $16$ GPS
coordinates, respectively.

###  6.2 General Circuit Analysis.

Time Complexity Anlaysis. We emphasize that the primary bottleneck in the
LocPIR algorithm stems from the evaluation of comparison circuit, which
involves $l$ XNOR and MUX gates, resulting in $3l$ evaluations of homomorphic
gates (with MUX gates taking twice the computational time compared to other
gates). In summary, the number of evaluations for the comparison circuits is
in the order of $O(Nl)$. The validation step necessitates $O(N+m)$
evaluations. Lastly, summing up all the services with HomAddXOR requires
$O(mN)$ evaluations. Thus, the total complexity of our model can be expressed
as $O(N(m+l))$.

(a) Time w.r.t $(N,l)$

(b) Time w.r.t $(m,N)$

Figure 4: LocPIR’s General Execution Time with Key Parameters: Number of
Bounding Boxes $N$, Input Length $l$, and Service Length $m$.

Timing Analysis of Parameters $(N,l,m)$. First, we conducted experiments on
our model by varying the number of bounding boxes ($N$) and the input GPS
length ($l$) (refer to Fig. 4.(a)). The service length was fixed at $m=9$, and
full threading with $n_{t}=6$ was utilized. It is observed that the slope of
the graphs changes at $N=6$, where the magnitude of the slope is affected by
the limited number of threads. Further validation of this claim can be seen in
Fig. 5.

In addition, we can observe a linear increase in execution time with respect
to $l$. As an example of concrete experimental results, when $N=10$, the
evaluation times for input lengths $l=8,16,24,32$ bits are $3.256$, $6.139$,
$8.764$, and $11.670$, respectively. These times correspond to $1.88\times$,
$2.69\times$, and $3.58\times$ of the first evaluation time.

Next, we examined the performance of our model by varying the service length
$m$ and the number of bounding boxes $N$ while keeping the input length $l$
fixed at $16$ (see Fig. 4.(b)). The time performance demonstrated a linear
relationship with the service length $m$, which is in line with our estimated
time complexity.

Figure 5: Execution Time w.r.t Thread Count $n_{t}$ for Varying Numbers of
Bounding Boxes $N=4,8,12,16,20,24,28$.

Highly Parallel Structure. The structure of LocPIR is _significantly
parallelizable_ (see Fig. 5). The figure shows that an increase in thread
count leads to a drastic improvement in time performance, specifically within
the range of $2$ to $6$. In conclusion, a sufficiently large number of
parallel computations can drastically enhance the performance of LocPIR.

##  7 Conclusion

This study introduces a location-based private information retrieval framework
capable of concealing location data from a public cloud during information
retrieval pertaining to GPS coordinates. It has been demonstrated that our
system can be re-engineered homomorphically using the TFHE scheme, noted for
its proficiency in executing non-linear polynomial evaluations such as
comparisons. Furthermore, the applicability of our system within a COVID-19
alert model conforming to standard security levels has been validated. Given
the highly parallel structure of our circuit, future research efforts will
concentrate on exploring and enhancing these design improvements.

Acknowledgments This work was supported in part by the MSIT (Ministry of
Science and ICT), Korea, under the ITRC (Information Technology Research
Center) support program (IITP-2024-RS-2022-00164800) supervised by the IITP
(Institute for Information & Communications Technology Planning & Evaluation),
and in part by the grant-in-aid of LG Electronics.

## References

  * [1] M. R. Albrecht, R. Player, and S. Scott.  On the concrete hardness of learning with errors.  Journal of Mathematical Cryptology, 9(3):169–203, 2015.
  * [2] Y. An, S. Lee, S. Jung, H. Park, Y. Song, and T. Ko.  Privacy-oriented technique for covid-19 contact tracing (protect) using homomorphic encryption: Design and development study.  Journal of medical Internet research, 23(7):e26371, 2021.
  * [3] Z. Brakerski.  Fully homomorphic encryption without modulus switching from classical gapsvp.  In Annual cryptology conference, pages 868–886. Springer, 2012\.
  * [4] Z. Brakerski, C. Gentry, and V. Vaikuntanathan.  (leveled) fully homomorphic encryption without bootstrapping.  ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014\.
  * [5] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène.  Tfhe: fast fully homomorphic encryption over the torus.  Journal of Cryptology, 33(1):34–91, 2020.
  * [6] J. Fan and F. Vercauteren.  Somewhat practical fully homomorphic encryption.  Cryptology ePrint Archive, 2012.
  * [7] C. Gentry, A. Sahai, and B. Waters.  Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based.  In Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 75–92. Springer, 2013.
  * [8] M. Jain, P. Singh, and B. Raman.  Shelbrs: Location-based recommendation services using switchable homomorphic encryption.  In International Conference on Security, Privacy, and Applied Cryptography Engineering, pages 63–80. Springer, 2021.
  * [9] O. Regev.  On lattices, learning with errors, random linear codes, and cryptography.  Journal of the ACM (JACM), 56(6):1–40, 2009.
  * [10] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa.  Efficient public key encryption based on ideal lattices.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 617–635. Springer, 2009.