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
118 views

Does using a verifiable secret sharing scheme ensure robustness of a protocol if it is secure under the semi-honest adversarial model

Consider a protocol $\pi$ which uses a linear secret sharing scheme like that of Shamir secret sharing. Further assume that the protocol $\pi$ has been proven to be secure (correctness and privacy) ...
3
votes
1answer
93 views

The role of the dealer in visual cryptography

In visual cryptography schemes (VCS), there is special person called dealer. The dealer sets up the system, and the only one who knows about secret image. After encryption, the dealer distributes the ...
4
votes
1answer
1k views

Beavers Triple Vs BGW Multiplication on MPC

Typically MPC protocols that are secure against semi-honest adversaries recommend the use of the revised GMW multiplication protocol by Gennaro et al. This is not the case against Active adversaries ...
3
votes
0answers
167 views

Majority encryption algorithm?

Assume that I want to leave an encrypted message to a group of $n$ people in a way that they can only decrypt it if they work together in the following sense: For some fixed $k < n$ every sub-...
4
votes
0answers
107 views

Committing to a secret shared value

Suppose I run a multiparty protocol. At the output stage, I have the function output in a secret shared manner among all parties. Now I want all the parties to commit to their value of the secret ...
6
votes
4answers
840 views

Shamir's Secret Sharing vs. Asmuth-Bloom scheme

I need to make use of a secret sharing scheme and I don't really know how to decide which one to use, Shamir's or Asmuth-Bloom (using CRT). The complexity for recovering the secret seems to be linear ...
1
vote
1answer
677 views

Shamir secret sharing: calculate rest of shares when you know secret and one share

Using Shamir secret sharing, one is starting with a secret and end up with a number of shares based on a polynomial. For example: INPUT: secret: 123456 Shares:4 ...
3
votes
1answer
485 views

Asmuth-Bloom's threshold secret sharing scheme

I was learning Asmuth-Bloom's threshold secret sharing scheme. I was working out an example as given in this Wikipedia article. As per the example, the secret, d is 2, the number of shares, n is 4 and ...
2
votes
1answer
491 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
1answer
336 views

How to implement oblivious transfer where probability of the receiver getting secret is exactly 1 out of 4? [duplicate]

As we know that oblivious transfer is done with probability of 1 out of 2. But how to implement it with probability of 1 out of 3 or 1 out of 4??
5
votes
1answer
338 views

Difference between hierarchical and multi level secret sharing

In this paper, the definitions are simply as follows. Multi-Level secret sharing: Higher level participants can help lower participants to get the secret. Compartmented secret sharing: Each level ...
5
votes
1answer
104 views

Terminology for secret sharing?

To my understanding, there are two "approaches" to t out of n threshold encryption. In both of them, n shares are given to different shareholders, and at least t of them must agree to "proceed". "...
2
votes
2answers
68 views

Can you update a (k,n) scheme to a (k+t, n+t) scheme (assuming old keys can be deleted)?

I know that $(k,n)$ can increased to $(k+t,n-s)$ one, by generating a random polynomial $p(x)$ of degree $k+t$ with constant term $0$, and then ordering each agent $a$ to add $p(a_x)$ (where $a_x$ is ...
1
vote
0answers
142 views

Weighted secret sharing scheme?

Is there a secret sharing scheme where secrets can be weighted, and that you need a total weight of $1$ to unlock the secret? I know that you could, of course, just figure out every subset that has ...
0
votes
2answers
73 views

Can we share an n-bit string by using shamir's secret sharing n times?

For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order 2? ...
1
vote
0answers
51 views

Is Shamir's Secret Sharing Scheme insecure for larger field? [duplicate]

According to wikipedia, if you are using shamir's secret sharing scheme with a field of order $p$, "High values of $p$ are risky because Eve knows that the chance for $f(x)\pmod{p}=f(x)$ increases ...
1
vote
0answers
28 views

Shamir SS: To associate shares to the public values $x_i$, when the shares are permuted [duplicate]

Suppose we use $(t,n)$ Shamir secret sharing as follows: We share the secret $\beta$ as $S=[s_1,..., s_n]$, where $X=[x_1,...,x_n]$ are the public values. For the sake of simplicity, lets assume that ...
4
votes
1answer
210 views

When all shares of a secret are given to adversary as a permuted matrix

Suppose we have a secret $\sigma$. The secret comes from a universe in which the elements are not necessarily distributed uniformly. We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (...
4
votes
1answer
139 views

Could we share a secret key using the Birthday problem?

I stumbled upon this code on-line, it seems obvious to me that generating all 2^40 keys in trivial time can always be achieved as can hashing each and everyone of them, using the SHARED Salt that "Eve"...
6
votes
2answers
249 views

Shamir's Secret Scheme : Knowing the threshold

If I am decoding a key by applying shares, is it possible to know when the threshold has been reached, and the secret revealed, without having to be told what the threshold is? Also, is it possible ...
4
votes
1answer
102 views

Information theoretical security of an inefficient Shamir based access structure

I have studied Sharmir's scheme as well as the multiple assignment scheme proposed by M. Ito. My question is if anyone can tell me if the following scheme is theoretically secure: Terms: P = set of ...
2
votes
1answer
611 views

How secure is Shamir's Secret Sharing for password sharing when attacker has t-1 shares?

I am designing protocol to share a random generated n long password between k parties using Shamir's Secret Sharing. I know that share alone does not reveal much information about the original ...
10
votes
1answer
342 views

Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the ...
3
votes
1answer
298 views

Multi-Party Encryption for a Shared Document

Is there an encryption algorithm/protocol where any of a pre-defined set of keys/passwords will succeed in decrypting a document? The number of keys can be fixed, say, 10 or 20 possible passwords. ...
5
votes
2answers
205 views

How many polynomials are used in Secure Multiparty Computation?

Secure Multiparty Computation based on Samir Secret sharing methods rely on Polynomials. Imagine corpus of data should be outsourced to bunch of untrusted servers for any computations. Now the data ...
2
votes
0answers
159 views

Can you explain “k out of n” from the VCS paper by Naor and Shamir

I am new to visual cryptography. I’ve just read the paper “Visual Cryptography” by Moni Naor and Adi Shamir and I'm stuck on the chapter about the “$k$ out of $n$” construction. I am aware that, on ...
2
votes
2answers
380 views

regular expression matching on encrypted data using secure multiparty computation

Lets consider Secure Multiparty Computation based on Secret Sharing schemes (rather than Garbled Circuits approach). If we have to do regular expression matching on secret shares of words of texts. ...
2
votes
0answers
139 views

Signing integers and UUIDs and restoring them from a third party server without tampering

I'm educating myself about cryptography. I know this is a long one, but please, bear with me. :) Now I have a scenario in my mind and I'd like to ask if what I've thought is sound (enough), what more ...
-2
votes
1answer
259 views

How do we solve Shammir 2,3 sharring scheme where arithmetic is modulo?

I am trying to get secret S and I have 3 values (2,2)(6,3)(4,9) and know that modulo is 13. I tried using Lagrange basis polynomial and got 8 but I am not sure if that is right and also I cannot find ...
3
votes
0answers
566 views

How to prove that a commitment hides the decryption of an ElGamal ciphertext?

I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question. For this question I need to prove that I've committed to a ...
2
votes
3answers
197 views

Security guarantees of Shamir's secret sharing when some co-efficients are zero

Shamir secret sharing techniques rely on polynomials for splitting and reconstructing. It's security properties are very good, i.e. it is impossible to reconstruct the secret when $t-1$ shares are ...
1
vote
1answer
97 views

Explanation of vector in Visual Cryptography

I'm starting to study about visual cryptography, but I am stuck with the following problem. On paper "Visual Cryptography" by Moni Naor and Adi Shamir, on page 6. How to read/what is the meaning of $...
2
votes
1answer
130 views

Secret only known on consensus

Does a method exist where a secret is generated so that is is unknown until 3 or more people (predetermined) reach consensus that it should be revealed?
1
vote
1answer
481 views

Two rounds of SHA-256 HMAC?

In a project we are working on, we have two applications within our datacenter that exchange messages. The messages are protected by an HMAC, and the secret key is stored on a SafeNet device. Update ...
5
votes
4answers
641 views

Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares?

Imagine we have $t-1$ shares in $(t,n)$ shamir secret sharing. So at least $t$ shares are needed. Question: Why cannot we use $t-1$ shares to find a root of the polynomial and then recover the ...
2
votes
1answer
101 views

What is this encryption system called?

Let's say you want to break down a message, for simplicity it is just a bit $0$ or $1$, $m$ into two messages $(m_1, m_2)$ as follows: If $m =0$, then $(m_1, m_2) = (0, 0)$ with probability $1/2$ and ...
1
vote
1answer
492 views

Secret Sharing Encryption

Suppose Alice shares a secret block cipher key, $K_{AB}$ with Bob, and a different secret block cipher key, $K_{AC}$ with Charlie. Describe a method for Alice to encrypt an m block message such that ...
2
votes
1answer
886 views

Any reason to use Shamir given faster XOR threshold secret sharing algos?

TL;DR: Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)? https://scholar.google.com/scholar?q=kurihara+secret+...
0
votes
0answers
414 views

Public key of a split key without calculating private key

I am searching for a secret splitting scheme where the private key doesn't exist, since each party chooses their own secrets. The other parties should however still be able to calculate the public key....
4
votes
0answers
230 views

Explanation of part of a visual cryptography algorithm

I have been working on a project involving visual cryptography and I am stuck with the following problem. My question is related to this paper, AN IMPROVED VISUAL CRYPTOGRAPHY SCHEME FOR SECRET ...
2
votes
1answer
140 views

Does pseudorandom secret sharing require a central dealer?

I'm trying to figure out whether pseudorandom secret sharing (as described in this paper) requires a central dealer, i.e. one party who doles out keys to the other players and thus who would be able ...
6
votes
2answers
854 views

An electronic voting system

This semester I am taking the course Cryptography. I will have a presentation about the topic "Voting Scheme". I am preparing myself by reading from the book “Cryptography : an Introduction” by N....
0
votes
1answer
191 views

Shamir secret sharing with field 2^8

I want to split a message using Shamir's Secret Sharing by splitting each byte of it so the field I'm using is $2^8$. Assume $(2,2)$ scheme, i.e., splitting it into $2$ shares and both of them are ...
3
votes
1answer
149 views

Image sharing without data overhead

The idea is to share $n$ images among $n$ persons so that all images can be reconstructed by someone in possession of all shares. However, there must not be any data overhead (which means the shares ...
1
vote
1answer
124 views

How are onetimepads distributed?

OTP encryption is unbreakable as it seems. I have read some stuff (wiki, blogpost, etc.) but i would not find any information how they are used. If i wanted to create a messenger service, how would i ...
3
votes
1answer
919 views

Choosing finite field size in Shamir's Secret Sharing Scheme

The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field $\rm{GF}(p)...
3
votes
1answer
545 views

Benefit of using random key in Shamir's Secret Sharing

I am implementing Shamir's Secret Sharing, and I find that in (t,n)-threshold scheme, the shares are just using 1,2,3...,n as the key to form the shares ...
2
votes
1answer
178 views

What is the difference between any secret sharing scheme and arithmetic secret sharing scheme

It looks like that only difference between two of them the variables. But it does not make sense for me and I could not find exact definition of arithmetic secret sharing scheme. I mean what exactly ...
2
votes
1answer
183 views

Recombination thresholds in degree reduction of multiplied Shamir shares

Shamir's secret sharing can be considered multiplicatively homomorphic, if one is aware of the fact that multiplying two shares of a (n,t)-threshold shared secret yields a share of the same secret, ...
0
votes
1answer
113 views

Using hashed password as shared secrets. Good or bad idea?

I built a system that allowed users to generate an unlimited number of email addresses. Instead of storing each one in a db, I created addresses dynamically and made the address an hmac signed ...