Paper 2025/1622

Random Variable Commitments for Any Sampleable Distribution, and a Certified Laplace Mechanism

Abstract

At CRYPTO'24, Bell et al. propose a definition of random variable commitment schemes (RVCS) and show that it leads to a notion of certified differential privacy (DP). We prove that there exists RVCS's for all efficiently sampleable distributions, under the discrete logarithm assumption. This follows from three lemmata that additionally enable simple modular design of new RVCS's; First, we show that the properties of RVCS's are closed under polynomial sequential composition. Secondly, we show that homomorphically evaluating a function $f$ on the output of an RVCS for distribution $Z$ leads to an RVCS for distribution $f(Z)$. Thirdly, we show that applying a `Commit-and-Prove'-style argument of knowledge for a function $f$ onto the output of an RVCS for distribution $Z$ results in an RVCS for distribution $f(Z)$. Further, we observe that Bell et al. use $\Sigma$-protocols and a knowledge soundness property seemingly significantly stronger than those typically used when studying $\Sigma$-protocols. To align the RVCS definition with the literature on $\Sigma$-protocols, we relax it slightly and show that known constructions fulfill this adapted definition. We propose another orthogonal relaxation which allows for sampling algorithms that abort with non-zero probability. We demonstrate the usefulness of the lemmata and definitional adaptations by constructing the first RVCS's for arbitrarily biased coins and a discrete Laplace distribution, leading to the first certified DP protocol for a discrete Laplace mechanism. Practicality is shown via an open-source Rust implementation.

Note: Change-notes: Changed title, namings/notation and publication info. This is the full version of the paper with the same title which will appear at Crypto'26.