Content deleted Content added
F -> mathbb{F} which is a more usual convention when referring to fields |
Link suggestions feature: 3 links added. |
||
| (9 intermediate revisions by 7 users not shown) | |||
Line 4:
The following definition is commonly used in most academic papers.<ref>{{cite book|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred|title=Cryptography and Coding |chapter=Pairing-Based cryptography at high security levels|series=Lecture Notes in Computer Science|date=2005|volume=3796|pages=13–36 |doi=10.1007/11586821_2|isbn=978-3-540-30276-6 }}</ref>
Let <math>\mathbb{F}_q</math> be a [[
; [[Bilinear map|Bilinearity]]: <math> \forall a,b \in \mathbb{F}_q^*, P\in G_1, Q\in G_2:\ e\left(aP, bQ\right) = e\left(P, Q\right)^{ab}</math>
; [[Degeneracy (mathematics)|Non-degeneracy]]: <math>e \neq 1</math>
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 book |last1=Boneh |first1=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |chapter=Short Signatures from the Weil Pairing |series=Lecture Notes in Computer Science |date=2001 |volume=2248 |editor-last=Boyd |editor-first=Colin |title=Advances in Cryptology — ASIACRYPT 2001 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-45682-1_30 |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.
While first used for [[cryptanalysis]],<ref>{{cite journal|last1=Menezes|first1=Alfred J. Menezes|last2=Okamato|first2=Tatsuaki|last3=Vanstone|first3=Scott A.|title=Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field|journal=IEEE Transactions on Information Theory|date=1993|volume=39|issue=5|pages=1639–1646 |doi=10.1109/18.259647 }}</ref> pairings have also been used to construct many cryptographic systems for which no other efficient implementation is known, such as [[identity-based encryption]] or [[attribute-based encryption]] schemes.▼
By using the bilinear property <math>x+y+z</math> times, we see that if <math>e(g^x,g^y)=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^z)</math>, then, since <math>G_T</math> is a prime order group, <math>xy=z</math>.
▲While first used for [[cryptanalysis]],<ref>{{cite journal|last1=Menezes|first1=Alfred J. Menezes|last2=Okamato|first2=Tatsuaki|last3=Vanstone|first3=Scott A.|title=Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field|journal=IEEE Transactions on Information Theory|date=1993|volume=39|issue=5|pages=1639–1646 |doi=10.1109/18.259647 }}</ref> pairings have also been used to construct many cryptographic systems for which no other efficient implementation is known, such as [[identity-based encryption]] or [[attribute-based encryption]] schemes. Thus, the security level of some pairing friendly elliptic curves have been later reduced.
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.
== Cryptanalysis ==
In June 2012 the [[National Institute of Information and Communications Technology]] (NICT), [[Kyushu University]], and [[Fujitsu#Fujitsu Laboratories|Fujitsu Laboratories Limited]] improved the previous bound for successfully computing a [[discrete logarithm]] on a [[supersingular elliptic curve]] from 676 bits to 923 bits.<ref>{{cite web |work=Press release from NICT |date=June 18, 2012 |url=http://www.nict.go.jp/en/press/2012/06/18en-1.html |title=NICT, Kyushu University and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography }}</ref>
In 2016, the Extended Tower [[General number field sieve|Number Field Sieve]] algorithm<ref>{{Cite journal |last1=Kim |first1=Taechan |last2=Barbulescu |first2=Razvan |date=2015 |title=Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case |url=https://eprint.iacr.org/2015/1027 |journal=Cryptology ePrint Archive |language=en}}</ref> allowed to reduce the complexity of finding discrete logarithm in some resulting groups of pairings.
==References==
| |||