# Most general order-preserving function

1. Mar 28, 2015

### Dragonfall

Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions

2. Mar 28, 2015

### Staff: Mentor

What do you mean by "order-preserving?" Is it the idea that if a < b, then f(a) < f(b)? If so any function that is strictly increasing satisfies the latter inequality. If you mean something different, you need to clarify your question.

3. Mar 28, 2015

### Dragonfall

What I need is a class of functions that is strictly increasing, very efficient to compute, and when one is selected uniformly and applied to x < y, the pair (f(x), f(y)) is uniformly distributed.

4. Mar 28, 2015

### Staff: Mentor

For every x,y? Then your class of functions has to be uncountable. What do you mean with "selected uniformly"? There is no clear definition of this on an arbitrary uncountable set.
Also, uniform distributions over the full real line do not exist.

f(x)=mx+c with suitable distributions of m and c can give a uniform distribution of (f(x),f(y)) in some finite range, or give nice non-uniform distributions as well.

5. Mar 28, 2015

### Dragonfall

OK the domain is integers [1, ..., n], forget about what the range is for now, we can decide that after. I have a pair of numbers (a, b). I want to apply a function at random from this class so that (f(a), f(b)) is uniformly random and f(a) < f(b).

f has to be efficiently computable. It also has to be "decomposable" into two parts f_1, f_2 such that f(x) = f_2 ( f_1 (x) ). Knowing ONLY ONE of f_1 or f_2, and given f(x), it should be infeasible to compute x.

I'm thinking Ax + B for A > 0 and random B. Knowing Ax+B, and only one of A or B doesn't tell you anything about x.

6. Mar 28, 2015

### Staff: Mentor

Uniformly random where?

Every f is "decomposable" that way, simply set f_1(x)=f(x), f_2(x)=x (or vice versa).
Knowing only one of an arbitrary and unknown "decomposition" makes the task impossible - see my example, one of the functions could be just the identify function.

I think it would really help if you give more context. What do you actually want to do?

7. Mar 28, 2015

### Dragonfall

No. If f_1 = f then knowing f_1 and knowing f(x) gives you x, assuming it's not one-way and is one to one.

You know that zero-knowledge proof of graph isomorphism? You have two permutations. Composition gives you the permutation. Knowing just one gives you nothing. I'm trying to come up with something similar for two ordered committed numbers.

8. Mar 29, 2015

### Staff: Mentor

So who is supposed to know what? What is the protocol you want to use, and what is the result?

9. Mar 29, 2015

### Dragonfall

You're not supposed to know that. I'm supposed to come up with it. And I have! Thanks for the inputs.

10. Mar 30, 2015