Abstrakt. Vi överväger scenarier där två parter, var och en i besittning av en graf, vill beräkna några algoritmer på deras gemensamma graf på ett integritetsbevarande sätt, det vill säga utan att läcka någon information om sina ingångar förutom det som avslöjas av algoritmens utdata. Genom att arbeta i det standardsäkra flerpartsparadigmet presenterar vi nya algoritmer för integritetsbevarande beräkning av APSD (alla par kortaste avstånd) och SSSD (enkel källa kortaste avstånd), samt två nya algoritmer för integritetsbevarande union. Våra algoritmer är betydligt effektivare än generiska konstruktioner. Som i tidigare arbete om integritetsbevarande data mining, visar vi att våra algoritmer är säkra förutsatt att deltagarna är "ärliga, men nyfikna."
REF tillhandahåller integritetsbevarande grafalgoritmer med säkerhet mot passiva motståndare för alla par kortaste avstånd och enkel källa kortaste avstånd.
Privacy-preserving graph algorithms in the semi-honest model
{'venue': 'in: Advances in Cryptology – ASIACRYPT’05, LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}