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

Hongxiao Wang, Siu-Ming Yiu, Yanmin Zhao, Zoe L. Jiang, Min XieIACR ePrint 2024

TL;DR

This paper introduces the first lattice-based construction for succinct mercurial functional commitments (MFCs) that support arbitrary Boolean circuits. This is a significant advancement as it enables post-quantum secure zero-knowledge functional elementary databases (ZK-FEDBs) capable of handling complex circuit queries, overcoming limitations of previous group-based schemes.

What Problem Does This Paper Address?

Vector commitments (VCs) are fundamental cryptographic tools used in applications like blockchains. Mercurial vector commitments (MVCs) and mercurial functional commitments (MFCs) are advanced variants that offer more sophisticated functionalities, particularly for building zero-knowledge sets and elementary databases. However, existing MFCs are limited to supporting only linear functions, which restricts their applicability. Furthermore, all prior MFCs and related ZK-FEDBs rely on group-based assumptions, making them vulnerable to quantum computer attacks. This paper addresses these critical limitations by developing a new MFC construction that supports general Boolean circuits and is based on lattice assumptions, thus providing post-quantum security.

Methods

The core of this work is the construction of a novel lattice-based MFC for Boolean circuits. The authors leverage the BASIS assumption, a falsifiable lattice assumption, to build their scheme. Key technical contributions include:

  • Formalizing MFC for Boolean Circuits: The paper first defines the system and security models for MFCs that can handle arbitrary Boolean circuits.
  • Lattice-Based Construction: They propose a new MFC construction that utilizes the BASIS assumption. This construction involves sophisticated techniques from lattice cryptography, including trapdoor generation and discrete Gaussian sampling over lattices.
  • Mercurial Property: The construction is designed to satisfy the mercurial property, allowing for both "soft" (probabilistic) and "hard" (definitive) openings, which is crucial for ZK-FEDB applications.
  • Succinctness: The scheme achieves succinct commitments and openings, meaning their size grows only logarithmically with the input length.
  • Post-Quantum Security: By basing the construction on lattice assumptions, the scheme is resistant to attacks from quantum computers.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap to Boolean Circuits: The most significant insight is demonstrating that MFCs can be extended to support general Boolean circuits, moving beyond the limitations of linear functions. This opens up a much wider range of applications.
  • Lattice-Based Security for MFCs: The paper successfully shows that the advanced functionalities of MFCs can be realized within the post-quantum secure framework of lattice cryptography, a crucial step for future-proofing cryptographic systems.
  • Leveraging the BASIS Assumption: The authors cleverly utilize the BASIS assumption, which is a basis-augmented SIS assumption, to achieve the desired properties of their MFC. This assumption is key to enabling private openings and the overall construction.
  • Application to ZK-FEDB: A key takeaway is how this new MFC can be directly used to build the first lattice-based ZK-FEDB, enabling complex circuit queries in a quantum-resistant manner.

Key Results

The paper presents the first lattice-based construction of a succinct mercurial functional commitment for Boolean circuits. This construction achieves:

  • Post-Quantum Security: Based on the BASIS assumption.
  • Support for General Boolean Circuits: Unlike previous MFCs limited to linear functions.
  • Mercurial Binding and Hiding: Satisfying the security requirements for mercurial commitments.
  • Succinctness: Commitment and opening sizes are polylogarithmic in the input length.
  • Application: Enables the construction of the first lattice-based ZK-FEDB, allowing for quantum-resistant Boolean circuit queries on databases.

The paper provides formal proofs for correctness, mercurial binding, and mercurial hiding, demonstrating the security and functionality of their proposed scheme.

Limitations and Future Work

  • Target Binding: The paper notes that their construction achieves "mercurial (target) binding," which is a weaker form of binding compared to arbitrary binding. This is a common trade-off in lattice-based schemes.
  • Parameter Instantiation: While parameters are instantiated to show succinctness and security, the specific performance implications (e.g., concrete sizes and running times) would require further analysis.
  • Future Work: The authors explicitly state that their construction can be used to build the first lattice-based ZK-FEDB within an existing generic framework. This application itself is a significant direction for future research and development. Further exploration into optimizing the parameters and exploring other applications of this new MFC would be valuable.

Summary updated

BibTeX
@article{wang2024lattice,
  author = {Hongxiao Wang and Siu-Ming Yiu and Yanmin Zhao and Zoe L. Jiang and Min Xie},
  title = {{Lattice-Based Succinct Mercurial Functional Commitment for Circuits: Definitions and Constructions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
}
Figure