跳转到主要内容

热门内容

今日:


总体:


最近浏览:


Chinese, Simplified

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-
q

subgroups of
Zp

, but we will describe it in more generic terms, as it is applicable to any group
G

where the discrete logarithm problem is believed to be hard (such as elliptic curve groups).

Definition #

Start with a finite group
G

of prime order
q

, where
q

is suitably large. For instance, we can use an order-
q

subgroup the multiplicative group
Zp

where
q

divides
p

, or an elliptic curve group or subgroup. Select two generators
g,h

of
G

such that
logg(h)

is not known. The parameters of the commitment scheme are
(G,q,g,h)

.

To generate a commitment
cG

to a secret integer
s

, where
0<s<q

, randomly sample
t$Zq

and compute:


c=Cg,h(s,t)=gsht

(When
g,h

are clear from context, we can simply write
C(s,t)

.)

To open the commitment, simply reveal
s

and
t

.

Intuition as to Why Pedersen Commitments are Binding #

Suppose Alice has sent Bob a commitment
c=C(s,t)

to a value
s

. She now wants to cheat by sending Bob an opening for
c

that corresponds to
ss

. In other words, she wants to break the binding property of Pedersen commitments.

That means Alice has to find
t

such that
gsht=c

. Since
gs

and
c

are already fixed, Alice is left to solve
ht=cgs

. In other words, she needs to compute
t=logh(cgs)

. Since the discrete logarithm problem is supposed to be hard in
G

, Alice will have a difficult time finding
t

.

Before committing to a value, Alice can also look for distinct pairs
(s,t),(s,t)

such that
C(s,t)=C(s,t)

, without regard for the specific values of
s

and
s

. This is also equivalent to computing a discrete logarithm in
G

. As the Pedersen paper points out: given
C(s,t)=C(s,t)

, where
ss

, then
tt

, and it is possible to compute the discrete logarithm of
h

with respect to
g

:


logg(h)=sstt(modq)

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
c=C(s,t)

to a value
s

. Bob wants to cheat by figuring out
s

, or at least something about
s

, from
c

.

Remember that
t

is sampled uniformly at random, and so every value of
t

is equally likely to be chosen, which means every value of
ht

is equally likely. Since
h

is a generator of
G

, that means that
t

“selects” every element of
G

uniformly at random.

If Bob is able to gain any advantage in guessing the value of
s

or
gs

from
c

, then he necessarily gains an advantage in guessing
t

or
ht

. However,
t

is selected uniformly at random, so
ht

is a uniform random element of
G

. You can’t gain information about a uniform random distribution.

The Additive Property #

Given two commitments,
c1=C(s1,t2)=gs1ht1

and
c2=C(s2,t2)=gs2ht2

, the product of
c1

and
c2

is
gs1+s2ht1+t2=C(s1+s2,t1+t2)

. 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;
C(x,y)n=C(nx,ny)

.

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
A=Cg,h(x,y)=gxhy

, Alice can demonstrate to Bob that she knows
x

and
y

without revealing either
x

or
y

. This is a useful protocol for protecting against the additive properties of Pedersen commitments being used maliciously. The protocol works as follows:


AliceBobt1,t2$ZqT=gt1ht2Tk$Zqks1=xk+t1,s2=yk+t2s1,s2gs1hs2=?AkT

This works because:


gs1hs2=gxk+t1hyk+t2=gxkhykgt1ht2=(gxhy)kT=AkT

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
k=Hash(ghAT)

, where the output of
Hash()

has the same bit length as
q

, she can proceed as though
k

were selected uniformly at random. Bob can compute
k

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
s

using the same set of generators, call them
c1=C(s,t1)

and
c2=C(s,t2)

, where
t2t1

, Alice can easily show that both
c1

and
c2

commit to the same value. The simplest way, given by Pedersen, is for Alice to reveal
r=t1t2(modq)

to Bob.

This works because Bob can check that


c1c21=gsht1gsht2=gssht1t2=ht1t2=hr

Proof of Equal Commitments with Different Binding Generators #

Suppose Alice has
c1=Cg1,h(s,t1)

and
c2=Cg2,h(s,t2)

, possibly with
g1g2

. Alice can prove to Bob that
c1

and
c2

commit to the same value.

Alice starts by selecting random integers
r1,r2,r3$Zq

, then computing
c3=Cg1,h(r1,r2)=g1r1hr2

and
c4=Cg2,h(r1,r3)=g2r1hr3

. She sends
c3,c4

to Bob.

Bob selects a random challenge value
k$Zq

and sends it to Alice.

Alice computes
z1=ks+r1

,
z2=kt1+r2

, and
z3=kt2+r3

in
Zq

and sends
z1,z2,z3

to Bob.

Bob then checks that
c3c1k=Cg1,h(z1,z2)

and
c4c2k=Cg2,h(z1,z3)

. If the condition holds, Bob accepts the proof as valid.

This works because:


c3c1k=(g1r1hr2)(g1sht1)k=g1r1hr2g1kshkt1=g1ks+r1hkt1+r2=g1z1hz2=Cg1,h(z1,z2)

and


c4c2k=(g2r1hr3)(g2sht2)k=g2r1hr3g2kshkt2=g2ks+r1hkt2+r3=g2z1hz3=Cg2,h(z1,z3)

In diagram form: #


AliceBobr1,r2,r3$Zqc3=Cg1,h(r1,r2),c4=Cg2,h(r1,r3)c3,c4k$Zqkz1=ks+r1z2=kt1+r2z3=kt2+r3z1,z2,z3c3c1k=?C(z1,z2)c4c2k=?C(z1,z3)

Again, this can be made non-interactive through the use of a Fiat-Shamir transform. Alice can use
k=Hash(g1g2hc1c2c3c4)

, again selecting a hash so that
k

and
q

have the same bit length.

While this construction is more complicated, it has the benefit of allowing for commitments to be made when
g1g2

.

Proof of Squared Commitments #

We can use the equality of commitments proof above to commit to both a secret
s

and its square.

Suppose Alice has a random
t1

and corresponding commitment
c1=Cg,h(s,t1)=gsht1

. Alice can select a random
t2

and compute
c2=Cc1,h(s,t2)=(c1)sht2

Note that
c2=Cc1,h(s,t2)=(c1)sht2=(gsht1)sht2=gs2hst1+t2=Cg,h(s2,st1+t2)

, so
c2

is a commitment to
s2

in base
g

.

Once
c1

has been generated, Alice can easily generate
c2

, provide both values to Bob, and use the equality proof above to demonstrate that
c2

commits to the square of the value committed to by
c1

.

Security Considerations #

Generator Selection #

Suppose that Alice knows
l=logg(h)

and has a commitment
c=C(s,t)=gsht

.

Then Alice can rewrite the commitment as
c=gsht

as
c=gs(gl)t=gsgtl=gs+tl

. Let
s=s+l

and
t=t1

. She can the fraudulently “open” the commitment
c

by sending
(s,t)

. This will appear as a valid opening to Bob, since:


gsht=gs+1(gl)t1=gs+lgl(t1)=gs+lgtll=gs+tl=gs+tl=c

If the discrete logarithm of
h

with respect to
g

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
g

and
h

are selected independently. Ideally,
g

and
h

should be chosen independently from one another using a nothing-up-my-sleeve construction. For instance,
g

and
h

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
t$Zq

, it is important that
t

be truly uniform.

Suppose there is an attack on the process used to generate
t

, and we have a set of commitments
c1,c2,,cn

to secrets
s1,s2,,sn

, not necessarily distinct. An attacker can then attack each
hti

and recover the corresponding values for
gsi

. 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.
si=ksj

or
si=sj+k

for some known value of
k

), these relationships can be recovered as well by examining
gsigk

and
(gsi)k

.

References #

本文地址
最后修改
星期二, 一月 28, 2025 - 15:59
Article