Paper 2020/385

Two-Sided Malicious Security for Private Intersection-Sum with Cardinality

Peihan Miao, Sarvar Patel, Mariana Raykova, Karn Seth, and Moti Yung


Private intersection-sum with cardinality allows two parties, where each party holds a private set and one of the parties additionally holds a private integer value associated with each element in her set, to jointly compute the cardinality of the intersection of the two sets as well as the sum of the associated integer values for all the elements in the intersection, and nothing beyond that. We present a new construction for private intersection sum with cardinality that provides malicious security with abort and guarantees that both parties receive the output upon successful completion of the protocol. A central building block for our constructions is a primitive called shuffled distributed oblivious PRF (DOPRF), which is a PRF that offers oblivious evaluation using a secret key shared between two parties, and in addition to this allows obliviously permuting the PRF outputs of several parallel oblivious evaluations. We present the first construction for shuffled DOPRF with malicious security. We further present several new sigma proof protocols for relations across Pedersen commitments, ElGamal encryptions, and Camenisch-Shoup encryptions that we use in our main construction, for which we develop new batching techniques to reduce communication. We implement and evaluate the efficiency of our protocol and show that we can achieve communication cost that is only 4-5 times greater than the most efficient semi-honest protocol. When measuring monetary cost of executing the protocol in the cloud, our protocol is 25 times more expensive than the semi-honest protocol. Our construction also allows for different parameter regimes that enable trade-offs between communication and computation.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Private Intersection-SumMalicious SecurityDistributed Oblivious PRFBatching Techniques
Contact author(s)
peihan @ berkeley edu
sarvar @ google com
marianar @ google com
karn @ google com
moti @ google com
2020-06-19: revised
2020-04-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Peihan Miao and Sarvar Patel and Mariana Raykova and Karn Seth and Moti Yung},
      title = {Two-Sided Malicious Security for Private Intersection-Sum with Cardinality},
      howpublished = {Cryptology ePrint Archive, Paper 2020/385},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.