  Localization is a computer vision task by which the position and orientation
of a camera is determined from an image and environmental map. We propose a
method for performing localization in a privacy preserving manner supporting
two scenarios: first, when the image and map are held by a client who wishes to
offload localization to untrusted third parties, and second, when the image and
map are held separately by untrusting parties. Privacy preserving localization
is necessary when the image and map are confidential, and offloading conserves
on-device power and frees resources for other tasks. To accomplish this we
integrate existing localization methods and secure multi-party computation
(MPC), specifically garbled circuits, yielding proof-based security guarantees
in contrast to existing obfuscation-based approaches which recent related work
has shown vulnerable. We present two approaches to localization, a baseline
data-oblivious adaptation of localization suitable for garbled circuits and our
novel Single Iteration Localization. Our technique improves overall performance
while maintaining confidentiality of the input image, map, and output pose at
the expense of increased communication rounds but reduced computation and
communication required per round. Single Iteration Localization is over two
orders of magnitude faster than a straightforward application of garbled
circuits to localization enabling real-world usage in the first robot to
offload localization without revealing input images, environmental map,
position, or orientation to offload servers.
