由子向量承諾系統所生之簡短零知識證明

Abstract

近年來，針對NP完備問題的零知識證明 (zero knowledge argument of knowledge) 有了更實際的構造，並在現實應用中發揮作用。然而，這樣的零知識證明大多需要由公正第三方來進行初始化，因此不適合在區塊鏈 (blockchain) 等去中心化的場域中使用。本篇論文鎖定於透明的證明 (transparent argument)，即初始過程不包含祕密資訊的證明。這有賴於使用透明的承諾系統 (commitment scheme)，而承諾系統的額外功能也能用以降低實際成本。本篇論文採納前人工作 [6,7]，將其轉化成基於離散對數難題 (discrete logarithm problem) 的透明多階段子向量承諾系統 (transparent multi­stage subvector commit­ment scheme)，使得在事先承諾的諸多訊息之中，可以揭露任意數量而不影響所產生的證明大小。本論文將其應用於近年來的互動預言機證明 (interactive oracle proof) 模型下的零知識證明，結果顯示在 2^16 個運算閘的計算問題上得以減少 58.7% 的證明大小。本論文也延伸此承諾系統，使其基於目前公認為後量子安全 (post-quantum secure) 的具結構的晶格 (structured lattice) 上的短向量難題假設。

In recent years, practical zero knowledge arguments of knowledge for NP-complete problems have been proposed and used in real-world applications. However, many of them require a trusted setup, which is unsuitable for decentralized areas like blockchain. We therefore focus only on transparent arguments, which do not involve any secret in the setup procedure. This is highly related to using commitment schemes that are transparent, but one also needs commitment schemes with nice features to reduce concrete costs. In this work, we modify the works [6,7] that are based on the hardness of the discrete logarithm problem, and turn them into a transparent multi-stage subvector commitment scheme. Such commitment schemes can open to an arbitrary number of committed messages without affecting the opening proof size. We then apply our multi-stage subvector commitment scheme to a recent IOP-based zero knowledge argument, obtaining arguments with a 58.7% reduction on proof size for circuits with 2^16 gates. We also extend our scheme to one that is alternatively based on structured lattice assumptions, which are currently believed to be post-quantum secure.