37 votes
Accepted

What is a Pedersen commitment?

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 ...
fgrieu's user avatar
  • 134k
32 votes
Accepted

Why can't the commitment schemes have both information theoretic hiding and binding properties?

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 ...
Chris Peikert's user avatar
17 votes
Accepted

Overview of relations between cryptographic primitives?

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 ...
ckamath's user avatar
  • 5,083
13 votes
Accepted

Why is the Pedersen commitment perfectly hiding?

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$ ...
poncho's user avatar
  • 140k
13 votes
Accepted

How to reveal/prove some personal information later

Congratulations! You've just reinvented hash based commitments. The idea of 'publish a disguised value' and later 'reveal the value of that disguised value' is known (in cryptographical circles) as ...
poncho's user avatar
  • 140k
11 votes

Why can't the commitment schemes have both information theoretic hiding and binding properties?

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 ...
WeCanBeFriends's user avatar
10 votes

Why can't the commitment schemes have both information theoretic hiding and binding properties?

To be a little more formal, consider the notation provided by Iftach, where $S$ denotes the commitment sender and $R$ denotes the receiver. Assume a commitment scheme $(S,R)$ is statistically hiding. ...
Russell Pekala's user avatar
8 votes
Accepted

Using Pedersen commitment for a vector

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 ...
Geoffroy Couteau's user avatar
7 votes
Accepted

Pedersen commitments and addition

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 ...
SEJPM's user avatar
  • 45.5k
7 votes

Sigma protocol for AND-composition involving the same secret

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 ...
Berry Schoenmakers's user avatar
6 votes
Accepted

What are the pros and cons of Pedersen commitments vs hash-based commitments?

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 ...
dade's user avatar
  • 1,303
6 votes
Accepted

What is the reason of using Pedersen Commitment scheme over HMAC?

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 ...
Farid Hajji's user avatar
6 votes
Accepted

Commitment based on authencticated encryption

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 ...
poncho's user avatar
  • 140k
5 votes

Mutual verification of shared secret

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 ...
Yehuda Lindell's user avatar
5 votes
Accepted

Prove that shares can reveal a seceret key. in a secret sharing scheme

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 ...
poncho's user avatar
  • 140k
5 votes

What is the reason of using Pedersen Commitment scheme over HMAC?

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 ...
Changyu Dong's user avatar
  • 4,118
5 votes
Accepted

Disjunctive zero knowledge proof of equality of committed values

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'$ ...
Berry Schoenmakers's user avatar
5 votes
Accepted

Zero knowledge proof for opening of Pedersen commit and discrete logarithm

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 ...
poncho's user avatar
  • 140k
5 votes

Division of two Elliptic curve points in KZG polynomial commitment scheme!

In this lecture, they use multiplicative notation for the pairing groups instead of additive notation. Thus, division is well-defined. Division is just the inverse of the group operation. The choice ...
Wilson's user avatar
  • 920
4 votes

Mutual verification of shared secret

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, ...
Vadym Fedyukovych's user avatar
4 votes
Accepted

Number generation for Fujisaki-Okamoto commitment scheme parameters

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)...
poncho's user avatar
  • 140k
4 votes
Accepted

Question on the remote coin flipping problem

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 (...
poncho's user avatar
  • 140k
4 votes
Accepted

Homomorphism with subtraction for Pedersen Commitment

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 ...
Changyu Dong's user avatar
  • 4,118
4 votes
Accepted

Are deterministic adversaries as powerful as probabilistic adversaries?

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 ...
Shan Chen's user avatar
  • 2,695
4 votes

What does "constant rate" mean in universal composable commitment scheme?

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)$. ...
Yehuda Lindell's user avatar
4 votes
Accepted

Prove I know a value $v$ in a Pedersen Commitment without revealing it

This extension of the Schnorr protocol would appear to work: $P := aG + vH$ $\operatorname{GenProof}(a, v)$: $x, y \leftarrow Z_q$ $P' := xG + yH$ $t := RandomOracle(P')$ (alternatively, the ...
poncho's user avatar
  • 140k
4 votes
Accepted

Pedersen commitment in elliptic curves

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 ...
fgrieu's user avatar
  • 134k
4 votes
Accepted

What is wrong with encryption-based / hash-based commitment schemes?

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. ...
Maeher's user avatar
  • 6,560
4 votes

Commitment to a polynomial

My solution is based on Pedersen commitments; in this scheme, we work in a prime-sized ($p$) subfield of some group, perhaps $\mathbb{Z}_{kp+1}$, so some prime $kp+1$; where both $p$ and $kp+1$ are ...
poncho's user avatar
  • 140k

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