1. Efficient Verifiable Secret Sharing with Share Recovery in BFT Protocols 2019 BFT CCS SecretSharing
    Soumya Basu, Alin Tomescu, Ittai Abraham, Dahlia Malkhi Calibra, Michael K. Reiter, and Emin Gün Sirer
    [View PDF on soumyabasu.com]
    [Show BibTex Citation]

    author = {Basu, Soumya and Tomescu, Alin and Abraham, Ittai and Malkhi, Dahlia and Reiter, Michael K. and Sirer, Emin G\"{u}n},
    title = {Efficient Verifiable Secret Sharing with Share Recovery in BFT Protocols},
    booktitle = {Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security},
    series = {CCS '19},
    year = {2019},
    isbn = {978-1-4503-6747-9},
    location = {London, United Kingdom},
    pages = {2387--2402},
    numpages = {16},
    url = {http://doi.acm.org/10.1145/3319535.3354207},
    doi = {10.1145/3319535.3354207},
    acmid = {3354207},
    publisher = {ACM},
    address = {New York, NY, USA},
    keywords = {byzantine fault tolerance, privacy, secret sharing},

Byzantine fault tolerant state machine replication (SMR) provides powerful integrity guarantees, but fails to provide any privacy guarantee whatsoever. A natural way to add such privacy guarantees is to secret-share state instead of fully replicating it. Such a com- bination would enable simple solutions to difficult problems, such as a fair exchange or a distributed certification authority. However, incorporating secret shared state into traditional Byzantine fault tolerant (BFT) SMR protocols presents unique challenges. BFT protocols often use a network model that has some degree of asynchrony, making verifiable secret sharing (VSS) unsuitable. However, full asynchronous VSS (AVSS) is unnecessary as well since the BFT algorithm provides a broadcast channel. We first present the VSS with share recovery problem, which is the subproblem of AVSS required to incorporate secret shared state into a BFT engine. Then, we provide the first VSS with share recovery solution, KZG-VSSR, in which a failure-free sharing incurs only a constant number of cryptographic operations per replica. Finally, we show how to efficiently integrate any instantiation of VSSR into a BFT replication protocol while incurring only constant overhead. Instantiating VSSR with prior AVSS protocols would require a quadratic communication cost for a single shared value and incur a linear overhead when incorporated into BFT replication. We demonstrate our end-to-end solution via a a private key-value store built using BFT replication and two instantiations of VSSR, KZG-VSSR and Ped-VSSR, and present its evaluation.