2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I would suggest to add some formal definitions in this question and structure the layout of the question, right now it is unnecessarily difficult to imagine what you actually mean. For formulas, please use MathJax (see the help options, basically latex code in between dollar signs) $\endgroup$ – tylo Aug 22 '16 at 15:56
  • $\begingroup$ In general, polynomial functions are not order-preserving. e.g; $f(x)=x^2-6x+9$ does not preserve the order of the triple $(1,2,6)$ which becomes $(4,1,9)$; are you restricting to non-negative coefficients for non-constant terms, and (odd powers or restriction to the domain of non-negative integers)? Assuming that, hint: how many examples does it take to find a polynomial from sample input/output pairs? $\endgroup$ – fgrieu Aug 22 '16 at 16:17
  • $\begingroup$ Are you doing your polynomial over the integers (or the reals), making sure that the polynomial is monotonic (at least, over the range of inputs you expect)? I ask because, in the crypto world, if someone talks about polynomials, they're almost always talking about evaluating it over some finite ring or field... $\endgroup$ – poncho Aug 22 '16 at 16:18
  • $\begingroup$ @fgrieu - your right, I construct a polynomial that always assures order. The attacker doesn't have access to the input, only output. But lets assume I have transformed all integers from 0 to 1000. So the attacker would see 1000 ordered outputs. $\endgroup$ – rsp Aug 22 '16 at 16:33
  • $\begingroup$ @poncho - I'm working only with integers. Sorry for my lack of structure on my question. $\endgroup$ – rsp Aug 22 '16 at 16:36
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thank you for your detailed answer. May I argue that polynomial interpolation couldn't be used because it requires the attacker to know the (input, output) pairs, as you mentioned. He only knows the outputs. Another thing you mentioned is the idea of querying the function for arbitrarily large input in order to make the term with the largest degree show itself. That is a great idea. One thing though, the attacker also doesn't have access to the function. So, I'm thinking that if I bound my inputs below a specific threshold, the largest degree doesn't show. $\endgroup$ – rsp Aug 22 '16 at 20:37
  • $\begingroup$ Thank you for your quick response. Now I understand why you were focused on the input-output idea. I didn't explain myself right, I'm sorry. I just wanted to state that only the output was visible to the attacker. $\endgroup$ – rsp Aug 22 '16 at 21:17
  • 1
    $\begingroup$ Only knowing the outputs is not a reasonable assumption. From today's point of view, known plaintext attacks (known pairs) are basically the lowest level of attacks a secure encryption scheme needs to withstand. $\endgroup$ – tylo Aug 23 '16 at 12:04
  • $\begingroup$ @tylo - I didn't know that. Thank you. Could you please point me where I can read about the different levels of attack an encryption scheme needs to withstand? $\endgroup$ – rsp Aug 23 '16 at 12:34
  • 1
    $\begingroup$ Attack model, and while we're at it: Kerckhoffs' principle. But I would suggest reading the entire context: Cryptanalysis. I hope that's giving a good overview. $\endgroup$ – tylo Aug 23 '16 at 12:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.