Related papers: Optimal Computational Secret Sharing

Optimal Computational Secret Sharing

URL: http://arxiv.org/abs/2502.02774v1
Date: Tue, 04 Feb 2025 23:37:16 GMT
Title: Optimal Computational Secret Sharing
Authors: Igor L. Aureliano, Alejandro Cohen, Rafael G. L. D'Oliveira,
Abstract summary: In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants. We present a construction achieving a share size of $tfrac|S|t + |K|t$.
Score: 51.599517747577266
License:
Abstract: In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants such that any subset of size $t$ can recover $S$, while any subset of size $t-1$ or fewer learns nothing about it. For information-theoretic secret sharing, it is known that the share size must be at least as large as the secret, i.e., $|S|$. When computational security is employed using cryptographic encryption with a secret key $K$, previous work has shown that the share size can be reduced to $\tfrac{|S|}{t} + |K|$. In this paper, we present a construction achieving a share size of $\tfrac{|S| + |K|}{t}$. Furthermore, we prove that, under reasonable assumptions on the encryption scheme -- namely, the non-compressibility of pseudorandom encryption and the non-redundancy of the secret key -- this share size is optimal.

Related papers

A Construction of Evolving $3$-threshold Secret Sharing Scheme with Perfect Security and Smaller Share Size [11.114225631904004]
We consider the evolving $k$-threshold secret sharing scheme with $k=3. We then propose a new evolving $3$-threshold scheme with perfect security. Based on this model of the revised scheme and the proposed conventional $3$-threshold scheme, we present a brand-new and more concise $3$-threshold secret sharing scheme.
arXiv Detail & Related papers (2024-10-17T13:17:11Z)
Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
arXiv Detail & Related papers (2024-06-18T08:54:04Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
arXiv Detail & Related papers (2024-06-07T12:07:16Z)
A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
arXiv Detail & Related papers (2024-02-02T05:04:01Z)
Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
Invertible Bloom Lookup Tables (IBLTs) have found applications in set reconciliation protocols, error-correcting codes, and the design of advanced cryptographic primitives. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. We show that hashing $n$ keys with any $k$-wise independent hash function $h:U to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that at least $n/2$ keys will have a unique hash value
arXiv Detail & Related papers (2023-06-13T07:15:02Z)
Code-routing: a new attack on position verification [0.0]
A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system. We give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme. This strategy completes the $f$-routing task using $O(SP_p(f))$ EPR pairs.
arXiv Detail & Related papers (2022-02-16T01:04:31Z)
An Efficient Simulation of Quantum Secret Sharing [7.195824023358536]
We propose a secure $d$-level $QSS$ protocol for sharing a secret with efficient simulation. It does not disclose any information about the secret to players. Its security analysis shows that the intercept-resend, intercept, entangle-measure, forgery, collision and collusion attacks are not possible in this protocol.
arXiv Detail & Related papers (2021-03-20T16:42:02Z)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
arXiv Detail & Related papers (2020-09-21T04:13:34Z)
Locally Private Hypothesis Selection [96.06118559817057]
We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
arXiv Detail & Related papers (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.