| Modern society is increasingly dependent on (and fearful of) massive amounts and availability of electronic information. There are numerous everyday scenarios where sensitive data must be --- sometimes reluctantly or suspiciously --- shared between entities without mutual trust. This prompts the need for mechanisms to enable limited (privacy-preserving) information sharing. A typical scenario involves two parties: one seeks information from the other, that is either motivated, or compelled, to share only the requested information. We define this problem as privacy-preserving sharing of sensitive information and are confronted with two main technical challenges: (1) how to enable this type of sharing such that parties learn no information beyond what they are entitled to, and (2) how to do so efficiently, in real-world practical terms.;This dissertation presents a set of efficient and provably secure cryptographic protocols for privacy-preserving sharing of sensitive information. In particular, Private Set Intersection (PSI) techniques are appealing whenever two parties wish to compute the intersection of their respective sets of items without revealing to each other any other information (beyond set sizes). We motivate the need for PSI techniques with various features and illustrate several concrete variants that offer significantly higher efficiency than prior work. Then, we introduce the concepts of Authorized Private Set Intersection (APSI) and Size-Hiding Private Set Intersection (SHI-PSI). The former ensures that each set element is authorized (signed) by some mutually trusted authority and prevents arbitrary input manipulation. The latter hides the size of the set held by one of the two entities, thus, applying to scenarios where both set contents and set size represent sensitive information.;Finally, we investigate the usage of proposed protocols in the context of a few practical applications. We build a toolkit for sharing of sensitive information, that enables (practical) privacy-preserving database querying. Furthermore, motivated by the fast-growing proliferation of personal wireless computing devices and associated privacy issues, we design a set of collaborative applications involving several participants willing to share information in order to cooperatively perform operations without endangering their privacy. |
