We know that a good hash function is a one way/trapdoor function. Easy to calculate one way, harder to work out a previous state.
I was wondering if anyone knew a good hashing system that allowed you to calculate an arbitrary number of steps into the state future.
E.g. instead of running the hash function 10,000 times to find out the h^10000(X), you could use a function to calculate what that would be , e.g. H(X,10000).
Thus, having a "fast forwarding" hash function that is fast in one direction, but provably hard in the other.
Anyone have knowledge/experience/ideas here? Much appreciated.
Follow up to the answer (to some degree).
Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.
A linear congruential generator (LCG) can be skipped ahead [link], in fact many PRNG's can be skipped/jumped ahead [link].
The problem with fast-forwarding any hash/prng, is that if you know the cycle period (which you do with most PRNGs), by fastforwarding the period-1, you effectively move back 1 state.
Thus if we found a way to say move forward quickly with a SHA256, the first person to correctly estimate its cycle period would also have the ability to move backward as well.
The only fix for this is to have a system with a huge number of varied cycles. E.g. having 256 bits worth of different cycles lengths, which each cycle being 64-256 bits in cycle length, fitting in 512 bits of state.
No known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.
tl;dr - if you can go forward and calculate its cycle length, you can go backward.
What you're asking for is akin to multiplication, which is just repeated addition. As we know from our grade school classes, these are reversible with subtraction and division.
My understanding of the current state of the art is that in order to make it not trivial to reverse, it requires the input of previous state to generate next state--each subsequent state is built on the previous state.
It's not inconceivable that someone could eventually invent such a thing... but given our current approaches and mathematical knowledge, it does seem it will require some breakthrough.
your p0 ... pi is your input (absorbing phase), while z0 ... zp is what you get when squeeze it p times.
for more informations : sponge corner
Keccak (SHA-3) has been implemented using it.
You could consider the compression function f as your hashing algorithm and squeeze your sponge the number of time you want.