I hope this question is not too speculative.

Applebaum, Nir and Pinkas have a new paper which has an $n-$party secret sharing scheme with:

  • reconstruction complexity of $O(n)$ additions
  • constant share size
  • sharing complexity of $O(n)$ additions
  • is a blackbox secret sharing scheme

The shamir scheme has complexity $n \log |F|$ where $F$ is the domain of the private key which is the exponent of some group $G.$ The recent Cramer-Xing (EUROCTYPT'20) scheme as complexity $n^2,$ independent of the size of the domain.

The authors remark that this is actually a "near" threshold scheme which provides privacy against unauthorized sets of density at most $\tau_p$ and correctness for authorized sets of density at least $\tau_c.$ However, they can make these two constants $\tau_p<\tau_c$ arbitrarily close.

While I find the use of erasure codes and code concatenation interesting, I am wondering about how large the impact of this paper may be:

(a) in practice for implementations and applications

(b) in theory leading to new developments

  • 1
    $\begingroup$ Their comments regarding applications to threshold FHE (end of page 8/beginning of page 9) seem true to me. Provided their construction is concretely efficient I imagine it can be used for lattice-based threshold crypto. Note the bigger bottleneck for lattice-based FHE is the requirement of noise flooding. Some authors have been beginning to relax this lately though. $\endgroup$
    – Mark Schultz-Wu
    Jun 12, 2023 at 21:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.