Scholarlink

Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of \(\tilde{O}(\lambda )\) together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by “RoK, Paper, SISsors” (RPS) [ASIACRYPT’24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity \(\tilde{O}(\lambda )\) and succinct verification for structured linear relations.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

RoK and Roll – Verifier-Efficient Random Projection for  \(\tilde{O}(\lambda )\) -Size Lattice Arguments

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Michael Klooß,
  • Russell W. F. Lai,
  • Ngoc Khanh Nguyen,
  • Michał Osadnik

摘要

Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of \(\tilde{O}(\lambda )\) together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by “RoK, Paper, SISsors” (RPS) [ASIACRYPT’24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity \(\tilde{O}(\lambda )\) and succinct verification for structured linear relations.