Polynomial Reconstruction in Finite Field

arina · 2010-02-18 22:37:37

Hello all,

I was wondering if anyone could help me with the math part of my university project. Say I have a polynomial equation like so:

Now if I were to find three points on this polynomial, they would be:

and.

The problem is that I need the points to be in a positive finite field with an x and y range of 0 up to 251. So I make the points part of this finite field GF(251) and they become:

and

The problem arises when I have to get back the original polynomial by performing Gaussian Elimination using these finite field points. One way could be to save the values 0, 7 and 26 to be multiplied by 251 and added to the new y-coordinate values so that I get back the original y-coordinates. That way I can reconstruct the polynomial. But storing these values is unpractical and a security threat, so I can't do that.

My question: How can I re-create the above polynomial using the finite field coordinate locations?

Trivia:
I'm working on an electronic security system that contains cryptography as well as error-correction. I'm currently designing the system in C (which, by the way can only store integer values up to 0xFFFFFFFF) but later on the compute intensive parts must be designed as hardware blocks in Verilog. My actual polynomial is 8th degree with coefficient values that can range from 0 to 0xFFFF. My x-y finite universe is from 0 to 65025. Currently I can't even store the original values in C variables since if

. Storing any kind of extra values (like: 0, 7 and 26) can cause security risk since an attacker could more easily compromise the system. And I've seen journal papers about such security systems that use finite fields and can still reconstruct the polynomial. Searching maths journal papers, I found the explanations full of jargon and I couldn't understand. Any ideas or suggestions (or even better: the solution) would be much appreciated.

Thank you.

Last edited by arina (2010-02-18 22:51:57)

Ricky · 2010-02-20 04:30:27

My question: How can I re-create the above polynomial using the finite field coordinate locations?

You can't.

First off, four points determine a cubic polynomial in the real numbers. So consider the polynomial which passes through

(0, 4 + 10*251), (1, 163 + 251), (2, 1888 + 5*251), and (3, 6685 * 251)

And remember that 4 points uniquely determine a cubic. This cubic must be different than the one you wrote, and so these points are not enough to determine your polynomial.

bobbym · 2010-02-20 05:27:32

Hi arina;

Besides from Rick's objection which is correct. You need 4 points to uniquely determine a cubic, but that you can provide.

I have worked on your problem and have reduced it down to some equations that cannot be uniquely determined as they have n equations with n+1 unknowns for no matter how many points you provide. Can you direct me to the papers you are mentioning. I know of no way to recover your points from the mod 251 operation you are subjecting them to. If you could use 4 diiferent Galois Fields we could maybe reconstruct the original 4 points by the chinese remainder theorem.

GF(251),GF(241), GF(239), GF(233) are a possibility.

arina · 2010-02-21 16:44:01

Hi Ricky,

Thanx for pointing that out. I'd forgotten to add another point since it was a 3rd degree polynomial. Sure, we can use the points you listed and try to reconstruct the polynomial that they define.
(0, 4 + 10*251), (1, 163 + 251), (2, 1888 + 5*251), and (3, 6685 * 251) == (0,2514), (1,414), (2,3143) and (3,1677935) Right?
Using Gaussian Elimination, the polynomial that passes thru them is:

However, I found this polynomial gives slightly different values for x = 2 and x=3 which are 3142 and 1677930 respectively. I wonder why that's happening.

One requirement that my program must fulfill is that the x-y coordinates as well as the polynomial coefficients must be Whole numbers. No floating points possible.

Hi Bobby,

CRT? Hmmm, I've heard other cryptography researchers mention it. Does that mean we'll need to have four coordinate values for each point to successfully rebuild the polynomial? I'm gonna go study up on how this CRT works.

Regarding my references, the engineering papers that I read regarding the security system I'm trying to build mentioned the finite field almost like an after-thought. I've created the rest of the security system and it works fine for small numbers like this cubic equation (since my real finite field is 0 to 65001). I have to write a program where the polynomial coefficients and x-coordinates are provided by the user during the encoding/hiding part. It must be between an 8th degree to 14th degree polynomial. The finite field isn't fixed either, it just has to be from 0 to around 65000 or so. It can be prime field or binary field since I've seen papers that use both.

So, there's no fixed polynomial equation and I must be able to solve any and all polynomial equations of 8th degree. During the decoding part, the user provides the right x-coordinates, the database provides the matching y-coordinates and my program must reconstruct the original polynomial. The program has to give back the exact polynomial coefficients to successfully complete the decoding process.

I'm listing the maths literature that I've been reading in trying to find the answer.

Polynomial Codes Over Certain Finite Fields at kom.aau.dk/~heb/kurser/NOTER/KOFA01.PDF
Construction of Galois Fields of Characteristic Two and Irreducible Polynomials at http://www.jstor.org/stable/2003204
Calculations in Galois Fields at http://www.drdobbs.com/cpp/184401858
Hardness of Reconstructing Multivariate Polynomials over Finite Fields at http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04389506
Solving Large Sparse Linear Systems Over Finite Fields at http://www.farcaster.com/papers/crypto-solve/solve.html

If you can't access some of the sites, please let me know where I can email them to you.

Bobby and Ricky, thanx again for taking the time in trying to help me. Looking forward to some advice/solution.

bobbym · 2010-02-21 22:24:31

Hi arina;

That is not the polynomial fit for these points:(0,2514), (1,414), (2,3143) and (3,1677935). You have computed the cubic incorrectly. That is why there is a discrepancy.

arina · 2010-02-22 14:32:35

Ok. So what is the best polynomial fit for these points? I thought maybe the polynomial was slightly off because my program can't allow the coefficients to have decimal points.

And why are these points better than using the points I gave for the original polynomial? (0,4), (1,163), (2,1888) and (3,6685)
Is the polynomial one of those that cannot be uniquely determined?

Thanx.

bobbym · 2010-02-23 03:35:59

Hi arina;

This is the correct cubic that passes through the points (0,2514), (1,414), (2,3143) and (3,1677935)

arina wrote:

Is the polynomial one of those that cannot be uniquely determined?

I know you hate jargon and so do I. So i will just state the theorem as it applies to real world problems. You can always fit a cubic through 4 different points that will be exact and it is unique. There is only one!

arina · 2010-02-23 14:35:54

Alright, thanx Bobby. So, this confirms that the slight inaccuracy was caused by lack of decimal points in my coefficients. Unfortunately, my program can't handle fractions either. But that's ok, I'll work on a way to overcome this limitation.

Meanwhile, back to my original question. I have a polynomial:

I find four points lying on the polynomial: (0,2514), (1,414), (2,3142) and (3,1677930)

If I were to reduce the points to a finite field, say GF(251) or GF(241), etc. and store the points in a database, how could I recover the original polynomial by performing Gaussian Elimination on the finite field points?

(0,2514), (1,414), (2,3142) and (3,1677930) == (0, 4 + 10*251), (1, 163 + 1*251), (2, 130 + 12*251), and (3, 246 + 6684*251)

Finite field points in database: (0,4), (1,163), (2,130) and (3,246).

Is there a way that I can get rid of the numbers: 10, 1, 12 and 6684 yet still be able to recover the original polynomial? Frankly, saving these values would cause a security threat to the scheme and make it vulnerable to brute force attacks.

bobbym · 2010-02-23 16:15:18

Hi arina;

When you take a number x and perform a modulo operation and you give me the answer there is no way to undo that operation to get the original number. Here is why: You choose a positive number and mod it by 5 now you tell me the answer is 4.

That means your original number could have been 4,9,14,19,24,29...
An infinite number of values. As far as the modulo 5 operator is concerned 4,9,14,19,24,29... are all the same, they all leave a remainder of 4 when divided by 5. Therefore I cannot recover the original. Now If you take some number and tell me that mod 5, it is 3 and mod 2 it is 1. Now I can recover it using the chinese remainder theorem. Your smallest original number was 3 the next one is 13 and then 23...

In other words you must provide more than one modulo answer for each point you wish to recover. Then you can use the recovered points to rebuild the cubic. Since this is a security job you cannot lay out the particulars of your task to me. So you must solve 2 problems

1) Each point must be acted upon by different mods. I have given you 4 Galois Fields in an earlier post, they provide 4 prime moduli from which we can possibly retrieve the original points.

2) You must choose your moduli in such a way that the answer is the smallest one possible. This is actually quite easy.

If you cannot solve problem 1 in a satisfactory way then we can work on another idea. But it would require me knowing just a little more about the latitude you have in picking the points and the type of polynomials involved.

arina · 2010-02-24 15:17:58

Hi bobby,

Wow, that's a very clear explanation. Looks like this could work. I'm starting to see the light at the end of the tunnel.

So how do I decide how many GFs I need to be able to solve the problem? In general, are four GFs enough to determine the original number with high accuracy? Even if the number is

?

And I can't use the same four GFs for all the points of my polynomial? Is that because of the extreme difference in size between the smallest y-value(414) and the largest(1677930)?

My aim is to reduce the coordinate value to a 16 bit number or numbers, meaning the finite field values have to fall between 1 and 65535. In this case I can't choose the moduli such that the answer is smallest, at least for the larger numbers. So, say I'm reducing 1677930 to finite field. I choose four GFs: GF(65521), GF(65519), GF(65497) and GF(65479).

So, if I save these numbers, I can get back the original 1677930 using Chinese Remainder Theorem? How's that work?

Thanx.

bobbym · 2010-02-24 17:03:18

Hi;

arina wrote:

Wow, that's a very clear explanation. Looks like this could work. I'm starting to see the light at the end of the tunnel.

That's precisely when things blow up in your face. I have had experience with problems of this nature. They fight back right up till the end.

arina wrote:

So, if I save these numbers, I can get back the original 1677930 using Chinese Remainder Theorem?

Yes I just did it. Here are some links that show a little about the CRT and a C++ implementation.

http://www.cut-the-knot.org/blue/chinese.shtml

http://channel9.msdn.com/forums/TechOff … orem-in-C/

A question: Do you have a choice as to what point you are going to pick. Your pick of 1677930 was not well suited to the idea.

arina · 2010-03-11 19:29:49

Hi again Bobby,

I've spent the week investigating how Chinese Remainder Theorem is used in RSA cryptography. Turns out, you were right. These problems really do fight back till the end.

From what I've seen, CRT usually reduces variable size by half (roughly speaking). So if the original value is up to 1024, CRT can be used to reduce the calculation size to 512 but the calculations have to be performed at least twice. So, a 200 bit binary number can be reduced to 16 bit binary remainders but the moduli will be around 100 bit binary numbers.

So now I'm looking at Zech's Logarithms in trying to solve the issue. Would you happen to know any resources that give simplified explanation and example on how to implement this Zech Log (aka Jacobi Logarithm)?

Thanx.

bobbym · 2010-03-11 22:06:40

Hi arina;

Unfortunately, if I ever knew anything about Zech logarithms I have forgotten it. I don't even remember a whole lot about discrete logarithms or how to calculate them. Went through the available literature but due to rust, I had great difficulty following any of it. Sorry to wimp out here.

I did not know that you were working with 200 bit ( approximately 65 decimal digits? ). I still don't see the problem though. There is a lot of software that can do multiprecision arithmetic. I would definitely try to keep it simple and avoid the use of any more complicated math. My feeling is that the math we have discussed is ample for the task. I would try to make that work, especially since I was able to recover the numbers from the mod operation. Here, size does not matter.

TanSY · 2011-05-15 20:54:49

Not sure if you still need the answer.

If I understand correctly, you were trying to reconstruct a polynomial of degree 3 using four points. And this 3-degree polynomial lied in a finite field.

A simple way to reconstruct any (d-1)-degree p(x) mod q, where q is a prime number, is by using Lagrange coefficient with d points (x,y) as the input. Lagrange coefficient is a special case of Vandermonde matrix but I guess the former is all you need. Wiki provides a good example for Lagrange coefficient in polynomial interpolation

bobbym · 2011-05-15 23:31:01

Hi;

The problem is not quite that easy. With 4 points it is possible to use Lagrange or many other means to interpolate. Trouble is he has subjected them to the modulo operator. Uniquely getting points back from modding them is not possible. For instance:

x can be 2, 12, 22, 32, 42...

That is why I was working with the CRT, bur he never came back.

Math Is Fun Forum

#1 2010-02-18 22:37:37

Polynomial Reconstruction in Finite Field

#2 2010-02-20 04:30:27

Re: Polynomial Reconstruction in Finite Field

#3 2010-02-20 05:27:32

Re: Polynomial Reconstruction in Finite Field

#4 2010-02-21 16:44:01

Re: Polynomial Reconstruction in Finite Field

#5 2010-02-21 22:24:31

Re: Polynomial Reconstruction in Finite Field

#6 2010-02-22 14:32:35

Re: Polynomial Reconstruction in Finite Field

#7 2010-02-23 03:35:59

Re: Polynomial Reconstruction in Finite Field

#8 2010-02-23 14:35:54

Re: Polynomial Reconstruction in Finite Field

#9 2010-02-23 16:15:18

Re: Polynomial Reconstruction in Finite Field

#10 2010-02-24 15:17:58

Re: Polynomial Reconstruction in Finite Field

#11 2010-02-24 17:03:18

Re: Polynomial Reconstruction in Finite Field

#12 2010-03-11 19:29:49

Re: Polynomial Reconstruction in Finite Field

#13 2010-03-11 22:06:40

Re: Polynomial Reconstruction in Finite Field

#14 2011-05-15 20:54:49

Re: Polynomial Reconstruction in Finite Field

#15 2011-05-15 23:31:01

Re: Polynomial Reconstruction in Finite Field

Board footer