Paper 2022/1482

Multi-Point HashDH OPRF using Multiplicative Blinding with Application to Private Set Intersection

Abstract

The privacy set intersection (PSI) protocol with the oblivious pseudorandom function (OPRF) as the core component is a crucial member of PSI family, and the most efficient PSI protocol at present also belongs to this category. Based on DDH assumption, Hash Diffie-Hellman (HashDH) PSI is one of the most classical PSI protocols. Benefiting by its low communication overhead, it still has tremendous research value today. The OPRF subprotocol at the bottom of classical DH-PSI protocol falls into the abstract blind-query-de-blinding OPRF paradigm, while employs the exponential blinding (Exp-HashDH) method. An alternative method called multiplication blinding (Mult-HashDH) offers the improvement which the exponential blinding can't give in performance. This method substitutes multiple variable-base exponentiations with fixed-base exponentiations, and by taking full advantage of this outstanding feature and pre-computation, the computational efficiency of the client can be at least doubled. However, neither Mult-HashDH OPRF nor Mult-HashDH PSI can give a strict security proof under the semi-honest model, which makes the security of the scheme is now reeling from a crisis of confidence. In this paper, the security proof of a modified Mult-HashDH OPRF is formally given under the semi-honest model, and then the HashDH PSI protocol is constructed based on it, which not only ensures the security of the scheme but also have no influence on damaging the efficiency of the protocol. the experimental comparison shows that our protocol achieves 2.65−13.20× speedup in running time.