-1
$\begingroup$

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there can be such an analogue.

Suppose that we have a standard cryptosystem. Mathematically, a cryptosystem or encryption scheme can be defined as a tuple $(\mathcal {P},\mathcal {C},\mathcal {K},\mathcal {E},\mathcal {D})$. Also, I provide some details about the Shamir's secret sharing scheme starting with the next theorem that determines the intuition of the whole theorem.

$\textbf{Theorem:}$ Let $p$ be a prime, and let $\{(x_1,y_1), . . . ,(x_{t+1},y{t+1})\}\subseteq\mathbb{Z}_p$ to be a set of points whose $x_i$ values are all distinct. Then there is a unique degree-$t$ polynomial $f$ with coefficients from $\mathbb{Z}_p$ that satisfies $y_i \equiv_p f(x_i)$ for all $i$ (I would add to the theorem where $s=f(0)$).

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

$$f(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0=s+\sum_{i=1}^ta_ix^i,\quad\text{such that $y_i \equiv_p f(x_i)$ and $s=f(0)$}\quad (1)$$

I have the following questions:

  1. Does $y_i \equiv_p f(x_i)$ mean $y_i\equiv f(x_i)(mod{p})$? Can we make calculations with the $y_i'$s like $y_1+...+y_{t+1}\equiv_{p}(f(x_1)+...f(x_{t+1})$? And if we can sum all $y_i$ does this mean that we obtain $s$?
  2. If we want to make a parallelism with the classic cryptosystem what could we define as the cipher-text $\mathcal{C}$ the keys $\mathcal{K}$, the encryption-decryption functions?

Let me put it simply. What is supposed to be the encrytoion-decrytpion scheme here? For example in a simple cryptosystem the agent needs the key to decrypt the message. In this case we have a $t$ out of $n$ scheme. What could we define as encryption and what as decryption process here?

$\endgroup$
1
  • $\begingroup$ ok maybe my question is not so clear.... $\endgroup$ Commented Jan 16, 2022 at 11:15

1 Answer 1

0
$\begingroup$

A secret sharing scheme is not a classical encryption scheme. So I don't think one can cast it in any meaningful way into that framework.

As for your other questions if you are operating in the finite field with $p$ elements where $p$ is a prime all computations are modulo $p$.

That $\equiv_p$ notation is a horrible notation but I presume it stands for equality modulo $p.$

The equation below $$y_1+...+y_{t+1}\equiv_{p}f(x_1)+...f(x_{t+1})=s$$ will not hold in general, certainly will not hold for a randomly chosen polynomial $f$ which is the whole point of Shamir secret sharing.

$\endgroup$
2
  • $\begingroup$ @kodly I did not conclude that holds. I ask if you can do such calculations...just ask...i do not know it. I am looking forward to understand the notation....an I wonder...could this hold? $\endgroup$ Commented Jan 17, 2022 at 13:39
  • 1
    $\begingroup$ no problem, fixed my answer $\endgroup$
    – kodlu
    Commented Jan 17, 2022 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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