TY - GEN
T1 - On the communication complexity of privacy-preserving information sharing protocols
AU - Zhang, Nan
PY - 2007/1/1
Y1 - 2007/1/1
N2 - We address issues related to privacy protection in distributed information sharing systems where multiple autonomous entities share data across their private databases. Most existing solutions place restrictions on adversarial behavior in order to enable communication-efficient privacy-preserving information sharing. These restrictions substantially underestimate the capabilities of adversaries in reality, and do not always suffice for real systems. We consider a threat space containing more powerful adversaries, including not only semihonest but also malicious ones, and analyze the tradeoff between privacy protection and communication complexity in information sharing. In particular, we use Kolmogorov complexity to derive lower bounds on the communication complexity required to defend against various kinds of adversaries.
AB - We address issues related to privacy protection in distributed information sharing systems where multiple autonomous entities share data across their private databases. Most existing solutions place restrictions on adversarial behavior in order to enable communication-efficient privacy-preserving information sharing. These restrictions substantially underestimate the capabilities of adversaries in reality, and do not always suffice for real systems. We consider a threat space containing more powerful adversaries, including not only semihonest but also malicious ones, and analyze the tradeoff between privacy protection and communication complexity in information sharing. In particular, we use Kolmogorov complexity to derive lower bounds on the communication complexity required to defend against various kinds of adversaries.
UR - http://www.scopus.com/inward/record.url?scp=34748842035&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34748842035&partnerID=8YFLogxK
U2 - 10.1109/isi.2007.379487
DO - 10.1109/isi.2007.379487
M3 - Conference contribution
AN - SCOPUS:34748842035
SN - 1424413303
SN - 9781424413300
T3 - ISI 2007: 2007 IEEE Intelligence and Security Informatics
SP - 289
EP - 295
BT - ISI 2007
PB - IEEE Computer Society
T2 - ISI 2007: 2007 IEEE Intelligence and Security Informatics
Y2 - 23 May 2007 through 24 May 2007
ER -