F-NMCOM — Non-malleable commitment

F-NMCOM (Non-malleable commitment) is part of Commitments and Proofs in the UC functionality encyclopedia. Status: a canonical, well-established UC functionality.

No functionality is printed under this name, and here the reason is the sharpest one this encyclopedia has recorded: in the UC framework, non-malleability is not a separate guarantee to define — it is a consequence of the definition already written down. Universal composability implies non-malleability, and not merely against other copies of the same protocol but against arbitrary other protocols. A functionality asserting non-malleability on top of F-COM would be asserting something F-COM already gives.

So the box a reader wants is F-COM, or F-MCOM where several commitments share a reference string — and the latter is the one that matters here, since malleability between concurrent commitments is the interesting case and the single-commitment box does not reach it.

Why there is no box

The harvest, and what it found. All three references resolved. Canetti and Fischlin print four functionalities — the common reference string, single commitment, multiple commitments, and \(\mathcal{F}_{\mathsf{zk}}\) — and no \(\mathcal{F}_{\mathsf{nmcom}}\). Di Crescenzo, Ishai and Ostrovsky (STOC 1998) and Fischlin and Fischlin (CRYPTO 2000) are both game-based treatments predating the UC framework; neither prints an ideal functionality, which is expected for citations naming the origin of the notion.

And this is not an extraction failure. None of the five recorded false-negative modes applies: the paper’s four boxes were found and read, and two of them are written up on this site from that same paper.

A forward search confirms the framing rather than overturning it. The standard statement is that universal composability “implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols)”, alongside resilience to selective decommitment. Non-malleable commitment remains an active subject — concurrent non-malleability, constant-round constructions, sub-exponential assumptions — but that work is game-based, defining non-malleability directly rather than through an ideal functionality.

What the closest printed things are

F-MCOM, the multi-commitment functionality, written from Canetti–Fischlin. This is the honest target for anyone who came here wanting non-malleability: it is where several commitments coexist under one reference string, so it is where mauling would have to happen, and realizing it rules mauling out.
F-COM, the single-commitment case, for completeness.
A weaker functionality that does name mauling. Kosba et al.’s \(\mathcal{F}_{\textsc{weak-nizk}}\), written up at F-SNARK, is worth reading beside this page: it is a rare instance of an ideal functionality that permits mauling, by adding an explicit interface for it. That it needed an extra interface to allow mauling is the cleanest available evidence that the unmodified functionality forbids it.

What would resolve this

Finding a paper that prints a functionality under this name would turn this into an ordinary entry. Failing that, the slot should be retired and its content folded into F-MCOM as a note on what UC security already implies. The second is the more likely outcome. Either way the finding is worth having stated, because “UC commitment is already non-malleable” is exactly the kind of fact a reader is entitled to before going looking for a box that does not exist.

Formal artifacts

No machine-checked formalization yet.

References:

Canetti and Fischlin. Universally composable commitments. In Advances in Cryptology – CRYPTO 2001, volume 2139 of LNCS, pages 19–40, 2001. Read at ePrint revision 20010710:161305, the only posting. Prints the common reference string functionality, the single- and multi-commitment functionalities, and \(\mathcal{F}_{\mathsf{zk}}\); no \(\mathcal{F}_{\mathsf{nmcom}}\).
Di Crescenzo, Ishai, and Ostrovsky. Non-interactive and non-malleable commitment. In 30th ACM Symposium on Theory of Computing (STOC), pages 141–150, 1998. Game-based, three years before the UC framework; prints no ideal functionality.
Fischlin and Fischlin. Efficient non-malleable commitment schemes. In Advances in Cryptology – CRYPTO 2000, volume 1880 of LNCS, pages 413–428, 2000. Likewise game-based; prints no ideal functionality.