Questions tagged [commitments]
A commitment scheme is a protocol where one party commits themselves to a secret value without revealing it. At a later point, the value can be revealed.
230
questions
4
votes
0
answers
64
views
The rigorous proof in the commitment based on CRHF
I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
- 135
3
votes
1
answer
94
views
Division of two Elliptic curve points in KZG polynomial commitment scheme!
I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help.
To verify, the verifier should ...
- 151
1
vote
1
answer
130
views
How to deal with Pedersen commitment message or randomness overflow?
For EC Pedersen commitment: The two generators are G and H. Two messages and randomness are $m_1$, $m_2$, $r_1$, $r_2$,
so the two Pedersen commitments are $Gm_1+Hr_1$ and $Gm_2+Hr_2$.
When adding ...
- 129
2
votes
1
answer
65
views
Implementing a Merkle tree using a 128 bit hash function?
I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a ...
- 139
2
votes
1
answer
55
views
Is a Pedersen commitment still secure when r is either 0 or 1?
Specifically if we know the $r$ takes values from the set $\{0,1\}$and $c=g^r*h^m$ does the hiding property still hold? I think I already managed to prove that the binding property holds due to the ...
- 23
2
votes
1
answer
87
views
Hiding sum of vectors. Hardness based on CVP
This is the problem
Let $\mathcal{L}$ be a lattice and $v_1,v_2,\ldots,v_n\notin\mathcal{L}$. Given the values $a_1,\ldots,a_n$ such that
$$a_1=\lfloor v_1\rceil+v_2+\ldots+v_n$$
$$a_2=v_1+\lfloor v_2\...
- 147
1
vote
1
answer
60
views
Looking for efficient implementations for Pedersen commitment
Hi I am currently developing a research project, but it seems that my implementation of Pedersen commitment is not efficient. I wonder if there are any efficient implementation of Pedersen ...
- 129
2
votes
1
answer
33
views
Can we pad witness of bulletproof and dory to be exponential size?
Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? ...
- 51
5
votes
1
answer
721
views
How to reveal/prove some personal information later
I want to put some personal info like name and email in e.g. some program that I release to the public but I don't want anybody be able to retrieve those personal info and only when I want they can ...
- 53
2
votes
1
answer
88
views
What is the difference between those two KZG Polynomial Commitment Schemes?
In short what are the differences (pros & cons) between multiplying by powers of Tau
(from this lecture https://youtu.be/tAdLHQVW)
and raising to powers of Tau
(from this lecture https://youtu.be/...
- 126
2
votes
1
answer
69
views
Pedersen commitments equivalence
Is there a zero-knowledge proof that proves that two Pedersen commitments commit the same value?
- 567
2
votes
1
answer
51
views
How to multiply the Pedersen Commitment of two numbers?
Given two numbers $x_1$, $x_2$ and their respective binding numbers, $b_1$ and $b_2$, let's take their Pedersen Commitment to be $C(x_n, b_n)$ $\forall n=1,2$.
What is $C(x_1 * x_2, b_1 * b_2)$?
- 123
2
votes
1
answer
166
views
In the Kate/KZG Polynomial Commitment Scheme, in which Polynomial Ring should the polynomial to be committed be?
In the Kate Polynomial Commitment scheme, a commitment of a Polynomial $f(x)$ at $x=s$ is defined as
$Com_f = f(s).G$ where $G$ is the generator of the Elliptic Curve of prime order which is used.
So ...
- 2,290
1
vote
1
answer
60
views
What is a practical application of evaluating at a point in the Kate Polynomial Commitment Scheme?
I understand how the Kate Polynomial Commitment Scheme Evaluation Proof works however, I don't understand what is the purpose of it?
In general, in a commitment scheme, Peggy commits to message & ...
- 2,290
3
votes
1
answer
92
views
Question about the soundness of using a pairing map in the Kate Polynomial Commitment Scheme
I am looking at the paper on Kate Polynomial Commitments.
On Page 7, VerifyEval, the verifier checks the following to verify commitment.
$e(\mathcal C, g) \stackrel {?}{=} e(w_i, \frac {g(\alpha)}{g(i)...
- 2,290
5
votes
2
answers
105
views
Coin flipping without commitments or random oracles
It's well known that two parties, Alice and Bob, can flip a fair coin using commitments.
Alice picks a random number $a \in \mathbb{Z}_q$ and computes $c_a = Com(a, r_a)$ where $r_a \xleftarrow{R} \...
- 163
3
votes
1
answer
72
views
Why is Lagrange interpolation required in Batch Opening case of KZG/Kate PCS?
From here - Batch Opening of KZG PCS
One can prove multiple evaluations $(\phi(e_i) = y_i)_{i\in I}$,for arbitrary points $e_i$ using a constant-sized KZG batch proof, $\pi_I = g^{q_I(\tau)}$, where
\...
- 2,290
0
votes
1
answer
36
views
Unable to find the Appendices of the Kate Polynomial Commitments paper
I am looking at the paper on Kate Polynomial Commitments.
The paper refers to Appendix A & Appendix B but it's not available with the document. Does anyone know where I find the full paper with ...
- 2,290
2
votes
2
answers
124
views
Proving same value in ciphertext and Pedersen commitment Using Sigma Zero Knowledge
Let we have 2 generator $G$ and $H$ in any elliptic curve.
A prover creates a ciphertext with Homomorphic ElGamal, $(r_1G,\;mG + r_1P)$ such that $r_1$ is random and $P$ is public key of the prover.
...
- 85
1
vote
0
answers
32
views
Comparison between commit value
Assume I have two commitment values $C_1=v_1G+r_1H$ and $C_2=v_2G+r_2H$ where $v_1$, $v_2$ secret values and $r_1$, $r_2$ blinding factors.
Then I give this commitment value with blinding factor to a ...
- 85
0
votes
0
answers
117
views
Difference between sigma protocol, Schnorr protocol, Pedersen commitment
Could you explain the difference between sigma protocol, Schorr protocol with examples. What is the advantage of using commit-and-prove zero knowledge proof over general zero knowledge proof?
- 169
3
votes
2
answers
435
views
How does taking the difference between commitments verifies that the messages are correct?
I have read that perdersen commitment can be used to hide the messages such as transactions by participants. The verifier will just have to make sure that the difference of the commitments is zero. ...
- 225
3
votes
0
answers
118
views
Use of term "Commitment"
As an amateur, my first encounter with commitments has been in the form of an hash of the committed value, then I have learnt about seeding the hash as blinding technique. Going on I have discovered ...
- 680
0
votes
0
answers
73
views
Are pedersen hashes of small inputs safe?
I understand that the end result of a Pedersen Hash (like this one) is a point in an Elliptic Curve.
In the example implementation mentioned above, the input $M$ is split into chunks of 200 bits (the ...
- 45
0
votes
0
answers
65
views
Commit and prove
Is it possible to commit to a value $s$ and then prove in NIZK way that $g = q^s$ ?
Both $g,q$ are known. Thank you.
- 1
0
votes
0
answers
48
views
zero-knowledge proof for correct multiplication of multiple share
Suppose we have the following relation, how can we prove in zero-knowledge that we know $a_i, b_i, m, m_p$?
$$ R: (C_1 = a_1G_1+a_2G_2, C_2=b_1G_1+b_2G_2+mH, C_3=(a_1b_1)G_1 + (a_2b_2)G_2 + m_pH) $$
...
- 11
0
votes
0
answers
40
views
Is the following attack on a DES-based commitment scheme valid?
I've encountered the following question while practising for an upcoming exam in Cryptography and would like to know if I'm on the right track:
The following is a suggestion for a DES-based ...
- 373
0
votes
1
answer
63
views
Deterministic Commitment Schemes
Are there any deterministic commitment schemes? What are their security properties, if so? Most ones I see are randomized.
1
vote
1
answer
71
views
How to complete this proof of statistically indistinguishable distributions?
Given that:
$$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n)$$
where $SD$ stands for statistical distance, $r$ is random uniform in $\{0,1\}^n$, $s$ is random uniform in $S \...
- 373
0
votes
1
answer
39
views
Vector commitments using only symmetric cryptography
A vector commitment scheme is a scheme (dough!) that allows a prover to prove that $v_i$ is a component of a vector $v$ without revealing any other information about $v$ . (So the prover commits to $v$...
- 243
0
votes
0
answers
11
views
Algorithms to secretly distribute elements from a known set / with a known global characteristic
I am assuming a set of $n$ players and a central "dealer" $C$ through which all communication is routed. The state I want to end up with is that each player $i$ has a secret $s_i$ unknown to ...
- 1
1
vote
0
answers
28
views
Does a salt by a trusted party remove the need for collision resistance for a binding commitment?
Say a Human is operating their trusted computer, Alice, and Human wants to hand copy a collision resistant commitment, with a security factor of 128 from Bob on to paper. Naturally we want the ...
- 488
1
vote
2
answers
153
views
Is there a scheme to enforce a random seed without leaking the seed?
End-to-end encrypted web services (like cryptpad) often include a 128-bit seed in the hash part of the URL (that is not sent to the server), to derive both an identifier that is sent to the server, ...
- 113
5
votes
2
answers
639
views
Is there anything like "Proof of Computation"?
Is there any cryptographic method for Proof Of Computation ?
If i am running my program on untrusted hardware (remote server), after some time i want to verify the ...
- 51
1
vote
0
answers
60
views
What issues does the following Distributed Shamir Secret Sharing scheme have?
What (obvious) security issues does the following "onion" Distributed Shamir Secret Sharing scheme on a blockchain for the purpose of e-voting have?
The blockchain in this context, is an ...
- 71
1
vote
0
answers
59
views
Compute a hash function given commitment to some secret element
Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
- 79
1
vote
1
answer
214
views
Zero-knowledge proof that the exponents of a Pedersen commitment are not zero
Given a value $v = g^ah^b$, with $a,b$ secret, I was wondering whether there was a way to prove in zero knowledge that neither exponent is zero. In other words, given $v$ and $g,h \in \mathbb{G}$, I ...
- 23
0
votes
1
answer
73
views
Proof of computationally binding correct?
I have defined the following commitment scheme and would like to prove that it is statistically hiding and computationally binding, but I'm not sure if my proof is accurate:
For $h$, a collision ...
- 373
1
vote
1
answer
250
views
Non-committing authenticated encryption schemes vs committing authenticated encryption schemes
I'm told that TLS 1.3 supports only non-committing authenticated encryption schemes. What is a non-committing authenticated encryption scheme? What is the difference between committing and non-...
- 137
1
vote
2
answers
147
views
Is there a winning strategy based on this coin-flipping protocol?
Given the coin flipping protocol:
A chooses $a \in_R \{0,1\}$ and computes $commit(a,r)$. She sends $commit(a,r)$ to B.
B chooses $b \in_R \{0,1\}$ and sends $b$ to A.
A sends $open(a,r)$ and B ...
- 373
1
vote
1
answer
116
views
A security issue of a Bit commitment scheme constructed by Naor in 1990
In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow:
Bob commits to bit $b_0\in_R\{0,1\}$:
Step 1: Alice chooses a random $r\in R$ and sends ...
- 336
1
vote
0
answers
164
views
Proving the range of a blinded value in a Pedersen commitment in zero knowledge
A prover has the following value:
$$C = (h^ag^x)^b$$
and he needs to prove in zero knowledge to a verifier that $x < t$, for some public threshold $t$.
The verifier knows $h$, $g$, $C$, and $t$. ...
- 23
1
vote
1
answer
67
views
Create an or-proof for a given list of elements with public input
Let $g\in G$ and $h\in H$ be two group generators. Given a list L of m group elements, where $L=(L_1,...,L_m)$, a prover wants to convince a public verifier (namely, a verifier who only has public ...
- 79
0
votes
2
answers
163
views
How to select $r$ in Pedersen commitment scheme?
I'm implementing Pedersen commitment scheme in order to enhance entropy of a pre-image of a hash. I'm using secp256k1 for my curve parameters.
I am following naming conventions from here:
What is a ...
- 125
1
vote
2
answers
183
views
What's the Apostrophe or single quote of a variable means in cryptography?
What's the meaning of Apostrophe over a variable in the context conversations of verification?
Reference number: https://people.eecs.berkeley.edu/~jfc/'mender/IEEESP02.pdf
- 205
2
votes
1
answer
56
views
Why randomness space must be significantly larger than the commitment space |R|>>|C| in order to generate a commitment string?
Why randomness space must be significantly larger than the commitment space |R|>|C|? the picture is from https://youtu.be/IkNZWJFcfcU?t=236
- 205
2
votes
1
answer
620
views
Range proof for elements in Vector Pedersen commitment
If I construct a vector pedersen commitment $c = a_1G_1 + a_2G_2 + ... + a_nG_n$ with an arbitrary scalar vector $(a_1, a_2, ..., a_n)$ and group elements $(G_1, G_2, ..., G_n)$, is it possible to ...
- 123
1
vote
0
answers
160
views
Can we transform LWE symmetric encryption scheme into a commitment scheme?
In the LWE symmetric encryption scheme, a ciphertext encrypting a message $\mu \in \{0,1\}$ under the secret key $\mathbf{s} \in \mathbb{Z}_q^n$ is $(\mathbf{a}, \mathbf{b}=\mathbf{a} \cdot \mathbf{s}+...
- 11
1
vote
2
answers
222
views
Does concept "Collision Resistance" and "Binding Commitment" in cryptography similar?
I found there are two perplexing and related concept "Collision Resistance" and "Computation Binding in Commitment" in cryptography.
I found the wikipedia's explanation is ...
- 205
1
vote
1
answer
87
views
Proof of knowledge of constant discrete log in the bilinear setting
Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\...
- 190