Questions tagged as ['secret-sharing']

Suppose that we have the usual problem of secure communication, where each of the $I$ agents have a private signal $s_1,s_2,\dots,I$ and they wish to compute any function $f(s_1,s_1,...,s_I)=(x_1,x_2,...,x_I)$ in such a way that no party learns more than their input $s_i$ and output $x_i$.

Although I have seen many cryptographic protocols designed to be secure and in order to solve the problem th ...

Let us consider the following verification protocol based on Feldman. Assume, $c_0,\cdots,c_k$ represent the coefficients of the polynomial $p()$ in $\mathbb{Z}_q$. For verifying share $(i,p(i))$ and public parameters group $G$ of prime order $p, q|p-1$ and generator $g$, the share generator provides $(g,d_0,\cdots,d_k)$ where $d_j=g^{c_j}, j \in\{0,1,\cdots,k\}$. The receiver of the share $s$,checks wh ...

Suppose I have a k-dimensional secret $\langle x_1,\cdots,x_k \rangle$ which I share using a packed Shamir's secret share $(t,k,n)$ where $t$ is the threshold and $n$ is the number of shares as follows: Construct a polynomial $f$ of degree $t+k-1$ such that $f(-1)=x_1, \cdots, f(-k)=x_k, f(-k-1)=r_1, \cdots, f(-k-t)=r_t$ where $r_1,\cdots,r_k$ are randomly sampled from the field. Now the n shares are gene ...

One way of verifying Shamir's secret shares is to use the technique by Feldman where $c_0,\cdots,c_k$ represent the coefficients of the polynomial $p()$ in $\mathbb{Z}_q$. For verifying share $(i,p(i))$ and public parameters group $G$ of prime order $p, q|p-1$ and generator $g$, the share generator provides $(g,d_0,\cdots,d_k)$ where $d_j=g^{c_j}, j \in\{0,1,\cdots,k\}$. The receiver of the share

In Rabin and Ben-Or, their basic assumption is that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly. Hence, they design a protocol of communication that is called verifiable secret sharing protocol (VSSP), and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the play ...

I am searching for a simle model that can simulate the following procedure.

Suppose that $i$ and $j$ are two agents that each one obtains her state dependets signal $s_i(\omega)$ and $s_j(\omega)$. After observing their own signals with probability $1$, they do not know anything about the signal that the other agent has, but they do know the common prior $\pi$ about the signals, s.t. $\pi:\Omega\to \D ...

Suppose we have a (t,n) Shamir-secret sharing scheme. A value of some computation is shared with n parties where at most $t-1$ parties are malicious. What is the best strategy to reconstruct the shares? I believe we can use Reed-Solomon error corrections to retrieve value for upto t<n/3. For t<n/2, we can randomly reconstruct $k$ times using $t$ shares and check for the value that appears the most n ...

Let us say we have to generate Shamir's secret share for n data points. Is there a way to speed up the implementation apart from using Horner's rule for the polynomial evaluation?

Is there a method by which a secret can be split across multiple nodes, such that:

1. No one node can learn the secret.
2. An adversary can't learn the secret by bringing up multiple dummy nodes.
3. Redundancy can be had if one or more nodes in the network fail.

There is a field of exchanging information that combines cryptography and game theory. I am interested in understanding this field, but it's a little complex for me. To begin with there is a paper of Barany which shows that instead of having a centralized mechanism of information where a mediator can inform the players about what strategy to follow, the players instead can replace the mediator w ...

Are there any different secret sharing schemes instead of Shamir's Secret Sharing , that is not based in polynomial interpolation over finite fields? Or is it the most efficient than the others?

With this question I am referring to the BGW multiplication by Gennaro et al (PDF here). The multiplication is described on the 4th page. (Another source for me was "A pragmatic Introduction to Secure Multi-Party Computation" p. 43-44)

Summary of BGW Multiplication Procedure: To do the multiplication of 2 secret values $\alpha$ and $\beta$ of every player $P_i$ has to have the share $f_{\alpha}(i ...

I want to put text into multisig cryptologic and store them in separate 3 locations with a fault tolerance of 1 but only 2 are needed to get the text. I think some people call is Shamir's Secret. So my question is there an easy to use application for something like this? Prefer not to develop something if it already exists.

This is about the paper Protecting AES with Shamir's Secret Sharing Scheme by Louis Goubin and Ange Martinelli which describes how to use Shamir Secret Sharing to obtain masked implementations of AES.

The end of section 3.1 suggests that the $\text{GF}(2)$-affine transformation $A$ involved in the definition of the AES S-Box is compatible with SSS in the sense that if $(x_i,y_i)$ is an SSS sharing of

I'm currently working on a distributed threshold DSA scheme that requires to find the product of two sums via secure multi-party computation. Specifically speaking, every one of $n$ parties $P_i$ possesses a DSA key pair $(sk_i, pk_i)$, where $sk_i=d_i \in \mathbb{Z}_q$ and $pk_i = g^{d_i}$. I want to collectively generate a signature $S_{\Sigma} = k_{\Sigma}^{-1}(m+r_{\Sigma}d_{\Sigma})$, where$k_ ...

Is there such a encryption and decryption mechanism: Given an encryption C = E(K1, M), where K1 is the encryption key and M is plain text, it have to apply decryption with two keys K2 and K3 sequentially to recover M, that is D(K3, D(K2, C)) = M. Given a K1, it is ideal to generate unlimited number of pairs K2 and K3 to ensure distributed trust. The encryption and decryption shall not be too slow for la ...

Let $t$ be a threshold in the Shamir secret sharing (SSS) scheme.

Assume we know $t'<t$ shares. Assume we are given some random values picked uniformly from the same field as the one used in SSS.

Question: can we distinguish the random values from the shares with a non-negligible probability?

With regards to SMPC with additive secret sharing, the protocol I am using involves a centralized node(the querier) orchestrating the share creation at client end via setting their random seeds. Now this allows the central party to reconstruct data. My question is does there exist an implementation with no member-member connections such that additive shares can be created without the central party knowi ...

Say, using something like Shamir's polynomial scheme, you split a secret $x$ among $n$ people (each given a "share" of the secret) such that you need all $n$ shares to recover the secret. How can one ensure that all $n$ participants will have access to the secret. E.g. with two people, Bob and Alice, Alice could tell Bob her share, and Bob could just take that and open the secret without disclosing  ...

I am a researcher in cryptography. Most of the time I generally do theoretical/Mathematical work only and not doing the implementation part.

I am not able to get the feel about the time complexity of algorithms theoretically. We can get the time complexity of algorithms by doing proper implementation. I want to implement algorithms/schemes to find out the time complexity and other aspects of algo ...

In Shamir's secret sharing scheme, Dealer performs the following steps

1. Choose a prime number $q$ such that $q > n$

2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

4. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

5. At least threshold number of participants ca ...

The question is related to the multi-secret sharing scheme described in the following paper:

[FY92] Matthew K. Franklin, Moti Yung: Communication Complexity of Secure Computation (Extended Abstract). STOC 1992: 699-710 (Link)

Following is some background. However, if you're familiar with that paper, you can skip directly to the main question below (highlighted with bold header font).

A $(t-k+1,t+1;k,n) ...

Given a secret splitting scheme $(n ,n)$ that creates $n$ shares from secret $s$. In this scheme all shares must be combined to create $s$.

How do you create a secret splitting scheme $(n, t)$? Of $n$ parts at least $t$ parts must be combined to determine secret $s$?

$n =$ # of Parts

$s =$ Secret

$t =$ Threshold of parts needed to create the secrets

$s_1, s_2, s_3, ... =$ Shares in a $(n, n)$ secret  ...

I want to compare additive secret share to Paillier encryption. However, I haven't found out how to set the parameters in such a way that the security level is consistent. Additive secret share (explained in SecureML) just like this: $a_1 = a - a_0 \mod 2^l$

I've been conducting some research into general-purpose MPC protocols and have been unable to pinpoint the exact security offered by the BMR protocol. The reference I've been using for the majority of my research is “A pragmatic introduction to secure multi-party computation" by Evans et al., which states that BMR is able to achieve security "against any $t < n$ number of corruptions among ...

Can Shamir secret sharing scheme (SSS) be verified using automated verification tools such as AVISPA? I read in the HLPSL manual that we cannot use arithmetic or relative operations such +,-,< ...etc in the HLPSL description of the protocol. Thus, we cannot implement LaGrange's interpolation formula?!! Do all protocol verification have this limitation?

(There are other protocol verification to ...

I understand there are already few question here which are similar but mine is a bit different in that I want to split AES 256 bit into two 128 bit key and then use a different AES key of 128bit to encrypt the two 128 bit key for transport of the key between two processor. is this secure to do? I am currently limited due to the design of my system. Following is what I require:

• I need to transport the ...

I am successfully working on Shamir's secret sharing scheme for few months. But the only issue I am facing is the calculation of theoretical time complexity.

Since I am from algorithmic background, I am unaware of the time complexities of the cryptographic operations. Although I found a question that discuss about running times of cryptographic primitive operations, I cannot able to figure out the ...

The problem I'm trying to solve: Identifying the cheater in (3,5)-Shamir's secret sharing when we can see only the 3 shares that were given to the system in the secret reconstruction process, and we can inquire the 3 people who inserted the shares into the system(they don't know what the other people inserted). Also, we have no knowledge about the correct secret, but we do know the wrong secret.

 ...

As I am going through the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018, I am stumbled by the key generation protocol (Sect. 4.1, p.10):

In Phase 1, they create a (commitment, decommitment) pair using a commitment scheme. Earlier in the paper, they mention that “in practice one can use any secure hash function H and define the commitment to x ...