1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Rob
    Jan 18 at 18:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – Rob
    Jan 18 at 18:33

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Hunger Learn
    Jan 18 at 14:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – kodlu
    Jan 18 at 14:54
  • $\begingroup$ thanks.... I think I am ok now $\endgroup$
    – Hunger Learn
    Jan 18 at 14:59
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – Hunger Learn
    Jan 18 at 16:45
  • $\begingroup$ 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... $\endgroup$
    – Hunger Learn
    Jan 18 at 16:47
  • $\begingroup$ 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? $\endgroup$
    – Hunger Learn
    Jan 18 at 16:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – Rob
    Jan 18 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.