Academic
Publications
Practical Private Set Intersection Protocols with Linear Complexity

Practical Private Set Intersection Protocols with Linear Complexity,10.1007/978-3-642-14577-3_13,Emiliano De Cristofaro,Gene Tsudik

Practical Private Set Intersection Protocols with Linear Complexity   (Citations: 10)
BibTex | RIS | RefWorks Download
The constantly increasing dependence on anytime-anywhere availability of data and the commensurately increasing fear of losing privacy motivate the need for privacy-preserving techniques. One interesting and common problem occurs when two parties need to privately compute an intersection of their respective sets of data. In doing so, one or both parties must obtain the intersection (if one exists), while neither should learn anything about other set elements. Although prior work has yielded a number of effective and elegant Private Set Intersection (PSI) techniques, the quest for efficiency is still underway. This paper explores some PSI variations and constructs several secure protocols that are appreciably more efficient than the state-of-the-art.
Conference: Financial Cryptography , pp. 143-159, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In contrast, [11] shows the overhead of only 6 seconds for computing private set intersection for two sets with 5,000 items (on comparable hardware), using specialized PSI tools...
    • ...They replace OPRF-s with unpredictable functions [25] and blind signatures [11]...
    • ...Hiding Overhead Exp-s Exp-s Length [13] Std HbC No O(w+v) O(w(log log v)) O(w+v) Short [20] Std Mal No O(w+v) O(w(log log v)) O(w+v) Short [27] Std HbC No O(w+v) O(w · v) O(w+v) Long [24] Std Mal No O(w+v) O(w+v) O(v) Long [25] ROM Mal No O(w+v) O(w+v) O(v) Short [11] (Fig.3) ROM HbC No O(w+v) O(w+v) O(v) Short [11] (Fig.4) ROM HbC(*) No O(w+v) O(w+v) O(v) mults Long [10] ROM Mal No O(w+v) O(w+v) O(v) Short...
    • ...Hiding Overhead Exp-s Exp-s Length [13] Std HbC No O(w+v) O(w(log log v)) O(w+v) Short [20] Std Mal No O(w+v) O(w(log log v)) O(w+v) Short [27] Std HbC No O(w+v) O(w · v) O(w+v) Long [24] Std Mal No O(w+v) O(w+v) O(v) Long [25] ROM Mal No O(w+v) O(w+v) O(v) Short [11] (Fig.3) ROM HbC No O(w+v) O(w+v) O(v) Short [11] (Fig.4) ROM HbC(*) No O(w+v) O(w+v) O(v) mults Long [10] ROM Mal No O(w+v) O(w+v) O(v) Short...

    Giuseppe Atenieseet al. (If) Size Matters: Size-Hiding Private Set Intersection

    • ...In PL-1, each sub-protocol (between P1 and Pi) relates to the two-party PSI problem [7], [9], [10], while the PL-2 relates to two-party PCSI [7], [9], [11]...
    • ...Recently in [10], Cristofaro and Tsudik proposed a construction of PSI based on blind RSA signatures...
    • ...We compare our basic and advanced schemes with existing schemes, FC10 (PSI) [10] and FNP (PCSI under HBC model) [7], respectively...
    • ...Party Basic scheme FC10 (PSI) [10] Advanced scheme FNP (PCSI) [7]...
    • ...Schemes Basic Advanced FC10 [10] Agrawal [22] FNP [7] CANS09 [18] CANS09 [18] Category PSI PCSI PSI PSI/PCSI PSI/PCSI PSI PCSI Security Uncond./HBC (PL-1) PL-2/HBC ROM/HBC ROM/HBC Standard/HBC Uncond./HBC Uncond./HBC...

    Ming Liet al. FindU: Privacy-preserving personal profile matching in mobile social n...

    • ...Previous work has attempted to address this problem by using distributed cryptographic primitives, such as generic Secure Multi-Party Computation [15] or Private Set Intersection (PSI) [11], [23], [8], [19], [7]...
    • ...Thus far, however, only solutions limited to the twoparty set intersection have achieved practical efficiency [11], [23], [8], [19], [7]...

    Emiliano De Cristofaroet al. Reclaiming privacy for smartphone applications

    • ...Privacy-preserving scheduling problems have been extensively studied in the past by researchers from the theoretical perspective, for instance, by modeling them as set intersection problems [20, 11], distributed constraint satisfaction problems [27, 28, 24, 25], secure multi-party computation problems [18, 12] and by framing them in the e-voting con-...
    • ...In the literature, the four most relevant bodies of work that address privacy in scheduling or similar scenarios are based on techniques from private set-intersection [20, 11], distributed constraint satisfaction [27, 28, 24, 25], secure multi-party computation [18, 12] and e-voting [19]...
    • ...De Cristofaro and Tsudik [11] provide efficient variations of private-set intersection protocols and present a comparison in terms of computational and communication complexity, adversarial model and privacy...

    Igor Bilogrevicet al. Privacy-preserving activity scheduling on mobile devices

    • ...This variant is called “Authorized Private Set Intersection” (APSI) in [DT10]...
    • ...Other results (such as [DT10]) construct linear-complexity PSI and APSI protocols secure in the semi-honest model, under assumptions of the one-more-XXX type [BNPS03], with much lower computational and communication complexity...
    • ...(Note that we overview prior work in Section 2). As shown in [DT10], via both analysis and experiments, there is an appreciable efficiency gap between the two “families” of PSI/APSI protocols: those secure in the malicious and in the semi-honest models...
    • ...Our starting point are the linear-complexity protocols from [DT10] (specifically,...
    • ...First, we modify the APSI construct of [DT10] and obtain APSI protocol secure in the malicious model, under the standard RSA assumption (in ROM)...
    • ...Then, we modify its PSI counterpart: while the linear-complexity PSI protocol in [DT10] is secure under the One-More-Gap-DH assumption [BNPS03] against semi-honest parties, our modified variant is secure in the malicious model under the standard DDH assumption (again, in ROM)...
    • ...In another recent result, [DT10] (Fig.4) presents an adaptive PSI protocol based on blind-RSA signatures [Cha83], secure in the semi-honest model, under the One-More-RSA assumption [BNPS03], in ROM...
    • ...[DT10] (Fig.3) includes another PSI secure in the presence of semi-honest adversaries, under the One-More-Gap-DH assumption, in ROM...
    • ...Authorized Private Set Intersection (APSI) is defined in [DT10] to extend PSI to support authorization of client inputs...
    • ...[DT10] shows that the PSI protocol in its Fig.3 (reviewed at the end of Section 2.1) can be instantiated in a RSA setting, where client input is a set of RSA signatures and the server obliviously verifies them by modifying the protocol as follows...
    • ...We start from the APSI protocol of [DT10] (reviewed in Section 2.2), secure in the semi-honest model...
    • ...Our APSI protocol differs from the one in [DT10] in the following: ‐ We modify inputs to the protocol and add efficient zero-knowledge proofs to prevent client and server from deviating from the protocol and to enable extraction of inputs...
    • ...It is a modified version of the PSI protocol of [DT10] (reviewed in Section 2.1), secure in the semi-honest model under the One-More-Gap-DH assumption (in ROM)...
    • ...Also, we specify whether they can support the extension for data transfer – a PSI variant introduced in [DT10] and discussed in details in the extended version of the paper [DKT10]...
    • ...Fig.3 of One-More O(w + v) O(w + v) O(v) [DT10] Gap-DH exps exps Fig.4 of One-More O(w + v) O(w + v) O(v) [DT10] RSA exps mults...
    • ...Fig.3 of One-More O(w + v) O(w + v) O(v) [DT10] Gap-DH exps exps Fig.4 of One-More O(w + v) O(w + v) O(v) [DT10] RSA exps mults...

    Emiliano De Cristofaroet al. Linear-Complexity Private Set Intersection Protocols Secure in Malicio...

Sort by: