Content deleted Content added
m Replace hyphen with en-dash. |
m Fixing broken anchor: Reminder of an inactive anchor: elliptic curve discrete logarithm problem |
||
Line 249:
{{hidden
| Why the bilinear map pairing is used |
The utility of the bilinear map pairing is to allow the multiplication of <math>q(x)</math> by <math>x-i</math> to happen securely. These values truly lie in <math>\mathbb{G}_1</math>, where division is assumed to be computationally hard. For example, <math>\mathbb{G}_1</math> might be an [[elliptic curve]] over a finite field, as is common in [[elliptic-curve cryptography]]. Then, the division assumption is called the [[Elliptic-curve cryptography#Rationale|elliptic curve discrete logarithm problem]]{{Broken anchor|date=2024-07-20|bot=User:Cewbot/log/20201008/configuration|target_link=Elliptic-curve cryptography#Rationale|reason= The anchor (Rationale) [[Special:Diff/1148439344|has been deleted]].}}, and this assumption is also what guards the trapdoor value from being computed, making it also a foundation of KZG commitments. In that case, we want to check if <math>q(x)(x-i) = p(x)-y</math>. This cannot be done without a pairing, because with values on the curve of <math>G \cdot q(x)</math> and <math>G \cdot (x-i)</math>, we cannot compute <math>G \cdot (q(x)(x-i))</math>. That would violate the [[computational Diffie–Hellman assumption]], a foundational assumption in [[elliptic-curve cryptography]]. We instead use a [[pairing]] to sidestep this problem. <math>q(x)</math> is still multiplied by <math>G</math> to get <math>G \cdot q(x)</math>, but the other side of the multiplication is done in the paired group <math>\mathbb{G}_2</math>, so, <math>H \cdot (t-i)</math>. We compute <math>e(G \cdot q(t), H \cdot (t-i))</math>, which, due to the [[bilinear map|bilinearity]] of the map, is equal to <math>e(G, H)^{q(t)\cdot(t-i)}</math>. In this output group <math>\mathbb{G}_T</math> we still have the [[Discrete logarithm#Cryptography|discrete logarithm problem]], so even though we know that value and <math>e(G, H)</math>, we cannot extract the exponent <math>q(t)\cdot(t-i)</math>, preventing any contradiction with discrete logarithm earlier. This value can be compared to <math>e(G \cdot (p(t) - y), H)=e(G, H)^{p(t) - y}</math> though, and if <math>e(G, H)^{q(t)\cdot(t-i)} = e(G, H)^{p(t) - y}</math> we are able to conclude that <math>q(t) \cdot (t-i) = p(t)-y</math>, without ever knowing what the actual value of <math>t</math> is, let alone <math>q(t)(t-i)</math>.
|style = border: 1px solid lightgray; <!-- copied from the Navier–Stokes equations page -->
|headerstyle = text-align:left
| |||