15
$\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.

$\endgroup$
  • 3
    $\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 '10 at 19:11
  • 1
    $\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 '10 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 '10 at 21:03
10
$\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)

$\endgroup$
  • $\begingroup$ Thanks, that and Jukka's follow-up were exactly the kind of thing I was looking for. $\endgroup$ – Joe Fitzsimons Sep 17 '10 at 11:49
5
$\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)} = 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.

$\endgroup$
  • $\begingroup$ Well, the fact that nothing better is known is indeed an answer. $\endgroup$ – Joe Fitzsimons Sep 16 '10 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$ – M.S. Dousti Sep 17 '10 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$ – user686 Oct 12 '11 at 13:53
  • $\begingroup$ See also this talk by Massey: iacr.org/publications/dl/massey96/html/massey.html $\endgroup$ – user686 Oct 12 '11 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$ – user686 Oct 12 '11 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.

$\endgroup$
  • $\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 '10 at 17:59
  • 2
    $\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 '10 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$ – M.S. Dousti Sep 16 '10 at 18:13
  • 1
    $\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 '10 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 '10 at 21:06

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.