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.

0
votes
0answers
10 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 ...
0
votes
0answers
32 views

Construction of a bit commitment scheme com'(b) from a given bit commitment scheme com(b) and give a ZK proof

You are given a bit commitment scheme $\text{Com(b)}$. Construct another bit commitment scheme $\text{Com'(b)}$ with the following property: Alice commits independently to two values $a$ and $b$, ...
1
vote
0answers
40 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
49 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
98 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
34 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
51 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
37 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
43 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
459 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
94 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
81 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
47 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
50 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
142 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
77 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
74 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
68 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
51 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/...
1
vote
1answer
834 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
53 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
76 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
40 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
59 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
216 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
128 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
291 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
232 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
59 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
80 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
148 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
122 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
36 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
69 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
57 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
446 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
93 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
74 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
54 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
70 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
790 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
105 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
167 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 ...
3
votes
1answer
648 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
294 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
99 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
376 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
290 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 ...
2
votes
1answer
231 views

Why is the El Gamal commitment scheme information theoretically binding?

I am a bit stuck on the following claim: The ElGamal commitment scheme is information theoretically binding As far as I understand, an adversary $A$ would win the binding game if it is able to ...
0
votes
0answers
66 views

How to authenticate indivisual value after applying homomorphic encryption using Paillier homomorphic

Assuming I have three parties in a system: Alice, Bob, and a Server. Alice and Bob needs to aggregate some messages $m1$ for Alice, and $m2$ for Bob. And send the aggregate $m1+m2$ to the Server. I ...