Secret Sharing for High Slices: Overview and Insights
Explore the concept of secret sharing for high slices, including schemes like Shamir's and Blakley's, access structures, share sizes, and more. Understand how authorized coalitions can recover secrets while unauthorized ones gain no knowledge, all through a randomized dealer sharing approach.
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
Secret Sharing for High Slices Secret Sharing for High Slices 1 1 1 0 0 0 Amos Beimel*, Oriol Farr s**, Or Lasri*, Oded Nir Ben-Gurion University of the Negev* Universitat Rovira i Virgili** Tel Aviv University TCC 2024
Secret Sharing Schemes Secret Sharing Schemes [Shamir 79, Blakley 79, ItoSaiNish87] ? ??????? A randomized dealer shares a secret ? by sending one message to every party. ?1 ?2 ?3 Dealer (?,?) ?4 ?5 ?6
Secret Sharing Schemes Secret Sharing Schemes [Shamir 79, Blakley 79, ItoSaiNish87] ? ??????? A randomized dealer shares a secret ? by sending one message to every party. ?1 ?2 ?3 Authorized coalitions can recover the secret Dealer (?,?) ?4 ?5 ?6
Secret Sharing Schemes Secret Sharing Schemes [Shamir 79, Blakley 79, ItoSaiNish87] ? ??????? A randomized dealer shares a secret ? by sending one message to every party. ?1 ?2 ?3 Authorized coalitions can recover the secret Dealer (?,?) ?4 Unauthorized coalitions learn nothing about the secret ?5 ?6
Secret Sharing Schemes Secret Sharing Schemes [Shamir 79, Blakley 79, ItoSaiNish87] ? ??????? Access structure - A list ? of authorized coalitions ?1 ?2 ?3 Dealer (?,?) Complexity measure: ?4 ?5 The size of the shares for ? ?6
Different Share Size for Different Access Structures Different Share Size for Different Access Structures Assume we deal with 1-bit secrets 1-bit shares ????-bit shares total share size ? total share size ? 1-threshold (singletons are authorized): ?-threshold [Shamir79]: Formula of size ? [BenalohLeichter88]: Monotone span program of size ? [KarchmarWidgerson93]: General access structures: Upper bound: ?.??+?(?)[ISN87, LV18, ABFNP19, ABNP20, ApplebaumNir21] Lower bound: ?( ??? ?)[ Csrimaz96] ? Open Problems: 1. Share Size of General Access Structures? 2. Natural Access Structures with Small Shares?
Slice Access Structures Slice Access Structures set-size ? ?-Slice access structures ? : if ? > ?: if ? = ?: if ? < ?: ? ? different ?-slices *A ?-threshold is a ?-slice ? ? ? ? or ? ? ? ? 1 ? 0 *There are 2 1 ?-slice The upper bound for general access structures is achieved by *Connections to ABE and symmetric PIR composing slice access structures!
S Share Size of hare Size of Slice Access Structures Slice Access Structures , 2? ? + ? ? 1 ? 1 Share size for ?-slices[LV18, AA18, ABFNP19]: ? log ? , For ? = ?(1): low" ?-slices cost ?? ? high (? ?)-slices cost ?? ? 1 1 0 0 For ? = log ?: ?-slices cost ??(??? ??? ?) (? ?)-slices cost ??(??? ?) Improve schemes for high slices? Can it help realize larger families of access structures? Asymmetry: Low slices are cheaper than high slices
Our Results Our Results 1 1. High Slices: A scheme for (? ?)-slices with share size ?? 2 ?( ? log ?) at most ? times the share size for ?-slices 0 1 2. Corollary: Better schemes for multislices (and hypergraphs) closer to improving general access structures?[AN21] 0 3. Computationalschemes for high slices: privacy only holds against bounded adversaries based on OWF schemes for high slices even better than for low ones 1 0
Our Results Our Results 1 1. High Slices: A scheme for (? ?)-slices with share size ?? 2 ?( ? log ?) at most ? times the share size for ?-slices 0 1 2. Corollary: Better schemes for multislices (and hypergraphs) closer to improving general access structures?[AN21] 0 3. Computationalschemes for high slices: privacy only holds against bounded adversaries based on OWF schemes for high slices even better than for low ones 1 0
1 1. A Perfect (Simple) Scheme for High Slices . A Perfect (Simple) Scheme for High Slices (n ?)-slice ? a secret ? The scheme: Denote by? the ?-slice that for every set ? of size ? satisfies: 1 ? ? ? ? 0 ? ?-slice? (? ?)-slice ? ?
1 1. A Perfect (Simple) Scheme for High Slices . A Perfect (Simple) Scheme for High Slices (n ?)-slice ? a secret ? The scheme: Denote by? the ?-slice that for every set ? of size ? satisfies: 1 ? ? ? ? 0 ? ?-slice? ?1 (? ?)-slice ? ? 1. Share ? according to ? to generate shares ?1, ,?? 2. Share every ?? to (? ?)-out-of-(? 1) threshold shares, and distribute one share to each party in ?1,...,?? {??}
1 1. A Perfect (Simple) Scheme for High Slices . A Perfect (Simple) Scheme for High Slices (n ?)-slice ? a secret ? The scheme: Denote by? the ?-slice that for every set ? of size ? satisfies: 1 ? ? ? ? 0 ? ?-slice? ?1 ?2 (? ?)-slice ? ? 1. Share ? according to ? to generate shares ?1, ,?? 2. Share every ?? to (? ?)-out-of-(? 1) threshold shares, and distribute one share to each party in ?1,...,?? {??}
1 1. A Perfect (Simple) Scheme for High Slices . A Perfect (Simple) Scheme for High Slices (n ?)-slice ? a secret ? The scheme: Denote by? the ?-slice that for every set ? of size ? satisfies: 1 ? ? ? ? 0 ? ?-slice? ?1 ?2 ?3 Correctness: The ? parties can recover the ?-shares of ?, and then the secret: ? ? ? ? (? ?)-slice ? ? 1. Share ? according to ? to generate shares ?1, ,?? 2. Share every ?? to (? ?)-out-of-(? 1) threshold shares, and distribute one share to each party in ?1,...,?? {??}
1 1. A Perfect (Simple) Scheme for High Slices . A Perfect (Simple) Scheme for High Slices Share size of ?-slices is ? ? Share size of (? ?)-slices is ? ? ? Corollary : The gap between share size of ?-slices and (? ?)- slices is at most ? 1 Connections to duality and secret sharing[Csirmaz20, AN21, Bogdanov23] Is there a gap between share sizes of dual access structures? 1 0 0
Open Questions Open Questions 1. Better Perfect Schemes for General Access Structures? via more improvements to slices/multislices 2. Better Computational Schemes for More Access Structures from OWFs? 3. Duality and Secret Sharing More positive results? Separations?
