Two-Server Offline/Online Private Information Retrieval With Small Client Storage

This paper introduces PIRS, a system for private information retrieval (PIR, where a user can fetch data from a database without revealing which data they want). PIRS uses two servers and splits the retrieval process into an offline phase, where the client preprocesses the database to create hints, and an online phase, where the client uses those hints to securely retrieve records. Unlike existing approaches, PIRS allows clients to store hints on the servers instead of locally, reducing storage needs from gigabytes to kilobytes by using secret sharing (a technique where data is split into pieces that are useless individually but combine to reveal the original).