Lattice-based Folding Scheme 入門

Folding schemes 是在 zk 證明系統中會用到的技術，能把很多可驗證的計算合併成一個，這樣證明時只需要對一個 instance 做證明即可。原本的 folding schemes（Nova、HyperNova）是基於橢圓曲線（離散對數問題），因此未來容易受到量子電腦攻擊。Lattice-based folding scheme 主流是基於 Ajtai 承諾（SIS，Short Integer Solution 問題），目前沒有已知的量子演算法能有效破解。

Ajtai 承諾需要秘密值（witness）是 low-norm 才能保持 binding，以確保承諾真的是對應到該秘密值而不是另一個值。但是，在做 folding 時秘密值的 norm 會不斷增長，我們必須確保 1) 一開始承諾的秘密值就是 low-norm、2) folding 後的秘密值必須保持 low-norm。我們分別用 norm check 解決 (1)、decomposition（進制分解）解決 (2)。

講者會分享他在一個讀書會中學到的 lattice-based folding （ github.com/coset-io/baby-lattice-folding ）相關的知識，希望能讓觀眾理解這些技術的一些背景及直覺。