Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

Is this cryptography?

I think the polynomial can be found..


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

How, why?

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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

but wait for bobbym


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Many thanks

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

Hi;

How about a small example please.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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...

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

(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?

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

Uniformly random? What ranges?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

That is not helping. What field?

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

Yes the second one excluding 0

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Thank you again for your help.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

Yes , P is a prime number.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Aydin
Member
Registered: 2014-05-26
Posts: 31

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

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

Offline

Board footer

Powered by FluxBB