Questions tagged [secret-sharing]

Secret sharing refers to splitting a secret among multiple parties so that together they can reconstruct it. All parties, or just a threshold number of them, can be required for reconstruction. If fewer than the required number of parties participate, no information should be leaked about the secret.

Filter by
Sorted by
Tagged with
5
votes
1answer
134 views

Back up an information as $n$ pieces and require exactly $n-1$ to recover it

Let $X\in \Bbb F_2^p$ be some information. How do I create $Y_1,\dots,Y_n \in \Bbb F_2^q$ so that having less than $n-1$ of the $Y_i$s gives you no information on $X$ but having $n-1$ of them allows ...
5
votes
1answer
246 views

Malicious Model and Arbitrary selecting inputs on MPC and PSI

Imagine the following setting: a party considers a secret sharing or multiparty protocol that is secure against semi-honest adversaries. The adversary selectively chooses the inputs such that it could ...
5
votes
3answers
2k views

Is there a way to use Shamir Secret Sharing with updatable data?

I want to divide a system that maintains these properties, based on Shamir's Secret Sharing: A secret key is split up to N pieces, where T of them are enough to reconstruct the key. The original key ...
5
votes
2answers
94 views

What's the functional difference between fountain codes and polynomial secret sharing?

Fountain codes, as I understand it, allow for the reconstruction of a set of data (e.g. a 64-bit word), by sending (without corruption or failure) chunks of data generated using a probabilistic ...
5
votes
1answer
1k views

What are the ways to generate Beaver triples for multiplication gate?

So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are ...
5
votes
1answer
807 views

Why only one secret value with Shamir's secret sharing? [duplicate]

Shamir's Secret Sharing works by sharing data points on a curve, whereby when you have the required number of data points, you can find the function of the curve and find out the secret, which is ...
5
votes
1answer
702 views

Elliptic Curve Verifiable Secret Sharing

I'm reading this paper, which on page 3(Section IV.C) presents a Jointly Random Verifiable Secret Sharing Scheme for Elliptic curves. The algorithm makes sense to me save for this part: "Each $P_{i\...
5
votes
1answer
203 views

Background: Secret Sharing and Multiplication Triples

I know that a nearly identical question was asked in (Secret Sharing and Multiplication Triples), but I am a few points shy of asking follow up questions in the comments, so I understand if this is ...
5
votes
1answer
658 views

Secret Sharing and Multiplication Triples

I do not understand the multiplication technique using triples and secret shares of the inputs. Could somebody explain me where I'm wrong? It works like this: The inputs are secret shared in XOR ...
5
votes
1answer
348 views

Difference between hierarchical and multi level secret sharing

In this paper, the definitions are simply as follows. Multi-Level secret sharing: Higher level participants can help lower participants to get the secret. Compartmented secret sharing: Each level ...
5
votes
1answer
140 views

Can Secure Multi-party Computation be used to reconstruct secret shares?

When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share? When searching I have found results ...
5
votes
1answer
427 views

Implementing Secure multi-party computation for online website

I need to know if the following is feasible: I want that any two users of my website have a private key such that the private key is divided into three parts one for website owner and one each for the ...
5
votes
2answers
209 views

How many polynomials are used in Secure Multiparty Computation?

Secure Multiparty Computation based on Samir Secret sharing methods rely on Polynomials. Imagine corpus of data should be outsourced to bunch of untrusted servers for any computations. Now the data ...
5
votes
0answers
39 views

How to create a shared secret S from a subset of existing secrets n, such that k out of n secrets can recreate S? [duplicate]

In traditional secret sharing schemes, like Shamir's Secret Sharing, first a secret S is generated. Then it is divided into n parts, such that a subset k of the n parts are sufficient to reconstruct S....
4
votes
2answers
4k views

What are the weaknesses of Shamir's Secret Sharing?

We just learned about this in school but i don't quite get the weakness of this method. If we let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-...
4
votes
4answers
537 views

Is there a secret sharing scheme which allows delegation/re-sharing without reconstructing the original secret?

EDIT: Ilmari Karonen's answer below well not exactly what I want, gives a very good idea of what I am trying to accomplish. Are there any known secret sharing schemes that allow new parties to be ...
4
votes
2answers
662 views

Shamir's secret sharing scheme - type of channels

For information theoretic security in Shamir's [m,m] secret sharing scheme, do i need both authentic and confidential channels? Another related query is ;is it true that if the channels are only ...
4
votes
1answer
732 views

What is the maximum number of shares in Shamir's Secret Sharing?

I am using codahale’s Shamir's Secret Sharing implementation of Shamir's secret sharing from Github. I am using this to generate a 32 byte random key encryption key (KEK) to encrypt a 32 byte data ...
4
votes
1answer
275 views

secret sharing with 3 parties under constraint

Suppose we have $3$ parties Alice, Bob and Charlie such that Alice can't talk with Bob. Suppose that Alice has some string $x\in\{0,1\}^n$ and Bob has a string $y\in\{0,1\}^n$. Suppose that Alice ...
4
votes
1answer
177 views

Multiplying two additively shared values

Alice has $p_a,q_a$ and Bob has $p_b,q_b$, all elements of a ring $R$. They want to obtain shares of the value $pq$ where $p=p_a+p_b$, $q=q_a+q_b$. How do they do this ? Does revealing their shares of ...
4
votes
1answer
1k views

Beavers Triple Vs BGW Multiplication on MPC

Typically MPC protocols that are secure against semi-honest adversaries recommend the use of the revised GMW multiplication protocol by Gennaro et al. This is not the case against Active adversaries ...
4
votes
1answer
210 views

When all shares of a secret are given to adversary as a permuted matrix

Suppose we have a secret $\sigma$. The secret comes from a universe in which the elements are not necessarily distributed uniformly. We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (...
4
votes
1answer
701 views

How can Shamir's method for secret sharing work in the GF(256)?

I have been reading about Shamir's secret sharing, and maybe i completely misunderstand something, but the field is meant to be a prime. However, when i look at the implementations of this algorithm, ...
4
votes
1answer
800 views

Security difference(s) between Shamir's Secret Sharing Scheme and Blakley's Secret Sharing Scheme?

We know that Blakley's scheme is less space-efficient than Shamir's and that they both work based on pretty different aspects (Shamir = polynomial-based; Blakley = hyperplane-based). Looking at how ...
4
votes
1answer
56 views

How to distributively compute a secret of that form $\mathsf{s=sk\cdot g^a}$?

Is there a standard way to distributively compute secrets shares such that any $t+1$ combination out of $n$ of them constructs the secret $\mathsf{s=sk\cdot g^a}$, for a generator $\mathsf{g} \in \...
4
votes
2answers
604 views

How to Distribute the Shares using Secret Sharing for arbitrary Monotone Access Structures

Consider 4 people, $A$,$B$,$C$,$D$, & a secret $s\in\{0,1\}^k$. Construct a scheme which enables the following subsets of people to retrieve the secret $\{A,B\}$, $\{A,C\}$, $\{B,C,D\}$. I know ...
4
votes
1answer
686 views

What's efficient MPC protocol for determining if sum's bigger than y?

My secure multi-party computation (MPC) in need is simply to determine if a sum of two private variable is bigger than a given value $y$, as $f(x_0, x_1) = [(x_0 + x_1) > y]$ in which the value ...
4
votes
1answer
841 views

Addition with Shamir secret sharing?

When performing Shamir secret sharing I'm trying to find $z_i$, such that $z = x + y$. Where $n = 6$ and $t = 3$. I believe this would be the correct solution (correct me if I'm wrong): Each party ...
4
votes
1answer
193 views

How to obtain a one-value share in Shamir's secret sharing

This is a trivial question, but I had to ask: since each generated share in a Shamir's secret sharing scheme initially consists of a pair of values (representing the coordinates of a point on the ...
4
votes
1answer
136 views

Shamir Interpolation Problem (Recovering secret with fewer parts than the threshold)

I'm studying about polynomials and interpolation with shamir secret sharing. I have some questions about it. I found that there are always lower-degrees polynomials that intersects with 2 or more ...
4
votes
1answer
391 views

Shamir Secret Sharing - P not prime

I was wondering what will happen if I use the Shamir Secret Sharing scheme with $P$ not being a prime, let's say it is $255$. An adversary which holds $k'$ shares ($k'<$ threshold $k$ ) can attack ...
4
votes
1answer
148 views

Can data stay encrypted unless I'm eliminated?

I work as a spy for a top secret and ruthless government organisation with a three letter acronym. I know all their dirty secrets and where the skeletons are literally buried. In order to protect ...
4
votes
1answer
140 views

Could we share a secret key using the Birthday problem?

I stumbled upon this code on-line, it seems obvious to me that generating all 2^40 keys in trivial time can always be achieved as can hashing each and everyone of them, using the SHARED Salt that "Eve"...
4
votes
1answer
76 views

Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being ...
4
votes
1answer
210 views

Does Shamir Secret Sharing provide integrity?

Shamir secret sharing splits into t number of shares with a t-threshold. However, I can find no information online if this scheme provide integrity (or authentication for that matter, which I assume ...
4
votes
1answer
358 views

Proactive secret sharing security flaws

I read a Shamir secret sharing notes where it mentioned the security flaws of PSS(Proactive Security Sharing) when only one server is responsible for generating $h(x)$. To give the question a bit ...
4
votes
1answer
172 views

How to perform Shamir Secret Sharing with a Tabula Recta?

In this post, a couple comments suggested that a tabula recta could be used to perform Shamir Secret Sharing. I'm specifically interested in this statement: you could just have a table of all 100 ...
4
votes
1answer
146 views

A problem in secret sharing and mixed operators over $\mathbb{Z}$

Recently, I studied an article in which it was written that having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$. The authors used this result to build a secret sharing scheme, but they did not ...
4
votes
1answer
459 views

Linear secret-sharing scheme for four players

I got stuck on this question during my exam revision. Consider the linear secret-sharing scheme for four players $P_1, P_2, P_3$ and $P_4$ based on the matrix $$ M= \begin{bmatrix} 1 & 0 &...
4
votes
1answer
114 views

How do you distribute secret shares without knowing who to first distribute them to?

Figure 1 on page 1249 of the “Multiparty Computation Secure Against Continual Memory Leakage” paper shows $m$ committees are elected in step 1 and then later in step 3 are each given a secret share. ...
4
votes
2answers
767 views

secure multiparty computation for multiplication

Suppose there are $N$ parties $p_j$, each with a binary $b_j\in{\{0,1\}}$. The problem needs to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{...
4
votes
1answer
103 views

Information theoretical security of an inefficient Shamir based access structure

I have studied Sharmir's scheme as well as the multiple assignment scheme proposed by M. Ito. My question is if anyone can tell me if the following scheme is theoretically secure: Terms: P = set of ...
4
votes
0answers
112 views

Privacy of Multiplication of Shamir Shared Secrets with an Active Adversary Where Final Result is Revealed to a Third Party Over a Secure Channel

I have the following question related to the privacy of multiplication of Shamir Shared Secrets: Suppose we have two secrets, a and b, shared by a Shamir Secret Sharing Scheme in a (k,n) ...
4
votes
0answers
107 views

Committing to a secret shared value

Suppose I run a multiparty protocol. At the output stage, I have the function output in a secret shared manner among all parties. Now I want all the parties to commit to their value of the secret ...
4
votes
0answers
571 views

How to prove that a commitment hides the decryption of an ElGamal ciphertext?

I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question. For this question I need to prove that I've committed to a ...
4
votes
0answers
231 views

Explanation of part of a visual cryptography algorithm

I have been working on a project involving visual cryptography and I am stuck with the following problem. My question is related to this paper, AN IMPROVED VISUAL CRYPTOGRAPHY SCHEME FOR SECRET ...
4
votes
0answers
279 views

Secure Secret sharing

I'm trying to come up with a new way to do oblivious transfer that is faster and requires less computation than existing methods. The basis of my method is shamir secret sharing. Below is an example ...
4
votes
0answers
406 views

Secret sharing - no dealer, modifiable, verifiable

I need to find a secret sharing scheme with these properties: The scheme is set up by all participants, ie no single entity called the dealer The parameters of secret sharing need to be modifiable,eg ...
3
votes
2answers
217 views

Is there a secret sharing scheme which allows sharing of a secret (one-out-of-n)

Is there a secret sharing scheme where the knowledge of just one share is sufficient to find the secret, in other words a (one-out-of-n) sharing scheme ? Plz I need to know if it is possible to make ...
3
votes
2answers
247 views

How does secret sharing solve the partial exposure problem?

I have been trying to understand how secret sharing methods like Shamir's secret sharing solve the problem of a share revealing information about the secret. I guess there are some random numbers ...