افتراض الخطية في القرار

يُعدّ افتراض الخطية القرارية ( افتراض DLIN ) افتراضًا يتعلق بصعوبة الحساب، ويُستخدم في تشفير المنحنيات الإهليلجية . ويُفيد هذا الافتراض تحديدًا في الحالات التي لا ينطبق فيها افتراض ديفي-هيلمان القراري (كما هو الحال غالبًا في التشفير القائم على الاقتران ). وقد طُوّر افتراض الخطية القرارية بواسطة بونيه ، وبوين، وشاشام. ^{[ 1 ]}

بشكل غير رسمي، ينص افتراض DLIN على أنه بالنظر إلى${\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}$، مع${\displaystyle u,\,v,\,h}$عناصر المجموعة العشوائية و${\displaystyle x,\,y}$الأسس العشوائية، يصعب تمييزها${\displaystyle h^{x+y}}$من عنصر مجموعة عشوائية مستقلة${\displaystyle \eta }$.

في التشفير القائم على الاقتران المتناظر، المجموعة${\displaystyle G}$مزود بخاصية الاقتران${\displaystyle e:G\times G\to T}$وهي دالة ثنائية الخطية . توفر هذه الخريطة خوارزمية فعالة لحل مسألة ديفي-هيلمان القرارية . ^{[ 2 ]} بالنظر إلى المدخلات${\displaystyle (g,\,g^{a},\,g^{b},\,h)}$من السهل التحقق مما إذا${\displaystyle h}$يساوي${\displaystyle g^{ab}}$ويتبع ذلك باستخدام الاقتران: لاحظ أن

${\displaystyle e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).}$

وبالتالي، إذا${\displaystyle h=g^{ab}}$ثم القيم${\displaystyle e(g^{a},g^{b})}$و${\displaystyle e(g,h)}$سيكونون متساوين.

بما أن هذا الافتراض التشفيري، الضروري لبناء تشفير وتوقيعات ElGamal ، لا ينطبق في هذه الحالة، فإن هناك حاجة إلى افتراضات جديدة لبناء التشفير في المجموعات الثنائية الخطية المتناظرة. يُعد افتراض DLIN تعديلًا لافتراضات ديفي-هيلمان لإحباط الهجوم المذكور أعلاه.

يترك${\displaystyle G}$لتكن مجموعة دورية من رتبة أولية${\displaystyle p}$. يترك${\displaystyle u}$،${\displaystyle v}$، و${\displaystyle h}$لنفترض أنها مولدات عشوائية منتظمة لـ${\displaystyle G}$. يترك${\displaystyle a,b}$لتكن عناصر عشوائية منتظمة من${\displaystyle \{1,\,2,\,\dots ,\,p-1\}}$عرّف التوزيع

${\displaystyle D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).}$

يترك${\displaystyle \eta }$ليكن عنصرًا عشوائيًا منتظمًا آخر من${\displaystyle G}$عرّف توزيعًا آخر

${\displaystyle D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).}$

ينص افتراض القرار الخطي على أن${\displaystyle D_{1}}$و${\displaystyle D_{2}}$لا يمكن التمييز بينهما حسابيًا .