التشفير القائم على الاقتران

التشفير القائم على الاقتران هو استخدام اقتران بين عناصر مجموعتين تشفيريتين لمجموعة ثالثة مع تعيين${\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 P}$يُنشئ${\displaystyle G_{1}}$و${\displaystyle Q}$يُنشئ${\displaystyle G_{2}}$، ثم${\displaystyle e(P,Q)}$يُنشئ${\displaystyle G_{T}}$(أي،${\displaystyle e(P,Q)\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}\to G_{1}}$؛
3. ${\displaystyle G_{1}\neq G_{2}}$ولا توجد تشاكلات قابلة للحساب بكفاءة بين${\displaystyle G_{1}}$و${\displaystyle G_{2}}$[ ^{2 ]​}

إذا كانت متناظرة، فيمكن استخدام الأزواج لتقليل مشكلة صعبة في مجموعة واحدة إلى مشكلة مختلفة، وعادة ما تكون أسهل، في مجموعة أخرى.

على سبيل المثال، في المجموعات المجهزة بوظيفة ثنائية الخطية مثل اقتران ويل أو اقتران تيت ، يُعتقد أن تعميمات مسألة ديفي-هيلمان الحسابية (CDH) غير قابلة للحل، بينما يمكن حل مسألة ديفي-هيلمان القرارية (DDH) الأبسط بسهولة باستخدام دالة الاقتران . تُسمى المجموعة الأولى أحيانًا بمجموعة الفجوة نظرًا للاختلاف المفترض في صعوبة هاتين المسألتين داخل المجموعة. ^{[ 3 ]}

على سبيل المثال، لنفترض${\displaystyle e:G\times G\to G_{T}}$ليكن اقترانًا ثنائيًا متناظرًا وغير منحطًا وقابلًا للحساب بكفاءة، حيث${\displaystyle G}$هي مجموعة ضربية ذات مولد${\displaystyle g}$لنفترض حالة من حالات مشكلة CDH: معطى${\displaystyle g}$،${\displaystyle g^{x}}$، و${\displaystyle g^{y}}$الهدف هو الحساب${\displaystyle g^{xy}}$وظيفة الاقتران${\displaystyle e}$لا يساعدنا ذلك بشكل مباشر في الحساب${\displaystyle g^{xy}}$مما يجعل مشكلة CDH غير قابلة للحل على الأرجح. ومع ذلك، بالنظر إلى حل مرشح${\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 e(g^{x},g^{y})=e(g,g)^{xy}}$و${\displaystyle e(g,g^{z})=e(g,g)^{z}}$

منذ${\displaystyle G_{T}}$هي مجموعة من الرتبة الأولية، المساواة${\displaystyle e(g,g)^{xy}=e(g,g)^{z}}$يشير إلى${\displaystyle xy\equiv z{\pmod {q}}}$، للتحقق من صحة إجابة المرشح.

على الرغم من استخدامها لأول مرة في تحليل الشفرات ، ^{[ 4 ]} فقد تم استخدام الاقترانات أيضًا لبناء العديد من الأنظمة التشفيرية التي لا توجد لها تطبيقات فعالة أخرى معروفة، مثل التشفير القائم على الهوية أو مخططات التشفير القائمة على السمات .

تُستخدم تقنية التشفير القائمة على الاقتران في مخطط الالتزام التشفيري KZG، ويتم توضيحها في مخطط التوقيع الرقمي BLS . ^{[ 3 ]}

في يونيو 2012، قام المعهد الوطني لتكنولوجيا المعلومات والاتصالات (NICT) وجامعة كيوشو ومختبرات فوجيتسو المحدودة بتحسين الحد السابق لحساب اللوغاريتم المنفصل بنجاح على منحنى إهليلجي فائق التفرد من 676 بت إلى 923 بت. ^{[ 5 ]}

في عام 2016، سمحت خوارزمية غربلة حقل الأرقام البرجية الموسعة (exTNFS) ^{[ 6 ]} بتقليل تعقيد إيجاد اللوغاريتمات المنفصلة في بعض مجموعات الأزواج الناتجة. توجد عدة صيغ لخوارزمية غربلة حقل الأرقام البرجية المتعددة والموسعة، مما يوسع نطاق تطبيقها ويحسن من تعقيدها. نُشر وصف موحد لجميع هذه الخوارزميات مع مزيد من التحسينات في عام 2019 ^{[ 7 ]} . في ضوء هذه التطورات، قدمت العديد من الدراسات ^{[ 8 ] [ 9 ]} تقديرات ملموسة منقحة لأحجام المفاتيح لأنظمة التشفير الآمنة القائمة على الأزواج.

• محاضرة حول التشفير القائم على الاقتران
• مكتبة بن لين PBC