CISPA
Browse

File(s) not publicly available

Multiparty Cardinality Testing for Threshold Private Intersection

conference contribution
posted on 2023-11-29, 18:18 authored by Pedro Branco, Nico DöttlingNico Döttling, Sihang PuSihang Pu
Threshold Private Set Intersection (PSI) allows multiple parties to compute the intersection of their input sets if and only if the intersection is larger than ????−????, where n is the size of each set and t is some threshold. The main appeal of this primitive is that, in contrast to standard PSI, known upper-bounds on the communication complexity only depend on the threshold t and not on the sizes of the input sets. Current threshold PSI protocols split themselves into two components: A Cardinality Testing phase, where parties decide if the intersection is larger than some threshold; and a PSI phase, where the intersection is computed. The main source of inefficiency of threshold PSI is the former part. In this work, we present a new Cardinality Testing protocol that allows N parties to check if the intersection of their input sets is larger than ????−????. The protocol incurs in ????̃(????????2) communication complexity. We thus obtain a Threshold PSI scheme for N parties with communication complexity ????̃(????????2).

History

Preferred Citation

Pedro Branco, Nico Döttling and Sihang Pu. Multiparty Cardinality Testing for Threshold Private Intersection. In: International Conference on Practice and Theory in Public Key Cryptography (PKC). 2021.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on Practice and Theory in Public Key Cryptography (PKC)

Legacy Posted Date

2022-05-02

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3633, title = "Multiparty Cardinality Testing for Threshold Private Intersection", author = "Branco, Pedro and Döttling, Nico and Pu, Sihang", booktitle="{International Conference on Practice and Theory in Public Key Cryptography (PKC)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC