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

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

##### Abstract

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)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Keywords
Private Intersection-SumMalicious SecurityDistributed Oblivious PRFBatching Techniques
Contact author(s)
peihan @ berkeley edu
History
2020-06-19: revised
See all versions
Short URL
https://ia.cr/2020/385

CC BY

BibTeX

@misc{cryptoeprint:2020/385,
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{https://eprint.iacr.org/2020/385}},
url = {https://eprint.iacr.org/2020/385}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.