24

what Pedersen commitments are In a commitment scheme such as Pedersen the committer (or sender) decides (or is given) a secret message $m$ taken in some public message space with at least two elements; decides a random secret $r$; produces from that $m$ and $r$ a commitment $c=\mathcal C(m,r)$ by applying some public method (the commitment algorithm $\...


22

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.


16

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..." Actually, that's not true, and the "information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value....


14

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$. In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but ...


12

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct? Because there are lots of different $r, s$ pairs that satisify the solution. In particular, for ...


9

You could use HMAC for this. HMAC is available in pretty much every crypto library out there. The process would work like this. Randomly pick A and C. For simplicity, let's assume they are strings (of any length). Compute $B=HMAC(A,C)$. Publish $B$. Once someone guesses $A$, you publish $C$. Anyone can then verify that $B=HMAC(A,C)$. As long as a good hash ...


8

You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent ...


7

Another way to look at it informally is this; If it is perfectly hiding, then you cannot tell what made the final value. It could equally be any combination. If it is perfectly binding, then there is only one combination that produces the final value, essentially binding the final value to that one combination. Let's say we are talking about addition, and ...


6

As you noticed correctly, a hash function is kind-of computationally binding if you assume collision resistance. However, it is impossible to achieve perfect hiding property for hash functions, due to the potential loss of information. Perfect hiding means, that a computationally unbound Alice COULD decomit any value: I.e. Pedersen commitments $c = g^xh^r$ ...


6

To be a little more formal, consider the notation provided by Iftach. Assume a commitment scheme $(S,R)$ is statistically hiding. This means that a computationally unbounded $R$ is unable to get any information about $m$ from the commitment $c$. Since the process of computing a commitment is known to both parties, this means that there must exist $(m,d)\...


6

Yes, you got the scheme essentially right - except that the group cannot be $\mathbb{Z}_p^*$, as the latter does not have prime order. It can however be many other things - like the multiplicative subgroup of squares over $\mathbb{Z}_p^*$, or an elliptic curve. Let us simply consider the scheme as you described it, over some group $\mathbb{G}$ of prime order ...


5

This cannot be done. It is provably impossible. In order to explain this in technical terms, what you are looking for is a FAIR protocol to compute equality of long random strings (I added the latter since it adds a constraint and so in theory could make it easier). In any case, if I had such a protocol, then I could toss a fair unbiased coin. Here is the ...


5

Proving uniqueness You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order. Details follow. Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public. Pick a large prime $p$ and a group ...


5

The obvious way to do this is to do a secret derivation on committed values, and have the dealer show that derived committed value is the same as the value he originally committed to. For this, I'll assume that the secret sharing scheme is over the prime field $GF(q)$. The dealer publishes the commitment $P$, and remembers the commitment value $v$. And, ...


5

The hash-based commitment scheme you are sketching is in fact not secure under collision resistance and preimage resistance of the hash function. For hiding, you need to assume that the hash function you are using behaves like a random oracle (i.e., whenever queried on a new value it returns a uniformly random value from the output domain of the hash ...


5

In this case, there probably is no difference. The Pedersen Commitment scheme is often used in cryptographic protocols because: It allows zero-knowledge proof to prove some properties of the committed value. It is perfectly hiding, which can be important in proving the security of the protocol. Hash based commitment schemes do not have the above two ...


5

It can be done with two Schnorr proofs, which can be interactive or noninteractive. This is a simple way of proving knowledge of a discrete log; in the noninteractive version, to prove the knowledge of $x$ s.t. $a = g^x$ (assuming a public hash function $H$), the prover picks a random value $r$, computes $t = g^r$, $c = H(t)$, and then publishes $t$ and $s =...


4

Yes, $p$, $g$ and $h$ are system parameters. $g$ and $h$ only need to generate large prime subgroups of $\mathbb{F}_p^{*}$, and the equation $p=2g+1$ is not required. (In fact, if I understand what you mean correctly, it does not always suffice as $-1/2$ has the same order as $2$) It is important that $g$ and $h$ not be related by a known equation of the ...


4

One could split both secrets into smaller parts, commit to parts and "gradually" open that commitments to each other, so that no party is better than (ahead of the other) one such part. For example, let secret be a big number split into bits. With an additively homomorphic bit commitment scheme, the other party could verify that bit commitments correspond ...


4

If you can select the distinct secret primes $p$ and $q$ such that $(p-1)/2$ and $(q-1)/2$ are also prime, then it becomes easy. For a random value $r$, $g = r^2$ will have order precisely $(p-1)(q-1)/4 \approx n/4$ unless $r, r-1$ or $r+1$ happens to not be relatively prime to $n$ (which, if you select $r$ randomly in the range $[2, n-2]$, happens with ...


4

Is the definition of 'box' i gave wrong? What is the correct definition? It is incorrect. The analogous description of a commitment scheme would be that it is a box that contains only one choice (for example, "heads" or "tails"), Alice can place either, and Bob can't tell (by looking at the box) which is in it. Later, Alice can open the box; Bob can then ...


4

In many applications, especially in zero-knowledge proofs, we need commitment schemes that are additively homomorphic. Pedersen commitment schemes do have this property, hash-based commitment schemes don't. If we do Pedersen commitments on elliptic curves for performance reasons, where we fix two points $P$ and $Q$ on a curve, we can define: $\text{commit}(...


4

Proving this statement for groups $G_1, G_2$ of different order is a bit tricky. If the groups are of the same order, one can simply use EQ-composition (see [4], which are the lecture notes corresponding to reference [3] above). For groups of different prime orders $p_1, p_2$, a simple $\Sigma$-protocol runs as follows. Let $n=p_1 p_2$. Prover sends ...


4

You used the wrong modulus when verifying the result. Note that although the computation is modulo $p$, i.e. you compute $g^xh^r \bmod p$, the exponents $x,r$ are in $Z_q$. And so the operations among the exponents are modulo $q$. That means, after the homomorphic operation, you get a commitment of $x_1-x_2 \bmod q$, not $x_1-x_2 \bmod p$ .


4

Following fkraiem's answer, I would share my thoughts. Generally speaking, we do not know if randomness helps, i.e., P=BPP is an open question. So probabilistic-polynomial-time (PPT) adversaries may not equal to deterministic ones. However, it seems that cryptography always (correct me if I am wrong) focuses on advantages (or something similar) related to ...


4

Constant rate in general means that the overhead from a non-secure method is constant. So, in a simple way, if I am committing to an $\ell$-bit message, then the size of the commitment is $O(\ell)$. In some cases, however, one also allows an additive factor that is independent of the message size. Thus, for example, it could be that to commit to a message of ...


4

What's special about your question is the "global" use of generators $g,h$ for all the commitments. This allows for a nice shortcut, leading to some potential savings. Asking for a proof that $x=x'$ for given $C=g^x h^y$ and $C'=g^{x'} h^{y'}$ only makes sense if we actually demand a proof of knowledge of all four exponents as well. Now, the interesting ...


4

The second construction is trivially not hiding. It is easy to verify a guess $m'$ just by recomputing $H(m')$ and comparing the result with the commitment. The first construction is a bit trickier. If it is a CPA secure encryption scheme, then it is certainly hiding. However it may not be binding. It is easy to construct secure encryption schemes, where ...


Only top voted, non community-wiki answers of a minimum length are eligible