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.
144
questions
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
361 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
235 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
176 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$ ...
15
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
347 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
367 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
118 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
108 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
899 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
180 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
429 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
713 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
437 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
185 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
158 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
180 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
129 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
221 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
395 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
890 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
302 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 ...
8
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
145 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
971 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
167 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
740 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
857 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 ...
17
votes
1answer
8k views
Why is the Pedersen commitment computationally binding?
This is how the Pedersen commitment seems to work:
Let $p$ and $q$ be large primes such that $q \mid (p-1)$, let $g$ be a generator of the order-$q$ subgroup of $Z_p^{\star}$. Let $a$ be a random ...
8
votes
2answers
3k views
Have I understood pedersen commitment correctly?
I want to do a one-sided integer commitment scheme. I.e. the whole process must be non-interactive where I at one point first publicly reveal some data and then at a later time reveal the committed ...
13
votes
1answer
6k views
Commitment scheme using hash functions
Let's say Alice and Bob are playing a game where Bob is trying to guess a number Alice has chosen.
Alice chooses a key $K$ and a number $N$ at random and performs $C=Commit(K, N)$ where $Commit(K, N)=...
2
votes
2answers
116 views
Zero-knowledge identification of the majority commitment
Alice is communicating with $n$ people. We do not assume that the $n$ people don't trust each other or trust Alice. Alice doesn't trust them either, and needs to assume that they will not form a ...
1
vote
1answer
80 views
Proving item association without revealing one of the associated items
I'm a total noob when it comes to cryptography but I believe this falls under the "zero knowledge" category.
I have two associated pieces of information:
tag — known by both parties. Unique per ...
4
votes
1answer
802 views
What type of hash functions provides non-malleability of hash digests?
I want to use a hash function for commitments. I don't want an attacker to construct a commitment related to a previously published (but still unopened) commitment.
A simple deterministic commitment ...
29
votes
4answers
4k views
How to fairly select a random number for a game without trusting a third party?
Several people are playing a game with random events and require a way to produce a random number. (Such as dice rolls or a lottery.)
Can this be done such that each player has the power to be ...
2
votes
2answers
330 views
Is there a cumulative commitment scheme?
For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single ...
