Mixing
Secret sharing over reals - constructing a (k,n) threshold scheme
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz
The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)
We first introduce a (k,k) secret-sharing scheme which distributes a
secret a taken from the interval [0,1). We use the Lebesgue
measure on [0,1) Choose independently, with a uniform distribution,
k-1 real numbers, $s_1$,.., $s_k-1$ in the interval [0,1). 2)
Choose $s_k$ $in$ [0,1) which satisfies $s_1$ +...+ $s_k-1$
+$s_k$ = a (mod 1). The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
For introducing a (k ,n) secret-sharing scheme for every k $leq$ n,
we observe that the same technique described in [BL] works here as
well.
I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!
secret-sharing
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz
The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)
We first introduce a (k,k) secret-sharing scheme which distributes a
secret a taken from the interval [0,1). We use the Lebesgue
measure on [0,1) Choose independently, with a uniform distribution,
k-1 real numbers, $s_1$,.., $s_k-1$ in the interval [0,1). 2)
Choose $s_k$ $in$ [0,1) which satisfies $s_1$ +...+ $s_k-1$
+$s_k$ = a (mod 1). The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
For introducing a (k ,n) secret-sharing scheme for every k $leq$ n,
we observe that the same technique described in [BL] works here as
well.
I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!
secret-sharing
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz
The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)
We first introduce a (k,k) secret-sharing scheme which distributes a
secret a taken from the interval [0,1). We use the Lebesgue
measure on [0,1) Choose independently, with a uniform distribution,
k-1 real numbers, $s_1$,.., $s_k-1$ in the interval [0,1). 2)
Choose $s_k$ $in$ [0,1) which satisfies $s_1$ +...+ $s_k-1$
+$s_k$ = a (mod 1). The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
For introducing a (k ,n) secret-sharing scheme for every k $leq$ n,
we observe that the same technique described in [BL] works here as
well.
I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!
secret-sharing
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz
The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)
We first introduce a (k,k) secret-sharing scheme which distributes a
secret a taken from the interval [0,1). We use the Lebesgue
measure on [0,1) Choose independently, with a uniform distribution,
k-1 real numbers, $s_1$,.., $s_k-1$ in the interval [0,1). 2)
Choose $s_k$ $in$ [0,1) which satisfies $s_1$ +...+ $s_k-1$
+$s_k$ = a (mod 1). The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
For introducing a (k ,n) secret-sharing scheme for every k $leq$ n,
we observe that the same technique described in [BL] works here as
well.
I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!
secret-sharing
secret-sharing
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Rahul Mathur
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Rahul Mathur
345
asked 3 hours ago
Rahul Mathur
345
345
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Rahul Mathur is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
This $(k,n)$ scheme works, but isn't very interesting.
Effectively, it is:
- For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.
For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $binom32 = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 bmod 1), (r_2, z-r_2 bmod 1), (r_3, z-r_3 bmod 1)$, and distribute to the three share holders the shares:
$$(r_1, z-r_2 bmod 1)$$
$$(r_2, z-r_3 bmod 1)$$
$$(r_3, z-r_1 bmod 1)$$
It works, as:
For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.
It's quite straight-forward; the biggest issue is that this requires distributing $binomn-1k-1$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.
answered 2 hours ago
poncho
87.1k2130220
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
This $(k,n)$ scheme works, but isn't very interesting.
Effectively, it is:
- For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.
For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $binom32 = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 bmod 1), (r_2, z-r_2 bmod 1), (r_3, z-r_3 bmod 1)$, and distribute to the three share holders the shares:
$$(r_1, z-r_2 bmod 1)$$
$$(r_2, z-r_3 bmod 1)$$
$$(r_3, z-r_1 bmod 1)$$
It works, as:
For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.
It's quite straight-forward; the biggest issue is that this requires distributing $binomn-1k-1$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.
answered 2 hours ago
poncho
87.1k2130220
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
add a comment |Â
up vote
4
down vote
accepted
This $(k,n)$ scheme works, but isn't very interesting.
Effectively, it is:
- For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.
For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $binom32 = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 bmod 1), (r_2, z-r_2 bmod 1), (r_3, z-r_3 bmod 1)$, and distribute to the three share holders the shares:
$$(r_1, z-r_2 bmod 1)$$
$$(r_2, z-r_3 bmod 1)$$
$$(r_3, z-r_1 bmod 1)$$
It works, as:
For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.
It's quite straight-forward; the biggest issue is that this requires distributing $binomn-1k-1$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.
answered 2 hours ago
poncho
87.1k2130220
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
This $(k,n)$ scheme works, but isn't very interesting.
Effectively, it is:
- For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.
For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $binom32 = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 bmod 1), (r_2, z-r_2 bmod 1), (r_3, z-r_3 bmod 1)$, and distribute to the three share holders the shares:
$$(r_1, z-r_2 bmod 1)$$
$$(r_2, z-r_3 bmod 1)$$
$$(r_3, z-r_1 bmod 1)$$
It works, as:
For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.
It's quite straight-forward; the biggest issue is that this requires distributing $binomn-1k-1$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.
answered 2 hours ago
poncho
87.1k2130220
This $(k,n)$ scheme works, but isn't very interesting.
Effectively, it is:
- For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.
For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $binom32 = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 bmod 1), (r_2, z-r_2 bmod 1), (r_3, z-r_3 bmod 1)$, and distribute to the three share holders the shares:
$$(r_1, z-r_2 bmod 1)$$
$$(r_2, z-r_3 bmod 1)$$
$$(r_3, z-r_1 bmod 1)$$
It works, as:
For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.
It's quite straight-forward; the biggest issue is that this requires distributing $binomn-1k-1$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.
answered 2 hours ago
poncho
87.1k2130220
answered 2 hours ago
poncho
87.1k2130220
answered 2 hours ago
poncho
87.1k2130220
answered 2 hours ago
poncho
87.1k2130220
87.1k2130220
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
add a comment |Â
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day!
– Rahul Mathur
2 hours ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
(500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement.
– Ken Goss
20 mins ago
add a comment |Â
Rahul Mathur is a new contributor. Be nice, and check out our Code of Conduct.
Rahul Mathur is a new contributor. Be nice, and check out our Code of Conduct.
Rahul Mathur is a new contributor. Be nice, and check out our Code of Conduct.
Rahul Mathur is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63427%2fsecret-sharing-over-reals-constructing-a-k-n-threshold-scheme%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password