Paper 2023/1880

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

Chris Peikert, University of Michigan–Ann Arbor
Yi Tang, University of Michigan–Ann Arbor

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 \emph{polylogarithmic} $\tilde{O}_{n,q}(\log^2 T)$ depth, thus strongly falsifying the expectation that doing so requires linear sequential work.

Note: Substantial improvements and generalizations, including a new attack on an essentially identical PoSW to the one of [LM'23].

Available format(s)
Attacks and cryptanalysis
Publication info
timed cryptographyproof of sequential worklatticeslattice trapdoors
Contact author(s)
cpeikert @ alum mit edu
yit @ umich edu
2024-02-14: revised
2023-12-07: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Chris Peikert and Yi Tang},
      title = {Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proofs of Sequential Work},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1880},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.