การเข้ารหัสแบบจับคู่คือการใช้การจับคู่ระหว่างองค์ประกอบของกลุ่ม การเข้ารหัสสองกลุ่ม กับกลุ่มที่สามที่มีการแมปเพื่อสร้างหรือวิเคราะห์ระบบการเข้ารหัส${\displaystyle e:G_{1}\times G_{2}\to G_{T}}$

คำจำกัดความต่อไปนี้มักใช้ในเอกสารวิชาการส่วนใหญ่^{[ 1 ]}

ให้เป็นฟิลด์จำกัดเหนือจำนวนเฉพาะ, ...​​​${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$${\displaystyle G_{1},G_{2}}$${\displaystyle q}$${\displaystyle G_{T}}$${\displaystyle q}$${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$

ความเป็นเส้นตรงสองเส้น

${\displaystyle \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}}$

ความไม่เสื่อมถอย

${\displaystyle e\neq 1}$

ความสามารถในการคำนวณ

มีอัลกอริทึม ที่มีประสิทธิภาพ ในการคำนวณอยู่${\displaystyle e}$

ถ้าใช้กลุ่มเดียวกันสำหรับสองกลุ่มแรก (เช่น) การจับคู่นั้นเรียกว่าสมมาตรและเป็นการจับคู่จากสององค์ประกอบในกลุ่มหนึ่งไปยังองค์ประกอบจากกลุ่มที่สอง${\displaystyle G_{1}=G_{2}}$

นักวิจัยบางคนจำแนกรูปแบบการจับคู่เป็นสาม (หรือมากกว่า) ประเภทพื้นฐาน:

1. ${\displaystyle G_{1}=G_{2}}$;
2. ${\displaystyle G_{1}\neq G_{2}}$แต่มีโฮโมมอร์ฟิซึมที่คำนวณได้อย่างมีประสิทธิภาพ${\displaystyle \phi :G_{2}\ถึง G_{1}}$
3. ${\displaystyle G_{1}\neq G_{2}}$และไม่มี โฮโม ^มอ ร์ฟิซึม ที่คำนวณได้อย่างมีประสิทธิภาพระหว่างและ[ ^{2 ]}${\displaystyle G_{1}}$${\displaystyle G_{2}}$

หากมีความสมมาตร การจับคู่สามารถช่วยลดความยากของปัญหาในกลุ่มหนึ่งให้กลายเป็นปัญหาที่แตกต่างออกไป ซึ่งโดยทั่วไปแล้วจะง่ายกว่าในอีกกลุ่มหนึ่ง

ตัวอย่างเช่น ในกลุ่มที่มีการแมปแบบไบลิเนียร์เช่นการจับคู่ Weilหรือการจับคู่ Tateเชื่อกันว่าการวางนัยทั่วไปของปัญหา Diffie–Hellman ในเชิงคำนวณ นั้นเป็นไปไม่ได้ ในขณะที่ ปัญหา Diffie–Hellman ในเชิงการตัดสินใจ ที่ง่ายกว่านั้น สามารถแก้ไขได้ง่ายโดยใช้ฟังก์ชันการจับคู่กลุ่มแรกบางครั้งเรียกว่ากลุ่มช่องว่างเนื่องจากความแตกต่างของความยากระหว่างสองปัญหาในกลุ่มนี้^{[ 3 ]}

ให้เป็นการจับคู่แบบทวิเชิงเส้นที่ไม่เสื่อมสภาพ คำนวณได้อย่างมีประสิทธิภาพ และให้เป็นตัวสร้างของพิจารณาตัวอย่างของปัญหา CDH , , , โดยสัญชาตญาณ ฟังก์ชันการจับคู่ไม่ได้ช่วยเราในการคำนวณซึ่งเป็นคำตอบของปัญหา CDH มีการคาดการณ์ว่าตัวอย่างของปัญหา CDH นี้แก้ไขไม่ได้ เมื่อกำหนดเราอาจตรวจสอบว่า โดยไม่ต้องทราบ, , และโดยการทดสอบว่าเป็นจริง หรือไม่${\displaystyle e}$${\displaystyle g}$${\displaystyle G}$${\displaystyle g}$${\displaystyle g^{x}}$${\displaystyle g^{y}}$${\displaystyle e}$${\displaystyle g^{xy}}$${\displaystyle g^{z}}$${\displaystyle g^{z}=g^{xy}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle e(g^{x},g^{y})=e(g,g^{z})}$

โดยใช้คุณสมบัติทวิเชิงเส้นหลายครั้ง เราจะเห็นว่าถ้าแล้ว เนื่องจากเป็นกลุ่มที่มีอันดับเฉพาะดังนั้น${\displaystyle x+y+z}$${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})}$${\displaystyle G_{T}}$${\displaystyle xy=z}$

แม้ว่าจะใช้ครั้งแรกสำหรับ^การวิเคราะห์การเข้ารหัส [ ^{4 ]}การจับคู่ยังถูกนำมาใช้เพื่อสร้างระบบการเข้ารหัสจำนวนมากซึ่งไม่มีการใช้งานที่มีประสิทธิภาพอื่นใดที่รู้จัก เช่นการเข้ารหัสตามเอกลักษณ์หรือ รูปแบบ การเข้ารหัสตามคุณลักษณะดังนั้น ระดับความปลอดภัยของเส้นโค้งวงรีที่เป็นมิตรต่อการจับคู่บางส่วนจึงลดลงในภายหลัง

การเข้ารหัสแบบจับคู่ถูกนำมาใช้ในระบบการยืนยันการเข้ารหัส KZG

ตัวอย่างร่วมสมัยของการใช้การจับคู่แบบไบลิเนียร์แสดงให้เห็นได้ในโครงการลายเซ็นดิจิทัล BLS ^{[ 3 ]}

การเข้ารหัสแบบจับคู่ (Pairing-based cryptography) อาศัยสมมติฐานเรื่องความยากที่แตกต่างจาก การเข้ารหัสแบบ เส้นโค้งวงรี (elliptic-curve cryptography ) ซึ่งเป็นวิธีการที่เก่ากว่าและได้รับการศึกษามาเป็นเวลานานกว่า

ในเดือนมิถุนายน พ.ศ. 2555 สถาบันเทคโนโลยีสารสนเทศและการสื่อสารแห่งชาติ (NICT) มหาวิทยาลัยคิวชูและบริษัทฟูจิตสึ แล็บโบราทอรีส์ จำกัดได้ปรับปรุงขอบเขตก่อนหน้าสำหรับการคำนวณลอการิทึมแบบไม่ ต่อเนื่อง บนเส้นโค้งวงรีซูเปอร์ซิงกูลาร์จาก 676 บิตเป็น 923 บิต^{[ 5 ]}

ในปี 2016 อัลกอริทึม Extended Tower Number Field Sieve ^{[ 6 ]}ช่วยลดความซับซ้อนของการค้นหาลอการิทึมแบบไม่ต่อเนื่องในกลุ่มการจับคู่บางกลุ่มที่ได้มา มีอัลกอริทึม Multiplier และ Extended Tower Number Field Sieve หลายรูปแบบที่ขยายขอบเขตการใช้งานและปรับปรุงความซับซ้อนของอัลกอริทึม คำอธิบายที่เป็นเอกภาพของอัลกอริทึมดังกล่าวทั้งหมดพร้อมการปรับปรุงเพิ่มเติมได้รับการเผยแพร่ในปี 2019 ^{[ 7 ]}จากความก้าวหน้าเหล่านี้ งานหลายชิ้น^{[ 8 ] [ 9 ]}ได้ให้การประมาณค่าที่เป็นรูปธรรมที่แก้ไขแล้วเกี่ยวกับขนาดคีย์ของระบบการเข้ารหัสแบบจับคู่ที่ปลอดภัย

• การบรรยายเรื่องการเข้ารหัสแบบจับคู่
• ห้องสมุด PBC ของเบน ลินน์