Graduate School and Research Center in Digital Sciences

Breaking and fixing the security proof of garbled bloom filters

Van Rompay, Cédric; Önen, Melek

DBSEC 2018, 32nd Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy, July 16-18, 2018, Bergamo, Italy / Also published in Lecture Notes in Computer Science, Vol.10980

We identify a flaw in the proof of security of Garbled Bloom Filters, a recent hash structure introduced by Dong et al. (ACM CCS 2013) that is used to design Private Set Intersection (PSI) protocols, a important family of protocols for secure cloud computing. We give counter-examples invalidating a claim that is central to the original proof and we show that variants of the GBF construction have the same issue in their security analysis.We then give a new proof of security that shows that Garbled Bloom Filters are secure nonetheless.

Document Doi Bibtex

Title:Breaking and fixing the security proof of garbled bloom filters
Keywords:garbled bloom filter, private set intersection, provable security
Type:Conference
Language:English
City:Bergamo
Country:ITALY
Date:
Department:Digital Security
Eurecom ref:5605
Copyright: © Springer. Personal use of this material is permitted. The definitive version of this paper was published in DBSEC 2018, 32nd Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy, July 16-18, 2018, Bergamo, Italy / Also published in Lecture Notes in Computer Science, Vol.10980 and is available at : http://dx.doi.org/10.1007/978-3-319-95729-6_17
Bibtex: @inproceedings{EURECOM+5605, doi = {http://dx.doi.org/10.1007/978-3-319-95729-6_17}, year = {2018}, title = {{B}reaking and fixing the security proof of garbled bloom filters}, author = {{V}an {R}ompay, {C}{\'e}dric and {\"{O}}nen, {M}elek}, booktitle = {{DBSEC} 2018, 32nd {A}nnual {IFIP} {WG} 11.3 {C}onference on {D}ata and {A}pplications {S}ecurity and {P}rivacy, {J}uly 16-18, 2018, {B}ergamo, {I}taly / {A}lso published in {L}ecture {N}otes in {C}omputer {S}cience, {V}ol.10980}, address = {{B}ergamo, {ITALY}}, month = {07}, url = {http://www.eurecom.fr/publication/5605} }
See also: