Welcome to the resource topic for
**2023/1880**

**Title:**

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

**Authors:**
Chris Peikert, Yi Tang

**Abstract:**

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 \log_{k} T), where the integer k \leq T may be freely chosen.

(The \tilde{O} notation hides polylogarithmic factors in the variables appearing in its subscript.)

In particular, with the typical parameterization \log q = \tilde{O}_{n,T}(1), for k=2 the attack finds a solution of quasipolynomial norm O(\sqrt{m})^{\log T} in only *polylogarithmic* \tilde{O}_{n,T}(1) depth; this strongly falsifies the assumption that finding such a solution requires depth *linear* in T.

Alternatively, setting k = T^{\varepsilon}, the attack finds a solution of polynomial norm O(\sqrt{m})^{1/\varepsilon} in depth \tilde{O}_{n,T}(T^{\varepsilon}), for any constant \epsilon > 0.

We stress that the attack breaks the *assumption* underlying the proposed PoSW, but not the *PoSW itself* as originally defined.

However, the attack does break a *slight modification* of the original PoSW, which has an essentially identical security proof (under the same kind of falsified assumption).

This suggests that whatever security the original PoSW may have is fragile, and further motivates the search for a PoSW based on a sound lattice-based assumption.

**ePrint:**
https://eprint.iacr.org/2023/1880

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .