Researchers at Know-Center and TU Graz are currently developing a successor to the Private Set Intersection (PSI) functionality of the Safe-DEED project. Having data privacy as the main priority, this application provides a flexible interface for Private Set Intersection in a secure environment.

What is Private Set Intersection and where can it be used?

With PSI two or more parties can engage in a protocol that computes an intersection of their respective data sets without ever leaking any information from one side to the other, revealing only the resulting intersection but not items outside of it. Private Set Intersection protocols can be built with various cryptographic building blocks for better optimization according to the specific use-case. One of the most practical applications of PSI is contact discovery for messenger apps, where the user wants to know which of his contacts are also using the messaging service. Here, PSI can solve potential privacy infringements, especially for users with high profile contacts. However, unfortunately, many applications still do not use PSI in this context yet, resorting to clear-text operations or using the weak approach of simply hashing the contacts and comparing hashes. Due to low entropy of phone numbers hashing is not sufficiently secure and these hashes can easily be decoded by brute-force approaches. Another use-case for PSI are calculations for ad effectiveness, where the company serving advertisements to a user wants to calculate how many of these users buy the advertised product. Since the company serving the ads and the company selling the product are two different entities, a direct comparison of all customers with all people might be problematic from a privacy standpoint. Again, PSI can help provide a secure solution here.

Private Set Intersection

Secure and easy PSI with PSIttacus

Building up on ideas and experiences from the Safe-DEED project, this new solution, our library called PSIttacus, is being developed in Rust and even the first prototype versions already vastly outperform its predecessor. Iteration after iteration, the project evolves continuously with new functionality upgrades. The latest version of the PSIttacus library is already in use by project partners and has been integrated into the prototypes for Use-Case #2 – Agile Marketing.

Wait, what is Rust?

Rust has been gaining popularity for the past couple of years as the programming language to go to if you value built-in memory safety and comfortable, no-cost wrappers with performance comparable to C. Various libraries or algorithms have already been rewritten by Rustaceans, enthusiast of the Rust language, more and more “crates” – packages written in Rust – are published every day. While Rust is used in many application fields, cryptography has turned out to be one of the most popular ones, as it allows to write performance-critical code without having to worry about the standard pitfalls of low-level languages such as C.

PSIttacus – A more practical insight

PSI is an actively researched topic and scholars publish new approaches and advancements on current problems continuously.  Based on these advancements different implementations of protocols are being developed under this project. In addition to the PSIttacus library, a binary interface that only requires minor configuration and input data sets is provided. Compared to the previous version written in C++ and Java for Safe-DEED, this Rust implementation performs at least 25 times faster on small sets of 5k entries and is scalable up to millions of entries and more with still reasonable execution times of under 1 minute. This is not only achieved with the base performance of Rust, but also with its straightforward approach to concurrency, which allows to utilize multithreading to speed up the heavy cryptographic calculations by at least 400%. Efforts to improve the library continue, with the main current focus lying on the implementation of additional PSI protocols optimized for different use-cases such as much larger sets or different threat models. The source-code will be released under an open-source licence.