Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Journal article
Title: Efficient and secure protocols for privacy-preserving set operations
Author: Sang, Y.
Shen, H.
Citation: ACM Transactions on Information and System Security, 2009; 13(9):1-35
Publisher: Association for Computing Machinery, Inc.
Issue Date: 2009
ISSN: 1094-9224
Statement of
Yingpeng Sang and Hong Shen
Abstract: Many applications require performing set operations without publishing individual datesets. In this article, we address this problem for five fundamental set operations including set intersection, cardinality of set intersection, element reduction, overthreshold set-union, and subset relation. Our protocols are obtained in the universally composable security framework, in the assumption of the probabilistic polynomial time bounded adversary, which actively controls a fixed set of t parties and the assumption of an authenticated broadcast channel. Our constructions utilize building blocks of nonmalleable NonInteractive Zero-Knowledge (NIZK) arguments, which are based on a (t + 1,N)-threshold version (N is the number of parties in the protocol) of the boneh-goh-nissim (BGN) cryptosystem whose underlying group supports bilinear maps, in the assumption that the public key and shares of the secret key have been generated by a trusted dealer. The previous studies were all based on the stand-alone model with the same assumptions on the adversary, broadcast channel, and key generation. For the first four operations, we propose protocols that improve the previously known results by an O(N) factor in the computation and communication complexities. For the subset relation, our protocol is the first one secure against the active adversary. Our constructions of NIZK have independent interest in that, though also mentioned as building blocks, the previous work did not illustrate how to construct them. We construct these NIZK with an additional nonmalleable property, the same complexity as claimed in the previous work, and also an improvement on the communication complexity.
Keywords: Bilinear groups; cryptographic protocol; noninteractive zeroknowledge argument; privacy preservation; set operations
RMID: 0020093813
DOI: 10.1145/1609956.1609965
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.