TY - GEN
T1 - Simple, Fast Malicious Multiparty Private Set Intersection
AU - Nevo, Ofri
AU - Trieu, Ni
AU - Yanai, Avishay
N1 - Publisher Copyright:
© 2021 ACM.
PY - 2021/11/12
Y1 - 2021/11/12
N2 - We address the problem of multiparty private set intersection against a malicious adversary. First, we show that when one can assume no collusion amongst corrupted parties then there exists an extremely efficient protocol given only symmetric-key primitives. Second, we present a protocol secure against an adversary corrupting any strict subset of the parties. Our protocol is based on the recently introduced primitives: oblivious programmable PRF (OPPRF) and oblivious key-value store (OKVS). Our protocols follow the client-server model where each party is either a client or a server. However, in contrast to previous works where the client has to engage in an expensive interactive cryptographic protocol, our clients need only send a single key to each server and a single message to a pivot party (where message size is in the order of the set size). Our experiments show that the client's load improves by up to 10x (compared to both semi-honest and malicious settings) and that factor increases with the number of parties. We implemented our protocol and conducted an extensive experiment over both LAN and WAN and up to 32 parties with up to $2^20 $ items each. We provide a comparison of the performance of our protocol and the state-of-the-art for both the semi-honest setting (by Chandran et al.) and the malicious setting (by Ben Efraim et al. and Garimella et al.).
AB - We address the problem of multiparty private set intersection against a malicious adversary. First, we show that when one can assume no collusion amongst corrupted parties then there exists an extremely efficient protocol given only symmetric-key primitives. Second, we present a protocol secure against an adversary corrupting any strict subset of the parties. Our protocol is based on the recently introduced primitives: oblivious programmable PRF (OPPRF) and oblivious key-value store (OKVS). Our protocols follow the client-server model where each party is either a client or a server. However, in contrast to previous works where the client has to engage in an expensive interactive cryptographic protocol, our clients need only send a single key to each server and a single message to a pivot party (where message size is in the order of the set size). Our experiments show that the client's load improves by up to 10x (compared to both semi-honest and malicious settings) and that factor increases with the number of parties. We implemented our protocol and conducted an extensive experiment over both LAN and WAN and up to 32 parties with up to $2^20 $ items each. We provide a comparison of the performance of our protocol and the state-of-the-art for both the semi-honest setting (by Chandran et al.) and the malicious setting (by Ben Efraim et al. and Garimella et al.).
UR - http://www.scopus.com/inward/record.url?scp=85119359612&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85119359612&partnerID=8YFLogxK
U2 - 10.1145/3460120.3484772
DO - 10.1145/3460120.3484772
M3 - Conference contribution
AN - SCOPUS:85119359612
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 1151
EP - 1165
BT - CCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 27th ACM Annual Conference on Computer and Communication Security, CCS 2021
Y2 - 15 November 2021 through 19 November 2021
ER -