Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience
Victor Shoup, Nigel P. Smart
Abstract
Abstract We present new protocols for Asynchronous Verifiable Secret Sharing for Shamir (i.e., threshold $$t<n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo><</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> ) sharing of secrets. Our protocols: Use only “lightweight” cryptographic primitives, such as hash functions; Can share secrets over rings such as $${\mathbb {Z}}/(p^k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo>/</mml:mo> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> as well as finite fields $$\mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math> ; Provide optimal resilience , in the sense that they tolerate up to $$t < n/3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo><</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> corruptions, where n is the total number of parties; Are complete , in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares; Employ batching techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in n , at least on the “happy path”, where no party provably misbehaves.