Mímir: A Stateless Private Search Engine

Abstract: Private search engines allow a user to retrieve documents from a public database that are similar to a text query, while the server learns nothing about what the user is searching for.  Our cryptographic protocol Mímir uses homomorphic encryption, i.e., computation on encrypted data, to realize the first stateless semantic private search engine for highly dynamic databases.  Unlike other state-of-the-art private search engines, Mímir has no database-dependent preprocessing step that needs to be redone every time the database gets updated: it requires no offline communication, and it trades higher but highly parallelizable server computation for low per-query communication.  The security of Mímir relies on the (Ring) Learning with Errors problem.  Mímir achieves 59% of the non-private search quality with 8.13 MiB of per-query communication and 0.77 s of latency on a single machine.  This outperforms the state-of-the-art private search engine Tiptoe in quality, communication and latency simultaneously, and matches the latency of PACMANN with 7.6× less communication. The talk focuses on semantic search, how to achieve it via homomorphic encryption, and how Mímir achieves statelessness.

Joint work: Gökberk Erdogan, Kamil Kluczniak, Emma Munisamy.

Suggested readings:

• Mímir: A Stateless Private Search Engine (ia.cr/2026/2605)