Skip to main content
Became Hot Network Question
edited title
Link
Maarten Bodewes
  • 94.5k
  • 13
  • 165
  • 319

What is the reason for shamirShamir scheme to use modulo prime?

added 8 characters in body
Source Link
Natwar
  • 441
  • 2
  • 8

In Shamir's secret sharing scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, if we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

In Shamir's secret scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, if we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

In Shamir's secret sharing scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, if we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

In Shamir's secret scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q, i=1,2, \cdots,n$$s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, weif we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

In Shamir's secret scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q, i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 we write without $\mod q$ what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

In Shamir's secret scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, if we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

Improved formatting and increasing readability
Link
Loading
Loading
Loading
Loading
Source Link
Natwar
  • 441
  • 2
  • 8
Loading