Advanced Techniques in Secret Sharing Schemes
Explore the advancements in polynomial secret-sharing schemes and their applications in cryptography. Discover how polynomial schemes provide efficient solutions for sharing secrets among multiple parties while maintaining security. Learn about the construction of polynomial conditional disclosure protocols and the reduction in share size with increasing polynomial degree. Uncover insights into linear and general secret-sharing schemes, and the quest for efficient non-linear schemes for diverse access structures.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Improved Polynomial Secret Improved Polynomial Secret- -Sharing Schemes Sharing Schemes Amos Beimel, Oriol Farr s, and Amos Beimel, Oriol Farr s, and Or Lasri Or Lasri BEN GURION UNIVERSITY AND UNIVERSITAT ROVIRA I VIRGILI NOVEMBER 2023
Overview oSecret sharing scheme: useful tool in cryptography oLinear secret sharing scheme: useful for applications, less efficient oPolynomial secret-sharing schemes generalize linear secret-sharing schemes oKnown: Linear Secret Sharing < Degree-2 secret sharing < General Secret Sharing oDoes the share size decrease as the degree of the polynomials grows? oOur result: YES! oTool: oWe construct a polynomial conditional disclosure of secrets (CDS) protocol
Secret-Sharing Schemes [Shamir79, Blakley79, Ito-Saito-Nishizeki87] Set of parties? = ??, ,?? and a Dealer? Access structure ? ??collection of authorized sets Example Example: ??= ? ? ? ? Dealer? holds a secret ? Creates random shares ??, ,?? Sends share ?? to party ?? Correctness Correctness: A set ? ? can compute the secret ? from its shares Security Security: A set ? ? cannot learn anything about the secret ? ? ? A set ? ? learns ? if and only if ? ? ?? ?? ?? ?1 ?? ?2
Share Size in Secret-Sharing Schemes This talk: 1-bit secrets ? {?,?} ?? size of share of party ?? The share sizeof a scheme is ??? ? ? ??? Main goal: Construct schemes with small share size for general access structures
Polynomial Secret Sharing: Motivation [Paskin-Radune20,Beimel-Othman-Peter22] A secret-sharing scheme is linear if for every ? ? the reconstruction function of the secret from the shares is linear Most known secret-sharing schemes with small share size are linear There is an ?-party access structure that requires shares of size at least ??/?[Babai-G l- Wigderson99] in every linear scheme General secret sharing schemes: Upper bound ??.????[Applebaum-Nir21] lower bound ? ?/???(?) [Csirmaz96] Questions: Can we construct efficient non-linear schemes for a broader family of access structures? Can we extend the lower bounds to a broader class of secret-sharing schemes? Obtain insight for general secret-sharing schemes General SS Polynomial SS Linear SS
Polynomial Secret-Sharing Schemes [Paskin-Cherniavsky-Radune20,Beimel-Othman-Peter22] Generalization of linear secret-sharing schemes to higher degrees The shares ??,??, ,?? are vectors over a field ?: ??= ??,?, ,??, ? Reminder: A set of parties ? ?, where ? = ?, reconstructs the secret from their shares using a function ???:? ? ?,? We call a secret-sharing a degree-? polynomial if for every ? ? the reconstruction function is a polynomial of degree ? (with ? variables) Example: If ? = 1, reconstruction function is linear the scheme is linear
Example Polynomial Secret-Sharing Scheme Two parties ? = ??,?? Access structure ? = ??,?? (?-out-of-? access structure) Randomness: ??,??,?? ? The shares: ??= ? + ??+ ??(??+??),??, ??= ??,??+ ?? The two parties together can reconstruct the secret: ?? (??+??) ??? ??,?? = ? + ??+ ??(??+ ??) ?? A polynomial of degree-?
Conditional Disclosure of Secrets (CDS) [Gertner-Ishai-Kushilevitz-Malkin98] ?? ,? ,? ?? ??,?,? ,? ,? A function ?: ?? ?,? ?1 ?2 ?? Each party has a private input ?? ?? ?? ?? The parties know a secret ? Goals: Correctness: If ? ??, ,?? = ?, Ref learns ? Ref Security: If ? ??, ,?? = ?, Ref learns nothing Each party sends one message Learns ? if and only if ? ??, ,?? = ? 10
Our results Secret Sharing Thm1: Every ?-party access structure can be realized by a secret-sharing scheme with degree-? reconstruction with share size ??.???+???, where ??= ?(?????? ?/??? ?) Degree-? Degree-? Unrestricted ??.???? [Applebaum- Nir21] ??.???? Previous Results No previous results [Beimel-Othman- Peter21] Improvement: Secret-sharing scheme for an arbitrary access structure with polynomial reconstruction of degree 243 and share size ??.????
Our results ?-Server CDS Thm2: For every ? > ? and function ?: ?? {?,?}, there is a degree-??- server CDS protocol for ?, with communication complexity ?? ? ? ??, where ??= ?(?????? ?/??? ?) Degree-? Degree-? Unrestricted ? ? [Liu-Viakuntanathan- Wee18] ? ?? ? /? [Beimel-Othman- Peter21] Previous Results ?/??? ? No previous results Lower bound degree-?: ? ?? ? /(?+?)[Beimel-Othman-Peter21] Improvement: ?-server CDS protocol with polynomial reconstruction of degree 243 and communication complexity of ? ?(? ?)/?
Construction Flow [Liu- [Liu- Viakuntanathan18, [Liu- Viakuntanathan -Wee17, Dvir- Gopi15] Secret-Sharing schemes ?-Server CDS Matching Vectors Viakuntanathan -Wee18] ?-server CDS Applebaum-Beimel- Nir-Peter20, Applebaum-Nir21] Polynomial Polynomial Polynomial Polynomial ?-Server Polynomial Polynomial ?-Server CDS CDS Sparse Matching Vectors Vectors Sparse Matching Polynomial Polynomial Secret-Sharing schemes ?-server CDS
Conclusion and Open Problems Thm1: Every ?-party access structure can be realized by a secret-sharing scheme with degree-? reconstruction of with share size ??.???+???, where ??= ?(?????? ?/??? ?) Thm2: For every function ?: ?? {?,?}, there is a degree-??-server CDS protocol for ?, with communication complexity ?? ? ? ?? o[Beimel-Othman-Peter21] proved a lower bound on polynomial ?-server CDS of ? ?? ? \ ?+? Open Problems Close the gap between the upper and lower bounds of degree-??-server CDS protocols 1. Improve the share size for degree-? secret-sharing schemes 2. Construct shorter ????-matching vectors obtain better ?-server CDS and ?-server PIR protocols 3.
