0
$\begingroup$

Are there any commutative one-way functions for floating points?

I tried to explain why I need these functions.
First, I describe the problem on a high level and then I further formalize it;

There are three parties. Alice, Bob, and Charlie. Charlie wants to check if Alice and Bob have the same value without knowing the exact value except if it is the same. This problem is called the socialist millionaire problem. However, there are four extra additional constraints/requirements in this situation:

  1. There are three parties instead of two. Alice and Bob don't want the other parties to know their values.
  2. The values to be compared are not integers, they are floating numbers.
  3. We would like to know if the values are roughly the same.
  4. There is no back and forth communication possible between Alice and Bob and Charlie. Only two one-way messages. One from Alice to Charlie and one from Bob to Charlie.

More formally,

$x_a$ and $x_b$ are the values of Alice and Bob respectively.
They are represented by floating numbers, $x_a, x_b\in\mathbb{R}$.

Charlie wants to check if the values are roughly the same: $x_a \approx x_b$.
This can be written as $|x_a - x_b| < \epsilon$, with $\epsilon$, a small positive floating number.

If we would have commutative one-way functions for floating numbers, it could help here to keep the exact values secret.

Alice and Bob would transform their values with the one-way function:
$y_a = f(x_a, k_a)$, with $k_a$, a public key produced by Alice
$y_b = f(x_b, k_b)$, with $k_b$, a public key produced by Bob
Then Alice would share ($y_a$, $k_a$) and Bob would share ($y_b$, $k_b$) by sending a single message to Charlie .

Charlie can then check if $|x_a - x_b| < \epsilon$ by checking
$|f(y_a, k_b) - f(y_b, k_a)|<\delta$, which is equivalent to
$|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$

Is my assumption correct that I need commutative one-way functions for floating points?

Does anyone know of any commutative one-way functions for floating points?

$\endgroup$
0
$\begingroup$

This would appear to be impossible.

You require that $|x_1 - x_2| < \epsilon$ implies that $|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$ ; this implies that $f(f(x_a, k_a), k_b)$ is continuous over $x_a$.

Now Charlie knows $k_a, k_b$ and can compute the target value $f(f(x_a, k_a), k_b)$; a simple bisection search over the function $f(f(x, k_a), k_b)$ would allow him to recover $x_a$ (or at least, a good approximation).

$\endgroup$
  • $\begingroup$ What if we would have different functions for Alice and for Bob? $f_a$ and $f_b$ respectively. This would tranlate to: $|f_b(f_a(x_a, k_a), k_b) - f_a(f_b(x_b, k_b), k_a)|<\delta$ $\endgroup$ – eavsteen Oct 10 at 15:48
  • $\begingroup$ @eavsteen: still unchanged; it still must be the case that $f_b(f_a(x_a, k_a), k_b) \approx. f_b(f_a(x_a + \epsilon, k_a), k_b)$, hence we have a continuous function... $\endgroup$ – poncho Oct 10 at 15:51
  • $\begingroup$ What if we use elliptic curves? $x_a$ is mapped onto a point on the elliptic curve and we use that point as the base point (generator). Instead of sharing the base point we keep it secret. In this case $k_a$ is an integer and is the number of multiplications of the base point. It is just much harder to go back to the original point and thus to do any kind of bisection search. $\endgroup$ – eavsteen Oct 10 at 16:12
  • $\begingroup$ @eavsteen: is the mapping between $x_a$ and the elliptic curve point continuous? If so, same issue. If not, then you lose the approximation that Charlie needs to reply on to determine if $x_a \approx. x_b$ $\endgroup$ – poncho Oct 10 at 17:12
  • $\begingroup$ if a function f is continuous does it then automatically mean that it is easy to return to x? Since it should be a one-way function, the bisection search would be very hard since you can't get the initial x or even a close to x. if f would be monotonous, I would agree that the bisection search would allow an easy return, but in other cases that is not necessarily the case. $\endgroup$ – eavsteen Oct 11 at 9:08

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.