I am sitting on a contradictory requirement in which I would need a function that is a one-way hash, but that is also monotone.

One-way: if $y=h(x)$, then computing $x=h^{-1}(y)$ is intractable, or at least, difficult. A textbook example could be SHA-2.

monotone: if $x_1 < x_2$, then $h(x_1) < h(x_2)$. In other words, the hashing would also preserve the order.

With these requirements a bit contradictory, does such function exist already? Would it still be possible to design one, or if not, would it conceivably be possible to construct an impossibility proof that such function cannot possibly exist?


If the order is preserved, then if we are given $h(x)$, we can find $x$ easily by doing binary search.

Therefore, such function cannot exist.

  • $\begingroup$ Where is the button for that? I cannot find one that says "accept". There is just: share, cite, edit. $\endgroup$ – erik Aug 4 '16 at 9:09
  • $\begingroup$ @erik It is the little check mark below the upvote count. $\endgroup$ – Kenny Lau Aug 4 '16 at 9:16
  • $\begingroup$ There isn't one! Maybe that is a setting that the site admin has to switch on per user or so? $\endgroup$ – erik Aug 5 '16 at 11:37
  • $\begingroup$ @erik See this. $\endgroup$ – Kenny Lau Aug 5 '16 at 11:38

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.