1. Secure parallel computation on national scale volumes of data 2020 DifferentialPrivacy MPC Usenix
    Sahar Mazloom, Phi Hung Le, Samuel Ranellucci, and Dov Gordon
    [View PDF on usenix.org]
    [Show BibTex Citation]

    @inproceedings {247676,
    title = {Secure parallel computation on national scale volumes of data},
    booktitle = {29th {USENIX} Security Symposium ({USENIX} Security 20)},
    year = {2020},
    address = {Boston, MA},
    url = {https://www.usenix.org/conference/usenixsecurity20/presentation/mazloom},
    publisher = {{USENIX} Association},
    month = aug,

We revisit the problem of performing secure computation of graph-parallel algorithms, focusing on the applications of securely outsourcing matrix factorization, and histograms. Leveraging recent results in low-communication secure multi-party computation, and a security relaxation that allows the computation servers to learn some differentially private leakage about user inputs, we construct a new protocol that reduces overall runtime by 320X, reduces the number of AES calls by 750X , and reduces the total communication by 200X . Our system can securely compute histograms over 300 million items in about 4 minutes, and it can perform sparse matrix factorization, which is commonly used in recommendation systems, on 20 million records in about 6 minutes. Furthermore, in contrast to prior work, our system is secure against a malicious adversary that corrupts one of the computing servers.