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 .