Stack Exchange Network

Stack Exchange network consists of 174 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
46 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
2
votes
1answer
63 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
73 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
70 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
49 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
46 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
181 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
47 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
65 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
37 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
52 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
193 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
111 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 ...
3
votes
1answer
231 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
174 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
65 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
138 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
99 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
32 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
61 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
47 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 ...
0
votes
0answers
28 views

Looking for a HINT. Trying to prove that a generalized Pedersen commitment is computationally binding [duplicate]

Let $G$ be a finite cyclic group of prime order $q$ with generators $g,h_1,h_2,...,h_n$ whose discrete logs with respect to one another is not known. A generalized Pedersen commitment to messages $m_1,...
2
votes
2answers
389 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
79 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
72 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
52 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
63 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?
5
votes
1answer
645 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
103 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
157 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
489 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, I will present the one I learned about): Public parameters - 2 primes $p,q$ ...
2
votes
1answer
249 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
92 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
341 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
262 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
202 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
58 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 ...
3
votes
1answer
292 views

Trouble understanding range proof of Greg Maxwell's Confidential Transaction

i've some trouble understanding the base of the range proof presented at https://elementsproject.org/elements/confidential-transactions/investigation.html I've understand the base of the Pedersen ...
4
votes
2answers
347 views

What type of commitment scheme is it?

I am having a task where I have to evaluate a commitment scheme. I checked already a few questions here, but they have not helped me :( I hope someone is able to help me out in that. What do I have? ...
4
votes
1answer
786 views

Range proof without knowing randomness

Party A has a ciphertext $c = (g^r, g^2 h^r)$, which is an encryption of the integer 2 under A's public key, $h$. The encryption scheme used is the additively homomorphic variant of El Gamal. This ...
0
votes
1answer
251 views

Comparing two committed values

Given two commitments on different values, Can a third party compare those two commitments to know which one is the higher value?
2
votes
1answer
129 views

Bit Commitment - from any One Way Permutations

In the Wiki Page on Commitments, it is given that a commitment scheme may be perfectly binding or perfectly concealing but not ...
0
votes
1answer
52 views

Commiting to a linear relation over a finite field

Suppose I have some finite field $k$. I am wondering if there exists a way to commit to a linear relation $a_1x_1 + a_2x_2 + \cdots + a_mx_m = b$ over $k$ , such that I can later reveal that a certain ...
1
vote
0answers
145 views

Why is one scheme “hiding” while the other one is OK?

I'm presented with these 2 following commitment schemes $Commit(x;r) = (c,k) $. This is presented as bad (not hiding) $Commit(x;r) = (H(x), x)$ So, not hiding means that attacker can deduce $x$ ...
8
votes
1answer
856 views

Why can't the commitment schemes have both information theoretic hiding and binding properties?

The commitment schemes like Pedersen's or Hash based, either have information theoretic hiding and computational binding or computational hiding and information theoretic binding. So can we ever get ...
0
votes
0answers
107 views

Easy example of commit scheme not binding

I'm told that the following commit scheme: $(c,k) = Commit(x;r) = (Enc_r(x),(x,r))$ Does not bind which means that the sender could produce $c,k,k'$ such that: $Open(c,k) \neq Open(c,k')$ I know ...
0
votes
1answer
264 views

Prove if it is a CCA secure Commitment

Assume we have a IND-CCA-secure PKC (Public-Key-Cryption) and we construct a commitment-scheme(commit, reveal) with that IND-CCA-secure PKC (so that commitment should be IND-CCA-secure too). But how ...
1
vote
1answer
119 views

Question on the remote coin flipping problem

I decided to ask the question here, because although the problem is mathematical, I'm interested in its application here. In the version i read in wikipedia, they suggested the following method for ...
-1
votes
1answer
726 views

Pedersen commitments and addition

For Confidential Transactions a Pedersen commitment is being used. The commitment preserves addition and the commutative property applies: $$C(\text{BF}_1, \text{data}_1) \oplus C(\text{BF}_2, \text{...