Crypto Seminar - Yi Tang

— 5:30pm

Location:
In Person and Virtual - ET - Blelloch-Skees Conference Room, Gates Hillman 8115 and Zoom

Speaker:
YI TANG, Ph.D. Student, Electrical Engineering and Computer Science Department, University of Michigan
https://web.eecs.umich.edu/~yit/

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

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 mlog T (or norm O(sqrt(m))log T with high probability) in only logarithmic Õn,q(log T) depth; this strongly falsifies the assumption that finding such a solution requires depth *linear* in T. (The Õ notation hides polylogarithmic factors in the variables appearing in its subscript.) Alternatively, the attack finds a solution of polynomial norm m1/ε in depth Õn,q(Tε), for any constant ε > 0. Similarly, the attack on the (slightly modified) PoSW constructs a valid proof in  polylogarithmic  Õn,q(log2 T) depth, thus strongly falsifying the expectation that doing so requires linear sequential work.

Joint work with Chris Peikert.

Reference paper

Event Website:
https://sites.google.com/view/crypto-seminar/home