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.
246
questions
0
votes
0
answers
15
views
[error reducing techinique in lattice based commitment]
I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
- 327
2
votes
2
answers
90
views
Is it possible to check pedersen commitment is of postive or negative number without knowing the original value
I generated a Pedersen commitment for a given account balance (say, 10) and stored it in the ledger. Now, when I debit 15 tokens from the same account, I first retrieve the Pedersen commitment of 10 ...
- 21
0
votes
0
answers
30
views
How can I determine if the result of subtracting two Pedersen commitments is negative or positive?
I'm using Pedersen commitments to maintain the account balance in the ledger.
Assume that when I create the account, I record the Pedersen commitment of 0 in a ledger (here, the blinding factor and ...
- 21
1
vote
1
answer
82
views
Proof of non membership in a Verkle Tree?
According to the author of the original paper[1],
Verkle Trees basically let you save space (typically bandwidth, which
can be expensive) by replacing a secure hash with a vector commitment
scheme, ...
- 111
0
votes
0
answers
31
views
Is the NIZK constructed based on Pedersen commitment transparent?
It is well-known that, in the setup phase of Pedersen commitment, it is necessary to generate $g,h\in G$. Then a user can compute $c = g^vh^r$ to commit the value $v$.
Is a trusted center needed to ...
- 63
2
votes
0
answers
126
views
Equality of ElGamal plaintext & Pedersen commitment message
Let's imagine two entities: Bob and Alice. Bob's public key is $B = bG$. Alice's public key is $A = aG$.
Alice encrypts her number $n$ with Bob's public key so Bob could decrypt it ($n$ is small ...
- 33
1
vote
1
answer
66
views
Where & how is the 2nd group used in the KZG Commitment Scheme in case the 2 groups are not the same?
This is about the KZG Polynomial Commitment Scheme
In Section 2, it's written
We use the notation $e : \mathbb G \times \mathbb G \mapsto \mathbb G_T$ to denote a symmetric (type 1) bilinear pairing....
- 2,169
0
votes
1
answer
82
views
Given pedersen commitments of some elements, how to prove that the sum of only one subset of these elements is equal to the given element θ？
Assume that Prover have $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$ where $V_{a_i}=G \cdot a_i + H \cdot r_{a_i}$) of $n$ elements $a_1,a_2,\cdots,a_n$. The Prover have another element $...
- 11
1
vote
1
answer
52
views
Interpolating polynomial discrete log
This is taken from page 16 of Stacking Sigmas
Essentially, let $0<t<\ell$ be integer values smaller than a certain prime modulus $q$. We have a set $\mathcal{X}$ with $|\mathcal{X}|=\ell-t+1$, $[...
- 187
1
vote
1
answer
67
views
Is it possible to batch ZKP proofs from different polynomials but same point?
According to the ZKP MOOC lecture by Dan Boneh, it is possible to batch proofs from different polynomials and different points into a single group element:
Nonetheless, I haven't been able to find ...
- 140
0
votes
1
answer
43
views
Public commitments to subsets
Problem
Suppose there is an entity with some users. The users are split into subsets (determined by the entity) and the entity needs to create public commitments to these subsets such that only a user ...
- 5
1
vote
0
answers
182
views
Quantum-safe algorithm for hiding cryptocurrency transaction amount [closed]
I have a decentralized coin system that I am trying to develop.
Each coin can be split up into 1,000,000 units.
I've been looking for a quantum-safe and practical (efficient) algorithm to send ...
- 91
0
votes
1
answer
111
views
Verification in Bulletproof commitment scheme
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 44 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf), the ...
- 181
0
votes
0
answers
42
views
Can homomorphic property of a commitment scheme be harmful?
Homomorphic properties turn out to be very useful, e.g., for achieving secure multiparty
computation.
As a concrete example, homomorphic commitments can be used as a building block for secure ...
- 363
1
vote
1
answer
34
views
Hiding and binding property of Goldwasser-Micali like bit commitment scheme
Let $N=pq$ be an RSA modulus, that is, $p$ and $q$ are large, distinct primes.
Let $J_{N}=\{y\in\mathbb{Z}^{*}_{N}:(\frac{y}{N})_{J}=1\}$ denote the set of all integers in $\mathbb{Z}^{*}_{N}$ with ...
- 363
0
votes
1
answer
35
views
implementing pedersen commtiment using lib sodium
Hi I want to implement pedersen commitment ontop of lib sodium
Below is what I am trying to do:
comm1: m1G+r1H
comm2: m2G+r2H
comm3: (m1+m2)G+(r1+r2)H
comm4: comm1+comm2
and comm3 should equals ...
- 327
2
votes
1
answer
96
views
How to find second subgroup for ECC Pairing?
Pretty new to ECC Pairings. I am trying to understand KZG Commitments from multiple sources. I found this blog beginner friendly and easier to understand. However, I'm stuck at ECC Pairings and having ...
- 31
0
votes
2
answers
103
views
Hiding property of Elgamal-like bit commitment
An Elgamal-like bit commitment scheme:
Let $\langle g \rangle$ be a group of order $n$, where $n$ is a large prime.
Let $h\in_{R}\langle g \rangle\setminus\{1\}$ denotes a random group element such ...
- 363
2
votes
0
answers
63
views
Poly-commitment based on Bulletproofs
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 41 and 42 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf),...
- 181
5
votes
1
answer
105
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 ...
- 147
3
votes
1
answer
121
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 ...
- 181
1
vote
1
answer
145
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 ...
- 327
2
votes
1
answer
152
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
65
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
95
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\...
- 187
1
vote
1
answer
115
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 ...
- 327
2
votes
1
answer
47
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? ...
- 61
5
votes
1
answer
753
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
240
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/...
- 152
2
votes
1
answer
136
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
59
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
296
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,169
1
vote
1
answer
149
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,169
3
votes
1
answer
103
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,169
5
votes
2
answers
117
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
110
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,169
0
votes
1
answer
37
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,169
2
votes
2
answers
167
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.
...
- 75
0
votes
0
answers
188
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?
- 179
3
votes
2
answers
491
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
152
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 ...
- 710
1
vote
1
answer
120
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 ...
- 65
0
votes
0
answers
72
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
42
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 ...
- 383
1
vote
1
answer
85
views
Deterministic Commitment Schemes
Are there any deterministic commitment schemes? What are their security properties, if so? Most ones I see are randomized.
- 11
1
vote
1
answer
98
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 \...
- 383
0
votes
1
answer
47
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
1
vote
0
answers
30
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 ...
- 498
1
vote
2
answers
170
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
848
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