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.
119
questions
1
vote
1answer
27 views
How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model?
For a PKE scheme $(Gen, Enc, Dec)$, the most 'obvious' idea is to commit to an encryption of a bit and in the reveal phase maybe send $r_g$, $r_e$ where $r_g$ is the randomness of $Gen$ and $r_e$ is ...
1
vote
0answers
25 views
Zero knowledge proof that ElGamal ciphertext encrypts the opening of Pedersen commitment
Given ElGamal ciphertext for a message $m$ with a random $r$ as $(c_1,c_2) \gets (g^r, g^my^r)$ for a public key $y$, and a Pedersen commitment $C \gets g^xh^r$, I have been able to create a proof ...
1
vote
1answer
37 views
Commitment based on authencticated encryption
Let $(E,D)$ be the encryption/decryption of an authenticated encryption scheme. Consider the following commitment scheme.
Generate a random key $k$. Commit to $m$ by sending $c=E_k(m)$.
Reveal $m$ by ...
0
votes
1answer
38 views
Orthogonal generators of a group in Lelantus protocol
In the Lelantus Paper, the authors mentionned this:
In our case, the commitment key ck specifies a prime-order group G and three orthogonal group generators $g, h_1$ and $h_2$.
G is mentioned in ...
0
votes
0answers
37 views
Prove knowledge of signature on committed value
Assume that a prover $P$, has previously obtained a signature $\sigma$ on a value $x$ from a verifier $V$. At a later stage, $P$ produces a Pedersen commitment $C$, to this value:
$C = g^x h^r$
I'm ...
1
vote
0answers
36 views
Zero-knowledge commitment verification
Assume everything takes place in a prime field.
Given the following:
$g$ - generator
$s$ - secret
$E(K, m)$ - a public-key encryption function using public key $K$ and plaintext $m$
The ...
1
vote
1answer
55 views
Which groups to use for Pedersen Commitments
I have been reading about Pedersen Commitments, and have come across some contradictory examples, which is confusing.
Just focusing on simple commitment of scalars (not EC points or vectors), then I ...
1
vote
0answers
44 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 ...
1
vote
1answer
78 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 ...
1
vote
1answer
112 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
88 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
65 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
73 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
78 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
94 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
37 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?
0
votes
0answers
26 views
Commitment HIDING ⇒ Real≈Ideal in Multiple Coin Tossing Security
I'm reading /Multiple_Coin_Tossing_Security/P2_Corrupted/ ("Information Security and Cryptography" Theorem 6.7.4 starting from page 325) and after description of Simulator for P2, the author continues ...
2
votes
1answer
72 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
88 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
36 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
180 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
152 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 ...
6
votes
0answers
156 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$-...
2
votes
1answer
79 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
52 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
85 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
71 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
177 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
42 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
116 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
57 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
96 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
661 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
120 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
262 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
50 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
59 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
235 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
103 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
84 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
108 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
77 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/...
5
votes
1answer
5k 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
66 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
128 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
52 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 ...
3
votes
0answers
88 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
275 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
187 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
520 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 $...
