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
2
votes
0answers
60 views

Commitment to a degree of a polynomial

Is there a way to commit to a degree of a polynomial without committing to every single one of its coefficients? The problem I am trying to solve is to prove that two polynomials are the same in a ...
2
votes
1answer
330 views

Zero knowledge proof for opening of Pedersen commit and discrete logarithm

I am looking for a proof of knowledge as such: $PK\{ (x,r) : C = g^xh^r \land V = g^x\}$ Where $C, V, g$ and $h$ are public information and $x$ and $r$ is known only to the prover. I.e. I have a ...
3
votes
1answer
393 views

Commitment to a polynomial

$A(x) \bmod B(x) = C(x)$ and $A(x) \bmod D(x) = E(x)$: A dealer knows $A(x)$ polynomial, which is a secret. He distributes $C(x)$ and $E(x)$ privately to $X$ and $Y$, respectively. $B(x)$ and $D(x)$ ...
2
votes
1answer
297 views

Simple commitment scheme using secure hash function

Can I create a simple commitment scheme using a secure hash function? If so, is concatenation with a random secret enough to preserve hiding? (i.e. $C = H( random\_string || message)$) Thank you
1
vote
0answers
72 views

How to sign comitted group elements?

I'm actually searching some particular primitive compatible with Groth Sahai commitment. I would like to know a signature scheme (on group elements), such that there exists an algorithm $\mathtt{...
2
votes
1answer
121 views

Constant size commitment to a bivariate polynomial

In this paper by Kate et al, a constant size polynomial commitment scheme is described. The commitment scheme assumes a public reference string: \begin{align*} \Big\{ \{ g^{ \tau^i }, g^{ \alpha \...
1
vote
1answer
298 views

What is wrong with encryption-based / hash-based commitment schemes?

In the slides to my information security class it is stated without explanation that a encryption-based commitment scheme defined as follows is broken: Commit: P outputs c = Enck(m) Reveal: P sends k ...
1
vote
0answers
152 views

Efficient protocols for set membership proofs with private sets

I found the paper on Efficient Protocols for Set Membership and Range Proofs in which efficient protocols for the following problem are discussed: Given a commitment $C_v$ to a value $v$ we want show ...
0
votes
1answer
42 views

How to determine r' in pederson commitment?

Can someone help me with that question? Assuming that someone knows $log_g(h)$ so that he can calculate any message $m'$ for commitment $c$, how to determine $r'$ in?
2
votes
1answer
81 views

Are Fujisaki commitments binding if the factorization of the group is known?

If I understand correctly, a Fujisaki commitment is as follows: $g^m \cdot h^r $ mod $n$, where $m$ is a message, $r$ is a random number, there exists $a$ such that $h^a = g$, and $n$ is an RSA ...
3
votes
1answer
203 views

Verifiable Encryption of a Pedersen Commitment

Can the Verifiable Encryption of a Discrete Logarithm scheme of the paper https://www.shoup.net/papers/verenc.pdf (page 19) be used to verify that a ciphertext encrypts the same value committed in a ...
1
vote
0answers
42 views

Gennaro multi trapdoor commitment scheme

In the Scheme Based on the SDH Assumption (page 11 of the paper https://link.springer.com/content/pdf/10.1007%2F978-3-540-28628-8_14.pdf), how does the commitment get revealed with the master trapdoor ...
3
votes
1answer
190 views

What information does $g^x$ reveal about $x$?

Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$. Consider the following standard protocol for ...
2
votes
1answer
233 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 ...
7
votes
0answers
389 views

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

Vector commitment allows one 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 $...
2
votes
1answer
119 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
67 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
112 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 \...
2
votes
2answers
83 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
328 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
55 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
293 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
75 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
142 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
979 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
154 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
560 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
57 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
60 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
475 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
124 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
90 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
225 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
109 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/...
14
votes
1answer
11k views

What is a Pedersen commitment?

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
77 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
186 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
59 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 ...
5
votes
0answers
137 views

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

I am trying to understand how to apply a multi-trapdoor commitment 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
348 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
259 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
799 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 $...
4
votes
2answers
1k 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
64 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
119 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
206 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
296 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
64 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
133 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
211 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 ...