Abstrakt. Vi anser att problemet med att beräkna skärningspunkten mellan privata dataset för två parter, där dataseten innehåller listor över element som tagits från en stor domän. Detta problem har många tillämpningar för online-samarbete. Vi presenterar protokoll, baserat på användningen av homomorphic kryptering och balanserad hashing, för både semi-hedest och skadliga miljöer. För listor över längd k, vi få O(k) kommunikation overhead och O(k ln ln k) beräkning. Protokollet för semihonest miljön är säker i standardmodellen, medan protokollet för den skadliga miljön är säker i den slumpmässiga oracle modellen. Vi överväger också problemet med att tillnärma storleken på skärningspunkten, visa en linjär lägre band för kommunikationen overhead för att lösa detta problem, och ge en lämplig säker protokoll. Slutligen undersöker vi andra varianter av matchningsproblemet, inklusive att utvidga protokollet till flerpartsinställningen samt att överväga problemet med ungefärlig matchning.
Freedman m.fl. REF tar hänsyn till problemet med att beräkna skärningspunkten mellan privata datamängder mellan två parter och analysera deras protokoll under ett antal hotmodeller.
Efficient Private Matching and Set Intersection
{'venue': 'EUROCRYPT', 'journal': None, 'mag_field_of_study': ['Computer Science']}