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
0answers
20 views

Efficient proof for Cartesian product

I am trying to find some efficient zero-knowledge arguments that could prove the vector ${\bf v}$ is the Cartesian product of two vectors ${\bf x}$ and ${\bf y}$. I know there are efficient inner ...
2
votes
1answer
46 views

Pedersen Commitment and Computational Zero Knowledge

I am curious at how "good" is computational zero knowledge? Consider Pedersen Commitment $z = g^x h^y$. There exists perfect ZK protocol (based on Schnorr's) to prove that one knows the ...
2
votes
0answers
24 views

Difference between a key value commitment and authenticated dictionary

I was wondering about the difference between an authenticated dictionary and a key value commitment scheme like KVac. Are they the same thing or they have different model or definitions? Thanks
1
vote
1answer
62 views

Gennaro & Goldfeder Key Generation Protocol

As I am going through the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018, I am stumbled by the key generation protocol (Sect. 4.1, p.10): In Phase ...
1
vote
1answer
37 views

Commitment scheme for a possible unordered growing collection of elements

Merkle trees can be used for vector commitment scheme. In particular given two sequences S, S' with the same elements in the same order the merkle root for S will be the same as the one for S'. What ...
1
vote
1answer
52 views

Zero-knowledge proof of committed value

I am considering the following questions and would appreciate any help. Problem formulation: Suppose Alice holds a secret value $x$ and there is a public Boolean predicate function $\texttt{Pred}$ ...
1
vote
1answer
32 views

Coin tosses in the context of commitment schemes

I was reading the “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” paper by Gennaro & Goldfeder, 2018 and I encountered this portion (Sect. 2.4, p.6): This excerpt leaves me slightly ...
0
votes
2answers
125 views

How can I prove “single-use authorization” from multiple parties without revealing identity?

I've been trying to create a distributed authorization protocol where identities are not revealed. Let me explain with an example. Let's assume we have 4 actors, Alice, Bob, Charlie, and Dan. Alice is ...
0
votes
1answer
47 views

Why must s be kept secret in pedersen commitments?

I was reading up on Pedersen commitment over at this website: https://asecuritysite.com/encryption/ped, where they calculate $h=g^s \bmod p$, and they say that $s$ must be a secret. I wonder why this ...
3
votes
2answers
149 views

Finding an elliptic curve of specific order

I wish to use elliptic curves for cryptographic operations like commitments etc. I see that most standard elliptic curves like $\operatorname{secp256k1, sect571r1}$ have a certain specific and fixed ...
0
votes
2answers
53 views

Solution to Discrete Log as a Commitment

Is the solution to a discrete logarithm a reasonable commitment scheme? By my analysis, the following scheme is a reasonable commitment scheme: Let $p$ and $q$ be large primes such that $q∣(p−1)$, let ...
1
vote
0answers
50 views

Does there exist a provably correct and recipient hiding encryption scheme?

I am looking for an encryption scheme $E$ and a commitment scheme $C$ which allow encrypting the message $m$ for the public key $y$ as $e = E_y(m)$, so that the ciphertext $e$ does not reveal any ...
2
votes
1answer
92 views

Proving statistically hiding for a simple commitment scheme in the ROM

It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting $\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{...
2
votes
1answer
51 views

Dishonest verifier running a concurrent zero-knowledge protocol

Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a ...
3
votes
1answer
78 views

Commitment schemes for arbitrarily large integers

My question is about commitment schemes for arbitrarily large integers. One scheme I know uses groups of unknown order (RSA or class group) and depends on the strong-RSA assumption. You chose a random ...
2
votes
1answer
73 views

Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols

In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where The prover sends a commitment to the ...
1
vote
0answers
104 views

Zero-knowledge proof of knowledge of a plaintext in exponential ElGamal

Consider the exponential ElGamal cryptosystem over some group $G$ with generator $g$. Let $m$ be a plaintext, and $(R, C) = (g^r, g^m \cdot y^r)$ an encryption thereof for some public key $y$. Assume ...
0
votes
0answers
26 views

UC-secure commitment in the ROM

Looking at the question Is this a UC-secure commitment scheme in the ROM?, I was wondering, is the commitment scheme proposed in the answer (which uses $H(M||r)$ as commit) secure in the UC-model, ...
0
votes
0answers
39 views

Why are the fully homomorphic encryption algorithms the commitment?

Is there some references about the commitment scheme based on FHE ? Why could the BFV, CKKS, BGV algorithm be convert to commitment? How ?
2
votes
0answers
52 views

How does the rejection sampling lemma work in the proof of HVZK?

In this protocol, Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$? Q2: How does the rejection sampling lemma work? refer to ...
0
votes
0answers
40 views

Is the BFV homomorphic encryption scheme a commitment scheme?

The BFV scheme can be described as: Public Key: $(p_0, p_1)$ To encrypt a plaintext $m$, the ciphertext is : $(c_0, c_1) , c_0= up_0+\Delta m + e_0, c_1=up_1 + e_1$
0
votes
1answer
66 views

Difference between a Polynomial Opening & a Polynomial Commitment

Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two ...
1
vote
0answers
45 views

Hash as encryption used by Monero

Monero uses a Pedersen commitment $yG + bH$ to obfuscate the value of a transaction, where $b$ is the value and $y$ is the blinding factor. For the receiver to know both variables, it uses a Diffie-...
0
votes
0answers
52 views

Why is the proof on the commitment correct?

In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
1
vote
1answer
59 views

All fully homomorphic encryptions (FHE) are converted into homomorphic commitments?

The GSW one of the FHE scheme is widely used as a homomorphic commitment scheme to build lattice based ABE, homomorphic signatures and NIZK and so on. But I cannot find other FHE schemes to be ...
0
votes
0answers
29 views

Does resuing pederson commitment preserve the hiding property?

Assume you have a pedersen commitment scheme where the commitment is: $$\mathcal C_1 =C(m,r)=g^m\cdot h^r$$ with $g,h$ being public generators in a public group $(G,\cdot)$ in which the discrete ...
1
vote
0answers
43 views

Question about hiding commitment scheme for integers

Given a generic group $\mathbb{G}$ of an unknown order (such as a $3000$-bit RSA group) and a randomly generated element $g \in \mathbb{G}$, is the commitment scheme $\mathrm{Com}(x)= g^x$ not ...
0
votes
0answers
81 views

A card game (for mental poker or any other card game)

I thought of a way to produce trustless card game in a flexible way. One feature that I want is it should be flexible (It should work for any type of card game, though I indeed started it as a ...
0
votes
0answers
56 views

Multiplication of a Pedersen commitment 10 times

Suppose I have a Pedersen Commitment $cm(x,r) = g^xh^r$ where $g,h$ are generators of group $G$ of prime order $p$. Based on $cm$, I want to create a commitment $cm' = (10\cdot x,r')$, without of ...
0
votes
0answers
54 views

Is there a concept of Pedersen commitment “in the base”?

This question Can Elgamal be made additively homomorphic and how could it be used for E-voting? says ElGamal can be made homomorphic over multiplication. So you can have $(g^r, h^r g^m)$ (i.e., ...
0
votes
1answer
60 views

Notation for commitment schemes

I was reading this set of lecture notes on commitment schemes, where they define a commitment scheme $\text{Com}(b, r) = f(r), h(r) \oplus b$ as a secure commitment scheme. In this case, $f : \{0,1\}^...
0
votes
0answers
116 views

Non-interactive zero-knowledge proof system for a language undecidable in polynomial time

I am studying through some material in an online course, and there is an exercise which I could not figure out. The problem is this: Let $L$ be a language that is not decidable in polynomial time (...
6
votes
0answers
76 views

Understanding anonymous credentials. Does someone understand how it works?

After reading a series of papers CL01 CL02 CL04, I feel like I understand the intuition behind the anonymous credential framework but I don't understand some details the mathematics behind it. I ...
0
votes
2answers
85 views

Constructing a commitment scheme from two (possibly defective) commitment schemes

If we have two commitment schemes Com1 and Com2, which are possibly defective (in the sense of not satisfying hiding or binding properties), is it possible to construct a commitment scheme which does ...
2
votes
1answer
48 views

How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment?

In anonymous credentials schemes, it is possible to anonymously prove knowledge of a signature. Proposals for anonymous credentials with attributes also include a method for proving statements about ...
3
votes
2answers
69 views

How to show that Cx is a commitment to a integer of length lm

With reference to Jan Camenisch and Anna Lysyanskaya's paper A Signature Scheme with Efficient Protocols, in proceedings of SCN 2002, I need some help to understand How to verify that $C_x$ is a ...
0
votes
0answers
123 views

regarding usage of hashing

I have a question regarding pitfalls of using only encryption. Suppose Bob and Alice want to flip a coin over a network. Alice proposes the following protocol. Alice randomly selects a value X ∈ {0,1}...
0
votes
0answers
32 views

Subset-sum Problem & Commitment Schemes

In this question I asked about a subset sum hash. Would it be possible to adapt that into a commitment scheme by keeping M private and revealing it at a later time? Would this be secure for some size ...
0
votes
0answers
94 views

Zero Knowledge Set Membership proof

ZK set membership: I am trying to create my own zero knowledge set membership proof for a commitment to an element in the set for small sets. I am a beginner in such works, so can someone help me find ...
3
votes
1answer
118 views

How to achieve identity authentication without revealing credentials

I am looking at a scenario where I would like to claim to an authority (call it A) that I am indeed me without revealing my identity documents. I am guessing some zero knowledge protocol has to be ...
4
votes
0answers
179 views

Computationally binding commitment

A Computationally Binding commitment scheme is defined as a tuple of protocols $(\mathsf{Keygen}, \mathsf{Com}, \mathsf{Open})$, that along with correctness guarantees that for all PPT algorithms the ...
1
vote
1answer
47 views

Constant size commitment to a membership of a fixed size of elements

Suppose there is a global set of $n$ elements, out of which I want to commit to $2n/3$ elements, i.e., anyone can take my commitment and test what $2n/3$ of the possible $n$ elements I committed to. ...
4
votes
2answers
160 views

Sigma proofs for Pedersen commitments arithmetic under different bases

I was wondering if it's possible to prove an equality of openings between $3$ Pedersen commitments $P\cdot Q$ and $R$ when $P, Q, R$ have different commitment keys. Suppose that commitment $R$ commits ...
0
votes
0answers
71 views

Can Pedersen commitment be used in pairing groups?

For bilinear groups: $(p,\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T,e,g_1,h_1,g_2,h_2)$, where $\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T$ are groups of prime oder $p$. $g_1,h_1$ are generators of $\mathbb{G}...
1
vote
1answer
110 views

Question of proving the opening of Pedersen Commitment

Given an opening $(m, r)$ of a Pedersen commitment $c = g^m h^r$, where $g, h$ are the generators of a group $G$ with prime order $q$ (public), a PPT prover wants to prove to a verifier the opening of ...
0
votes
0answers
88 views

Computational Binding of Pedersen Commitment

Let us assume that Alice and Bob are playing a game. Alice first commits her value chosen from $\{0,1\}$ via Pedersen commitment scheme and sends the commitment to Bob. Then Bob sends his value chosen ...
0
votes
0answers
72 views

Does Schnorr identification protocol using commitment scheme?

In schnorr identification protocol, a prover needs to choose a random,let's say $r$ at the beginning, then commit to this randomness as $g^r\bmod p$. When we say "commit", does it really mean we are ...
0
votes
1answer
46 views

Is the random oracle commitment scheme secure against PPT active adversaries?

The probability that a probabilistic polynomial adversary corrupting the sender can finds two pairs $(m,r)$ such that the output of the random oracle $c$ is the same (break the binding property) is ...
0
votes
1answer
97 views

Computational binding implies Perfect hiding?

Given a commitment scheme which is computationally binding (based on some conjectured hard problem, say), does it also imply that the scheme is unconditionally hiding? My idea was: Since the scheme ...
4
votes
1answer
217 views

Is it possible I can open pedersen commitments without revealing r?

With setup $p$ and $q$ where $p = 2q + 1$, and $g$ and $h$ is the generator with order $q$. In Pedersen commitment, I commit the value m with $c=g^m h^r \bmod p$, then de-commit by revealing $(m, r)$....