A new multi-party private set intersection protocol based on OPRFs

Abstract

In many crucial real-world applications, parties must jointly perform some secure multi-party computation (MPC) while keeping their inputs hidden from other parties. Private Set Intersection (PSI), the specific area of Multi-Party Computation, let the parties learn the intersection of their private data sets without sharing their secret data with others. For instance, a smartphone user downloads a messaging application, naturally, he wants to discover who are the other contacts that are using the same application. The naive and insecure solution is to send all contacts to the server to discover them. However, the user does not want to share his contacts with the application for privacy issues. To handle this, in recent years, companies and organizations start to use PSI to enhance privacy and security with a little cost of communication and computation. In this paper, we introduce a novel method to compute Private Set Intersection with multi parties where there are at least three or more parties participating in the protocol. By employing the Zero-Secret Sharing scheme and Oblivious Pseudo-Random Functions (OPRFs), parties securely calculate the intersection with computational and communication complexities which are both linear in the number of parties.

Birçok önemli gerçek dünya uygulamasında, taraflar girdilerini diğer taraflardan gizli tutarken bazı güvenli çok taraflı hesaplama (MPC) işlemlerini birlikte yapmalıdır. Çok Taraflı Hesaplamanın özel alanı olan Özel Set Kesişimi (PSI), tarafların gizli verilerini başkalarıyla paylaşmadan veri kümelerinin kesişimini öğrenmelerini sağlar. Örneğin, bir akıllı telefon kullanıcısı bir mesajlaşma uygulaması indirir, doğal olarak aynı uygulamayı kullanan diğer kişilerin kim olduğunu keşfetmek ister. Naif ve güvensiz çözüm, tüm kişileri, sunucuya göndermek ve kim olduklarını keşfetmektir. Ancak kullanıcı, gizlilik sorunları için uygulama ile temaslarını paylaşmak istemezler. Bunu halletmek için, son yıllarda şirketler ve kuruluşlar, küçük bir iletişim ve hesaplama maliyetiyle gizliliği ve güvenliği artırmak için PSI kullanmaya başladılar. Bu makalede, protokole en az üç veya daha fazla tarafın katıldığı çoklu taraflarla Özel Set Kesişimi hesaplamak için yeni bir yöntem tanıtıyoruz. Taraflar, Sıfır Gizli Paylaşım ve Habersiz Sözde Rastgele Fonksiyonları kullanarak, her ikisi de kullanıcı sayısı ile doğrusal olan hesaplama ve iletişim karmaşıklıklarıyla kesişimi güvenli bir şekilde hesaplar.