Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:

$m = (n(n+1)/2)\ \bmod 2^{64}$

It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\rfloor$ . For all other numbers the inversion is not that trivial but I have the feeling it could be done without brute force.

  • $\begingroup$ Welcome to Cryptography. Is this homework? $\endgroup$ – kelalaka Feb 12 at 17:49
  • $\begingroup$ @kelalaka No, cryptography is a hobby, hashing part of my research, but I'm missing essential mathematical education, I was hoping someone could point me in the right direction. I legitimately do not know if it is efficiently inverted, if not it could be a novel one-way function. $\endgroup$ – Wolfgang Brehm Feb 12 at 18:07
  • $\begingroup$ It can be efficiently inverted - does that answer your question? $\endgroup$ – poncho Feb 12 at 18:09
  • $\begingroup$ @poncho How do you know it can be efficiently inverted? $\endgroup$ – Wolfgang Brehm Feb 12 at 18:11
  • 1
    $\begingroup$ Because I figured out how to invert it. It's not that hard, you can figure it out as well (it's a technique that comes in useful time to time). Hint: the lower $i$ bits of $m$ depend solely on the lower $i+1$ bits of $n$ ; any other bits of $n$ have no effect... $\endgroup$ – poncho Feb 12 at 19:41

As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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