# Function with no fast path and with fast proof

When a function is iterated and each time a previous result is used as input to the next iteration (feedback), so that there is a limited benefit from parallel computing, is there such function that:

• requires polynomial time to get the result of N iterations

• has an Nth result that can be verified in constant time to be the Nth result for a given start value

Assuming that Alice iterates the function:

Problem with Makwa: At first Bob must use and throw away p and q.

Problem with LCS35: At first Bob must construct the puzzle.

But I need a function so that Alice can choose an arbitrary number or data to begin iterating with, not something prepared by Bob. Only when Alice has done N iterations Bob will join and verify.

• I've read crypto.stackexchange.com/questions/9327/… but it was answered before Makwa was created and I'd like to know more about Makwa in this regard and whether my question is asking for the impossible. Jan 27 '16 at 18:08
• There was some discussion concernig this on the PHC list some time ago. This and this was one of their outcomes. BTW: Makwa isn't suitable (as you found out)
– SEJPM
Jan 28 '16 at 22:43

The following paragraph applies even if the honest prover does not use iteration.

Strictly speaking, only a constant-size part of the input can be read from in
constant time, so one could always find a suitable result in constant time.
For a deterministic verifier that makes at most k probes to an alleged result
consisting of M w-bit words, one can find a suitable result with ​ 2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$kparallel
simulations of the verifier, each of which uses only ​ $(\hspace{.02 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k)\hspace{-0.04 in}+\hspace{.02 in}$O(1) ​ words of overhead.
If instead the verifier is probabilistic, then either ​ $\binom{M}{\hspace{.02 in}k\cdot \hspace{.02 in}(1+\hspace{.03 in}\Omega(1))\hspace{-0.03 in}}$$\cdot$2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k$\cdot$(1+$\hspace{.03 in}$Ω(1)) ​ parallel
simulations will be enough, or the adversary can very-efficiently go from an actual result
to one that makes the verifier's acceptance probability be between Ω(1) and 1-$\hspace{.02 in}$Ω(1).

However, it may well be possible to achieve what you're asking about with a probabilistic
word RAM verifier, by simply accepting that "the adversary ... be between ... ."
PCPs of proximity with highly-efficient verifiers do something that is somewhat similar.