1
$\begingroup$

Let $a_1$ through $a_k$ be some permutation of the first $k$ primes. Let $n \in [1,k!]$ be a parameter specifying the exact ordering by taking the $n$th permutation in a sorted list or by some other simple mechanism.

Then define $f(n,k)=a_1^{p_1}+a_2^{p_2}+\ldots+a_k^{p_k}$, where $p_i$ is the $i$th prime, and the $a_i$ are the permutation of the primes indicated by $n$.

e.g. $f(5,4)=2^2+7^3+3^5+5^7=78715$.

I conjectured that all such sums may be distinct. Supposing that were true, this appears like it could potentially serve as a bijective one-way function using a suitably high value of $k$ and an effectively randomized permutation.

For very small $k$ (up to $20$ or so), the $f(n,k)$ sums are spread far apart and have little opportunity for individual terms to overlap, making it easy to greedily home in on the correct inputs. Beyond that, it quickly becomes more difficult. Barring some tidy solution that I cannot see, finding $f^{-1}(f(n,k))$ seems totally intractable once it's extended to $k>1000$ or more, while $f(n,k)$ is trivial to calculate to very large values. Accordingly, my question:

Could $f(n,k)$ conceivably make a suitable one-way function?

In particular, I'm looking for advice on whether there is likely to be some way to efficiently find $f^{-1}(f(n,k))$ after all, and also whether $f$ looks like it has other properties that would make it either a strong or poor choice for this purpose.

$\endgroup$
  • 2
    $\begingroup$ Welcome back with your question Permutation of first k prime powers as a one-way function?. $\endgroup$ – kelalaka Feb 24 at 17:34
  • $\begingroup$ @kelalaka I was sure I've seen this post before $\endgroup$ – Baby desta Feb 24 at 19:14
  • $\begingroup$ @Babydesta It is hidden from you but here crypto.stackexchange.com/questions/77647/… $\endgroup$ – kelalaka Feb 24 at 19:21
  • 1
    $\begingroup$ Could f(n,k) conceivably make a suitable one-way function? I'm not sure if this helps but if you are looking to invent a hash function, the length of the output should be of fixed size. But your function gets larger for larger inputs. $\endgroup$ – Baby desta Feb 24 at 19:31
  • $\begingroup$ The function described is (conjecturally) injective in it's destination domain $\Bbb N$, not bijective as stated in the question. Not all points in $\Bbb N$ are reached ! To get a bijection we need to to restrict the destination domain. $\endgroup$ – fgrieu Feb 24 at 21:51
1
$\begingroup$

As this stands this is a hard to evaluate and inefficient proposal.

Firstly key size is effectively $\log n\!=O(n (\log n-1))$ but the largest value (attained for the identity permutation) is $\sum_{i\leq k} p_i^{p_i}$ which is larger than

$$(n \log n)^{n \log n}=O(e^{n (\log n)^2}).$$

You would need to look at reduction modulo so elarge integer to make it efficient.

While it may be that the type of diophantine equation that needs to be solvable (for prime arguments) for the original function to have collisions is unsolvable, such things are almost impossible to prove. I am not an expert but I know of no such results even for few terms.

And once you do a modular reduction, all bets are off.

Computationally, you probably cannot check much beyond the first 20 or so primes for no collisions.

One idea is to check the differences of the values the set of functions for a fixed $k$ give, since there are quadratically many differences, they’d be more likely to repeat. If this happens this means that you might be able to find a modular reduction that will yield a collision.

|improve this answer|||||
$\endgroup$

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.