Cryptology ePrint Archive: Report 2020/407

Feather: Lightweight Multi-party Updatable Delegated Private Set Intersection

Aydin Abadi and Sotirios Terzis and Changyu Dong

Abstract: With the growth of cloud computing, the need arises for Private Set Intersection (PSI) protocols that can operate on outsourced data and delegate computation to cloud servers. One limitation of existing delegated PSI protocols is that they are all designed for static data and do not allow efficient update on outsourced data. Another limitation is that they cannot efficiently support PSI among multiple clients, which is often needed in practice. This paper presents “Feather”, the first delegated PSI protocol that supports efficient data updates and scalable multi-party PSI computation on outsourced datasets. The clients can independently prepare and upload their private data to the cloud once, then delegate the computation an unlimited number of times. The update operation has O(1) communication and computation complexity, and this is achieved without sacrificing PSI efficiency and security. Feather does not use public key cryptography, that makes it more scalable. We have implemented a prototype and compared the concrete performance against the state of the art. The evaluation indicates that Feather does achieve better performance in both update and PSI computation.

Category / Keywords: cryptographic protocols / Private Set Intersection, Cloud Computing, Cryptographic Protocols, Multi-party Computation

Date: received 10 Apr 2020, last revised 3 May 2020

Contact author: aydin abadi at ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200503:151939 (All versions of this report)

Short URL: ia.cr/2020/407


[ Cryptology ePrint archive ]