Pairing-based cryptography: Difference between revisions

Revision as of 13:12, 7 June 2024

Revision as of 08:02, 9 June 2024

Line 20:

If symmetric, pairings can be used to reduce a hard problem in one group to a different, usually easier problem in another group.

For example, in groups equipped with a [[Bilinear map|bilinear mapping]] such as the [[Weil pairing]] or [[Tate pairing]], generalizations of the [[Diffie–Hellman problem|computational Diffie–Hellman problem]] are believed to be infeasible while the simpler [[decisional Diffie–Hellman assumption|decisional Diffie–Hellman problem]] can be easily solved using the pairing function. The first group is sometimes referred to as a '''Gap Group''' because of the assumed difference in difficulty between these two problems in the group.<ref name=":0">{{Cite journal |last=Boneh |first=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |date=2001 |editor-last=Boyd |editor-first=Colin |title=Short Signatures from the Weil Pairing |url=https://link.springer.com/chapter/10.1007/3-540-45682-1_30 |journal=Advances in Cryptology — ASIACRYPT 2001 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=514–532 |doi=10.1007/3-540-45682-1_30 |isbn=978-3-540-45682-7}}</ref>.

Let <math>e</math> be a non-degenerate, efficiently computable, bilinear pairing. Let <math>g</math> be a generator of <math>G</math>. Consider an instance of the [[Computational Diffie–Hellman problem|CDH problem]], <math>g</math>,<math>g^x</math>, <math>g^y</math>. Intuitively, the pairing function <math>e</math> does not help us compute <math>g^{xy}</math>, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given <math>g^z</math>, we may check to see if <math>g^z=g^{xy}</math> without knowledge of <math>x</math>, <math>y</math>, and <math>z</math>, by testing whether <math>e(g^x,g^y)=e(g,g^z)</math> holds.

Line 30:

Pairing-based cryptography is used in the [[Cryptographic commitment#KZG commitment|KZG cryptographic commitment scheme]].

A contemporary example of using bilinear pairings is exemplified in the [[BLS digital signature]] scheme.<ref name=":0" />.

Pairing-based cryptography relies on hardness assumptions separate from e.g. the [[elliptic-curve cryptography]], which is older and has been studied for a longer time.