Aarhus University Seal / Aarhus Universitets segl

The Communication Complexity of Threshold Private Set Intersection

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

The Communication Complexity of Threshold Private Set Intersection. / Ghosh, Satrajit; Simkin, Mark.

Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. ed. / Alexandra Boldyreva; Daniele Micciancio. Vol. II Cham : Springer, 2019. p. 3-29 (Lecture Notes in Computer Science, Vol. 11693).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Ghosh, S & Simkin, M 2019, The Communication Complexity of Threshold Private Set Intersection. in A Boldyreva & D Micciancio (eds), Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. vol. II, Springer, Cham, Lecture Notes in Computer Science, vol. 11693, pp. 3-29, 39th Annual International Cryptology Conference, CRYPTO 2019, Santa Barbara, United States, 18/08/2019. https://doi.org/10.1007/978-3-030-26951-7_1

APA

Ghosh, S., & Simkin, M. (2019). The Communication Complexity of Threshold Private Set Intersection. In A. Boldyreva, & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings (Vol. II, pp. 3-29). Springer. Lecture Notes in Computer Science Vol. 11693 https://doi.org/10.1007/978-3-030-26951-7_1

CBE

Ghosh S, Simkin M. 2019. The Communication Complexity of Threshold Private Set Intersection. Boldyreva A, Micciancio D, editors. In Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. Cham: Springer. pp. 3-29. (Lecture Notes in Computer Science, Vol. 11693). https://doi.org/10.1007/978-3-030-26951-7_1

MLA

Ghosh, Satrajit and Mark Simkin "The Communication Complexity of Threshold Private Set Intersection". and Boldyreva, Alexandra Micciancio, Daniele (editors). Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. Cham: Springer. (Lecture Notes in Computer Science, Vol. 11693). 2019, 3-29. https://doi.org/10.1007/978-3-030-26951-7_1

Vancouver

Ghosh S, Simkin M. The Communication Complexity of Threshold Private Set Intersection. In Boldyreva A, Micciancio D, editors, Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. Vol. II. Cham: Springer. 2019. p. 3-29. (Lecture Notes in Computer Science, Vol. 11693). https://doi.org/10.1007/978-3-030-26951-7_1

Author

Ghosh, Satrajit ; Simkin, Mark. / The Communication Complexity of Threshold Private Set Intersection. Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings. editor / Alexandra Boldyreva ; Daniele Micciancio. Vol. II Cham : Springer, 2019. pp. 3-29 (Lecture Notes in Computer Science, Vol. 11693).

Bibtex

@inproceedings{8849a351b8ad420ab7ebe010d1ca88db,
title = "The Communication Complexity of Threshold Private Set Intersection",
abstract = "Threshold private set intersection enables Alice and Bob who hold sets (formula presented) and (formula presented) of size n to compute the intersection (formula presented) if the sets do not differ by more than some threshold parameter t. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of (formula presented). We show that an almost matching upper bound of (formula presented) can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of (formula presented). For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings. Prior to this work, all previous protocols had a communication complexity of (formula presented). Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter t and only logarithmically on the set size n.",
author = "Satrajit Ghosh and Mark Simkin",
year = "2019",
doi = "10.1007/978-3-030-26951-7_1",
language = "English",
isbn = "9783030269500",
volume = "II",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "3--29",
editor = "Alexandra Boldyreva and Daniele Micciancio",
booktitle = "Advances in Cryptology – CRYPTO 2019",
note = "39th Annual International Cryptology Conference, CRYPTO 2019 ; Conference date: 18-08-2019 Through 22-08-2019",

}

RIS

TY - GEN

T1 - The Communication Complexity of Threshold Private Set Intersection

AU - Ghosh, Satrajit

AU - Simkin, Mark

PY - 2019

Y1 - 2019

N2 - Threshold private set intersection enables Alice and Bob who hold sets (formula presented) and (formula presented) of size n to compute the intersection (formula presented) if the sets do not differ by more than some threshold parameter t. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of (formula presented). We show that an almost matching upper bound of (formula presented) can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of (formula presented). For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings. Prior to this work, all previous protocols had a communication complexity of (formula presented). Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter t and only logarithmically on the set size n.

AB - Threshold private set intersection enables Alice and Bob who hold sets (formula presented) and (formula presented) of size n to compute the intersection (formula presented) if the sets do not differ by more than some threshold parameter t. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of (formula presented). We show that an almost matching upper bound of (formula presented) can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of (formula presented). For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings. Prior to this work, all previous protocols had a communication complexity of (formula presented). Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter t and only logarithmically on the set size n.

UR - http://www.scopus.com/inward/record.url?scp=85071502495&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-26951-7_1

DO - 10.1007/978-3-030-26951-7_1

M3 - Article in proceedings

AN - SCOPUS:85071502495

SN - 9783030269500

VL - II

T3 - Lecture Notes in Computer Science

SP - 3

EP - 29

BT - Advances in Cryptology – CRYPTO 2019

A2 - Boldyreva, Alexandra

A2 - Micciancio, Daniele

PB - Springer

CY - Cham

T2 - 39th Annual International Cryptology Conference, CRYPTO 2019

Y2 - 18 August 2019 through 22 August 2019

ER -