| Paper ID | D3-S2-T4.2 |
| Paper Title |
FastShare: Scalable Secret Sharing by Leveraging Locality |
| Authors |
Swanand Kadhe, Nived Rajaraman, Kannan Ramchandran, University of California Berkeley, United States |
| Session |
D3-S2-T4: Multi-Party Computation I |
| Chaired Session: |
Wednesday, 14 July, 22:20 - 22:40 |
| Engagement Session: |
Wednesday, 14 July, 22:40 - 23:00 |
| Abstract |
Shamir's secret sharing scheme is widely used in many cryptographic protocols such as secure multi-party computation. It allows a secret to be distributed to $n$ parties such that any $t$ parties learn no information about the secret, whereas any $t+1$ parties can recover the secret. However, the 'worst-case' recovery guarantees come at the price of $O(n^2)$ computation cost. This quadratic cost limits its scalability to applications involving only a small number of participants. This paper presents a framework, called FastShare, for designing scalable secret sharing schemes that ensure 'worst-case' security guarantees at a lower computation cost by relaxing the recovery constraint from worst-case to 'average-case' in a statistical sense. In particular, FastShare considers the setup where each party takes part in the recovery process with some probability $\rho$, independently of others. The core idea of FastShare is to construct a `signal' using the secret and random masks by inserting zeros at judiciously chosen locations, and take its finite field fast Fourier transform (FFT) to generate the shares. We present a scheme designed using FastShare where the judicious zero placement ensures that the shares form a codeword of a locally recoverable code. The locality property along with the FFT allows us to recover the secret with $O(n\log n)$ cost from a `random' subset of shares of large enough average size. We analyze its security and recovery thresholds, and characterize a trade-off between $\rho$ and the probability of successfully recovering the secret. Further, we carry out numerical simulations to demonstrate the applicability of the proposed scheme for a wide range of values of $n$.
|
