Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes

We put forth new protocols for oblivious transfer extension and vector OLE, called Silver, for SILent Vole and oblivious transfER. Silver offers extremely high performances: generating 10 million random OTs on one core of a standard laptop requires only 300ms of computation and 122KB of communication. This represents 37% less computation and ∼ 1300× less communication than the standard IKNP protocol, as well as ∼ 4× less computation and ∼ 14× less communication than the recent protocol of Yang et al. (CCS 2020). Silver is silent: after a one-time cheap interaction, two parties can store small seeds, from which they can later locally generate a large number of OTs while remaining offline. Neither IKNP nor Yang et al. enjoys this feature; compared to the best known silent OT extension protocol of Boyle et al. (CCS 2019), upon which we build up, Silver has 19× less computation, and the same communication.

Due to its attractive efficiency features, Silver yields major efficiency improvements in numerous MPC protocols. Our approach is a radical departure from the standard paradigm for building MPC protocols, in that we do not attempt to base our constructions on a well-studied assumption. Rather, we follow an approach closer in spirit to the standard paradigm in the design of symmetric primitives: we identify a set of fundamental structural properties that allow us to withstand all known attacks, and put forth a candidate design, guided by our analysis. We also rely on extensive experimentations to analyze our candidate and experimentally validate their properties. In essence, our approach boils down to constructing new families of linear codes with (plausibly) high minimum distance and extremely low encoding time. While further analysis is of course welcomed in order to gain total confidence in the security of Silver, we hope and believe that initiating this approach to the design of MPC primitives will pave the way to new secure primitives with extremely attractive efficiency features.