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
1
vote
0answers
32 views

Secure protocols with the dynamic programming solution concept?

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,....
0
votes
0answers
28 views

Security of verifiable shamir secret share

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 ...
0
votes
0answers
30 views

Linear operations on packed Shamir secret share

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 ...
0
votes
0answers
26 views

Fast implementations of verifiable Shamir's Secret shares

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))...
1
vote
1answer
50 views

Secret sharing is based in random variables that are uniformly distributed?

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 ...
2
votes
0answers
19 views

Example of exchanging information

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)$. ...
2
votes
1answer
38 views

Reconstruction of shamir secret shares in the presence of malicious parties

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 ...
1
vote
1answer
44 views

How to speed up Shamir secret share generation?

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?
0
votes
1answer
50 views

Secret Sharing in a decentralized network

Is there a method by which a secret can be split across multiple nodes, such that: No one node can learn the secret. An adversary can't learn the secret by bringing up multiple dummy nodes. ...
3
votes
0answers
32 views

Algorithmic game theory and protocol design for communication

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 ...
2
votes
2answers
210 views

Different secret sharing schemes instead of Shamir's?

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?
3
votes
1answer
63 views

BGW multiplication by Gennaro et al.: Why does H(x) have exactly degree t and why is $2t + 1 \le n$ necessary?

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 ...
0
votes
0answers
30 views

Multisignature 2 of 3 cryptology

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 ...
3
votes
2answers
114 views

Protecting AES via Shamir Secret Sharing

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. ...
1
vote
1answer
46 views

Find the product of two sums via SMPC

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$ ...
1
vote
2answers
144 views

fast encryption with one key and fast decryption with multiple keys sequentially

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 ...
0
votes
3answers
116 views

Are the shares of Shamir secret sharing uniformly distributed random numbers?

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. ...
0
votes
0answers
21 views

Centralized orchestration of Secret Shares for SMPC

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 ...
4
votes
1answer
54 views

Secret sharing such that all shareholders obtain access to the secret (one shareholder can't just run off with the shares)

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. ...
0
votes
0answers
71 views

Which contemporary programming language is apt for implementation of algorithms in cryptography?

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 ...
1
vote
1answer
103 views

What is the reason for Shamir scheme to use modulo prime?

In Shamir's secret sharing scheme, Dealer performs the following steps Choose a prime number $q$ such that $q > n$ Choose a secret $s$ from finite field $\mathbb{Z}_q$ Choose $t-1$ degree ...
3
votes
0answers
59 views

Product of secrets in multi-secret sharing schemes (aka packed secret sharing schemes)

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). ...
2
votes
1answer
57 views

How to create (n, t) secret splitting from (n, n) secret splitting?

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$ ...
0
votes
1answer
43 views

The security level of secret share compared to homomorphic encryption

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 (...
0
votes
0answers
50 views

What security does the BMR protocol offer against corruption?

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 ...
0
votes
0answers
47 views

Shamir secret sharing in automated verification tools

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 +,-,< ......
0
votes
1answer
71 views

Splitting an AES-256 key into two?

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 ...
2
votes
0answers
74 views

Detailed running time analysis for Shamir secret sharing scheme

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 ...
2
votes
2answers
101 views

Identifying the cheater in (3,5)-Shamir's secret sharing

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 ...
1
vote
1answer
72 views

Gennaro & Goldfeder Key Generation Protocol

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
vote
1answer
82 views

SS/HE/GC/OT secure integer comparison

I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in ...
0
votes
0answers
72 views

Proof of theoritical security of Shamir's secret sharing

community ! I'm looking for the proof of theoritical security of Shamir's secret sharing. I found some articles saying that it's assimilable to the halting problem, which implies that there is no ...
0
votes
1answer
85 views

Time complexity of a brute force attack on Shamir's Secret Sharing SSS

I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key. I'm confused between if it is $O(p^k)$ or $O(p)$, such that $p$ is the ...
0
votes
1answer
96 views

Are Shamir shares independent?

Assume we have a secret $s \in Z_p$. We generate the set of secret shares $\{ (x_i, s_i) \}_{i=1}^{N}$ according to a $(N,k)$ Shamir's scheme. The evaluations are generated according to the following ...
1
vote
2answers
81 views

Transparent Voting and Advance Secret Code

In the book "Introduction to the Theory of Computation", Michael Sipser writes The field of cryptography, as this area is known, now extends well beyond secret codes for private ...
0
votes
2answers
118 views

Is the dealer a volunteer in Shamir secret sharing scheme?

In this Paper, Shamir secret sharing scheme there is one dealer and n players. The dealer gives a share of the secret to the players, but only when specific conditions are fulfilled will the players ...
0
votes
1answer
39 views

summation problem?

Let there are two given numbers $x,y$ which is $A=x+y$ and we know just $A$. How we can find this just $x$ and $y$? If you suppose $a$ a random number, then we know $x_1=a$ and $y_1=A-a$ satisfies in $...
2
votes
1answer
63 views

Real-world offline phase implementation in MPC setting

I've been reading up on various basic MPC primitives (multiplication, inversion, exponentiation and so on of secrets shared between multiple parties). One of the problems of implementing MPC in real-...
2
votes
1answer
59 views

How to do unmasked addition on SSS masked shares?

I'm trying to understand how Shamir's Secret Sharing algorithm is applied to AES when doing threshold masking. I understand how the secrets are created and the secret is calculated and I'm now trying ...
2
votes
1answer
112 views

Should the field size in Shamir secret sharing scheme be larger than secret?

I'm playing around with implementing Shamir's secret sharing scheme in Kotlin. Here is implementation so far: ...
0
votes
0answers
60 views

Shamir secret sharing scheme only works with certain parameters

im doing a small programming project, where I have to implement shamirs secret sharing scheme. I want to share the secret S = 21426848149916227113669602 I want a k of three, meanng that three shares ...
0
votes
1answer
76 views

Difference between Multi-linear and Multi-Secret Sharing Schemes

I've been reading papers on secret sharing schemes and came to two different terms, namely, multi-linear secret sharing schemes and multi-secret sharing schemes. As an example, the term multi-linear ...
0
votes
0answers
23 views

How to compare the size of two shared secrets?

Suppose there are two secrets x and y which are split as $[[x]]=x_1+x_2+\cdots+x_n$ and $[[y]]=y_1+y_2+\cdots+y_n$. Is there anyway to generate a bit [[x > y]] with additional assumptions?
1
vote
2answers
109 views

How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key

Given an elliptic curve with generator $G$, is it possible to generate a random point on the curve $Q = a \cdot G$ without knowing the secret value $a$ that generated it? Note that just using an $a$ ...
3
votes
1answer
229 views

How do I multiply two points on an elliptic curve?

Tell me if there is a way to multiply two points on an elliptic curve? For example, as in secp256k1 ...
1
vote
1answer
105 views

Proving I can solve an equation without disclosing the solution (zero-knowledge proof)

Given a (potentially multivariable) equation $f(x)=0$, Peggy wants to prove to Victor that she knows a solution $x^\star$ to it without actually disclosing anything information about the value of $x^\...
1
vote
0answers
80 views

Understanding multiplication of Shamir secret sharing during threshold (EC)DSA signing

I have been looking at the threshold (EC)DSA schemes for honest majority by Gennaro et al. https://www.sciencedirect.com/science/article/pii/S0890540100928815. In the scheme, there are steps where we ...
0
votes
1answer
148 views

Multi-Linear Secret Sharing vs. Shamir Secret Sharing

I hope someone can help me. I read several papers including the original paper, "Multi-linear Secret-sharing Schemes," by Beimel et al., and watched the following video https://www.youtube....
5
votes
1answer
95 views

Secure Secret Sharing to a Distributed Key

Setup There are two groups, $A$ and $B$. Each group is in a Shamir's secret sharing scheme ($t_A$ of $N_A$ and $t_B$ of $N_B$). Each group has a public key that is associated with the identity of the ...
8
votes
5answers
2k views

Computational Complexity Of Breaking Information Theoretic Security

Wikipedia mentions that Shamir's secret sharing(SSS) for example, has information theoretic security. While I understand the concept that the adversary would just not have enough information to break ...

1
2 3 4 5
9