Are large polynomials secure for order preserving "hashing"? (newbie question) I've been searching for some time now for an answer to this simple question: if I have a large polynomial that is secret, and I use it to transform a set of integers so as to obtain a new set that preserves the order for each transformation, can the polynomial be deduced by an attacker only from the output?

Notes to take into consideration:


The polynomial is carefully chosen to assure the outputs maintain order
I'm working only with positive integers
An attacker would only be able to see the generated outputs, never the inputs nor the polynomial (of course)
The attacker could have access to large sets of generated outputs


One example of a valid polynomial could be: $$f(x) = 31x^{15}-27x^{14}+13x^{12}-10x^{9}+5x^{7} $$

Can the attacker deduce the polynomial from the output only, even if I make the polynomial much harder? Are polynomials even a possible solution for order-preserving "hashing"?

I assumed an attacker would be able to find out the secret polynomial through some fancy math tricks and algorithms, so I added the following three difficulties:


I'm "pre-transforming" the input before inserting it into the polynomial by adding a large integer $\beta$ to it, so as to skew the input away from small positive integers - this $\beta$ value is unique per polynomial
I'm "post-transforming" the generated outputs by dividing them with a common divisor as large as possible but that still maintains order - I'm doing this to take some information out of the generated outputs (the remainder) of the divisions. The common divisor is calculated the following way: $$commonDivisor = 10^{numDigits(f(1)-f(0))-1}$$
where $numDigits(x)$ outputs the number of digits in the provided number.
I'm also adding a random deviation value $\alpha$ to every output, that is small enough to not make it larger than the next output: $$out_{n-1}+\alpha_{n-1} &lt; out_{n} + \alpha_{n}$$


All these operations together would produce something like the following:

$$f(x+\beta) = \frac{pol(x)+\alpha_x}{10^{numDigits(f(1)-f(0))-1}}$$

Continuing the previous question, would these changes make any real difference to the challenge of finding the polynomial, or are there ways to crack this?

A  not too technical answer would be very much appreciated due to my lack of experience in this field.
The basic method is easily cracked: it is well known how to find a polynomial of degree at most $k$ from $k+1$ (input, output) pairs; that's the polynomial interpolation problem. There are numerous ways to efficiently carry it for high degree and large integers (one such method is to carry it modulo some medium primes, and use the Chinese Remainder Theorem in the end).

"pre-transforming" alone does not help at all against the above.

"post-transforming" and "adding a random deviation" makes recovering the polynomial more difficult. However, some simple attacks remain feasible, depending on adversarial model. In particular, if the adversary can query the function for arbitrarily large input: the degree of the polynomial and the highest degree coefficient of the polynomial divided by commonDivisor are easily found; then the attack can be repeated by subtracting known high coefficients, until finding all coefficients; in this setup, commonDivisor does not help much.

I do not see how to make the idea secure in a cryptographic sense.

Also: It does not seem that the "post-transforming" method proposed is guaranteed to maintain the property that distinct input leads to distinct output.

Addition following comment: if input is not known, that makes attack harder; however


you proposed: lets assume I have transformed all integers from 0 to 1000, and in cryptographic terms that's to be assimilated to a lot of known plaintext;
known plaintext has been a standard assumption for about as long as cryptography matured to a science, for reasons similar to the above;
as the saying goes: attacks only get better; they never get worse.