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.

  • $\begingroup$ 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. $\endgroup$ Commented Jan 27, 2016 at 18:08
  • $\begingroup$ 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) $\endgroup$
    – SEJPM
    Commented Jan 28, 2016 at 22:43

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.