category
Pedersen commitments were originally described as part of Pedersen’s verifiable secret-sharing scheme in 1992. Section 3 of the Pedersen paper notes that the commitment scheme is “very similar” to a scheme proposed by Bos, Chaum, and Purdy in an unpublished set of notes proposing a voting system.
Pedersen commitments are simple. Committing to a value requires only two modular exponentiations and a multiplication. Because a random value is required for each commitment, commitments are non-deterministic. And, because Pedersen commitments rely heavily on group structure, they inherit a large number of useful properties that allow for useful operations and proofs for the committed values.
Pedersen’s original proposal described the commitment in terms of order-
subgroups of , but we will describe it in more generic terms, as it is applicable to any group where the discrete logarithm problem is believed to be hard (such as elliptic curve groups).Definition #
Start with a finite group
of prime order , where is suitably large. For instance, we can use an order- subgroup the multiplicative group where divides , or an elliptic curve group or subgroup. Select two generators of such that is not known. The parameters of the commitment scheme are .To generate a commitment
to a secret integer , where , randomly sample and compute:
(When
are clear from context, we can simply write .)To open the commitment, simply reveal
and .Intuition as to Why Pedersen Commitments are Binding #
Suppose Alice has sent Bob a commitment
to a value . She now wants to cheat by sending Bob an opening for that corresponds to . In other words, she wants to break the binding property of Pedersen commitments.That means Alice has to find
such that . Since and are already fixed, Alice is left to solve . In other words, she needs to compute . Since the discrete logarithm problem is supposed to be hard in , Alice will have a difficult time finding .Before committing to a value, Alice can also look for distinct pairs
such that , without regard for the specific values of and . This is also equivalent to computing a discrete logarithm in . As the Pedersen paper points out: given , where , then , and it is possible to compute the discrete logarithm of with respect to :
To summarize, breaking the binding property of Pedersen commitments is equivalent to solving the discrete log problem.
Intuition as to Why Pedersen Commitments are Hiding #
Suppose Alice has sent Bob a commitment
to a value . Bob wants to cheat by figuring out , or at least something about , from .Remember that
is sampled uniformly at random, and so every value of is equally likely to be chosen, which means every value of is equally likely. Since is a generator of , that means that “selects” every element of uniformly at random.If Bob is able to gain any advantage in guessing the value of
or from , then he necessarily gains an advantage in guessing or . However, is selected uniformly at random, so is a uniform random element of . You can’t gain information about a uniform random distribution.The Additive Property #
Given two commitments,
and , the product of and is . That is, the product of any two Pedersen commitments is a commitment to the sum of the committed values.This also allows for scalar multiplication through exponentiation;
.This additive property can be incredibly useful. It allows for a variety of operations to be performed on committed values before revealing them. Systems like Bulletproofs, for instance, exploit this property of the Pedersen scheme to commit to entire vectors of values at once, aggregating the commitments into a single value.
Useful Algorithms and Properties of Pedersen Commitments #
Proof of Knowledge of Secret #
Given a commitment
, Alice can demonstrate to Bob that she knows and without revealing either or . This is a useful protocol for protecting against the additive properties of Pedersen commitments being used maliciously. The protocol works as follows:
This works because:
This is secure because, in order to trick Bob, Alice needs to break the discrete log problem.
A straightforward application of the Fiat-Shamir transform can turn this into a non-interactive proof. If Alice selects
, where the output of has the same bit length as , she can proceed as though were selected uniformly at random. Bob can compute in the same way, and verify the rest of the proof from there.An Easy Proof of Equal Commitments #
Given two commitments to a secret
using the same set of generators, call them and , where , Alice can easily show that both and commit to the same value. The simplest way, given by Pedersen, is for Alice to reveal to Bob.This works because Bob can check that
Proof of Equal Commitments with Different Binding Generators #
Suppose Alice has
and , possibly with . Alice can prove to Bob that and commit to the same value.Alice starts by selecting random integers
, then computing and . She sends to Bob.Bob selects a random challenge value
and sends it to Alice.Alice computes
, , and in and sends to Bob.Bob then checks that
and . If the condition holds, Bob accepts the proof as valid.This works because:
and
In diagram form: #
Again, this can be made non-interactive through the use of a Fiat-Shamir transform. Alice can use
, again selecting a hash so that and have the same bit length.While this construction is more complicated, it has the benefit of allowing for commitments to be made when
.Proof of Squared Commitments #
We can use the equality of commitments proof above to commit to both a secret
and its square.Suppose Alice has a random
and corresponding commitment . Alice can select a random and computeNote that
, so is a commitment to in base .Once
has been generated, Alice can easily generate , provide both values to Bob, and use the equality proof above to demonstrate that commits to the square of the value committed to by .Security Considerations #
Generator Selection #
Suppose that Alice knows
and has a commitment .Then Alice can rewrite the commitment as
as . Let and . She can the fraudulently “open” the commitment by sending . This will appear as a valid opening to Bob, since:
If the discrete logarithm of
with respect to is known to Alice (or if an insecure group is chosen that makes computing the discrete log easy), the binding property is lost.This is why it is important to ensure that generators
and are selected independently. Ideally, and should be chosen independently from one another using a nothing-up-my-sleeve construction. For instance, and can be selected using an agreed-upon PRF and algorithm D.3.1 from the ANSI X9.62 standard (“Finding a Point on an Elliptic Curve”).Random Number Generator Issues #
In selecting the hiding value
, it is important that be truly uniform.Suppose there is an attack on the process used to generate
, and we have a set of commitments to secrets , not necessarily distinct. An attacker can then attack each and recover the corresponding values for . From this, the attacker can quickly identify repeated commitments to the same value. In cases where commitments are suspected of having a simple linear relationship (e.g. or for some known value of ), these relationships can be recovered as well by examining and .References #
- 登录 发表评论
- 5 次浏览
最新内容
- 10 hours ago
- 1 day 9 hours ago
- 1 day 9 hours ago
- 1 day 10 hours ago
- 2 days 5 hours ago
- 2 days 6 hours ago
- 2 days 6 hours ago
- 2 days 6 hours ago
- 2 days 6 hours ago
- 2 days 7 hours ago