16
$\begingroup$

Apologies in advance if this question is too simple.

Basically, what I want to know is if there are any functions $f(x)$ with the following properties:

Take $f_n(x)$ to be $f(x)$ when the domain and codomain are restricted to $n$-bit strings. Then

  1. $f_n(x)$ is injective
  2. $f_n(x)$ is surjective
  3. $f_n(x)$ takes strictly less resources (either space/time/circuit depth/number of gates) to compute under some reasonable model than $f^{-1}_n(y)$, where $y=f_n(x)$.
  4. The resource difference for $f_n(x)$ vs $f^{-1}(y)$ scales as some strictly increasing function of $n$.

I can come up with examples where the function is either surjective or injective, but not both unless I resort to a contrived computational model. If I choose a computational model which allows left shifts in unit time on some ring, but not right shifts, then it is of course possible to come up with a linear over head (or higher if you consider some more complicated permutation as a primitive). For this reason I am interested only in reasonable models, by which I mostly mean Turing machines or NAND circuits or similar.

Obviously this must be true if $P\neq NP$, but it would seem that this is also possible if $P=NP$, and so should not amount to deciding that question.

It is entirely possible that this question has an obvious answer or an obvious obstacle to answering which I have missed.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ This is not an area I understand well, but it seems like you are looking for a permutation on n bits that is hard to invert. I remember reading in a paper of Hastad (nada.kth.se/~johanh/onewaync0.ps) that there exist permutations that are in $NC^0$, but are P-hard to invert. $\endgroup$
    – Robin Kothari
    Sep 16, 2010 at 19:11
  • 2
    $\begingroup$ See also references to prior work in Håstad's 1987 paper. It mentions that Boppana and Lagarias (1986) give an example of a permutation that is in NC$^0$, but cannot be inverted in NC$^0$. $\endgroup$
    – Jukka Suomela
    Sep 16, 2010 at 20:22
  • 1
    $\begingroup$ Thanks, this is exactly what I was looking for. Maybe one of you wants to repost as an answer? Do you know if there is anything similar for time complexity? $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 21:03

3 Answers 3

Reset to default
11
$\begingroup$

I was asked to repost my comment. I pointed out this paper by Hastad, which shows that there exist permutations in $NC^0$ that are P-hard to invert:

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, that and Jukka's follow-up were exactly the kind of thing I was looking for. $\endgroup$
    – Joe Fitzsimons
    Sep 17, 2010 at 11:49
7
$\begingroup$

For boolean circuits over full binary basis (with the complexity measure $C(f)$ being the number of gates in a minimal circuit) the best known ratio for permutations $\frac{C(f^{-1})}{C(f)} = \text{const}$. As far as I know, the best constant was obtained in this work by Hiltgen and is equal to 2.

Edit. As you want the ratio to be increasing when $n$ grows, this doesn't answer your question. However, for boolean circuits over full binary basis nothing better is known.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Well, the fact that nothing better is known is indeed an answer. $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 22:53
  • $\begingroup$ I also suggest reading section 1.2 "Computational Asymmetry" of the following paper: Jean-Camille Birget, One-way permutations, computational asymmetry and distortion, Journal of Algebra, 320(11), Computational Algebra, 1 December 2008, Pages 4030-4062. In addition, you may be interested in this link: springerlink.com/content/4318u2t21682752u $\endgroup$
    – Sadeq Dousti
    Sep 17, 2010 at 16:49
  • $\begingroup$ A followup to the work of Hiltgen is a paper by Hirsh and Nikolenko showing a function with a constant gap between computing it and inverting it, but where there is also a trapdoor allowing easier inversion: logic.pdmi.ras.ru/~hirsch/papers/09csr.ps.gz $\endgroup$
    – user6584
    Oct 12, 2011 at 13:53
  • $\begingroup$ See also this talk by Massey: iacr.org/publications/dl/massey96/html/massey.html $\endgroup$
    – user6584
    Oct 12, 2011 at 13:57
  • $\begingroup$ Finally, let me add that it would be a major breakthrough to show the existence of a function family with a super-constant gap: showing such a gap would imply that (the search version of) circuit-SAT does not have linear-size circuits. $\endgroup$
    – user6584
    Oct 12, 2011 at 13:59
0
$\begingroup$

First of all, I wanted to point out that surjectivity is not well-defined without first defining the codomain of the function. So, in my description below, I'll explicitly refer to the codomain over which the function is surjective.

Both the discrete logarithm or RSA functions are permutations which are conjectured to be hard to invert. Below, I'll describe the discrete-logarithm function.

Let $p_n$ be an $n$-bit prime, and $g$ be a generator of the multiplicative group $\mathbb{Z}_{p_n}^*$. Define $f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ as $f_n(x) = g^x \pmod{p_n}$.

Then, $f_n$ is a function whose properties are as stated in your question: It is both injective and surjective (over codomain $\mathbb{Z}_{p_n}$), it is computable in polynomial time, yet it is conjectured that no efficient algorithm can invert $f_n$ on average.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Well they have the same complexity to compute and invert on a quantum computer, so I kind of assumed that there wasn't a proof that they required different resources, only a bunch of failed attempts to come up with polynomial time algorithms. $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 17:59
  • 4
    $\begingroup$ Ok, I think perhaps you misunderstand the point of my question. I do know that there are a wealth of functions believed to be hard to invert, and this forms the basis of public key crypto. What I am after is a case where there is a proven difference, even is it is relatively mild (I would be perfectly happy with a function that takes O(n) to compute and O(n log n) to invert for instance). $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 18:13
  • $\begingroup$ [Regarding the 1st comment] You are seeking a one-way family of permutations. The mere existence of such constructs, even on the Turing Machine model of the computation, is yet to be proved (proving so results in a proof of the existence of public-key crypto. See case 5 in cstheory.stackexchange.com/questions/1026/…) Hence, you cannot rely on unproven assumptions. However, if you want an assumption which works both in the Turing Machine model and Quantum model, I can provide you with details of assumptions based on the hardness of the "Lattice Problem". $\endgroup$
    – Sadeq Dousti
    Sep 16, 2010 at 18:13
  • 2
    $\begingroup$ I'm only seeking a very weak form of one-way function, and I'm uncertain of the status of the problem for sufficiently weak conditions. I certainly don't require an exponential difference. $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 18:24
  • 2
    $\begingroup$ No, the time complexity is governed by the time complexity of the modular exponential in all cases you mention. The modular exponential is the slow part of Shor's algorithm, so there isn't more than a constant difference in the asymptotic scaling. $\endgroup$
    – Joe Fitzsimons
    Sep 16, 2010 at 21:06

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.