Paper 2011/509

Policy-Enhanced Private Set Intersection: Sharing Information While Enforcing Privacy Policies

Emil Stefanov, Elaine Shi, and Dawn Song

Abstract

Companies, organizations, and individuals often wish to share information to realize valuable social and economic goals. Unfortunately, privacy concerns often stand in the way of such information sharing and exchange. This paper proposes a novel cryptographic paradigm called Policy-Enhanced Private Set Intersection (PPSI), allowing two parties to share information while enforcing the desired privacy policies. Our constructions require minimal additional overhead over traditional Private Set Intersection (PSI) protocols, and yet we can handle rich policy semantics previously not possible with traditional PSI and Authorized Private Set Intersection (APSI) protocols. Our scheme involves running a standard PSI protocol over carefully crafted encodings of elements formed as part of a challenge-response mechanism. The structure of these encodings resembles techniques used for aggregating BLS signatures in bilinear groups. We prove that our scheme is secure in the malicious model, under the CBDH assumption, the random oracle model, and the assumption that the underlying PSI protocol is secure against malicious adversaries.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
authorized private set intersectionmultiple authoritiesrich
Contact author(s)
emil @ berkeley edu
History
2011-09-18: received
Short URL
https://ia.cr/2011/509
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/509,
      author = {Emil Stefanov and Elaine Shi and Dawn Song},
      title = {Policy-Enhanced Private Set Intersection: Sharing Information While Enforcing Privacy Policies},
      howpublished = {Cryptology ePrint Archive, Paper 2011/509},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/509}},
      url = {https://eprint.iacr.org/2011/509}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.