Score:1

What could a_0=s in Shamir's secret sharing scheme represent?

ua flag

What could $a_0=s$ in Shamir's secret sharing scheme represent?

As we already know in a $k$ out of $n$ secret sharing scheme, a secret is split in $n$ parts however only $k=t$ parts (of a polynomial of degree $t-1$) are needed if we want to compute the secret. Suppose that $f$ is the polynomial function such that

$$f(x)=a_{t-1}x^{t-1}+a_{t-2}x^{t-2}+\cdots+a_1x+a_0=s+\sum_{i=1}^{t-1}a_ix^i,\text{such that } s=f(0)$$

$s\in\mathbb{F}_p$, say $s=5<p=11$, but in some cases we want to encode secrets like letters etc. Could we do this with this technique?

it flag
Rob
For example: s is a private CA signing key. a=Hash("SECRET"), a^s is an assertion that a user has the attribute "SECRET", signed by the CA. Often, strings are hashed into numbers. You do need to take some care when taking hashes of public information, so that users can't divide out values and multiply in chosen replacements. But points may be a hash or MAC in some protocols, etc.
it flag
Rob
Note: Plain "Shamir Secret Sharing" picks N random points in F_p, to define a curve. The curve itself is kept secret. N distinct, possibly random, points on that curve are required to construct the polynomial exactly, where f(0) is just a convenient point to agree upon as the secret key we want them to compute. The formula to take N points and calculate the curve, or just the key is really simple.
Score:3
sa flag

This is about encoding a quantity. It can represent anything you want. This encoding would be part of a publicly known protocol.

If you are in $\mathbb{F}_p$ the quantity $s=a_0$ can represent one out of any $p$ quantities.

Standard ways of encoding text include the ASCII code (look it up) for which $p\geq 256$ is sufficient.

If you use $\mathbb{F}_p$ you can also represent all binary vectors/strings of length $\lfloor \log_2 p\rfloor +1$ which is useful since modern symmetric ciphers operate on binary strings.

Hunger Learn avatar
ua flag
So if I want to define $s$ in such a way that it represents a description back to those who reconstruct the secret like "(1,g)" which will mean for example: To some agent was given the code number "$1$" and he has "good" information about the stock market, then how should I define the polynomial function and what extra assumptions to I need for the maths?
kodlu avatar
sa flag
you need to define your "language", i.e., the total number of possible messages. Sort them in a list, say {(1,g1), (2,g2,f), ....} and the contents of the list do not matter. If the list has $k$ messages then you number the messages (say) from 1 to k. In this case $s=2$ would represent the second message. nothing needs to change about the mathematics. this is really no longer about crypto.
Hunger Learn avatar
ua flag
thanks.... I think I am ok now
Score:1
it flag
Rob

When you are trying to do Attribute Based Encryption schemes, the collection of points has a nice property such that if you scale the x-axis by a scalar, the polynomial still passes through the same y-intercept. So, you can use this scheme to represent a hash for point combinations; and give different users an incompatible set of points (to help in collusion-resistant schemes). Points on a polynomial can be used as a sort of commutative/idempotent hash, where the original points can be discarded by pinning the curve at points x=1,x=2,...x=n.

There is a whole genre of cryptography using Kronecker Delta and secret sharing schemes; where you can encode digital circuits in equations. You can use Shamir point addition to do things that resemble things that you do with Elliptic Curves.

Hunger Learn avatar
ua flag
thanks for the nice answer, but since I am not so familiar with cryptography and I do not know the literature I do not exactly know how to define the mathematical structure for such cases. I am aware of the scheme of Scahmir and the classic protocols of BGW and BR, but in my case research is not about cryptography...I just need some tools to translate them in my research. Shamir's scheme in it's most simple formulation seems to work fine for an encoding scheme that is informational secure and the players easily reconstruct the secret for my model, but I need something more...
Hunger Learn avatar
ua flag
That is why I asked the question here...If you can provide a paper that simply defines and explains what you write above maybe it would help me...any reference but in it's most simple analytical view I would appreciate it...
Hunger Learn avatar
ua flag
Anyway how is a hash function defined? its mathematical structure? is it injective or bijective? or any other nice properties? and how is this connected with shamirs scheme?
it flag
Rob
google: cpabe, Zeutro, LSSS (Linear Secret Sharing Schemes). Allison Lewko, Brent Waters, Dan Boneh. All of the papers focus on pairings, but you need to understand LSSS to really understand what they are doing. In my case, it's about key derivation schemes that use boolean combinations of attributes. There are lots of similar crypto schemes that use polynomials; and are related to Shamir secret sharing.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.