Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SECRET SHARING:
Reports tagged with secret sharing:
TR15-182 | 13th November 2015
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>


TR16-023 | 23rd February 2016
Ilan Komargodski, Moni Naor, Eylon Yogev

How to Share a Secret, Infinitely

Revisions: 4

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best ... more >>>


TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>


TR16-131 | 21st August 2016
Andrej Bogdanov, Siyao Guo, Ilan Komargodski

Threshold Secret Sharing Requires a Linear Size Alphabet

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>


TR17-038 | 23rd February 2017
Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>


TR17-051 | 16th March 2017
Mark Bun, Justin Thaler

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>


TR17-076 | 21st April 2017
Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 2

We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve ... more >>>


TR17-165 | 3rd November 2017
Toniann Pitassi, Robert Robere

Lifting Nullstellensatz to Monotone Span Programs over Any Field

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula.

This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different ... more >>>


TR17-189 | 25th December 2017
Benny Applebaum, Barak Arkis

Conditional Disclosure of Secrets and $d$-Uniform Secret Sharing with Constant Information Rate

Revisions: 1

Consider the following secret-sharing problem. Your goal is to distribute a long file $s$ between $n$ servers such that $(d-1)$-subsets cannot recover the file, $(d+1)$-subsets can recover the file, and $d$-subsets should be able to recover $s$ if and only if they appear in some predefined list $L$. How small ... more >>>


TR18-143 | 16th August 2018
Mark Bun, Justin Thaler

The Large-Error Approximate Degree of AC$^0$

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>


TR18-200 | 29th November 2018
Ashutosh Kumar, Raghu Meka, Amit Sahai

Leakage-Resilient Secret Sharing

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>


TR19-082 | 2nd June 2019
Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

Approximate degree, secret sharing, and concentration phenomena

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>


TR20-055 | 22nd April 2020
Ashutosh Kumar, Raghu Meka, David Zuckerman

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>


TR21-050 | 2nd April 2021
Marshall Ball, Alper Cakan, Tal Malkin

Linear Threshold Secret-Sharing with Binary Reconstruction

Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`$t$-out-of-$n$') secret-sharing where the linear reconstruction function is restricted to coefficients in $\{0,1\}$. We prove upper and lower bounds on the share size of such schemes. One ramification of our results is ... more >>>


TR21-052 | 12th April 2021
Benny Applebaum, Oded Nir

Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$.
The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$.
more >>>


TR22-006 | 12th January 2022
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

Secret Sharing, Slice Formulas, and Monotone Real Circuits

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>


TR23-013 | 7th February 2023
Noam Mazor

A Lower Bound on the Share Size in Evolving Secret Sharing

Revisions: 1

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an ... more >>>


TR23-087 | 9th June 2023
Benny Applebaum, Oded Nir, Benny Pinkas

How to Recover a Secret with $O(n)$ Additions

Revisions: 1

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is ... more >>>


TR23-091 | 18th June 2023
Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan

Succinct Computational Secret Sharing

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size ... more >>>


TR23-136 | 14th September 2023
Benny Applebaum, Oded Nir

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and ... more >>>


TR24-108 | 28th June 2024
Benny Applebaum, Eliran Kachlon

Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known ... more >>>




ISSN 1433-8092 | Imprint