19

The answer you posted is actually correct (more or less, see below): have each participant commit to their random number $r_i$ by publishing, e.g., $\mathcal{H}(r_i)$ in the first round. And then in the second round, each participant opens the commitment by publishing $r_i$ and everyone checks that it matches the committed value by hashing it. The final ...


18

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.


17

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 $\...


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


11

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


11

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

The problem pointed out by JGWeissman on Bitcoin.SE is only an issue if the hash function lacks collision resistance. Admittedly, collision resistance is one of the strongest properties usually demanded of hash functions, and collision attacks have been found for some hash functions commonly used in the past, such as MD5, but still, any secure cryptographic ...


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


6

Say $m$ persons meet physically and want to draw a positive integer $x$ less than $n$. Each person $j$ secretly selects a positive integer $x_j$ less than $n$, writes it down on a piece of paper, and fold it to hide her choice. The $m$ folded pieces of paper are brought together then publicly unfolded, revealing the $x_j$. The outcome of the protocol is $x =...


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$ ...


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

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


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


4

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


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

Commitment functions should be at least hiding and binding, and in your case, you want non-malleable. Using a hash function as a commitment does require addition assumptions on the hash that are not covered by (second) pre-image and collision resistance for both non-malleability (as you point out) and hiding: the hash can be assumed to not reveal 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

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

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


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

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