As of May 31, 2023, we have updated our Code of Conduct.

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.

Filter by
Sorted by
Tagged with
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 ...
constantine's user avatar
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 ...
tesoke's user avatar
  • 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 ...
js wang's user avatar
  • 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 ...
Lorenzo's user avatar
  • 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 ...
GeorgeT's user avatar
  • 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\...
Cristian Baeza's user avatar
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 ...
js wang's user avatar
  • 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? ...
Walker's user avatar
  • 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 ...
Maloo's user avatar
  • 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/...
ShAr's user avatar
  • 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?
Fiono's user avatar
  • 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)$?
Jim's user avatar
  • 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 ...
user93353's user avatar
  • 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 & ...
user93353's user avatar
  • 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)...
user93353's user avatar
  • 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} \...
Ari's user avatar
  • 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 \...
user93353's user avatar
  • 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 ...
user93353's user avatar
  • 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. ...
midmotor's user avatar
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 ...
midmotor's user avatar
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?
user1850484's user avatar
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. ...
xenon's user avatar
  • 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 ...
baro77's user avatar
  • 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 ...
popeye's user avatar
  • 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.
Kydon's user avatar
  • 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) $$ ...
Parsa G's user avatar
  • 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 ...
Anon's user avatar
  • 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.
basketball9's user avatar
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 \...
Anon's user avatar
  • 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$...
miraunpajaro's user avatar
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 ...
4t4r4x's user avatar
  • 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 ...
Nic's user avatar
  • 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, ...
lukasl's user avatar
  • 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 ...
fin's user avatar
  • 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 ...
desertkun's user avatar
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)...
Doron's user avatar
  • 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 ...
John N.'s user avatar
  • 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 ...
Anon's user avatar
  • 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-...
Willi's user avatar
  • 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 ...
Anon's user avatar
  • 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 ...
ming alex's user avatar
  • 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$. ...
John N.'s user avatar
  • 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 ...
Doron's user avatar
  • 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 ...
Ilia Sidorenko's user avatar
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
Sheldon's user avatar
  • 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
Sheldon's user avatar
  • 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 ...
Shigeyuki Azuchi's user avatar
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}+...
maon_mea's user avatar
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 ...
Sheldon's user avatar
  • 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$, $\...
Mathdropout's user avatar

1
2 3 4 5