Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proofs of Sequential Work

This work completely breaks the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023. In addition, it breaks an essentially identical variant of the PoSW, which differs from the original in only an arbitrary choice that is immaterial to the design and security proof (under the falsified assumption). This suggests that whatever security the original PoSW may have is fragile, and further motivates the search for a construction based on a sound lattice-based assumption.

Specifically, for sequentiality parameter $T$ and SIS parameters $n,q,m = n \log q$, the attack on the sequentiality assumption finds a solution of quasipolynomial norm $m^{\lceil \log T \rceil}$ (or norm $O(\sqrt{m})^{\lceil \log T \rceil}$ with high probability) in only logarithmic $\tilde{O}_{n,q}(\log T)$ depth; this strongly falsifies the assumption that finding such a solution requires depth linear in $T$. (The $\tilde{O}$ notation hides polylogarithmic factors in the variables appearing in its subscript.) Alternatively, the attack finds a solution of polynomial norm $m^{1/\varepsilon}$ in depth $\tilde{O}_{n,q}(T^{\varepsilon})$, for any constant $\varepsilon > 0$. Similarly, the attack on the (slightly modified) PoSW constructs a valid proof in polylogarithmic $\tilde{O}_{n,q}(\log^2 T)$ depth, thus strongly falsifying the expectation that doing so requires linear sequential work.