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.

• Secret Sharing
• Polynomial Schemes
• Cryptography
• Access Structures
• Advanced Techniques

gtaun Follow

Uploaded on Sep 25, 2024 | 0 Views

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.

Presentation Transcript

1. 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

2. 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

3. Definitions and background

4. 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

5. 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

6. 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

7. 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

8. 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-?

9. 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

10. Our results

11. 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 ??.????

12. 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 ? ?(? ?)/?

13. High level Construction

14. 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

15. 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.

16. Thanks!