Title: Interactive Line-Point Zero-Knowledge with Sublinear Communication and Linear Computation

Abstract: Studies of vector oblivious linear evaluation (VOLE)-based zero-knowledge (ZK) protocols flourish in recent years. Such ZK protocols feature optimal prover computation and a flexibility for handling arithmetic circuits over arbitrary fields. However, most of them have linear communication, which constitutes a bottleneck for handling large statements in a slow network. The pioneer work AntMan (CCS’22), achieved sublinear communication for the first time within VOLE-based ZK, but lost the advantage of fast proving. In this work, we propose two new VOLE-based ZK constructions that achieve sublinear communication and linear computation, simultaneously. Let C be a circuit with size S, input size n, and depth d. In particular, our first ZK, specialized for layered circuits, has communication O(n + d log S), while our second ZK can be used to prove general circuits and has communication O(n + d log S + d2). Our results are obtained by introducing the powerful sum-check techniques from the mature line of works on interactive proofs into the context of VOLE-based ZK for the first time. Reminiscent of the non-interactive line-point zero-knowledge proof system (ITC’21), we introduce an interactive line-point zero-knowledge (ILPZK) proof system, which closely connects with VOLE-based ZK protocols. In addition, our works also enrich the studies of ZK based on interactive proofs, with new interesting features (e.g., having information-theoretic UC-security, naturally supporting any field) achieved.

Speaker Biograph: 林富春，上海交通大学任教，博士毕业于新加坡南洋理工大学，先后在加拿大卡尔加里大学和英国帝国理工学院从事博士后研究，在编码与密码领域取得一系列重要成果，研究成果发表在美密会、亚密会、CCS、INFOCOM、《IEEE Transactions on Information Theory》、《中国科学》等编码与密码领域著名国际学术会议或期刊上。担任FOCS、EUROCRYPT、ASIACRYPT、IEEE Transactions on Information Theory等编码与密码领域著名国际学术会议或期刊的审稿人。

报告时间：2024年11月29日 15:00-16:30

地点：腾讯会议 233195826

邀请人：秦静教授 杨海宁助理研究员