A private set operation ( \(\textsf {PSO}\) ) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a client to securely outsource their dataset to cloud storage, and then when needed, securely issue main set operations, such as union, intersection, and difference, to the server, and receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the \(\textsf {PSO}\) schemes, named \(\textsf {naSIM}\) , is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security notions has been raised as an open problem. In this paper, we propose a new security notion for the \(\textsf {PSO}\) schemes, called \(\textsf {aIND}\) , and show that this concept is stronger than \(\textsf {naSIM}\) . Furthermore, we propose a new \(\textsf {PSO}\) construction that satisfies the security notion \(\textsf {aIND}\) . We also show that, despite covering a much higher level of security, the computational and storage overheads of our construction are comparable to the most efficient existing \(\textsf {PSO}\) scheme, and in relation to other available schemes, it exhibits a reduction of at least \(73\%\) in overheads. Evaluating and updating cryptographic schemes to adapt to fast processing in cloud environments are recognized as a necessity in the literature. However, previous \(\textsf {PSO}\) schemes have paid less attention to this issue. In this paper, we address this necessity and show that by using parallelization techniques, the computational overheads of encryption and set operations can be reduced by \(50\%\) and \(74\%\) , respectively.
