Symmetric Private Shortest Path Retrieval for LM-Enabled Route Services on Consumer Devices

Route optimization is widely utilized in consumer electronics like Google Maps and Facebook connections. However, due to the limitations of consumer devices, users often rely on online service providers to process large-model-enabled route services, which may involve sensitive information such as location and social relationships. This raises privacy concerns, necessitating the need for a system that ensures expected utility while protecting the privacy of both consumers and service providers. This problem, known as Symmetric Private Shortest Path Retrieval, has been studied in the literature, either focusing on specific data types or a simple private setting where the data user and owner are the same. In this paper, we propose a low-latency symmetric private shortest path query for generic graph data in a more realistic public service model. We propose several novel techniques, including a chained encryption method and an oblivious key transfer mechanism to efficiently reveal the queried shortest path without leaking additional information to either the consumers or service provider. Experimental results demonstrate that our scheme outperforms the state-of-the-art by being approximately 46 to 53 times faster and consuming roughly 36 to 74 times less bandwidth for a city navigation service.