240818 - ZKPunk's ZK Insights

Highlights

Additive NTT (ANTT) by Ingonyama

有限扩展域上的加法 FFT 出现于 20 世纪 80 年代末。我们将加法 FFT 称为加法 NTT (ANTT)，是对加法子群而非乘法子群的求值。有趣的是，它们根本不是傅里叶变换，但它们服从类似 FFT 的递归结构，实现了 $O (n l o g n)$ 复杂度。链接是参考的书籍和 Ingonyama 为 Open-Binius 项目实现的 python 参考代码。

Theory: NTT201 book, chapter 3: https://github.com/ingonyama-zk/papers/blob/main/ntt_201_book.pdf
Reference code, Open-Binius repo: https://github.com/ingonyama-zk/open-binius/tree/main/ref/antt

Fibonacci Air Implementation in Plonky3

This repo implements a Fibonacci sequence generator and prover using the Plonky3 framework.

https://github.com/BrianSeong99/plonky3_fibonacci

Lemma is a ZK theorem proving framework that enables individuals to post unsolved theorem definitions accompanied by a bounty for anyone that can submit a valid Mathematical proof which solves the theorem. These proofs are validated on chain, and the bounties are trustlessly released to the solver.

https://github.com/asm-nop/lemma

Cryptographic Right Answers: Post Quantum Edition

后量子加密技术（PQC）的前景复杂而充满挑战，新算法和新标准不断涌现，如 Kyber、Dilithium 和 SPHINCS+，它们提供了更高的安全性，可抵御量子攻击。要驾驭这一格局，开发人员应优先使用成熟的加密库，避免定制实现，并专注于混合方案。

The post-quantum cryptography (PQC) landscape is complex and challenging, with new algorithms and standards emerging, such as Kyber, Dilithium, and SPHINCS+, which offer improved security against quantum attacks. To navigate this landscape, developers should prioritize using established cryptographic libraries, avoiding custom implementations, and focusing on hybrid schemes.

https://www.latacora.com/blog/2024/07/29/crypto-right-answers-pq/

Updates

Sparta(0)

Rust implementation of the SuperSpartan IOP

Papers

Succinct Non-Subsequence Arguments

https://eprint.iacr.org/2024/1264

Safe curves for elliptic-curve cryptography

https://eprint.iacr.org/2024/1265

AES-based CCR Hash with High Security and Its Application to Zero-Knowledge Proofs

https://eprint.iacr.org/2024/1271

A bound on the quantum value of all compiled nonlocal games

https://eprint.iacr.org/2024/1276

Improved Polynomial Division in Cryptography

论文的核心技术贡献是离散傅里叶变换下导数算子和逐点除法的新型共轭表示和组合，能够利用洛必达法则高效计算多项式除法。

https://eprint.iacr.org/2024/1279

Stackproofs: Private proofs of stack and contract execution using Protogalaxy

https://eprint.iacr.org/2024/1281

Basic Lattice Cryptography: The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA)

https://eprint.iacr.org/2024/1287

VerITAS: Verifying Image Transformations at Scale

VerITAS 使用零知识证明来证明只有某些编辑被应用于签名过的照片，首次实现了为真实大图像（3000 万像素）进行证明。其关键创新在于设计了一个新的证明系统，该系统能够证明对大量见证数据的有效签名。

https://eprint.iacr.org/2024/1066

Hekaton: Horizontally-Scalable zkSNARKs via Proof Aggregation

Hekaton 构造了一个新的「分发-聚合」框架，可以高效处理任意大规模计算。该框架将大型计算分解成小块，在分布式系统中并行证明这些小块，然后将得到的小块证明聚合成一个简洁的证明。实验表明 Hekaton 实现了很强的横向可扩展性（证明时间随着集群中节点数量的增加而线性减少），并且能够快速证明大型计算：它可以在一小时内证明大小为 $2^{35}$ 个门的电路，这比之前的工作快得多。

https://eprint.iacr.org/2024/1208

Learnings

Abstract Algebra Online Course

抽象代数涉及群、环、场和模块。这些抽象结构出现在许多不同的数学分支中，包括几何、数论、拓扑学等。它们甚至出现在量子力学等科学课题中。

Abstract Algebra deals with groups, rings, fields, and modules. These are abstract structures which appear in many different branches of mathematics, including geometry, number theory, topology, and more. They even appear in scientific topics such as quantum mechanics.

https://www.youtube.com/playlist?list=PLi01XoE8jYoi3SgnnGorR_XOW3IcK-TP6

Galois Theory Notes

The author has arXived their Galois theory course notes from 2021-2023, making them publicly available along with other course materials. The author notes that the Galois theory notes have been particularly popular, possibly due to their visually appealing format with color and icons.