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

ePrint Report: Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proofs of Sequential Work

Chris Peikert, Yi Tang

This note describes a total break of 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.
Specifically, for sequentiality parameter $T$ and SIS parameters $n,q,m = n \log q$, the attack computes a solution of norm $(m+1)^{\log_{k} T}$ (or norm $O(\sqrt{m})^{\log_{k} T}$ with high probability) in depth $\tilde{O}_{n,q}(k …

chris cryptanalysis crypto eprint report proof report tang work