39
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 ...
- 138k
34
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 ...
- 5,773
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 ...
- 5,133
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$ ...
- 145k
13
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 ...
- 1,303
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 ...
- 145k
12
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. ...
- 121
9
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 ...
- 19.1k
8
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
...
- 45.7k
8
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 ...
- 1,323
7
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 ...
- 84
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 ...
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 ...
- 145k
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 ...
- 145k
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 ...
- 4,148
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'$ ...
5
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. ...
- 6,613
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 ...
- 145k
5
votes
Accepted
MuSig: could the rogue key attack be mitigated by using commitments instead of key transformations?
Yes, the rogue key attack can be prevented by committing to a public key before exchanging the keys. But this requires that you never use a public key with more than one group of signers. If you use ...
- 271
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 ...
- 929
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 (...
- 145k
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)...
- 145k
4
votes
Accepted
Why is the El Gamal commitment scheme information theoretically binding?
How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r'$ that with $g^r = g^{r'}$, or am I overseeing something?
Yes, you're probably thinking the ...
- 12.6k
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 ...
- 4,148
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 ...
- 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)$. ...
- 27.6k
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 ...
- 145k
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 ...
- 138k
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 ...
- 145k
4
votes
Accepted
Sigma protocol with Pedersen commitment and Hash function
This is no longer a secure commitment. Note that there should not be any way to efficiently verify if a given commitment value $c$ is to a message $m$. However, once you derive the randomness in this ...
- 27.6k
Only top scored, non community-wiki answers of a minimum length are eligible