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
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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$. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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
user avatar
  • 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
user avatar
  • 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 ...
user avatar
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}+...
user avatar
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 ...
user avatar
  • 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$, $\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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? ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 <...
user avatar
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,...
user avatar
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 : ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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: \{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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))$...
user avatar
  • 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 ...
user avatar