Private set intersection (PSI) is a cryptographic technique enabling two parties to compute the intersection of their private sets without revealing anything else. In this work, we review the bottleneck of FHE-based PSI and propose novel protocols to mitigate the overhead. Specifically, we expand upon and propose a novel and efficient protocol, named Polynomial Multiplication Triples \(\prod _{\text {PMT}}\) , which processes various applications. Subsequently, we devise an optimized PSI protocol based on our new protocol \(\prod _{\text {PMT}}\) , ensuring security against semi-honest adversaries. Experimentation demonstrates that our protocols process a better performance. Compared to the basic protocol \(\prod _{\text {PMT}}\) , our improved protocol \(\prod _{\text {PMT}}\) has better computational performance. For instance, the improved protocol \(\prod _{\text {PMT}}\) is \(28.175\times \) better for set size \(2^{20}\) . Compared to previous state-of-the-art PSI protocols that have a similar communication cost in the online phase, our running-time-optimized protocol has better computational performance. For instance, our online computation is 4.72–19.43 \(\times \) and 1.48–30.3 \(\times \) better than [10] and [48], respectively.