Statistical Verifiable Secret Sharing: Achieving Privacy and Correctness
Statistical verifiable secret sharing offers a relaxed approach to achieving privacy, correctness, and commitment in a secure multi-party computation context. It enhances round complexity and is achievable for diverse scenarios, even with a dishonest dealer. This method ensures privacy, correctness, and commitment with negligible probability, making it a valuable tool in secure information sharing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
THE ROUND COMPLEXITY OF VERIFIABLE SECRET SHARING: THE STATISTICAL CASE Ranjit Kumaresan (UMD) Arpita Patra C. Pandu Rangan (IITMadras)
VERIFIABLE SECRET SHARING (VSS) Two-phase protocol A dealer shares a secret among a set of n parties (t of which are malicious) in the sharing phase The secret is recovered in a reconstruction phase
VERIFIABLE SECRET SHARING (VSS) Two-phase protocol A dealer shares a secret among a set of n parties (t of which are malicious) in the sharing phase The secret is recovered in a reconstruction phase If the dealer is honest No information about the secret is leaked in the sharing phase Perfect Privacy All honest parties recover the dealer s secret Perfect Correctness
VERIFIABLE SECRET SHARING (VSS) Even if the dealer is dishonest The view of the honest parties in the sharing phase defines a value s such that each honest party outputs s in the reconstruction phase Perfect Commitment
VERIFIABLE SECRET SHARING (VSS) Building block in honest majority MPC constructions Critical Parameter: Round Complexity Perfect VSS possible iff t < n/3 What about t < n/2 ? Relaxation: Statistical VSS
STATISTICAL VERIFIABLE SECRETSHARING Relax any requirement of Perfect VSS to hold with all but negligible probability Privacy Correctness Commitment Improves round complexity even for t < n/3 [PCRR09] Achievable for t < n/2 assuming broadcast channel [RB89, CDDHR99]
STATISTICAL VSS (INTHISWORK) If the dealer is honest No information about the secret is leaked in the sharing phase Perfect Privacy All honest parties recover the dealer s secret except with negl. prob. Statistical Correctness Even if the dealer is dishonest The view of the honest parties in the sharing phase defines a value s such that each honest party outputs s in the reconstruction phase except with negl. prob. Statistical Commitment
PRIOR WORK ON ROUND COMPLEXITY Perfect VSS: Long line of work BGW88, GIKR01, FGGRS06, 3 round sharing is optimal (with only one broadcast round [KKK08]) Statistical VSS for t < n/3 2 round sharing is optimal [PCRR09] Statistical VSS for t < n/2 3 round sharing is necessary [PCRR09] What is the optimal round complexity?
BEST KNOWN PRIOR WORK Perfect VSS (t< n/3) Stat VSS (t< n/3) Stat VSS (t<n/2) Sharing Phase 3 [GIKR01] [FGGRS06] 2 [PCRR09] > 5 [CDDHR99] Recon Phase 1 2 2
OUR RESULTS Perfect VSS (t< n/3) Stat VSS (t< n/3) Stat VSS (t<n/2) Stat VSS (t<n/2) Sharing Phase 3 3 (exp) [optimal] 4 (efficient) [GIKR01] [FGGRS06] 2 [PCRR09] >5 [CDDHR99] Recon Phase 1 2 2 2 Settles the question of optimal round complexity of Statistical VSS for t < n/2 For t < n/3, settled by [PCRR09]
ORGANIZATIONOFTHETALK Building Block: Multi Verifier ICP Definition & Properties
ORGANIZATIONOFTHETALK Building Block: Multi Verifier ICP Overview of 4 round efficient VSS protocol
ORGANIZATIONOFTHETALK Building Block: Multi Verifier ICP Overview of 4 round efficient VSS protocol 3 round inefficient VSS protocol Generalizing Multi Verifier ICP Construction
MULTIVERIFIER ICP: DEFINITION & PROPERTIES ICP - Information Checking Protocol Well known constructions by [Rab94, CDDHR99] Use to get Statistical VSS for t < n/2 2 phase protocol run by D (with input s) and INT and every other player as verifier [PCR09] Sh(D, INT, s) INT holds D s signature D,INT(s) on s Rec(D, INT, s) INT reveals D,INT(s), Verifiers accept/reject
PROPERTIESOF MULTI VERIFIER ICP Honest D w.h.p. D,INT(s) revealed only as s Honest INT w.h.p. every verifier accepts D,INT(s) Adversary does not learn any information about s when D is honest Round Complexity of construction [PCR09]: Sh takes 3 rounds Rec takes 2 rounds
EFFICIENT4-ROUND STAT VSS PROTOCOL High level idea: Build on [CDDHR99] (based on bivariate polys) Use ICP to sign points on the polynomial Adapt round efficient Multi Verifier ICP into [CDDHR99] Construction Techniques: Random pad sent to D Enables D to cross-check and broadcast shares when necessary Early reveals Deal with overlapping Sh and corresponding Rec executions
USING MVICP ASASUBPROTOCOL Both D and INT are corrupt With D s help, INT can reveal any value in Rec Weak commitment until last round In the last round of Sh, a corrupt D could arbitrarily change the secret Say that D conflicts with INT Weak reconstruction Decision to accept a signature reveal is based on a voting mechanism
GENERALIZING MULTI VERIFIER ICP Have multiple INTs which receive the same value Let U represent the set of INTs If U contains t players, then can we ask for more? Specifically, want All players in U to be committed to one reveal (say, v) at the end of SetSh(D, U, u) even when D is corrupt u = v, for honest D Adversary does not have any information about u at the end of sharing phase unless either D or some player in U is corrupt Directly gives us VSS!
TOWARDS A 3-ROUND PROTOCOL SetSh(D, U, u) : For each Piin U: Round 1: D sends D,i(u)to Pi For random rij, Pi sends i,j(rij) to each Pj in U Round 2: Pi broadcasts aij = u+rij, bij= u+rji for all j Round 3: If aij bji, D broadcasts u If Pi conflicts with Pj, then broadcast entire view (i.e., including MVICP polynomials associated with D,i(u)) ` If both Pi and Pj broadcast their entire view we call it a mutual conflict
TOWARDS A 3-ROUND PROTOCOL SetRec(D, U, u) ` If D broadcasted u, then output u and terminate If no mutual conflict, then ask players to Reveal signatures Prove consistency with their broadcasts If any player passes the tests above, accept his value of u and terminate reconstruction Dealing with mutual conflicts is tricky
DEALINGWITH DISHONEST VERIFIERS Dishonest external verifiers could either Vote for corrupt party s reveal Two successful reveals on different secrets! Abort Only one successful reveal Technique: Share Verification Info via SetSh! Non-mutually conflicting executions are good Require mutually conflicting reveals to pass all good verification points
3-ROUND CONSTRUCTION: HIGH LEVEL Sharing: For all t-sized U: SetSh(D, U, u) For all t-sized V: SetSh(D, V, verV(u)) Reconstruction: For all t-sized U: If no mutual conflict, execute SetRec(D, U, u) Else, reconstruct check points from non-mutually conflicting SetSh(D, V, verV(u)) Flip Side: Exponential communication complexity MVICP poly F used in SetSh is of degree O(2 t) Need to increase field size for security Verification info for u held by V
RECAP 4-round sharing 2-round reconstruction efficient statistical VSS protocol 3-round sharing 2-round reconstruction inefficient statistical VSS protocol Open: 3-round efficient protocol?
