To reconstruct a Polynomial with only the knowledge of Y`s

Aydin · 2014-05-26 22:30:44

The ultimate goal is hiding the value of Xs and coefficient and giving away the value of Ys. Scenario:Assume we have a polynomial with uniformly random random coefficients chosen from Fp. We pick distinct random Xs values from same field and obtain n different Ys. Now we keep all coefficients and Xs and only give away Ys.

note:all operation are modulo arithmetic

1)My question is can anybody with this Y`s obtain constant term of the initial polynomial?

2)Furthermore, if we construct some more polynomials with different random coefficients. Then use the same X values as above to obtain Y values for each polynomials. Assuming that all polynomials have the same constant term, can anybody without the knowledge of Xs and coefficients obtain the constant term, by having only Ys ?

If not why?

Many thanks

Agnishom · 2014-05-26 22:32:37

Is this cryptography?

I think the polynomial can be found..

Aydin · 2014-05-26 22:36:03

How, why?

Agnishom · 2014-05-26 22:41:12

Are you giving out just the y's and nothing else? Then maybe not.

but wait for bobbym

Aydin · 2014-05-26 22:45:36

if not why? (sorry for keep asking "why" as I need a concrete proof.

Many thanks

bobbym · 2014-05-26 22:45:37

Hi;

How about a small example please.

Aydin · 2014-05-26 22:47:20

In (n,n) Shamir secret sharing if the shareholders have all Y values but not X values, can they still construct the secret?
Hope it helps...

bobbym · 2014-05-26 22:51:05

I remember working on a similar question and the answer was yes. I do not know enough about shamir to answer in this case. Please show me some math question then I can help.

Aydin · 2014-05-26 22:57:41

(n,n) Shamir secret sharing: We construct a polynomial of degree n-1, whose coefficients are uniformly random. Then we get some distinct x values. We give away x values . The secret is the constant term in this polynomial. n-1 share holders cannot obtain the secret but n shareholders can (as we gave away a pair (x,y) to each shareholders). They can do it with Lagrange interpolation.

***** What if we do not send out the X values and only send Y values. would the n shareholders be able to reconstruct a polynomial to obtain the secret?

bobbym · 2014-05-26 22:59:55

Uniformly random? What ranges?

Aydin · 2014-05-26 23:02:22

all operation are modulo arithmetic e.g. mod p, where p is a prime, preferable large enough.

bobbym · 2014-05-26 23:05:11

That is not what I asked. These coefficients of the polynomial, what are there ranges?

Aydin · 2014-05-26 23:16:54

The coefficients are uniformly random chosen from Fp (field)
The x values are distinct values randomly chosen from same field.

bobbym · 2014-05-26 23:19:00

That is not helping. What field?

What uniform distribution? [0,1]? [0,1,2,3,4...p]?

Aydin · 2014-05-26 23:30:14

We pick a prime P which is large enough, then we use modular arithmetic instead of real arithmetic. So these coefficient and x values are chosen from this field [0,p). P is greater than the constant term and constant term and the degree of polynomial.

Regards

Aydin · 2014-05-26 23:31:30

Yes the second one excluding 0

Aydin · 2014-05-26 23:33:41

The coefficients could be zero but X values cannot be zero.

bobbym · 2014-05-26 23:34:56

You are showing something else. You say no 0 but you posted [0,p).

Aydin · 2014-05-26 23:37:20

As I explained later , the [0,p) applies to coefficients and (0,p) applies to X values. Moreover the X values should be distinct random number.

bobbym · 2014-05-26 23:40:06

Aydin wrote:

So these coefficient and x values are chosen from this field [0,p).

You said there they include 0.

Aydin wrote:

As I explained later , the [0,p) applies to coefficients and (0,p) applies to X values. Moreover the X values should be distinct random number.

Here you said something else. Which is it?

Aydin · 2014-05-26 23:43:37

Please consider the latest comment(the second comment that separates coefficients range from x values range)

Thank you again for your help.

bobbym · 2014-05-26 23:44:41

p I assume is a prime, therefore this is a Galois field?

Aydin · 2014-05-26 23:45:39

Yes , P is a prime number.

bobbym · 2014-05-26 23:48:31

Here is where you come to help. Make up a polynomial that fits your criterion. Give me the y's and the degree of the poly. Also, provide the mod. I will try to crack your code.

Aydin · 2014-05-27 00:09:11

Cool,
p=123457
y1=316
y2=637
degree of the polynomial is one

Math Is Fun Forum

#1 2014-05-26 22:30:44

To reconstruct a Polynomial with only the knowledge of Y`s

#2 2014-05-26 22:32:37

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#3 2014-05-26 22:36:03

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#4 2014-05-26 22:41:12

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#5 2014-05-26 22:45:36

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#6 2014-05-26 22:45:37

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#7 2014-05-26 22:47:20

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#8 2014-05-26 22:51:05

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#9 2014-05-26 22:57:41

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#10 2014-05-26 22:59:55

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#11 2014-05-26 23:02:22

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#12 2014-05-26 23:05:11

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#13 2014-05-26 23:16:54

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#14 2014-05-26 23:19:00

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#15 2014-05-26 23:30:14

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#16 2014-05-26 23:31:30

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#17 2014-05-26 23:33:41

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#18 2014-05-26 23:34:56

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#19 2014-05-26 23:37:20

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#20 2014-05-26 23:40:06

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#21 2014-05-26 23:43:37

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#22 2014-05-26 23:44:41

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#23 2014-05-26 23:45:39

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#24 2014-05-26 23:48:31

Re: To reconstruct a Polynomial with only the knowledge of Y`s

#25 2014-05-27 00:09:11

Re: To reconstruct a Polynomial with only the knowledge of Y`s

Board footer