A doubt on Proofs-of-Sequential-Work protocols

Question

Proofs-of-Sequential-Work ($\mathsf{PoSW}$) are cryptographic protocols that engage two parties, a prover with $\mathtt{poly}(N)$-parallel processors and a deterministic verifier such that the verifier can check in $\mathcal{O}(\log{N})$-time if the prover has spent $\Omega(N)$-parallel time to compute an inherently sequential function. Some well-known examples (that are not verifiable delay functions) are,

1. Simple Proofs of Sequential Work
2. Incremental Proofs of Sequential Work
3. Reversible Proofs of Sequential Work

Ref. [1,2] and Ref.3 exploit the inherent sequentiality of random oracles and random permutation oracles, respectively, in their design.

But, Theorem 3.6 in the following paper refutes the existence of $\mathsf{PoSW}$s in the random oracle model and the authors extend the same for the random permutation oracle in Sect. 4.3., Can Verifiable Delay Functions be Based on Random Oracles?

I am unable to understand the actual implication of Theorem 3.6. So, my question is does Theorem 3.6 and Sect. 4.3 refute the $\mathsf{PoSW}$s in Ref. [1,2,3]?

Answer 1

I would like to post the answer recieved in a personal commmunication by the author of the Theorem 3.6.

Theorem 3.6 only rules out tight proofs-of-sequential-work in the random oracle model. The constructions in Refs. [1,2,3] are not tight, and thus, would not be captured by its lower bound.

A proofs-of-sequential-work is tight if it can be computed honestly in time $N$ but not in parallel time $\sigma(N)<N-o(N)$.