Mixing
Pedersen commitment in elliptic curves
$begingroup$
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 two different generators of the same group?
Pedersen Commitment $C$ will look like that.
$$C = aG + bH$$
$C$ is a point on the curve, right?
Now in the situation when $a=0$ we have
$$C = 0G + bH = bH$$
How do I know that $bH$ is generated by $H$ without revealing $b$?
How do I know that $bH$ is not generated by $G$?
elliptic-curves commitments
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
$endgroup$
add a comment |
$begingroup$
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 two different generators of the same group?
Pedersen Commitment $C$ will look like that.
$$C = aG + bH$$
$C$ is a point on the curve, right?
Now in the situation when $a=0$ we have
$$C = 0G + bH = bH$$
How do I know that $bH$ is generated by $H$ without revealing $b$?
How do I know that $bH$ is not generated by $G$?
elliptic-curves commitments
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
$endgroup$
add a comment |
$begingroup$
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 two different generators of the same group?
Pedersen Commitment $C$ will look like that.
$$C = aG + bH$$
$C$ is a point on the curve, right?
Now in the situation when $a=0$ we have
$$C = 0G + bH = bH$$
How do I know that $bH$ is generated by $H$ without revealing $b$?
How do I know that $bH$ is not generated by $G$?
elliptic-curves commitments
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
$endgroup$
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 two different generators of the same group?
Pedersen Commitment $C$ will look like that.
$$C = aG + bH$$
$C$ is a point on the curve, right?
Now in the situation when $a=0$ we have
$$C = 0G + bH = bH$$
How do I know that $bH$ is generated by $H$ without revealing $b$?
How do I know that $bH$ is not generated by $G$?
elliptic-curves commitments
elliptic-curves commitments
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
edited Feb 1 at 13:50
Geoffroy Couteau
9,03511834
9,03511834
asked Feb 1 at 11:25
zie1onyzie1ony
1235
asked Feb 1 at 11:25
zie1onyzie1ony
1235
asked Feb 1 at 11:25
zie1onyzie1ony
1235
1235
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
- Is that required that $G$ and $H$ are two different generators of the same group?
Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w,H$ can be found by anyone. These facts are assumed or stated.
$C=a,G+b,H$ is a point on the curve
Yes, though at some implementation level, it is a bitstring describing a point on the curve.
- How do I know that $b,H$ is generated by $H$ without revealing $b$?
Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.
Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.
- How do I know that $b,H$ is not generated by $G$?
Point $b,H$ is generated by $G$, even though it may not have been obtained by computation of $x,G$ for some integer $x$. Obtaining integer $x$ such that $x,G=b,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.
My guess is that the intended question 3 is:
How do I know that the alleged $C=b,H$ was obtained by computation of $b,H$ without being revealed $b$?
As a verifier in a Pedersen commitment, you don't know that the alleged $C=b,H$ was obtained by computation of $b,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.
As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:
- prover generates random integer $r$, computes and sends point $Tgets r,H$
- verifier generates and sends random integer $i$
- prover computes and sends integer $sgets i,b+rbmod n$, where $n$ is the (public) order of the curve
- verifier knowing point $b,H$ computes point $i,(b,H)$, then point $i,(b,H)+T$; computes point $s,H$; and ensures $i,(b,H)+T=s,H$.
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
$endgroup$
add a comment |
$begingroup$
Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.
If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.
Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
$endgroup$
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
add a comment |
$begingroup$
- Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
- Yes.
- Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
- I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.
answered Feb 1 at 12:15
loveshlovesh
34719
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66973%2fpedersen-commitment-in-elliptic-curves%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
- Is that required that $G$ and $H$ are two different generators of the same group?
Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w,H$ can be found by anyone. These facts are assumed or stated.
$C=a,G+b,H$ is a point on the curve
Yes, though at some implementation level, it is a bitstring describing a point on the curve.
- How do I know that $b,H$ is generated by $H$ without revealing $b$?
Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.
Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.
- How do I know that $b,H$ is not generated by $G$?
Point $b,H$ is generated by $G$, even though it may not have been obtained by computation of $x,G$ for some integer $x$. Obtaining integer $x$ such that $x,G=b,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.
My guess is that the intended question 3 is:
How do I know that the alleged $C=b,H$ was obtained by computation of $b,H$ without being revealed $b$?
As a verifier in a Pedersen commitment, you don't know that the alleged $C=b,H$ was obtained by computation of $b,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.
As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:
- prover generates random integer $r$, computes and sends point $Tgets r,H$
- verifier generates and sends random integer $i$
- prover computes and sends integer $sgets i,b+rbmod n$, where $n$ is the (public) order of the curve
- verifier knowing point $b,H$ computes point $i,(b,H)$, then point $i,(b,H)+T$; computes point $s,H$; and ensures $i,(b,H)+T=s,H$.
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
$endgroup$
add a comment |
$begingroup$
- Is that required that $G$ and $H$ are two different generators of the same group?
Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w,H$ can be found by anyone. These facts are assumed or stated.
$C=a,G+b,H$ is a point on the curve
Yes, though at some implementation level, it is a bitstring describing a point on the curve.
- How do I know that $b,H$ is generated by $H$ without revealing $b$?
Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.
Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.
- How do I know that $b,H$ is not generated by $G$?
Point $b,H$ is generated by $G$, even though it may not have been obtained by computation of $x,G$ for some integer $x$. Obtaining integer $x$ such that $x,G=b,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.
My guess is that the intended question 3 is:
How do I know that the alleged $C=b,H$ was obtained by computation of $b,H$ without being revealed $b$?
As a verifier in a Pedersen commitment, you don't know that the alleged $C=b,H$ was obtained by computation of $b,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.
As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:
- prover generates random integer $r$, computes and sends point $Tgets r,H$
- verifier generates and sends random integer $i$
- prover computes and sends integer $sgets i,b+rbmod n$, where $n$ is the (public) order of the curve
- verifier knowing point $b,H$ computes point $i,(b,H)$, then point $i,(b,H)+T$; computes point $s,H$; and ensures $i,(b,H)+T=s,H$.
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
$endgroup$
add a comment |
$begingroup$
- Is that required that $G$ and $H$ are two different generators of the same group?
Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w,H$ can be found by anyone. These facts are assumed or stated.
$C=a,G+b,H$ is a point on the curve
Yes, though at some implementation level, it is a bitstring describing a point on the curve.
- How do I know that $b,H$ is generated by $H$ without revealing $b$?
Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.
Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.
- How do I know that $b,H$ is not generated by $G$?
Point $b,H$ is generated by $G$, even though it may not have been obtained by computation of $x,G$ for some integer $x$. Obtaining integer $x$ such that $x,G=b,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.
My guess is that the intended question 3 is:
How do I know that the alleged $C=b,H$ was obtained by computation of $b,H$ without being revealed $b$?
As a verifier in a Pedersen commitment, you don't know that the alleged $C=b,H$ was obtained by computation of $b,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.
As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:
- prover generates random integer $r$, computes and sends point $Tgets r,H$
- verifier generates and sends random integer $i$
- prover computes and sends integer $sgets i,b+rbmod n$, where $n$ is the (public) order of the curve
- verifier knowing point $b,H$ computes point $i,(b,H)$, then point $i,(b,H)+T$; computes point $s,H$; and ensures $i,(b,H)+T=s,H$.
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
$endgroup$
- Is that required that $G$ and $H$ are two different generators of the same group?
Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w,H$ can be found by anyone. These facts are assumed or stated.
$C=a,G+b,H$ is a point on the curve
Yes, though at some implementation level, it is a bitstring describing a point on the curve.
- How do I know that $b,H$ is generated by $H$ without revealing $b$?
Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.
Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.
- How do I know that $b,H$ is not generated by $G$?
Point $b,H$ is generated by $G$, even though it may not have been obtained by computation of $x,G$ for some integer $x$. Obtaining integer $x$ such that $x,G=b,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.
My guess is that the intended question 3 is:
How do I know that the alleged $C=b,H$ was obtained by computation of $b,H$ without being revealed $b$?
As a verifier in a Pedersen commitment, you don't know that the alleged $C=b,H$ was obtained by computation of $b,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.
As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:
- prover generates random integer $r$, computes and sends point $Tgets r,H$
- verifier generates and sends random integer $i$
- prover computes and sends integer $sgets i,b+rbmod n$, where $n$ is the (public) order of the curve
- verifier knowing point $b,H$ computes point $i,(b,H)$, then point $i,(b,H)+T$; computes point $s,H$; and ensures $i,(b,H)+T=s,H$.
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
edited Feb 1 at 17:39
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
answered Feb 1 at 13:12
fgrieufgrieu
82k7178351
82k7178351
add a comment |
add a comment |
$begingroup$
Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.
If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.
Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
$endgroup$
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
add a comment |
$begingroup$
Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.
If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.
Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
$endgroup$
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
add a comment |
$begingroup$
Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.
If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.
Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
$endgroup$
Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.
If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.
Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
edited Feb 1 at 17:16
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
answered Feb 1 at 13:22
Geoffroy CouteauGeoffroy Couteau
9,03511834
9,03511834
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
add a comment |
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
"Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right?
$endgroup$
– Maeher
Feb 1 at 16:27
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that.
$endgroup$
– Geoffroy Couteau
Feb 1 at 17:16
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
$begingroup$
Ah, the dreaded double negative. :D
$endgroup$
– Maeher
Feb 1 at 17:26
add a comment |
$begingroup$
- Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
- Yes.
- Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
- I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.
answered Feb 1 at 12:15
loveshlovesh
34719
$endgroup$
add a comment |
$begingroup$
- Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
- Yes.
- Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
- I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.
answered Feb 1 at 12:15
loveshlovesh
34719
$endgroup$
add a comment |
$begingroup$
- Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
- Yes.
- Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
- I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.
answered Feb 1 at 12:15
loveshlovesh
34719
$endgroup$
- Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
- Yes.
- Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
- I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.
answered Feb 1 at 12:15
loveshlovesh
34719
edited Mar 25 at 7:15
answered Feb 1 at 12:15
loveshlovesh
34719
answered Feb 1 at 12:15
loveshlovesh
34719
answered Feb 1 at 12:15
loveshlovesh
34719
34719
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66973%2fpedersen-commitment-in-elliptic-curves%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
