<p>For boolean circuits over full binary basis (with the complexity measure <span class="math-container">$C(f)$</span> being the number of gates in a minimal circuit) the best known ratio for permutations <span class="math-container">$\frac{C(f^{-1})}{C(f)} = \text{const}$</span>. As far as I know, the best constant was obtained in <a href="https://doi.org/10.1007/3-540-57220-1_80" rel="nofollow noreferrer" title="Hiltgen, A.P.L. (1993). Constructions of feebly-one-way families of permutations. In: Seberry, J., Zheng, Y. (eds) Advances in Cryptology — AUSCRYPT '92. AUSCRYPT 1992. Lecture Notes in Computer Science, vol 718. Springer, Berlin, Heidelberg">this work</a> by Hiltgen and is equal to 2.</p>
<p>Edit. As you want the ratio to be increasing when <span class="math-container">$n$</span> grows, this doesn't answer your question. However, for boolean circuits over full binary basis nothing better is known.</p>

CC BY-SA 3.0
2011-10-12T13:53:45.757Z
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: http://logic.pdmi.ras.ru/~hirsch/papers/09csr.ps.gz
user6584
CC BY-SA 3.0
2011-10-12T13:57:38.963Z
See also this talk by Massey: http://www.iacr.org/publications/dl/massey96/html/massey.html
user6584
CC BY-SA 3.0
2011-10-12T13:59:20.880Z
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.
user6584
CC BY-SA 2.5
2010-09-16T22:53:46.840Z
Well, the fact that nothing better is known is indeed an answer.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-17T16:49:42.150Z
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: http://www.springerlink.com/content/4318u2t21682752u/
Sadeq Dousti
CC BY-SA 4.0
2010-09-16T22:07:27.043Z
2022-10-04T15:21:19.497Z
2022-10-04T15:21:19.497Z
Grigory Yaroslavtsev
<p>First of all, I wanted to point out that surjectivity is not well-defined without first defining the <a href="http://en.wikipedia.org/wiki/Codomain" rel="nofollow">codomain</a> of the function. So, in my description below, I'll explicitly refer to the codomain over which the function is surjective.</p>

<p>Both the <a href="http://en.wikipedia.org/wiki/Discrete_logarithm" rel="nofollow">discrete logarithm</a> or <a href="http://en.wikipedia.org/wiki/RSA" rel="nofollow">RSA</a> functions are permutations which are conjectured to be hard to invert. Below, I'll describe the discrete-logarithm function.</p>

<p>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}$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-16T17:59:59.170Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T18:13:50.927Z
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).
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T18:13:53.267Z
[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 http://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds)

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".
Sadeq Dousti
CC BY-SA 2.5
2010-09-16T18:15:47.477Z
[Regarding 2nd comment] Well, it seems I misunderstood! Let me think more about it.
Sadeq Dousti
CC BY-SA 2.5
2010-09-16T18:24:32.510Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T20:38:58.577Z
Just one question: in your first comment, yo said "they [discrete log & RSA] have the same complexity to compute and invert on a quantum computer." I think the computation and inverting are both polynomial on a quantum computer, yet the required time of the best algorithm for computation and inverting differs by orders of magnitude. Am I right?
Sadeq Dousti
CC BY-SA 2.5
2010-09-16T21:06:26.663Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T17:48:11.360Z
2010-09-16T18:01:42.757Z
2010-09-16T18:01:42.757Z
Sadeq Dousti
<p>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:</p>

<p><a href="http://dx.doi.org/10.1016/0020-0190(87)90053-6">http://dx.doi.org/10.1016/0020-0190(87)90053-6</a> <a href="http://www.nada.kth.se/~johanh/onewaync0.ps">(PS)</a></p>

CC BY-SA 2.5
2010-09-17T11:49:29.420Z
Thanks, that and Jukka's follow-up were exactly the kind of thing I was looking for.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-17T02:52:43.850Z
2010-09-17T02:52:43.850Z
Robin Kothari
<p>Apologies in advance if this question is too simple.</p>

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

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

<ol>
<li>$f_n(x)$ is injective</li>
<li>$f_n(x)$ is surjective</li>
<li>$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)$.</li>
<li>The resource difference for $f_n(x)$ vs $f^{-1}(y)$ scales as some strictly increasing function of $n$.</li>
</ol>

<p>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. </p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-16T19:11:46.283Z
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 (http://www.nada.kth.se/~johanh/onewaync0.ps) that there exist permutations that are in $NC^0$, but are P-hard to invert.
Robin Kothari
CC BY-SA 2.5
2010-09-16T20:22:34.643Z
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$.
Jukka Suomela
CC BY-SA 2.5
2010-09-16T21:03:30.757Z
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?
Joe Fitzsimons
<cc.complexity-theory>
Are there any classes of functions which require provably different resources to compute versus computing their inverse?
Joe Fitzsimons
# Are there any classes of functions which require provably different resources to compute versus computing their inverse?

(Asked by: username_0 on 2010-09-16)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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 (http://www.nada.kth.se/~johanh/onewaync0.ps) that there exist permutations that are in $NC^0$, but are P-hard to invert.  
> **username_2**: 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$.  
> **username_0**: 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?  

---

## 3 answers

### Answer by username_1 on 2010-09-17. Score: 11 | Accepted answer

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)](http://www.nada.kth.se/~johanh/onewaync0.ps)

> **Comments:**
> **username_0**: Thanks, that and Jukka's follow-up were exactly the kind of thing I was looking for.  

---

### Answer by username_3 on 2010-09-16. Score: 7

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](https://doi.org/10.1007/3-540-57220-1_80 "Hiltgen, A.P.L. (1993). Constructions of feebly-one-way families of permutations. In: Seberry, J., Zheng, Y. (eds) Advances in Cryptology — AUSCRYPT '92. AUSCRYPT 1992. Lecture Notes in Computer Science, vol 718. Springer, Berlin, Heidelberg") 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.

> **Comments:**
> **username_0**: Well, the fact that nothing better is known is indeed an answer.  
> **username_5**: 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: http://www.springerlink.com/content/4318u2t21682752u/  
> **username_4**: 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: http://logic.pdmi.ras.ru/~hirsch/papers/09csr.ps.gz  
> **username_4**: See also this talk by Massey: http://www.iacr.org/publications/dl/massey96/html/massey.html  
> **username_4**: 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.  

---

### Answer by username_5 on 2010-09-16. Score: 0

First of all, I wanted to point out that surjectivity is not well-defined without first defining the [codomain](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Discrete_logarithm) or [RSA](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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).  
> **username_5**: [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 http://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds)  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".  
> **username_5**: [Regarding 2nd comment] Well, it seems I misunderstood! Let me think more about it.  
> **username_0**: 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.  
> **username_5**: Just one question: in your first comment, yo said "they [discrete log & RSA] have the same complexity to compute and invert on a quantum computer." I think the computation and inverting are both polynomial on a quantum computer, yet the required time of the best algorithm for computation and inverting differs by orders of magnitude. Am I right?  
> **username_0**: 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.  

---

