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
0answers
58 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
72 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
43 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
34 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
30 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
32 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
40 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
62 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 ...
0
votes
0answers
13 views

Modular arithmetic does not work in Threshold signature (TSS) implementation [migrated]

I was implementing threshold signatures protocol described in this paper and I run into a case where it fails and I don't understand reasons why. In the end, u and <...
2
votes
0answers
60 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
87 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
62 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
53 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
61 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
63 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
60 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
105 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
51 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
50 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
99 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
55 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
71 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
77 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
136 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
92 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
58 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
121 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
83 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
32 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
67 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
43 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
93 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
42 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
32 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
89 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
236 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
44 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 ...
5
votes
3answers
205 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....
2
votes
1answer
59 views

How (generally) do modern schemes deal with an adversary with the capacity to either instantly, or over time, corrupt a majority of parties

I'm curious about the honest minority case and what cryptographers have and are currently using to get around this. My motivation is primarily the MPC space, but I'm sure there are other subfields ...
1
vote
0answers
40 views

Looking for an algorithm to encrypt with a single key and decrypt with a lot of keys without consuming too much space

Is it possible to have an encryption scheme that could be encrypted with a particular key, then decrypted with a large amount of keys without massively inflating the size of the final result? I am ...
6
votes
2answers
269 views

Using XOR to derive a data key for ECIES

I have been thinking about a rather simple enhancement for (EC)IES / RSA-KEM. The scheme would allow you to encrypt data while the calculation of the session / data key can be performed afterwards or ...

1
2 3 4 5
9