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
1answer
25 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
125 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 ...
1
vote
2answers
100 views

Inside attack (attack from participants) in secret sharing

I have considered a $(t,n)$ secret sharing scheme with $n$ secret, say $a1,a2....an$. It's third party secure, but it has inside adversaries. While reconstructing secrets, a group of $t$ qualified ...
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 ...
0
votes
3answers
110 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. ...
3
votes
1answer
294 views

Pseudorandom zero-sharing: how does it work?

TL;DR How can the shares of the PRZS protocol proposed in [CDI05] reconstruct the "secret" $0$? Is the number of shares required to reconstruct $0$ equal to $2t + 1$? Long question The paper "...
0
votes
0answers
19 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
52 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. ...
2
votes
1answer
52 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$ ...
7
votes
1answer
305 views

Why is a number of shares that is greater than a threshold required to construct a secret?

In this paper of Asmuth–Bloom threshold SSS, the algorithm is as follows: Shares Distribution To distribute n shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, the ...
2
votes
0answers
54 views

Asymmetric encryption, multiple recipients, traitor must share private key

Is there an asymmetric encryption scheme, or public-key encryption, where multiple recipients can access the data, but in order for one of the recipients to leak the key to the data, they would need ...
1
vote
0answers
62 views

Function secret sharing and sharing a truth table

I was reading a paper (Function Secret Sharing by Boyle, Gilboa and Ishai, PDF) on Function Secret Sharing and in that the author talked about a naive construction of a p party DPF wherein the truth ...
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
87 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
58 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). ...
3
votes
0answers
54 views

What is the fundamental difference between multipartite and multilevel secret sharing?

According to this paper , Multipartite secret sharing scheme is a scheme in which the set of participants is divided into disjoint parts and all participants in the same part play an equivalent role ...
0
votes
1answer
41 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 (...
1
vote
1answer
236 views

Does the transposition cipher have a network application?

So I'm reading a chapter in my networking book, and it talks about substitution and transposition ciphers. I know that most network security uses public key or symmetric encryption, but I wonder ...
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
48 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
1answer
94 views

Publicly verifiable secret sharing scheme

In https://www.win.tue.nl/~berry/papers/crypto99.pdf, Schoenmakers proposes a publicly verifiable secret sharing scheme, that uses a non-interactive DLEQ proof to allow any participant to verify the ...
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 ...
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 ...
0
votes
2answers
126 views

Secret sharing scheme verifiability

This secret sharing scheme takes place in the polynomial ring over a finite field $F_p[x]$, $p$ being a large prime, in the following simplified way: The dealer chooses a private polynomial $f(x)$. ...
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 ...
2
votes
2answers
100 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 ...
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 ...
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
67 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 ...
2
votes
2answers
801 views

Running time of Shamir's secret sharing scheme

Let $p>n$ be a prime number. The key steps in the $(t,n)$ Shamir's secret sharing is as follows: Steps of dealer: Choosing $s \in \mathbb{Z}_p^*$ Selecting $b_i \in \mathbb{Z}_p^*$ for polynomial ...
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 ...
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
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 ...
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
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?
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....
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^\...
2
votes
1answer
160 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
0answers
70 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 ...
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:...
1
vote
1answer
251 views

What is definition of "adversary"? And what do they do?

Currently I am writing my last assignment about secret sharing. But I don't clearly understand adversary. I know this is a fundamental concept in secret sharing. But I couldn't find references that ...
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 ...

1
2 3 4 5
9