Efficient commutative one-way encryption or hashing

Question

Spent two days researching the subject, but so far I haven't come up with a satisfying answer as to whether there is a feasible solution to the following problem:

A has a secret $m$ whereby $0 \leq m \leq 320$ (so a pretty small set of options).

A then uses some sort of function $f$ to calculate $f(m)$ and sends the result to B.

B also has some sort of function $g$ and calculates $g(f(m))$ and sends it back to A.

B has a guess n what the secret may be and sends the guess g(n) to A

A can now its function $f$ to calculate $f(g(n))$:

If $f(g(n)) = g(f(m))$ then $m = n$

Things of note:

• B must not be able to guess what the function $f$ might be based on $f(m)$ (since the possible values are not that many, it is imperative that $f()$ cannot be guessed simply by brute-forcing)
• A must not be able to know what the guess $n$ is, unless $n = m$.
• A must not be able to guess what the function $g$ might be based on $g(f(m))$ (that means no simple XOR)
• There is literally no need to decipher. So does not matter whether we talk hashing, async or sync encryption.
• It should be fast, like in mobile-phone-browser fast.
• Should be save against an attacker with way more calculation power and time.
• Key-generation for functions $f$ and $g$ may take considerable time. No problem. That is one-time-setup.
• There is no third person C available to help as an impartial mediator.

Thankful for any input

PS: I looked at homomorphic encryption, but to me these things seem to be all-out focused on basic math like addition and/or multiplication, which would not be exactly what I am looking for (as far as my research went, they all boil down to RSA is probably the quickest one of them and if benchmarks published by others are true, then it would probably be too slow)

I also looked at ZK, but the point is: How would A or B calculate a proof over something they don't know? If A where to prove they know a point m that is in the given range, then that's nice for them, but to B this means nothing. B cannot generate a proof that they know A's secret, because, well, they do not know. Of course A (or B) can generate a proof that $m$ (or $n$) have been chosen and then one of them reveals and the other verifies that the reveal is what has been used to generate the proof. However, this would not work, because then, at a certain point, one needs to reveal and then the other one knows the secret regardless of whether $m = n$ or not.

Answer 1

Here is an idea. All quantities are integers, sometime assimilated to bytestrings of stated fixed size.

Let $p$ be a public safe prime in interval $[2^{2047},2^{2048}-2^{64})$, that is a prime $p$ in this range with $q=(p-1)/2$ also prime.

Let A (resp. B) secretly choose a random odd 2046-bit $e_A$ (resp. $e_B$), which will be used by function $f$ (resp. $g$). Notice that $x\mapsto x^{e_A}\bmod p$ is a bijection over the interval $[0,p)$, same for $x\mapsto x^{e_B}\bmod p$.

Define a public random-like injection $h$ from $[0,2^{64})$ to $[0,c/2)$, e.g. $h(x)=x+2^{64}\operatorname{SHAKE256}(x,1976)+2^{2045}$.

Define functions $f$ and $g$ from and to $[0,2^{2048})$, assimilated to 256-byte bytestrings, as follows: $$\begin{align}f(x)&=\begin{cases}(h(x)^{2e_A}\bmod p)+2^{64}&\text{if }x\in[0,2^{64})\\((x-2^{64})^{e_A}\bmod p)+2^{64}&\text{if }x\in[2^{64},2^{2048})\end{cases}\\\\g(x)&=\begin{cases}(h(x)^{2e_B}\bmod p)+2^{64}&\text{if }x\in[0,2^{64})\\((x-2^{64})^{e_B}\bmod p)+2^{64}&\text{if }x\in[2^{64},2^{2048})\end{cases}\end{align}$$

The desired property $\forall m,n\in[0,2^{64})$, $f(g(n))=g(f(m))\implies m=n$ holds.

Proof: given the range of $m$, the evaluation of $f(m)$ is in the first case of the definition of $f$, and the evaluation of $g$ in $g(f(m))$ is in the second case of the definition of $g$. Thus $g(f(m))=\left(\left(h(m)^{2e_A}\right)^{e_B}\bmod p\right)+2^{64}$. Similarly $f(g(n))=\left(\left(h(n)^{2e_B}\right)^{e_A}\bmod p\right)+2^{64}$. Thus $f(g(n))=g(f(m))$ implies $\left(\left(h(n)^2\right)^{e_A}\right)^{e_B}\bmod p\ =\ \left(\left(h(m)^2\right)^{e_A}\right)^{e_B}\bmod p$, thus $h(n)^2\bmod p=h(m)^2\bmod p$ (invoking that $x\mapsto x^{e_B}\bmod p$ and $x\mapsto x^{e_A}\bmod p$ are injective), thus $(h(m)-h(n))(h(m)+h(n))\bmod p=0$, thus $h(m)=h(n)$ (invoking $0\le h(x)<c/2$), thus $m=n$ (invoking that $h$ is injective).

It's easy to show that for all $x\in[0,2^{2048})$, $f(g(x))=g(f(x))$ (which does not imply the above property).

I don't see how $B$ could find $m$ from $f(m)$, or find $e_A$, or otherwise get information about $m$; some for $A$ finding $n$ or $e_B$, or otherwise getting information about $n$.

Note: using an even exponent for $h(m)$ is to avoid a leak of the Jacobi symbol of $h(m)$.

Answer 2

I guess what you are trying to looking for is Private Set Intersection (PSI)? Based on your description, you are probably looking for elliptic-curve Diffie-Hellman (ECDH) based PSI