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
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 ...