Privacy has become increasingly valuable and rare as technology has become more closely integrated with our lives. Private information retrieval (PIR) protocols allow you to retrieve information through an encoded query while also protecting your personal information. Our current security standard online can be viewed as a "no-privacy baseline," which means the vast majority of our online information retrieval isn't protected by any of these protocols. Cryptographers like UT Computer Science professor David Wu are building innovative solutions that support this growing preference for online privacy.
In a joint paper with Samir Menon titled "Spiral: Fast, High-Rate Single-Server PIR via FHE Composition" Professor Wu introduces the Spiral family of single-server PIR protocols. Spiral leverages cryptographic techniques to first encrypt user queries before they are sent to the server. The server can then directly compute the encrypted query and derive an encrypted response. Users can then decrypt the result to learn the requested record. This encryption scheme is homomorphic, specifically, it allows computation on the encrypted data in a way that does not require decryption of the query by the database. The computations (retrieving requested information for example) are performed on the ciphertext itself.
Homomorphic encryption is a technique for computing on encrypted data. As a simple example, consider an encrypted calculator. Suppose you wanted to calculate the sum of two plus three without revealing the inputs to the calculator. Using homomorphic encryption, you would first generate a secret key and use it to encrypt the values two and three. This yields two ciphertexts, which would resemble long random-looking strings which hide the values two and three. The calculator would then take those ciphertexts, and apply an "addition" algorithm on the encrypted values. This yields an encryption of their sum, but does not leak any information about the inputs to the user. Given the encrypted output, the user can then use their secret key to decrypt and learn the sum. Only the holder of the secret key is able to decrypt.
How can we use such an encryption scheme to construct a private information retrieval scheme? For simplicity, consider an example database with just three records. Let's say the user is interested in retrieving record 2. To do so, the user would construct an indicator vector. The indicator vector is "1" when the user is interested in retrieving the record and "0" in all other positions (the vector in this example would be [0,1,0]). Then, the user encrypts the vector using the homomorphic encryption scheme described in the last paragraph. To construct the response, the database will multiply each component with the record in the database then sum up the results. This yields an encryption of the desired record the user wished to return. Overall, the main challenge in private information retrieval is reducing the total communication. The basic protocol described here is inefficient as the query the user inputs is essentially as big as the database itself. However, through composing two homomorphic encryption schemes, the Spiral system can reduce communication through enabling trade-offs in the total upload/downloads made and the amounts of server-side computation.
Spiral has achieved many impressive results. For example, a base version of Spiral simultaneously reduces query size by four-and-a-half times, decreases response size by one-and-a-half times, and doubles the server throughput compared to all previous systems. Additionally, and arguably most importantly, in settings where communication costs dominate (e.g., serving content on Amazon Web Services), the monetary cost of using a protocol like Spiral is estimated to only be 1.9 times more than the no-privacy baseline where the client directly downloads the desired record. Solutions like these are critical to a future in which full privacy online is feasible. To showcase the viability of private information retrieval, Wu and Menon have built a live demo using Spiral to privately browse a subset of Wikipedia. After an initial (one-time) client-side setup, articles can be loaded in just a span of 3-4 seconds. The server in this case has no information about which articles the client requested.
Co-written by Trinity Erales and Lauren Cotton
