Introduction
Blindstore is a cryptographic product that implements a Private Information Retrieval (PIR) protocol. PIR protocols allow a user to retrieve the \(i\)-th record of a database without letting the database server know the content of \(i\). Otherwise said, the user accesses a database (which provides all of its content through a mapping index → value) and upon requesting an index he is served with the correct value, although the server cannot know which index (and therefore which value) it served. The same result can also by obtained trivially by having the user retrieve the whole database and perform the search locally, but this solution is often very costly.
The protection is effective even if the server is not to be trusted. Thus Blindstore safeguards the privacy of users accessing the database.
The implementation of Blindstore has its theoretical foundation in the protocol described in the paper “Single-Database Private Information Retrieval from Fully Homomorphic Encryption” published by Xun Yi, Mohammed Golam Kaosar, Russell Paulet, and Elisa Bertino in May 2013. The protocol illustrated in the paper uses Somewhat Homomorphic Encryption (SHE), a simplification of Fully Homomorphic Encryption (FHE) which allows homomorphic computation of operations on plaintexts. I.e., in FHE schemes encryption and decryption (which take place using a public/private key pair) have the following property: performing an operation on the ciphertext of two encrypted messages, by adding or multiplying them, will result in a ciphertext which, when decrypted, will be equivalent to the addition or multiplication of the two plaintext messages.
Theory
The theoretical protocol behind Blindstore describes a database accessible by index → value pairs, with the index being \(l\)-bit long. The user generates a public/private key pair and sends the public key to the database server. Then he chooses an index \(i\), encrypts it with the public key, and sends it to the server as a query. The server computes an encryption of \(i\)-th record based on the database content, the query, and the public key, and sends the response back to the user. The user decrypts the response to obtain the requested value. Since the server cannot decrypt \(i\) alone, and uses all the values in the database for the computation of the response, the server is unable to know which index (and therefore which value from the database) was requested by the user.
Implementation
The cryptographic library is written in C++. The whole application is work in progress.
FHE schemes being computationally expensive, the current (alpha, non-optimized) implementation of Blindstore has a response time of 2.88 seconds for a query to a database with 10-bit indexes and 1-Kb records (benchmarks measured on an i5 @ 2.50 GHz machine).
Practical applications
A Blindstore server is an added value to a service provider, as it can guarantee to clients that it has no way to know which piece of information they requested to the service provider.
There are several possible practical applications of Blindstore.
People directory
As Blindstore protects the privacy of the query, it can be used to create databases storing contact information for human right activists. This would allow citizens in totalitarian countries to access the database without disclosing the identity of the person they've requested information about.
Online encyclopedia
Another use case for Blindstore is a shared online encyclopedia such as Wikipedia, with the content indexed by the article's title. In this case the user could access any article without the server knowing which article has been requested.
Service location
Blindstore can be used to anonymize a service that provides the user with a list of points of interest (restaurants, bars, hotels...) near his location, as pinpointed by the GPS in the user's smartphone. Usually the user would need to provide his location to the server in order to obtain the relevant information, at the detriment of the user's privacy. With Blindstore, information about points of interest can be organized in geographical quadrants, with the user sending a query containing the coordinates of the quadrant he's in at that moment. The server is unable to decrypt the request (the user location quadrant) but can nonetheless provide the relevant data (points of interests in the user quadrant).
Masking of commodities demand
Many commodities (real estate, stock exchange, currencies, plane tickets, hotel stays) are subject to price fluctuations depending on demand. The public demand or interest on a particular commodity (for instance, a house) can be evaluated by the number of information queries about it (for instance, hits on a particular page of the real estate agency website). Being unable to evaluate the number of requests would make financial speculations impossible.
The same reasoning can be applied to request of information from a large multinational about the status or health of a small company: this kind of request can have an impact on the stock value of the company.
Masking of knowledge
Let's imagine a scenario in which a mining company knows that there is gold (or oil or diamonds or any other valuable resource) in a particular area. To extract this gold, the company must request a license to exploit that area before anyone else does. Asking the state for an exploitation permit for that particular area informs them that there is gold in that area, independently of whom asked for it; subsequently the state could use this information, either by selling it to some other company or by exploiting the area themselves. In this case, the mining company is the only party in possess of a valuable piece of information (the presence of gold in that area); using the Blindstore protocol to request the exploitation permit makes sure that the mining company remains the only holder of that information.
