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
0
votes
1answer
77 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
109 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
18 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
50 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
70 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
85 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
57 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
51 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
40 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
47 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
46 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
65 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
69 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
99 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
65 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
63 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
65 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
66 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
94 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
80 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
109 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
53 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
51 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
103 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
57 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
72 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
85 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$ ...
2
votes
1answer
156 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
98 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
68 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
129 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
88 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 ...
0
votes
1answer
39 views

Generating and distributing a secret without trusting the source

I have multiple entities (servers) that all share a private secret already. Those servers need a rotating secret (TTL a few hours). All servers must have the same set of secrets at all times. I have ...
1
vote
1answer
33 views

Encrypting a broadcast message decryptable by a subset of receivers

I wasn't certain how to title this request/problem, but here goes: I'm A, and I want to send a message that is received by B, C, D. Each receiving entity here is part of some set of domains D1, D2, D3:...
0
votes
0answers
25 views

Value of Prime P in shamir secret sharing

How the value of prime integer taken in Shamir's Secret sharing scheme. I have taken p which is greater than my secret and the no of shares. When i do calculation without modp then secret reconstruct ...
2
votes
1answer
68 views

Is linear secret sharing over the addittive group of integers modulo $p$ with $p$ non-prime secure?

In Maurer, Ueli. "Secure multi-party computation made simple." Discrete Applied Mathematics 154.2 (2006): 370-381. I have found the following technique for $k$-out-of-$k$ linear secret ...
0
votes
1answer
45 views

Can you use a "power of 2" gate in the BGW protocol

I am learning about the BGW Protocol and I understand that for a MUL gate, you need to follow the degree reduction protocol. I am wondering if it is possible to implement a single input and single ...
1
vote
1answer
72 views

Secret sharing by using just "private secrets"?

TLS is using 3 way handshake. Isn't that possible to use such 3 way handshake protocol to share a secret without using a public key scheme, for instance as follows: Let A, B be private secrets of ...
0
votes
1answer
111 views

Splitting Secret Key

If I split a key $k$ into three pieces as $k1, k2$ and $k3$ how should I distribute the keys among three people such that any two of them are able to evaluate PRF, but be secure from any one of them ...
0
votes
0answers
43 views

addition of shares from shamirs scheme and additive scheme

Assume we have two secrets $s_1$ and $s_2$. We use Shamir's scheme to produce $\{(x_i,y_i)\}$ as $n$ shares of $s_1$ with a threshold $t$. Then, we use the additive scheme to generate shares for $s_2$,...
0
votes
0answers
20 views

Threshold schemes

I am looking for a reference that lists all major $(n,k)$ secret sharing schemes. Can anyone help me get such a reference?
1
vote
0answers
33 views

Black-box secret sharing schemes

My question is about black box secret sharing schemes (BBSSS). Do these schemes have any advantages over the better known secret sharing schemes like Shamir’s?
0
votes
1answer
92 views

Noisy secret sharing

I am looking for a secret sharing scheme that is robust against noise, the shares are going to be noisy. We do not want to reconstruct the secret perfectly and a noisy reconstruction with a bound on ...
0
votes
1answer
59 views

Secret Sharing Domain Questions

all, I have a very fundamental question on Secret Sharing schemes such as SPDZ families. As far as I can see for now, SS schemes always assume a certain variable range. For example, suppose the bit ...
1
vote
2answers
266 views

Shamir secret sharing with no dealer

Suppose we have a set of $N$ parties. I am looking for a scheme to generate shares of a random secret $s$ where any subset of the participants with size $k$ can recover the secret similar to Shamir's ...
0
votes
0answers
46 views

Shamir's Secret sharing for Key encryption

I have studied Shamirs Secret Sharing(SSS) scheme. Now my doubt is to how to apply this in real time applications. I have an application which receives encrypted data from server and decrypts the data ...
4
votes
3answers
214 views

Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....

1
2 3 4 5
9