4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What would you use such a function for? $\;$ $\endgroup$
    – user991
    Commented Nov 7, 2013 at 6:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 7, 2013 at 7:18
  • $\begingroup$ @D.W. Some people place a much higher trust in unstructured problems than in highly structured number theoretic problems. $\endgroup$
    – CodesInChaos
    Commented Nov 7, 2013 at 9:47
  • $\begingroup$ 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. $\endgroup$
    – SDL
    Commented Nov 11, 2013 at 17:44

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – pg1989
    Commented Nov 7, 2013 at 10:14
  • 2
    $\begingroup$ I don't see a requirement in the OP that it should be easy to invert when knowing a secret parameter. $\endgroup$
    – CodesInChaos
    Commented Nov 7, 2013 at 12:39
  • $\begingroup$ I will then make an update about bijective polynomials. $\endgroup$
    – Dmitry Khovratovich
    Commented Nov 7, 2013 at 15:07
  • 1
    $\begingroup$ the trapdoor functions of McEliece and MPKC are not bijective ... $\endgroup$
    – juaninf
    Commented Feb 20, 2014 at 13:15
-2
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Nov 14, 2013 at 13:33
  • $\begingroup$ 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? $\endgroup$
    – SDL
    Commented Nov 14, 2013 at 19:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Nov 14, 2013 at 21:30
  • 2
    $\begingroup$ 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}$ $\endgroup$
    – user991
    Commented Nov 14, 2013 at 22:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Thomas
    Commented Nov 16, 2013 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.