Blindstore

Blindstore provides an online lookup service which returns the correct answer without ever knowing what the question was. The protocol guarantees that the server can’t know which record the client requested. The client still only receives the record they requested.

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.

Impressions

Pier-42 working in a meeting room at IdeaSquare

A member of Pier-42 presenting the project concept.

A member of Pier-42 describing the mathematics of the project.

Members of Pier-42 working on a schematic.

Pier-42 working on their project strategy.

Pier-42 members discussing their project.

Project Team

Alejandro Avilés

Alejandro Avilés, aka Ome, software engineer by day, a bunch of other things by night. After a stint as an open-source web developer at CERN, he started working on cryptocurrencies and blockchain early in 2017 at Bity, a Swiss startup. Now, moved by a burning curiosity in cryptoeconomics, decentralization and governance, he co-organizes community exercises to explore these topics with bonfire.link.

Anastasis Andronidis

Anastasis Andronidis is a computer scientist, graduated with excellence from Aristotle University of Greece. After having a 4 years job in a GRID data center in Greece, where he was responsible for databases and distributed frameworks and applications, he start working at CERN as a Technical Student on OpenStack solutions and Linux administrating. Having experience with big infrastructures and parallelization software, he also worked on Puppet as a OpenLab summer student at CERN in 2012, on Apache Hama as a Google’s Summer of Code intern, and now he is a PMC member of the Apache Hama project.

Andrea Leri

Currently a storage engineer at CERN, Andrea is a security minded professional at heart. After having pursued his interests in Italian, Swedish and Scottish universities, he is now working on storage technologies that make life easier for both users and system administrators. In the past he has worked on secure authentication schemes, key management software and account lifecycle projects. He is an advocate of open source software and privacy enhancing techniques.

Benjamin Lipp

Benjamin is currently in the final semester of his undergraduate studies in physics at Karlsruhe Institute of Technology in Germany. He works as Linux system administrator in two non-profit associations and is passionate about open source software, security and cryptography. Besides that, he loves running and photography. This year, he was a CERN openlab summer student working on OpenStack. Benjamin has been part of the team that founded Blindstore.

Bogdan Kulynych

Bogdan is currently in the final year of his undergraduate studies in Applied Mathematics at Kyiv-Mohyla Academy in Ukraine. He also studied at Jagiellonian University in Poland as an Erasmus Mundus student. Bogdan is interested in Machine Learning, Data Analysis, and Cryptography. This year, he was a CERN openlab summer student working on the Invenio project. Concerned over the issues of privacy on the Internet, he was the one who came up with the idea of Blindstore, and lead the technical efforts behind the project.

Christophe Sahut

Christophe is Corporate Infrastructure Architect at SGS (Société Générale de Surveillance), the world’s leading inspection, verification, testing and certification company. Based in Geneva, he’s in charge of several global IT infrastructure projects related to cloud architectures and security. He has a strong technical background on security and opensource technologies as a trainer and consultant. Technology agnostic, Christophe kept from his trainer past the enthusiasm to share his knowledge and experience.

Daniele Raffo

Formerly a CERN civil servant, Daniele holds a Ph.D. in Computer Science focusing on the security of wireless networks. He has experience in the fields of systems, networking, security, and Java programming. Partisan of Linux and Free Software in general, he is the author of the official Handbook for Enigmail, the OpenPGP plugin for Mozilla, as well as a reviewer for other technical books.

Ferdinando Buscema

Ferdinando is a Magic Experience Designer, a corporate specialist designing “magical experiences” for organizational growth. With a background in mechanical engineering and humanistic psychology, Ferdinando has been chosen as a partner by multinational companies, to create high-value edutainment events. Ferdinando is also an international performer, credited at the Magic Castle in Hollywood, the most exclusive stage for magical entertainment. He serves as an Advisor the philanthropic foundation Fetzer Institute.

Gretta Hohl

Gretta was born in Romania, as part of the Hungarian German minority. She studied Computer Science in Berlin Germany focusing on robotics and artificial intelligence. During her studies she worked several years as student researcher in the artificial intelligence group at the Free University Berlin. She developed embedded systems and co-lead the humanoid robots research project FUmanoids. Since three years she is developing software at the SAP Innovation Center Potsdam.

Linga Kalinde Mangachi

Linga Kalinde Mangachi is an Executive MBA in Management of Technology candidate at EPFL. Following undergraduate studies in the United States and an MSc. in Management of Intellectual Property at Queen Mary in London she has pursued a career in Intellectual Property, Policy and Regulatory Affairs. Linga has worked in various roles in international organizations, multinational companies and in start-ups.

Tommaso Papini

Tommaso was born in Figline Valdarno (Florence, Italy) in 1990. He started his bachelor degree in Computer Science (2009) at the University of Florence and graduated in December 2012 with a score of 110/100 cum laude. During the second year of his bachelor degree he also studied at the Polytechnic University of Madrid as Erasmus student. Tomasso enrolled then for a master degree in Computer Science (2012) at the University of Florence and is still studying to graduate. In October 2013 he started his 1 year Technical Student programme at CERN, working as a web developer in the Indico Team.

Yigit Demirag

Yigit is a MSc. student in Electrical and Electronics Engineering Department of Bilkent University in Turkey. He spent two summers at CERN as Openlab Summer Student and Google Summer of Code Student working on vectorization and SIMD optimization of Random Number Generators on Intel’s Haswell Architecture and on the second generation MIC architecture, Knights Landing. His current research area focuses on designing and fabricating nano devices that mimic synapses of the biological brain. He is passionate about Artificial Intelligence, High Performance Computing and Privacy.