Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
65 views

Pedersen commitments in bulletproofs

In Bulletproofs range proof, Pedersen commitments look like $C=aG+bH$ If I need to proof several values' range proof and keep G as constant, do I need to change H everytime? I have found it doesn't ...
5
votes
0answers
51 views

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $i$-...
0
votes
0answers
39 views

Honest Verifier Zero-Knowledge Game for Sigma Protocols

I am looking for how an adversary to special HVZK would work. In Boneh and Shoup's book (BonehShoup) they have Attack Game 20.4 for special cHVZK. Here, the adversary produces a pair (x,y) (witness ...
0
votes
1answer
44 views

Selectively opening only a few commitments

I have k messages $m_1,m_2...m_k$ and I want to commit to all of them but open only a few of them -- as asked by Bob. Each message is of $n$ bits. Show how one can commit to all the $k$ messages and ...
1
vote
0answers
59 views

Prove that two commitments are commitments to the same value

Let $x$ be the secret value, $(n,a,b,c)$ a public key, $(n_C, g, h)$ the commitment public key. Furthermore let $r, r_C$ be two random numbers. Define $C = g^x h^{r_C} \bmod n_C$, $C_x = a^x b^r \...
1
vote
2answers
61 views

Zero Knowledge for Low Entropy Witness

For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$. Now, let us say I have a dlog statement in the form of $y = g^w$. Theory says I could use a ...
2
votes
1answer
122 views

Disjunctive zero knowledge proof of equality of committed values

I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols). ...
1
vote
1answer
40 views

Can 2 bit commitment protocols be secure when sent together with the same bit

Suppose I have 2 bit commitment schemes, C1 and C2 which are computationally hiding.Suppose I commit the same bit using both and send them to an adversary who knows that the same bit was committed. Is ...
2
votes
1answer
60 views

trapdoor commitment from lattice-based assumptions?

I'm wondering that is there any equivocal commitment scheme (i.e., trapdoor commitment) can be constructed from lattice-based assumptions? I know there are a lot of commitment schemes from lattices as ...
1
vote
0answers
43 views

Simple reduction of commitments to one way functions

I am looking for an explicit and simple reduction of commitments to one way functions. I don't care about the number of rounds, only simplicity. I am aware of the simple reductions you can find in ...
0
votes
1answer
59 views

How to change the following commitment scheme to Pedersen commitment?

In my question here Zero knowledge set membership protocol The suggested solution allows a prover to choose a commitment $C$. Then, A trusted third party ($T$) can validate if $C$ is valid or not. ...
4
votes
3answers
514 views

Pedersen commitment in elliptic curves

I try to understand Pedersen commitment in elliptic curves over finite fields. I could use some clarification. Let's say we have two generators $G$ and $H$. Is that required that $G$ and $H$ are ...
2
votes
2answers
103 views

How do I create a cryptographic signature and commitment scheme with accountable evidence?

This is a weird one... I am looking for a method which I don't even know how to call, nor whether it actually exists! Given a pair of asymmetric keys $s_{k}/P_{k}$ and defining $Sig_{k} \dagger B_{i}$...
1
vote
1answer
114 views

Zero knowledge set membership protocol

I read that paper Efficient Protocols for Set Membership and Range Proofs of Camenisch et. al that describes the zero knowledge range proof. The paper applications looks interesting like if you want ...
0
votes
1answer
49 views

Commitment which allows negative proof

I need to create a commitment to a value X such that I can provide either proof that the commitment is to X or proof that the commitment is not to some other given value Y != X. If I use a simple ...
0
votes
0answers
53 views

Prove I know a value v in a set s.t. K = H(v) [duplicate]

Is it possible to prove that I know a value v in a finite set, such that the hash of the value v is K. Where v is private and K is public
3
votes
2answers
154 views

Prove I know a value $v$ in a Pedersen Commitment without revealing it

Given a Pedersen Commitment: $P = aG + vH$ Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to. Is there a way to prove I know $v$ ...
1
vote
1answer
84 views

How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
3
votes
1answer
75 views

What does “constant rate” mean in universal composable commitment scheme?

I'm wondering what does the "constant rate" mean in universal composable commitment scheme? I have known the rate of a commitment scheme is message length divided by the communication complexity of ...
0
votes
2answers
77 views

Commitment scheme: hiding property

Given two commitment schemes $Com_1, Com_2$ (both have the hiding property), I'd like to prove $Com_1(m) || Com_2(m)$ is also hiding. I built these hybrids and want to show $H_0 =_c H_1 =_c H_2$. \...
2
votes
1answer
57 views

How many bits are needed to commit one bit non-interactively in the standard model?

I'm wondering the state-of-art result about how many bits are needed to commit a single-bit non-interactively? I noticed in the paper of Naor's bit commitment: http://www.wisdom.weizmann.ac.il/~naor/...
3
votes
1answer
2k views

What is a Pedersen commitment? [closed]

I couldn't find any answer providing a high-level overview on what Pedersen commitments are or what they are used for.
2
votes
1answer
55 views

Commitment in two party protocols

I have been reading Fast Secure Two-Party ECDSA Signing by Lindell, and I see that in key generating and signing (pages 9-10, especially visible from Figure 1), only the first party performs a ...
2
votes
1answer
85 views

Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$?

For Pedersen commitments of the form $C = x\times G + r\times H$, what is the worst thing I can do if I already know $H$ such that $H = a\times G$ ? For standard curves, there are specifications for ...
1
vote
0answers
46 views

Why isn't a range proof calculated using size?

For example a Pedersen commitment for an elliptic curve of maximum $2^{64}$, requires every number between $0 \to 2^{64}$ to be checked. Why do range proofs, in the case of a Pedersen commitment, not ...
2
votes
0answers
65 views

Multilinear trapdoor commitments secure against concurrent man-in-the-middle attacks

I am trying to understand how to apply a multi-trapdoor commitments described by Gennaro and what makes them secure against a concurrent MiM attack. There are two ways to construct a multi-trapdoor ...
5
votes
4answers
243 views

Are deterministic adversaries as powerful as probabilistic adversaries?

SOURCE states the following in the proof of Theorem 2: Without loss of generality, I will assume that A is deterministic. If A is randomized, we can determinize it by fixing a sequence of coins ...
1
vote
1answer
140 views

Homomorphism with subtraction for Pedersen Commitment

I was trying to use Pedersen's homomorphic property for some privacy preserving mechanism, and to the best of my knowledge $Com(x1,r1)\cdot Com(x2,r2)^{-1} = g^{x1-x2}h^{r1-r2}$ That is, if we ...
4
votes
2answers
344 views

Sigma protocol for AND-composition involving the same secret

Say we have two public cyclic groups $G_1$, $G_2$ of corresponding prime orders $p_1$, $p_2$, and known generators $g_1$, $g_2$. Say $g_3$ is also a generator of $G_2$. For publicly known $C_1$ and $...
2
votes
1answer
292 views

What is the reason of using Pedersen Commitment scheme over HMAC?

I want to implement non-interactive Bit Commitment scheme for messages of arbitrary length. And I am curious, what is the reason of using Pedersen Commitment scheme over Salted Hash (in other words ...
0
votes
1answer
60 views

Enforcing Randomness in Malicious Setting

I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the ...
1
vote
0answers
93 views

ZK proof of committed value

I'm looking for a scheme that a prover can commit to a value $d$, via a commitment $C$, while also provide ZK-proof that this value $d$, together with a public key $e$, are RSA pairs. (i.e private and ...
6
votes
1answer
156 views

In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end?

To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]: Alice sends Bob the commitment $c = commit(x)$ Bob sends Alice ...
2
votes
1answer
150 views

Is this a UC-secure commitment scheme in the ROM?

To prove UC-security (universally composable security) of a commitment scheme, we must show that a commitment scheme is extractable and equivocal. That is, we must construct a simulator that is able ...
1
vote
1answer
43 views

What is the concrete communication complexity of Commitment schemes?

Say you want to commit an $n$-bit plaintext, $x \leftarrow ^ r \{0,1\}^n$. What is the concrete communication cost, in terms of $n$, of the following: Data sent by verifier to initialize (applies in ...
1
vote
0answers
73 views

Are all commitment schemes pseudo-random functions?

I am interested in understanding whether or not we can use commitment schemes that are both hiding and binding as pseudorandom functions. My reasoning is that if a commitment is hiding, then an ...
1
vote
1answer
69 views

Randomized public-key encryption as binding commitment / “collision-resistance”?

I am looking to use randomized public-key encryption in a context where it should also serve as a sort of "binding commitment". That is, I want to encrypt a value $x$ with some randomness $rnd$ under ...
3
votes
2answers
479 views

Using Pedersen commitment for a vector

I'm reading Bootle/Groth. I'm trying to understand how they are committing to a vector using Pedersen commitment. Here's my understanding of Pedersen commitment in the context of this paper: We have ...
0
votes
1answer
108 views

Is it possible to obtain the value committed to by Pedersen commitment given the blinding key?

I know that the purpose of the blinding key is to make it difficult to obtain the hidden value. More formally: the Pedersen commitment is comprised of the blinding key $\alpha$, two generators $H$ and ...
2
votes
1answer
75 views

Commitment for bid

Alice and Bob are sitting on an online casino table which exposes the following game: the table randomly generates a number R and piblishes this number. The player which "bids" the highest number ...
0
votes
1answer
56 views

Is the commitment $g^u\cdot x$ with $x\in\langle g\rangle$ and $u \gets \mathbb{Z}_n$ hiding and binding?

Consider the following commitment scheme, where $x$ belongs to $\langle g\rangle$ and $u$ is uniformly chosen from $\mathbb{Z}_n$: $$\mathsf{commit}(u,x) = g^u\cdot x$$ Is it binding and hiding?
-2
votes
1answer
71 views

What is the general purpose of concealment algorithms introduced in…? [closed]

What is the general purpose of concealment algorithms introduced in https://eprint.iacr.org/2003/050.pdf?
6
votes
1answer
910 views

What are the pros and cons of Pedersen commitments vs hash-based commitments?

Obviously, it's possible to create a commitment scheme comm(r, S) by using a hash function H and computing H(S||r). This scheme is secure under the assumption that H is collision and preimage ...
1
vote
1answer
106 views

Zero-knowledge voting with hidden weights

Assume a voting with delegates, where each delegate's vote $v_i \in \{-1,1\}$ has a certain weight $w_i$ depending on the number of people who elected the delegate. Is there a way to calculate the ...
3
votes
1answer
172 views

Prove that shares can reveal a seceret key. in a secret sharing scheme

I am trying to build a cryptographic system that has several components and ran into a problem with a secret sharing scheme. Let $v$ be a value we are interested committing to. I generate a ...
4
votes
1answer
734 views

Why is the Pedersen commitment perfectly hiding?

I learned today about the Pedersen commitment scheme. A quick reminder (I know there are some variants of this scheme, so I will present the one I learned about): Public parameters - 2 primes $p,q$...
2
votes
1answer
308 views

Cheating in a commitment scheme based on discrete log

Question: Consider the following commitment scheme: Public parameters: large primes $q$ and $p$ such that $p = 2\cdot q + 1$, and two generators $g, g'$ of a $q$-order subgroup of $\mathbb Z_p^*$. ...
0
votes
1answer
105 views

Why are they called “commitment”, “challenge”, and “response”?

I'm reading Proof Systems for General Statements about Discrete Logarithms, and I think I'll have a better understanding of the process if I can understand where the terms come from. They give a basic ...
10
votes
1answer
398 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
2
votes
1answer
302 views

Help with a zero knowledge proof

Can you please help with the following? Let $C_1= g^r h_1^x h_2^y$, $C_2 = a^z$ and $C_3=(g^{r'}h_1^x h_2^y)^z$. Basically, $C_1$ is a commitment on the values $x, y$ and $C_3$ is another, blinded ...