Mă voi concentra pe securitatea semi-onest în acest răspuns. Puteți împărți protocoalele PSI relevante în două categorii:
În Bazat pe Diffie-Hellman protocoale (originare în Huberman-Franklin-Hogg), părțile trebuie să calculeze câteva exponențiații pentru fiecare articol din seturile lor.
În Bazat pe transferul ignorant protocoale (cele principale în acest caz ar fi KKRT și Chase-Miao), părțile efectuează mai întâi câteva sute de OT de bază (fiecare necesitând câteva exponențieri), indiferent de dimensiunea setului lor PSI. Tot ceea ce vine mai târziu în protocol folosește doar operațiuni cu chei simetrice mult mai eficiente, cum ar fi apelurile către AES/SHA.
Abordarea Diffie-Hellman are invariabil costuri de comunicare mai mici, indiferent cât de mari sunt seturile PSI. Și atunci când seturile PSI sunt mici, timpul pentru a efectua câteva exponențiații per element este mai mic decât timpul pentru a efectua „OT de bază” ale celorlalte protocoale. În general, Diffie-Hellman PSI pentru seturi mici este o regulă grozavă.
Dar cât de mic este? Menționați seturi care conțin ~1000 de articole. Cu seturi de această dimensiune, nu mai este absolut clar care protocol este cel mai bun. În experimentele pe care le-am desfășurat în grupul nostru de cercetare, limita (unde protocoalele bazate pe OT devin mai rapide) este chiar sub 500 de articole pe rețele foarte rapide și puțin peste 1000 de articole pe rețele foarte lente.Dar chiar și în rețelele rapide, diferența de performanță nu este de ce să te agăți pentru această aplicație: vorbim de 0,35 vs 0,25 secunde pentru a efectua PSI.
În concluzie, Aș recomanda implementarea protocolului Diffie-Hellman PSI a lui Huberman-Franklin-Hogg, deoarece (1) timpul de rulare este suficient de aproape de cel mai mic; (2) comunicarea este cea mai scăzută; (3) simplitatea protocolului îl face mai ușor de implementat.
Editare decembrie 2021: Am publicat recent un îmbunătățirea protocolului Huberman-Franklin-Hogg pentru PSI pe seturi mici. Este mai rapid, utilizează mai puțină comunicare și are o securitate mai puternică (răușitoare). Aceasta ar fi ultima mea recomandare.
Pentru a răspunde la întrebarea dvs. despre PSI cu mai multe părți: acum este destul de ușor să convertiți majoritatea protocoalelor PSI cu două părți în mai multe părți.
Majoritatea protocoalelor PSI sunt construite dintr-un PRF ignorant subiacent (în Diffie-Hellman PSI, PRF ignorant este $x \mapsto H(x)^k$ Unde $H$ este un oracol aleatoriu). În KMPRT am arătat cum să construim PSI multipartit din OPRF cu două părți. Una dintre construcții este securizată împotriva adversarilor semi-cinstiți, iar cealaltă are o proprietate de securitate cu litere mai mici. Într-o hârtie care va apărea la Crypto 2021, arătăm că această a doua construcție este de fapt sigură împotriva adversarilor rău intenționați.
În general, PSI cu mai multe părți implică în esență fiecare parte să efectueze o PSI cu două părți modificată cu o parte centrală (cel care primește rezultatul).
