Paper 2024/617

Lattice-Based Succinct Mercurial Functional Commitment for Boolean Circuits: Definitions and Constructions

Abstract

Vector commitments (VC) have gained significant attention due to their extensive use in applications such as blockchain and accumulators. Mercurial vector commitments (MVC) and mercurial functional commitments (MFC), as variants of VC, are central techniques for constructing more advanced cryptographic primitives, such as zero-knowledge sets and zero-knowledge functional elementary databases (ZK-FEDB). However, existing MFCs $\textit{only support linear functions}$, which limits their applicability—for instance, in building ZK-FEDBs that support only linear function queries. Moreover, to the best of our knowledge, the current MFCs and ZK-FEDBs, including the state-of-the-art proposed by Zhang and Deng (ASIACRYPT '23) using RSA accumulators, are all based on group-based assumptions and $\textit{cannot resist quantum computer attacks}$. To address these limitations, we $\textit{first}$ formalize the system and security models of MFC to support Boolean circuits. Then, we target specific properties of a new falsifiable assumption, namely the $\mathsf{BASIS}$ assumption proposed by Wee and Wu (EUROCRYPT '23), to construct the $\textit{first}$ lattice-based succinct mercurial functional commitment for Boolean circuits. As an application of our construction, we demonstrate how it can be used to build the $\textit{first}$ lattice-based ZK-FEDB within the existing generic framework.