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.
198
questions
1
vote
1
answer
48
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
49
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 ...
- 189
1
vote
1
answer
188
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-...
- 37
0
votes
0
answers
31
views
How is there a $\frac{1}{poly(n)}$ bias in a multiple-round coin tossing protocol with commitment?
On p.2, Example 1.1 (in this paper), there is a description of a coin tossing protocol with bias 1/4. In the paragraph below the example, they note that for a protocol with $r$ rounds (assume for the ...
- 189
1
vote
2
answers
137
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 ...
- 189
1
vote
1
answer
54
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 ...
- 186
0
votes
0
answers
37
views
Oblivious Commitment vs Normal Commitment used in Identification Scheme
How does oblivious commitment remove the active security? How is it useful over a normal commitment scheme.
1
vote
0
answers
39
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
58
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 ...
- 21
0
votes
2
answers
74
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 ...
- 115
1
vote
2
answers
73
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
44
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
182
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
83
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
104
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
55
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$, $\...
- 188
2
votes
1
answer
86
views
Commit the output of verifiable random functions
The problem setting is as follows. Suppose there exists a public input $x$ and the prover evaluates $y \gets VRF_{sk}(x)$, but the prover does not wish to reveal the output $y$. My question is would ...
- 43
2
votes
2
answers
259
views
Verifying a prediction of the future
I'm trying to find an algorithm to prove that someone knows some short secret message (for example some prediction of the future) before finally revealing it.
For example:
Alice knows what temperature ...
- 23
1
vote
1
answer
53
views
Is there a blind signature that can sign on a commitment?
For the blind signature that can sign on a commitment, I mean finally, the user can get a signed commitment, rather than a signed message inside the commitment. It means the verification also takes a ...
- 707
0
votes
0
answers
30
views
How can we prove that the advantage for this hide game for any adversary is equal 0?
Here is the Scheme:
Here is the HIDE game:
Here is my idea but I am not quite sure. I would appreciate some input.
We want to bring advantage = 0 for all adversaries. We can show that advantage = 0 ...
- 21
0
votes
2
answers
68
views
Can two parties with a common secret jointy issue a commitment?
Let's say parties A and B have a common secret $k$. Is there a protocol where both the parties jointly release a commitment to $k$ so that later on, neither A or B can deny what the common secret was?
...
- 81
0
votes
0
answers
123
views
Faking Pedersen Commitment
Today, I found a website for Pedersen commitment scheme; however, the generators g and h are not independent and therefore a ...
- 149
0
votes
1
answer
75
views
Different setup for Pedersen Commitment
I have read many question on this website and understood the Pedersen commitment until I came across with this page.
This page, it computes $\mathcal h= g^s \bmod p$ where $s$ is secret, instead of ...
- 197
0
votes
0
answers
99
views
Are there batched vector/polynomial commitment proofs with sublinear proof size for Verkle Trees?
High level goal: a Verkle tree (Merkle tree using algebraic vector commitments at each level rather than hashes) with depth d where I can prove the existence of <...
1
vote
0
answers
102
views
Why the Kate Commitment and the Algebraic Group Model is used a lot in zk-SNARKs proving system since 2019？
I am engaged in the research of zk-SNARKs. After I read some papers about zk-SNARKs, I realize the Kate Commitment and the Algebraic Group Model is used a lot since 2019. They are used in Sonic, Plonk,...
- 11
0
votes
0
answers
59
views
How such so called Merkle pre image are computed?
I’ve just encountered the following source code which is used as an authentication mechanism where the bytes32 leaf is the hashed action to authenticate :
...
- 175
0
votes
1
answer
80
views
What does it mean for g and h to be indendent in pedersen commitments?
I'm looking at a research paper about the insecurity of a specific (wrong) usage of Pedersen commitments.
First, I'll go through the steps of Pedersen commitments, so that it can be shown if I have a ...
4
votes
0
answers
72
views
MuSig: could the rogue key attack be mitigated by using commitments instead of key transformations?
Background
MuSig is an extension of/derivation from Schnorr signatures using cyclic groups on elliptic curves. In the original paper, the authors point out that naive multi-Schnorr is vulnerable to a ...
- 141
1
vote
0
answers
37
views
Efficient proof for Cartesian product
I am trying to find some efficient zero-knowledge arguments that could prove the vector ${\bf v}$ is the Cartesian product of two vectors ${\bf x}$ and ${\bf y}$. I know there are efficient inner ...
- 43
2
votes
1
answer
105
views
Pedersen Commitment and Computational Zero Knowledge
I am curious at how "good" is computational zero knowledge?
Consider Pedersen Commitment $z = g^x h^y$. There exists perfect ZK protocol (based on Schnorr's) to prove that one knows the ...
- 75
2
votes
0
answers
35
views
Difference between a key value commitment and authenticated dictionary
I was wondering about the difference between an authenticated dictionary and a key value commitment scheme like KVac.
Are they the same thing or they have different model or definitions?
Thanks
- 105
1
vote
1
answer
95
views
Gennaro & Goldfeder Key Generation Protocol
As I am going through the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018, I am stumbled by the key generation protocol (Sect. 4.1, p.10):
In Phase ...
- 197
1
vote
1
answer
96
views
Commitment scheme for a possible unordered growing collection of elements
Merkle trees can be used for vector commitment scheme. In particular given two sequences S, S' with the same elements in the same order the merkle root for S will be the same as the one for S'. What ...
- 11
1
vote
1
answer
66
views
Zero-knowledge proof of committed value
I am considering the following questions and would appreciate any help.
Problem formulation:
Suppose Alice holds a secret value $x$ and there is a public Boolean predicate function $\texttt{Pred}$ ...
- 43
1
vote
1
answer
43
views
Coin tosses in the context of commitment schemes
I was reading the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018 and I encountered this portion (Sect. 2.4, p.6):
This excerpt leaves me slightly ...
- 197
0
votes
2
answers
143
views
How can I prove "single-use authorization" from multiple parties without revealing identity?
I've been trying to create a distributed authorization protocol where identities are not revealed. Let me explain with an example.
Let's assume we have 4 actors, Alice, Bob, Charlie, and Dan. Alice is ...
0
votes
1
answer
71
views
Why must s be kept secret in pedersen commitments?
I was reading up on Pedersen commitment over at this website: https://asecuritysite.com/encryption/ped, where they calculate $h=g^s \bmod p$, and they say that $s$ must be a secret.
I wonder why this ...
- 3
3
votes
2
answers
311
views
Finding an elliptic curve of specific order
I wish to use elliptic curves for cryptographic operations like commitments etc. I see that most standard elliptic curves like $\operatorname{secp256k1, sect571r1}$ have a certain specific and fixed ...
- 139
0
votes
2
answers
126
views
Solution to Discrete Log as a Commitment
Is the solution to a discrete logarithm a reasonable commitment scheme?
By my analysis, the following scheme is a reasonable commitment scheme:
Let $p$ and $q$ be large primes such that $q∣(p−1)$, let ...
1
vote
0
answers
52
views
Does there exist a provably correct and recipient hiding encryption scheme?
I am looking for an encryption scheme $E$ and a commitment scheme $C$ which allow
encrypting the message $m$ for the public key $y$ as $e = E_y(m)$, so that the ciphertext $e$ does not reveal any ...
- 243
2
votes
1
answer
110
views
Proving statistically hiding for a simple commitment scheme in the ROM
It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting
$\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{...
- 23
2
votes
1
answer
79
views
Dishonest verifier running a concurrent zero-knowledge protocol
Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a ...
- 23
3
votes
1
answer
155
views
Commitment schemes for arbitrarily large integers
My question is about commitment schemes for arbitrarily large integers. One scheme I know uses groups of unknown order (RSA or class group) and depends on the strong-RSA assumption.
You chose a random ...
- 188
3
votes
1
answer
121
views
Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols
In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where
The prover sends a commitment to the ...
- 227
1
vote
0
answers
236
views
Zero-knowledge proof of knowledge of a plaintext in exponential ElGamal
Consider the exponential ElGamal cryptosystem over some group $G$ with generator $g$. Let $m$ be a plaintext, and $(R, C) = (g^r, g^m \cdot y^r)$ an encryption thereof for some public key $y$.
Assume ...
- 531
2
votes
0
answers
68
views
How does the rejection sampling lemma work in the proof of HVZK?
In this protocol,
Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$?
Q2: How does the rejection sampling lemma work?
refer to ...
- 389
0
votes
1
answer
150
views
Difference between a Polynomial Opening & a Polynomial Commitment
Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two ...
- 135
1
vote
0
answers
53
views
Hash as encryption used by Monero
Monero uses a Pedersen commitment $yG + bH$ to obfuscate the value of a transaction, where $b$ is the value and $y$ is the blinding factor.
For the receiver to know both variables, it uses a Diffie-...
- 515
0
votes
0
answers
58
views
Why is the proof on the commitment correct?
In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
- 389
2
votes
1
answer
112
views
All fully homomorphic encryptions (FHE) are converted into homomorphic commitments?
The GSW one of the FHE scheme is widely used as a homomorphic commitment scheme to build lattice based ABE, homomorphic signatures and NIZK and so on. But I cannot find other FHE schemes to be ...
- 129