Efficient and Non-Interactive Non-Malleable Commitment

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam D. Smith

Abstract: This paper introduces the first efficient, non-interactive, non-malleable commitment schemes based on standard cryptographic assumptions such as the Discrete Logarithm problem and RSA. By utilizing a public parameter model and a novel three-part structure, the authors achieve a constant-size commitment (approximately $3k$ bits) regardless of the message length. This represents a significant improvement over previous schemes that required either multiple rounds of interaction or commitment sizes proportional to the message length.

Introduction

A commitment scheme is a fundamental cryptographic primitive acting as a digital "sealed envelope." It consists of two phases: a Commit phase, where a sender locks a message $m$, and a Decommit phase, where the sender reveals $m$ and proves it matches the original commitment. To be useful, these schemes must satisfy two core properties: hiding (the receiver learns nothing about $m$ before opening) and binding (the sender cannot change $m$ after committing).

The Problem of Malleability

Standard commitment schemes are often malleable. An adversary, upon seeing a commitment to $x$, might be able to generate a valid commitment to a related value $f(x)$ (e.g., $x+1$) without ever knowing $x$. This is particularly problematic in scenarios like electronic auctions, where a bidder could systematically outbid an opponent simply by manipulating the bits of the opponent's commitment.

Prior to this work, non-malleable schemes faced a trade-off between communication and efficiency:

  1. Interactive Schemes: Required multiple rounds of back-and-forth communication, which is slow and unsuitable for many network protocols.
  2. Inefficient Non-Interactive Schemes: Based on general complexity assumptions, these resulted in massive commitment sizes proportional to the message size, making them impractical for large data like databases.

The Efficient Non-Interactive Construction

The authors propose a construction in the public parameter model, where a trusted setup provides initial values available to all parties. The core of their Discrete Logarithm (DLog) based approach is an evolution of the Pedersen commitment, utilizing a three-part structure: $\langle A, B, Tag \rangle$.

  • Component A: A commitment to two random keys ($r_1, r_2$) intended for a Message Authentication Code (MAC).
  • Component B: The actual commitment to the message $m$. Crucially, the mathematical "generators" used for this commitment are derived from $A$ using a Universal One-Way Hash (UOWH) function.
  • Tag: A MAC of component $B$ using the keys committed to in $A$.

The Logic of Non-Malleability

The security of this scheme hinges on the dependency of $B$ on $A$. To create a related commitment, an adversary faces a dilemma. If they try to reuse the sender's $A$, they cannot generate a valid $Tag$ for a modified $B$ because they do not know the underlying MAC keys. If they choose a different $A'$, the UOWH function ensures that the mathematical "base" of the commitment $B$ changes, preventing the adversary from mathematically "shifting" the original value into a related one.

Key Results and Insights

  • Communication Efficiency: The scheme allows for committing to messages of arbitrary size while keeping the commitment length fixed at roughly $3k$ bits (where $k$ is the security parameter, e.g., 1024 bits). This is a massive improvement over the $O(Mk)$ overhead (where $M$ is message size) of previous non-interactive methods.
  • Strong Security Guarantees: The main constructions are perfectly hiding, meaning that even an adversary with infinite computational power cannot extract information about the message from the commitment alone.
  • Standard Assumptions: Security is rooted in well-established problems like the Discrete Logarithm problem and the RSA assumption, rather than more exotic or unproven complexity assumptions.

Conclusion and Future Work

By providing a non-interactive and communication-efficient solution, this paper transformed non-malleable commitments from a theoretical curiosity into a practical tool for secure protocol design. While the scheme requires a public parameter model (a trusted setup), the authors note that if users have unique identities, the scheme can be simplified even further. This work remains a cornerstone for building secure auctions, zero-knowledge proofs, and other complex cryptographic protocols where malleability poses a threat.

Summary updated

BibTeX
@article{crescenzo2001efficient,
  author = {Giovanni Di Crescenzo and Jonathan Katz and Rafail Ostrovsky and Adam D. Smith},
  title = {{Efficient and Non-Interactive Non-Malleable Commitment}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2001},
  url = {https://openreview.net/forum?id=1S8wCRRVLMc},
}
Figure