报告名称：Code-Based Zero-Knowledge from VOLE-in-the-Head and Their Applications: Simpler, Faster, and Smaller

报告专家：徐燕虹

专家所在单位：上海交通大学

报告时间：2024-10-29，16:00-18:00

报告地点: 数统学院201

专家简介：徐燕虹，上海交通大学助理研究员，研究方向为零知识证明以及后量子隐私签名协议设计。加入上海交通大学之前，她在新加坡南洋理工大学取得博士学位，在加拿大卡尔加里大学担任博士后研究员。目前，在密码旗舰会议和期刊发表论文多篇，包括亚密会、PKC、Theoretical Computer Science等。

报告摘要：

Zero-Knowledge (ZK) protocols allow a prover to demonstrate the truth of a statement without disclosing additional information about the underlying witness. Code-based cryptography has a long history but did suffer from periods of slow development. Recently, a prominent line of research have been contributing to designing efficient code-based ZK from MPC-in-the-head (Ishai et al., STOC 2007) and VOLE-in-the head (VOLEitH)  (Baum et al., Crypto 2023) paradigms, resulting in quite efficient standard signatures. However, none of them could be directly used to construct privacy-preserving cryptographic primitives. Therefore, Stern's protocols remain to be the major technical stepping stones for developing  advanced code-based privacy-preserving systems.

This work proposes new code-based ZK protocols from VOLEitH paradigm for various relations and designs several code-based privacy-preserving systems that considerably advance the state-of-the-art in code-based cryptography. Our first contribution is a new ZK protocol for proving the correctness of a regular (non-linear) encoding process, which is utilized in many advanced privacy-preserving systems. Our second contribution are new ZK protocols for concrete code-based relations.   In particular, we provide a ZK of accumulated values  with optimal witness size for the accumulator (Nguyen et al.,  Asiacrypt 2019).  Our protocols thus open the door for constructing more efficient  privacy-preserving systems. Moreover, our ZK protocols have the advantage of being simpler, faster, and smaller compared to Stern-like protocols.  To illustrate the effectiveness of our new ZK protocols, we develop ring signature (RS) scheme, group signature (GS) scheme, fully dynamic attribute-based signature scheme from our new ZK. The signature sizes of the resulting schemes are two to three orders of magnitude smaller than those based on Stern-like protocols in various parameter settings. Finally, our first ZK protocol yields a standard signature scheme, achieving ``signature size + public key size'' as small as $3.05$ KB, which is slightly smaller than the state-of-the-art signature scheme (Cui et al., PKC 2024) based on the regular syndrome decoding problems.