# Are there any bijective one-way functions not based on number-theoretic hardness assumptions?

I'm trying to find a bijective function $y=F(x)$ which should be easy to compute in one direction but hard to compute in the other, where the one-way property is not based on a number theoretic assumption.

The hard direction should be preferably as hard as computing hash preimages, but it could also be that there is only some practical asymmetry (such as taking 1000 times as long to compute one direction than the other).

Poligh-Helmman encryption, LUC encryption and RSA encryption can provide some form of one-wayness since decryption/encryption take very different times, but they are all number theoretic based and require changing the plaintext and ciphertext space to avoid weak plaintexts.

-
What would you use such a function for? $\;$ – Ricky Demer Nov 7 '13 at 6:01
The term you are looking for is "one-way permutation". There are many candidate constructions. Why would you insist that you are not willing to rely upon number-theoretic hardness assertions? That seems unnecessarily limiting and not well motivated. – D.W. Nov 7 '13 at 7:18
@D.W. Some people place a much higher trust in unstructured problems than in highly structured number theoretic problems. – CodesInChaos Nov 7 '13 at 9:47
The function is for a special kind of Proof-of-work. Currently I'm using a hash function using the subset of invertible values of the domain. But this is far from perfect. – SDL Nov 11 '13 at 17:44

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions.

There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece cryptosystem).

An MQ scheme typically consists of a low-degree invertible polynomial transformation $S$ (public or secret) and two secret affine transformations $A_1,A_2$. The public key is exposed a polynomial(s) $A_2(S(A_1(x)))$. There are many insecure candidates for the nonlinear layer (see survey in this paper), but it is generally assumed that the HFE cryptosystem with sufficiently large parameters is secure.

The code-based cryptosystems hide the generator of some linear code in a similar manner by multiplying it by properly chosen matrices and expose the public key as a matrix.

Both families produce terribly large public keys up to several megabytes, and are of limited use because of that and the lack of systems that withstood a lot of cryptanalysis (except for the original McEliece proposal).

UPDATE: You may also want to look at some bijective polynomials suggested in the recent algebraic papers. I do not know if there exist efficient inversion algorithms.

For example: $\left(X^{2^k}+X+a\right)^{-l}+X$ over $\mathbb{F}_{2^n}$, where $n/\text{GCD}(n,k)$ is odd, $l(2^k+1)\equiv 2^{n/2-1}\pmod{2^n-1}$, Tr$(\delta)=1$ in this 2010 paper

For odd $p$: $\left(X^{p^k}-X+a\right)^{\frac{p^n+1}{2}}+X^{p^k}+X$ over $\mathbb{F}_{p^n}$ in this 2012 paper.

-
But these schemes have seen renewed interest in the last decade because of their presumed resistance to quantum attacks. Shor's algorithm can't touch McEliece; that would be like trying to use a hammer to pick a lock. – pg1989 Nov 7 '13 at 10:14
I don't see a requirement in the OP that it should be easy to invert when knowing a secret parameter. – CodesInChaos Nov 7 '13 at 12:39
I will then make an update about bijective polynomials. – Dmitry Khovratovich Nov 7 '13 at 15:07
the trapdoor functions of McEliece and MPKC are not bijective ... – juaninf Feb 20 '14 at 13:15

I found that the best way to implement F is by using a T-function.

-
At a glance they seem trivial to invert. Just start with $x_0$ and compute the input bit. Then proceed to the next bit, where you can evaluate $f$ since you already computed all input bits with lower index. Use as S-Box and being non-linear in no way implies being hard to invert. – CodesInChaos Nov 14 '13 at 13:33
Yes. My answer was missing some info. I said "using" a T-function, but I didn't said how. Let T1.. Tn be T-functions. Let S1..Sn be fixed bit-shuffles. Then F=(T1 o S1 o T2 o S2 .... Tn o Sn) should be hard to invert. What do you think? – SDL Nov 14 '13 at 19:45
I don't understand the details of your suggestion, but it seems very unlikely that you can obtain a function that's both hard to invert and bijective like that. – CodesInChaos Nov 14 '13 at 21:30
The inverse of a T-function is a T-function that can be easily found from the original T-function, $\hspace{.58 in}$ and the inverse of a bit-shuffle is a bit-shuffle that can be easily found from the original bit-shuffle. $\hspace{.41 in}$ – Ricky Demer Nov 14 '13 at 22:07
@SDL "hard to compute" has a specific meaning in cryptography (and as you probably guessed, it happens to mean "infeasible"). Maybe you should detail exactly what your requirements are in your question in unambiguous terms. – Thomas Nov 16 '13 at 1:24