IACR News item: 07 December 2023
Chris Peikert, Yi Tang
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.