Computationally Hiding

A commitment scheme is computationally hiding if, for all probabilistic polynomial-time adversaries, the commitment string reveals no information about the underlying message. This relies on the assumed hardness of a computational problem, such as the discrete logarithm problem or factoring large integers. It's a weaker guarantee than statistical hiding but is sufficient for most practical applications where adversaries have bounded computational resources.

A secure commitment scheme must satisfy two properties: hiding and binding. Hiding ensures the secret is concealed. Binding ensures the committer cannot later open the commitment to a different value. Computational hiding is often paired with perfect binding (unconditionally secure), creating a hybrid scheme. The Pedersen commitment is a classic example, offering computational hiding under the Discrete Logarithm assumption and perfect binding.

The Pedersen commitment C = g^m * h^r is a standard construct offering computational hiding.

• g, h are public generators of a cryptographic group.
• m is the secret message.
• r is a random blinding factor. The commitment C hides m because the adversary cannot distinguish between commitments of different messages due to the randomness introduced by r and the assumed hardness of the Discrete Logarithm Problem for the group.

Computational hiding is fundamental to privacy-preserving protocols:

• ZK-Rollups: Hiding transaction details within a validity proof.
• Confidential Transactions: Hiding asset amounts (e.g., in Mimblewimble).
• Voting Schemes: Hiding individual votes until tallying.
• Commit-Reveal Schemes: Securing on-chain auctions or random number generation by first posting a hidden commitment.

Security is conditional on the intractability of underlying computational problems. If an adversary gains sufficient computational power (e.g., through quantum computing breaking discrete logarithms), the hiding property fails. This is why computational hiding is contrasted with statistical hiding, which provides security against even computationally unbounded adversaries. The choice between them is a trade-off between security strength and efficiency.

Computational hiding interacts with other core concepts:

• Zero-Knowledge Proofs: Often rely on computationally hiding commitments to conceal witness data.
• Oblivious Transfer: Uses hiding to protect sender's unselected messages.
• Indistinguishability: Hiding is formally defined through computational indistinguishability between commitments of any two messages.
• Random Oracle Model: Some schemes prove hiding security in this idealized model.

A foundational cryptographic scheme that is both computationally hiding and unconditionally binding. It allows a prover to commit to a value v without revealing it, using a random blinding factor r. The security relies on the discrete logarithm problem, making it infeasible to compute v from the commitment C = v*G + r*H.

• Key Use: Core component of confidential transactions in Mimblewimble and Zcash.
• Property: Hiding is computational; an adversary with infinite computing power could theoretically break it, but this is considered practically impossible.

Zero-knowledge proof systems leverage computational hiding to prove statement validity without revealing underlying data. The witness (private inputs) is computationally hidden within the proof.

• zk-SNARKs: Use elliptic curve pairings and a trusted setup. The prover's secret witness is hidden based on the hardness of the elliptic curve discrete logarithm problem.
• zk-STARKs: Rely on cryptographic hashes and are post-quantum secure. Hiding is based on the collision resistance of the hash function.

While Merkle roots are deterministic (not hiding), computational hiding is applied to the data within the leaves. For example, a vector commitment can hide the values in a Merkle tree while still allowing proofs of inclusion.

• Application: Used in data availability sampling for Layer 2 rollups. Nodes can verify data is available without needing to see the full, potentially private, content of each transaction.

Blockchain-based voting protocols use computationally hiding commitments to ensure ballot secrecy until the tally phase. A voter commits to their choice vote with a random nonce r and publishes the hash H(vote, r).

• Process: The commitment hides the vote during the voting period.
• Reveal: Later, voters reveal (vote, r) to open their commitment, allowing the result to be computed publicly while maintaining anonymity until the reveal.

This protocol uses Pedersen Commitments to hide transaction amounts. Instead of plaintext values, the blockchain stores commitments that are sums of Pedersen commitments.

• Mechanism: A transaction output is a commitment C = x*G + a*H, where a is the amount and x is a private key (blinding factor).
• Result: The network can verify that no new money was created (by checking the sum of input/output commitments) without knowing the actual amounts involved.

Range proofs demonstrate a committed value lies within a specific range (e.g., 0 to 2^64) without revealing the value. They are built upon computationally hiding commitment schemes.

• Function: Prove a Pedersen commitment C commits to a value v where 0 ≤ v < 2^n.
• Importance: Essential for Confidential Transactions to prevent overflow attacks and negative amounts, all while keeping the actual value secret.

It's critical to distinguish computationally hiding from perfectly hiding commitments. A computationally hiding scheme relies on the assumed hardness of a computational problem (e.g., discrete log). A perfectly hiding scheme (e.g., some Pedersen Commitment variants) provides information-theoretic security, meaning even an adversary with unlimited computing power cannot learn the value. Most practical blockchain systems opt for computational hiding for its efficiency and compatibility with zero-knowledge proof systems.

Computationally binding is the complementary security property to computationally hiding in a commitment scheme. It guarantees that once a commitment is made, the committer cannot change the underlying value. This ensures the commitment is final and can be reliably opened later. A secure commitment scheme must possess both properties: it must be hiding (conceal the value) and binding (fix the value).

A Pedersen Commitment is a specific, widely-used commitment scheme based on elliptic curve cryptography. It is perfectly hiding and computationally binding under the discrete logarithm assumption. Its homomorphic properties allow commitments to be added together, making it essential for confidential transactions in cryptocurrencies like Monero and in various blockchain scaling solutions.

A Merkle tree (or hash tree) is a data structure used to efficiently verify the contents of large datasets. While not hiding by itself, it is often used in conjunction with commitment schemes. The root hash of a Merkle tree can act as a short, binding commitment to a set of data. Computationally hiding can be added by committing to hashes of encrypted or blinded data within the tree.