A new efficient authorized private set intersection protocol from Schnorr signature and its applications

Private set intersection (PSI) has been proposed to achieve sharing sensitive information with privacy, which allows two participators to compute the intersection of their private sets without revealing any other information. Authorized private set intersection (APSI) is a variant of PSI such that APSI requires client sets for intersection must be authorized. Although many schemes have been proposed for linear optimization in the existing APSI publications, how to linearly optimize the APSI protocol based on the Schnorr signature has not been proposed yet. In this paper, we propose a new efficient APSI protocol with linear complexity (denoted by LC-APSI) from the Schnorr signature. LC-APSI is proven secure in the random oracle model by assuming the intractability of the gap Diffie-Hellman problem. Apart from the existed efficient APSI protocols based on RSA and IBE, the new proposal fills up the technical extensions and applications of APSI. In particular, our proposal on sharing sensitive information is also instantiatedwhich can be used to the practical applications in cloud computing or outsourced data sharing.