# Tag Info

31

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 $\... 29 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. 15 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 ... 10 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 ... 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 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)\...

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

First, we'll recap the Pedersen-Commitment scheme and then we'll show that it is indeed additively homomorphic. For reference, the original paper by Pedersen is free by now. The commitment scheme Let $q,p\in\mathbb P$ be primes such that $p=r\cdot q+1$, for some $r\in\mathbb N$. Let $q$ be the order of a subgroup of $\mathbb Z_p^*$ called $G_q$. Let $g,h\... 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 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}(...

5

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

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 =... 5 is there a property that guarantees that$D_{k'}(c)$fails to verify/decrypt? No, there is not; all the security guarantees that authenticated encryption provides is of the form "if you don't know the keys, then it is difficult to..."; it says nothing about the difficulty of anything if you do know the keys. And, it turns out that, with GCM, you can ... 4 My preference would be to use hash for this purpose. Cons of using symmetric cipher include: Symmetric cipher keys are shorter than hashes (128-256 bits), where as hashes are longer (160-512 bits). When considering the length of symmetric cipher output, it is commonly short (like 128 bits). This length is often inadequate to protect against birthday attack ... 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 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 , which are the lecture notes corresponding to reference  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 This extension of the Schnorr protocol would appear to work:$P := aG + vH\operatorname{GenProof}(a, v)$:$x, y \leftarrow Z_qP' := xG + yHt := RandomOracle(P')$(alternatively, the verifier picks$t$after learning$P'$)$x' := x + ta, y' := y + tv$return$(P', x', y')\operatorname{Verify}(P, P', x', y')$:$t := RandomOracle(P')$accept ... 4 Is that required that$G$and$H$are two different generators of the same group? Yes. Pedersen commitment uses random public generators$G$and$H$of a suitable large group where the Discrete Logarithm is hard, thus$G$and$H$can safely be assumed distinct. Also, that condition implies no integer$w$such that$G=w\,H\$ can be found by anyone. These ...

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