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.
158
questions
0
votes
1answer
68 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
76 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?
7
votes
1answer
2k 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
140 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
234 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
1k 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
428 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
163 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 ...
14
votes
1answer
741 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
326 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
462 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
100 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 ...
2
votes
1answer
460 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
559 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?
...
3
votes
1answer
1k 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
364 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
246 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
59 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
177 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$ ...
16
votes
3answers
2k 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
148 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
375 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
395 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
2k 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{...
4
votes
0answers
120 views
Committing to a secret shared value
Suppose I run a multiparty protocol. At the output stage, I have the function output in a secret shared manner among all parties.
Now I want all the parties to commit to their value of the secret ...
1
vote
0answers
109 views
Clarification on the state of the art of qubit commitment
What is the current state of research on quibit commitment?
It seems that the answer is not 2001 but it seems to me that a lot of these pdf are referring to a old protocols of quantum bit commitment ...
2
votes
1answer
912 views
How to prove secret value in Pedersen commitment is equal to secret value in Fujisaki commitment?
We have Pedersen commitment C to the secret value x, and Fujisake commitment C' to the secret value x. How can we make a zero-knowledge proof of equality for x value in the commitments?
5
votes
1answer
186 views
Coin flipping with limited communication between participants
Alice and Bob want to play a coin flipping game. Alice wins if the coin flips head.
They choose to trust a independent third party that generates a random beacon (such as NIST). There is no ...
0
votes
1answer
442 views
How to prove knowledge of discrete logarithm in a product?
Definitions
Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit ...
5
votes
0answers
745 views
How to prove that a commitment hides the decryption of an ElGamal ciphertext?
I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question.
For this question I need to prove that I've committed to a ...
3
votes
1answer
453 views
Number generation for Fujisaki-Okamoto commitment scheme parameters
I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "...
5
votes
1answer
222 views
Is authenticated encryption basically a lockable box?
I recently used a custom construction as a commitment scheme, which was taken from the standard picture you give people while explaining commitment schemes.
Basically commitment schemes can be ...
1
vote
0answers
67 views
Commitment scheme to share money
I have such problem: party $X$ has an amount of money $M$, which it needs to share with $n$ other parties. Every week the amount of money is different.
Let say not, that I am a party A, which is one ...
10
votes
6answers
1k views
Mutual verification of shared secret
Is it possible to develop a scheme where two parties, unsure if they have the same secret, can verify that the other does or does not share the same secret, without one party being able to cheat and ...
1
vote
1answer
160 views
Bilinear map + commitment
Let $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ be yclic group of the same order and $ e: \mathbb{G}_1 \times \mathbb{G}_2\rightarrow \mathbb{G}_T$, such that $u\in \mathbb{G}_1, g \in \mathbb{G}_2, a,b,...
0
votes
2answers
183 views
Length of prime number used in Pedersen Commitment
I am writing a program using a Pedersen commitment scheme and all I'm missing is an appropriate length for my prime $p$. I have heard that a length of $2^{80}$ is ok, is that correct?
0
votes
1answer
132 views
Bit commitment, two blobs with same bit, without revealing it?
Suppose we have bit commitment scheme:
$n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$
Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit.
Ok, suppose we have $y_1$ and ...
1
vote
0answers
227 views
PRG variant as a commitment scheme
I would like to use a PRG in order to achieve the commitment properties (i.e. Hiding and Binding), however, if we look at a general PRG we cannot state that it has the Binding property.
First I show ...
-1
votes
1answer
399 views
Witness and Commitment in Commitment schemes [closed]
In connection to a commitment scheme, how are witness and commitment different? Are 'Binding' and 'Hiding' properties defined w.r.t. witness and commitment or both?
5
votes
3answers
913 views
How do I generate a number for a lottery and later proves its existence
I want to create a lottery that works like this: I choose a secret number A in the range [0:999] and publish an object B. People must try to guess the number A to win. When somebody wins, I want to ...
6
votes
2answers
307 views
Hamiltonicity proof of knowledge
I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$.
So the question will be ...
9
votes
2answers
2k views
Can I prove set membership and uniqueness without revealing the element?
Assuming a publicly known set $\Psi$ with $N$ unique elements.
I have a set $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_m\}$ where $m\leqslant N$. I would like to publicly prove that all the elements in $...
2
votes
1answer
149 views
Generating shared secret random permutation
There are three blind card game players. Each player does not trust any other, even prejudicing other two players may not be blind, or there may be others in the room, peeking at their cards.
In ...
1
vote
1answer
990 views
Rock-paper-scissors over network, how to protect from cheating server?
I'm trying to design cryptographic protocol to play Rock-Paper-Scissors with two parties, neither trusting each other, nor trusting server they use for communication, so game is 'provably fair'.
So ...
3
votes
2answers
173 views
Proving a decision was randomly made [duplicate]
Alice and Bob want to agree on a bit $0$ or $1$. Both know it would be fair to pick that at random, but there's no way they could meet to throw a dice and no third party they could trust. Are there ...
1
vote
1answer
1k views
How to prove that a ciphertext is encrypting multiplication of two values?
Zero-knowledge proofs with soundness, completness and zero-knowledge enable a prover to convince a verifier that a witness validates successfully a predicate without giving any information about the ...
4
votes
3answers
1k views
What are the pros/cons of using symmetric crypto vs. hash in a commitment scheme?
In a commitment scheme, are there any differences on using a symmetric cipher versus using a hash?
If at the "opening", I have to reveal $r$ (a random number concatenated with the messaged at the ...
12
votes
1answer
4k views
Difference between Pedersen commitment and commitment based on ElGamal
Does any of you know what is the difference between the Pedersen commitment and the commitment that uses the ElGamal encryption scheme?
For the sake of completeness, I recall what both of them look ...
3
votes
1answer
751 views
Bit commitment with 1-out-of-2 oblivious transfer
I know a protocol for bit commitment using regular OT (Bob has 1/2
chance of learning the bit Alice transferred to him) which goes like this:
COMMITMENT PHASE
Alice chooses a bit $b$
For $i=0$...
4
votes
2answers
891 views
Decrypting without using the private key
Let $g$ be a generator of a multiplicative group $G$ of order $q$, $x$ be a private key, and $h=g^x$ be a public key of an exponential ElGamal cryptosystem.
Given a ciphertext $c$ produced as the ...