Depending at the cryptographic function used applying it $i$-times to a given input can be computed in different complexity classes (based at their input size).
$$f^i(m_0) = c_i$$
For example for most block-cipher it takes (even with knowing the secret key) about $i$ times the time as applying it just once (at least as far as I know). Same for $i$ steps backwards. Finding $m_0$ for given $c_i$ also takes about $i$ times the time as a single operation (lets ignore some small optimizations here).
Computing the power of a number/generator e.g. for Elliptic curves or RSA does only take about $\log_2(i)$ times the time applying a single multiplication (roundabout). Same for $i$ steps backwards. Finding $m_0$ for given $c_i$ only takes about $\sqrt{N}$ steps (or even faster) (with $N$ the domain size of $m, c$). So this will not work.
Question: Besides block-cipher are there some other cryptographic methods were:
- $f^i(m)$ takes $i$ times the time of $f^1(m)$
- $f^{-i}(c)$ takes $i$ times the time of $f^{-1}(c)$
- $f^{-1}(c)$ similar computation time as $f^1(m)$
- computing $i$ for given $m_0$ and $c_i$ takes about $N$ computation steps or worse, with $N$ domain size of $m,c$
(constant factor or something like $\frac{1}{log{N}} N$ is still fine. Just not $N^p$ with $p<0.9$)
- (if there is some secret needed to compute $f,f^{-1}$ (like keys for block-cipher) the factor $i$ should not get smaller if this secret is known to the adversary)
- ($f,f^{-1}$ no brute force methods like block-chain)
