33 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 ...
user avatar
  • 122k
29 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 ...
user avatar
14 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$ ...
user avatar
  • 131k
10 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 ...
user avatar
9 votes
Accepted

How do I generate a number for a lottery and later proves its existence

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 (...
user avatar
  • 37.7k
8 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. Assume a commitment scheme $(S,R)$ is statistically hiding. This means that a computationally unbounded $R$ is unable to get any ...
user avatar
8 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 ...
user avatar
  • 4,463
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 ...
user avatar
  • 44.6k
7 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 ...
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 ...
user avatar
  • 131k
5 votes

Can I prove set membership and uniqueness without revealing the element?

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. ...
user avatar
  • 35.3k
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 ...
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 ...
user avatar
  • 131k
5 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 ...
user avatar
  • 1,293
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 ...
user avatar
  • 4,008
5 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 ...
user avatar
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'$ ...
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 ...
user avatar
  • 131k
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 (...
user avatar
  • 131k
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)...
user avatar
  • 131k
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, ...
user avatar
4 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 ...
user avatar
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 ...
user avatar
  • 4,008
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 ...
user avatar
  • 2,625
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)$. ...
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 ...
user avatar
  • 131k
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 ...
user avatar
  • 122k
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. ...
user avatar
  • 6,411
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 ...
user avatar
  • 131k

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