التعلم من الأخطاء

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
📷 يحتوي على 116 صور
الموسوعة الحرة

في علم التشفير ، يُعدّ التعلّم مع الأخطاء ( LWE ) مسألة رياضية شائعة الاستخدام لإنشاء خوارزميات تشفير آمنة . [ 1 ] وهي تقوم على فكرة تمثيل المعلومات السرية كمجموعة من المعادلات مع وجود أخطاء. بعبارة أخرى، يُعدّ التعلّم مع الأخطاء وسيلة لإخفاء قيمة السرّ عن طريق إدخال تشويش عليه. [ 2 ] وبعبارة أدق، يشير إلى المسألة الحسابية لاستنتاج علاقة خطيةن{\displaystyle n}دالة -aryو{\displaystyle f}على حلقة منتهية من عينات معطاةyأنا=و(xأنا){\displaystyle y_{i}=f(\mathbf {x} _{i})}قد يكون بعضها خاطئًا. يُعتقد أن مشكلة LWE صعبة الحل، [ 1 ] وبالتالي فهي مفيدة في علم التشفير.

وبشكل أدق، تُعرَّف مشكلة LWE على النحو التالي. ليكنZq{\displaystyle \mathbb {Z} _{q}}يرمز إلى حلقة الأعداد الصحيحة moduloq{\displaystyle q}ودع Zqن{\displaystyle \mathbb {Z} _{q}^{n}}يرمز إلى مجموعةن{\displaystyle n}- متجهات فوقZq{\displaystyle \mathbb {Z} _{q}}توجد دالة خطية مجهولة معينةو:Zqن→Zq{\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}والمدخل لمسألة LWE هو عينة من الأزواج(x،y){\displaystyle (\mathbf {x} ,y)}، أينx∈Zqن{\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}وy∈Zq{\displaystyle y\in \mathbb {Z} _{q}}، بحيث يكون ذلك باحتمالية عاليةy=و(x){\displaystyle y=f(\mathbf {x} )}علاوة على ذلك، فإن الانحراف عن المساواة يتبع نموذج ضوضاء معروف. تتطلب المسألة إيجاد الدالةو{\displaystyle f}أو ما يقارب ذلك، باحتمالية عالية .

طُرحت مسألة LWE بواسطة عوديد ريغيف عام 2005 [ 3 ] (الحائز على جائزة غودل لعام 2018 عن هذا العمل)؛ وهي تعميم لمسألة تعلم التكافؤ . بيّن ريغيف أن مسألة LWE لا تقل صعوبة عن حل العديد من مسائل الشبكة في أسوأ الحالات . لاحقًا، استُخدمت مسألة LWE كفرضية صعوبة لإنشاء أنظمة تشفير المفتاح العام ، [ 3 ] [ 4 ] مثل تبادل مفاتيح التعلم الحلقي مع الأخطاء الذي ابتكره بيكرت. [ 5 ]

تعريف

يرمز بـتي=R/Z{\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }المجموعة الجمعية على الأعداد الحقيقية بتردد واحد . ليكنs∈Zqن{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}ليكن متجهًا ثابتًا.ϕ{\displaystyle \phi }ليكن توزيع احتمالي ثابت علىتي{\displaystyle \mathbb {T} }. يُرمز إليه بـأs،ϕ{\displaystyle A_{\mathbf {s} ,\phi }}التوزيع علىZqن×تي{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }تم الحصول عليها على النحو التالي.

  1. اختر متجهًاأ∈Zqن{\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}من التوزيع المنتظم علىZqن{\displaystyle \mathbb {Z} _{q}^{n}}،
  2. اختر رقمًاهـ∈تي{\displaystyle e\in \mathbb {T} }من التوزيعϕ{\displaystyle \phi }،
  3. يقيمت=⟨أ،s⟩/q+هـ{\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}، أين⟨أ،s⟩=∑أنا=1نأأناsأنا{\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}هو المنتج الداخلي القياسي فيZqن{\displaystyle \mathbb {Z} _{q}^{n}}، تتم عملية القسمة في حقل الأعداد الحقيقية (أو بشكل أكثر رسمية، هذه "القسمة علىq{\displaystyle q}" هو رمز لتشاكل المجموعةZq⟶تي{\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }رسم الخرائط1∈Zq{\displaystyle 1\in \mathbb {Z} _{q}}ل1/q+Z∈تي{\displaystyle 1/q+\mathbb {Z} \in \mathbb {T} }والإضافة الأخيرة هي فيتي{\displaystyle \mathbb {T} }.
  4. أخرج الزوج(أ،ت){\displaystyle (\mathbf {a} ,t)}.

مشكلة التعلم مع الأخطاءلدبليوهـq،ϕ{\displaystyle \mathrm {LWE} _{q,\phi }}هو أن تجدs∈Zqن{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}، مع إمكانية الوصول إلى عدد كبير من العينات المختارة منأs،ϕ{\displaystyle A_{\mathbf {s} ,\phi }}.

لكلα>0{\displaystyle \alpha >0}، يُرمز إليه بـدα{\displaystyle D_{\alpha }}التوزيع الغاوسي أحادي البعد ذو المتوسط ​​الصفري والتباين α2/(2π){\displaystyle \alpha ^{2}/(2\pi )}أي أن دالة الكثافة هيدα(x)=ρα(x)/α{\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }أينρα(x)=هـ-π(|x|/α)2{\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}ودعΨα{\displaystyle \Psi _{\alpha }}يكون التوزيع علىتي{\displaystyle \mathbb {T} }تم الحصول عليها من خلال النظردα{\displaystyle D_{\alpha }}modulo one. ستكون نسخة LWE التي تم اعتمادها في معظم النتائج هيلدبليوهـq،Ψα{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}

نسخة القرار

تُعدّ مسألة LWE الموصوفة أعلاه نسخة البحث من المسألة. أما في نسخة القرار ( DLWE )، فالهدف هو التمييز بين الضرب الداخلي المشوّش والعينات العشوائية المنتظمة منZqن×تي{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }( عمليًا، نسخة منفصلة منه). أظهر ريجيف [ 3 ] أن نسختي القرار والبحث متكافئتان عندماq{\displaystyle q}هو عدد أولي محدود بكثير حدود فين{\displaystyle n}.

بشكل بديهي، إذا كان لدينا إجراء لحل مشكلة البحث، فيمكن حل نسخة القرار بسهولة: ما عليك سوى إدخال عينات الإدخال الخاصة بمشكلة القرار إلى برنامج حل مشكلة البحث. لنرمز إلى العينات المعطاة بـ{(أأنا،بأنا)}⊂Zqن×تي{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }إذا أعاد برنامج الحل مرشحًاs{\displaystyle \mathbf {s} }للجميعأنا{\displaystyle i}، احسب{⟨أأنا،s⟩-بأنا}{\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}إذا كانت العينات مأخوذة من توزيع LWE، فسيتم توزيع نتائج هذه الحسابات وفقًا لذلك.χ{\displaystyle \chi }ولكن إذا كانت العينات عشوائية بشكل منتظم، فسيتم توزيع هذه الكميات بشكل منتظم أيضًا.

حل البحث بافتراض اتخاذ القرار

أما بالنسبة للاتجاه الآخر، فبوجود خوارزمية لحل مشكلة القرار، يمكن حل نسخة البحث على النحو التالي: استعادةs{\displaystyle \mathbf {s} }إحداثية واحدة في كل مرة. للحصول على الإحداثية الأولى،s1{\displaystyle \mathbf {s} _{1}}خمنك∈Zq{\displaystyle k\in \mathbb {Z} _{q}}ثم قم بما يلي. اختر رقمًار∈Zq{\displaystyle r\in \mathbb {Z} _{q}}بشكل عشوائي منتظم. قم بتحويل العينات المعطاة{(أأنا،بأنا)}⊂Zqن×تي{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }كما يلي. احسب{(أأنا+(ر،0،...،0)،بأنا+(رك)/q)}{\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}}أرسل العينات المحولة إلى محلل القرار.

إذا كان التخمينك{\displaystyle k}كان ذلك صحيحًا، فالتحويل يأخذ التوزيعأs،χ{\displaystyle A_{\mathbf {s} ,\chi }}لنفسه، وبخلاف ذلك، منذq{\displaystyle q}إذا كان العدد أوليًا، فإنه يأخذه إلى التوزيع المنتظم. لذا، بالنظر إلى خوارزمية حل متعددة الحدود لمسألة القرار التي تخطئ باحتمالية ضئيلة جدًا، بما أنq{\displaystyle q}محدودة بواسطة متعددة حدود ما فين{\displaystyle n}، لا يستغرق الأمر سوى وقت متعدد الحدود لتخمين كل قيمة ممكنة لـك{\displaystyle k}واستخدم أداة الحل لمعرفة أيها صحيح.

بعد الحصول علىs1{\displaystyle \mathbf {s} _{1}}نتبع إجراءً مماثلاً لكل إحداثية أخرىsج{\displaystyle \mathbf {s} _{j}}أي أننا نحولبأنا{\displaystyle \mathbf {b} _{i}}العينات بنفس الطريقة، وتحويلهاأأنا{\displaystyle \mathbf {a} _{i}}العينات عن طريق الحسابأأنا+(0،...،ر،...،0){\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}، حيثر{\displaystyle r}موجود فيجذ{\displaystyle j^{\text{th}}}إحداثيات. [ 3 ]

أظهر بيكرت [ 4 ] أن هذا الاختزال، مع تعديل بسيط، يصلح لأيq{\displaystyle q}هذا ناتج عن متعددات حدود صغيرة ومميزة (فين{\displaystyle n}) الأعداد الأولية. الفكرة الرئيسية هي إذاq=q1q2⋯qت{\displaystyle q=q_{1}q_{2}\cdots q_{t}}لكلqℓ{\displaystyle q_{\ell }}خمن وتحقق لمعرفة ما إذا كانsج{\displaystyle \mathbf {s} _{j}}متطابق مع0تعديلqℓ{\displaystyle 0\mod q_{\ell }}ثم استخدم نظرية الباقي الصينية لاستعادةsج{\displaystyle \mathbf {s} _{j}}.

متوسط ​​صلابة السطح

أظهر ريجيف [ 3 ] إمكانية الاختزال الذاتي العشوائي لمسائل LWE و DLWE لأيq{\displaystyle q}وχ{\displaystyle \chi }. عينات معينة{(أأنا،بأنا)}{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}منأs،χ{\displaystyle A_{\mathbf {s} ,\chi }}من السهل أن نرى ذلك{(أأنا،بأنا+⟨أأنا،ت⟩)/q}{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}هذه عينات منأs+ت،χ{\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}.

لنفترض إذن وجود مجموعة ماS⊂Zqن{\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}بحيث|S|/|Zqن|=1/بولي⁡(ن){\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}وبالنسبة للتوزيعاتأs′،χ{\displaystyle A_{\mathbf {s} ',\chi }}، معs′←S{\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}، كان DLWE سهلاً.

عندها سيكون هناك شيء مميزأ{\displaystyle {\mathcal {A}}}، الذين، الذين تم إعطاؤهم عينات{(أأنا،بأنا)}{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}، يمكن تحديد ما إذا كانت عشوائية بشكل منتظم أم منأs′،χ{\displaystyle A_{\mathbf {s} ',\chi }}إذا كنا بحاجة إلى التمييز بين العينات العشوائية المنتظمة وأs،χ{\displaystyle A_{\mathbf {s} ,\chi }}، أينs{\displaystyle \mathbf {s} }يتم اختيارها بشكل عشوائي منتظم منZqن{\displaystyle \mathbb {Z} _{q}^{n}}يمكننا ببساطة تجربة قيم مختلفةت{\displaystyle \mathbf {t} }تم أخذ عينة عشوائية منتظمة منZqن{\displaystyle \mathbb {Z} _{q}^{n}}، احسب{(أأنا،بأنا+⟨أأنا،ت⟩)/q}{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}وقم بتغذية هذه العينات إلىأ{\displaystyle {\mathcal {A}}}. منذS{\displaystyle {\mathcal {S}}}يشكل جزءًا كبيرًا منZqن{\displaystyle \mathbb {Z} _{q}^{n}}باحتمالية عالية، إذا اخترنا عددًا متعدد الحدود من القيم لـت{\displaystyle \mathbf {t} }سنجد واحداً بحيثs+ت∈S{\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}}، وأ{\displaystyle {\mathcal {A}}}سوف ينجح في تمييز العينات.

وبالتالي، لا يوجد مثل هذاS{\displaystyle {\mathcal {S}}}يمكن أن توجد، مما يعني أن LWE و DLWE (حتى عامل متعدد الحدود) تكون بنفس الصعوبة في الحالة المتوسطة كما هي في أسوأ الحالات.

نتائج الصلابة

نتيجة ريغيف

بالنسبة لشبكة ذات أبعاد nل{\displaystyle L}، لنفترض أن معامل التنعيمηε(ل){\displaystyle \eta _{\varepsilon }(L)}يشير إلى الأصغرs{\displaystyle s}بحيثρ1/s(ل*∖{0})≤ε{\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }أينل*{\displaystyle L^{*}}هو ثنائيل{\displaystyle L}وρα(x)=هـ-π(|x|/α)2{\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}يتم توسيعها لتشمل المجموعات عن طريق جمع قيم الدالة عند كل عنصر في المجموعة. ليكندل،ر{\displaystyle D_{L,r}}يرمز إلى التوزيع الغاوسي المنفصل علىل{\displaystyle L}عرضر{\displaystyle r}للشبكةل{\displaystyle L}وحقيقير>0{\displaystyle r>0}احتمال كلx∈ل{\displaystyle x\in L}يتناسب معρر(x){\displaystyle \rho _{r}(x)}.

تُعرَّف مسألة أخذ العينات الغاوسية المنفصلة (DGS) على النحو التالي: مثال علىدجيSϕ{\displaystyle DGS_{\phi }}يُعطى بواسطةن{\displaystyle n}شبكة ذات أبعادل{\displaystyle L}وعددر≥ϕ(ل){\displaystyle r\geq \phi (L)}الهدف هو إخراج عينة مندل،ر{\displaystyle D_{L,r}}يُظهر Regev أن هناك انخفاضًا منGapSVP100نγ(ن){\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}لدجيSنγ(ن)/λ(ل*){\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}لأي وظيفةγ(ن)≥1{\displaystyle \gamma (n)\geq 1}.

ثم يوضح ريجيف أنه توجد خوارزمية كمومية فعالة لـدجيS2نηε(ل)/α{\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}تم منحه حق الوصول إلى وسيط لـلدبليوهـq،Ψα{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}للأعداد الصحيحةq{\displaystyle q}وα∈(0،1){\displaystyle \alpha \in (0,1)}بحيثαq>2ن{\displaystyle \alpha q>2{\sqrt {n}}}وهذا يستلزم صعوبة تطبيق نظرية LWE. مع أن برهان هذه الفرضية ينطبق على أيq{\displaystyle q}لإنشاء نظام تشفير، المعاملq{\displaystyle q}يجب أن تكون متعددة الحدود فين{\displaystyle n}.

نتيجة بيكرت

يثبت بيكرت [ 4 ] وجود اختزال زمني احتمالي متعدد الحدود منGapSVPζ،γ{\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }}حل المشكلة في أسوأ الحالاتلدبليوهـq،Ψα{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}استخدامبولي⁡(ن){\displaystyle \operatorname {poly} (n)}عينات للمعلماتα∈(0،1){\displaystyle \alpha \in (0,1)}،γ(ن)≥ن/(αسجل⁡ن){\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}،ζ(ن)≥γ(ن){\displaystyle \zeta (n)\geq \gamma (n)}وq≥(ζ/ن)ωسجل⁡ن){\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})}.

الاستخدام في علم التشفير

تُعدّ مسألة LWE مسألةً متعددة الاستخدامات تُستخدم في بناء العديد من أنظمة التشفير [ 3 ] [ 4 ] [ 6 ] [ 7 ] . في عام 2005، بيّن ريغيف [ 3 ] أن صيغة القرار من مسألة LWE صعبة بافتراض صعوبة مسائل الشبكة الكمومية.جيأصSVPγ{\displaystyle \mathrm {GapSVP} _{\gamma }}(لγ{\displaystyle \gamma }كما سبق) وSأناVPت{\displaystyle \mathrm {SIVP} _{t}}معت=يا(ن/α){\displaystyle t=O(n/\alpha )}في عام 2009، أثبت بيكرت [ 4 ] نتيجة مماثلة بافتراض الصعوبة الكلاسيكية فقط للمسألة ذات الصلة.جيأصSVPζ،γ{\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}إن عيب نتيجة بيكرت هو أنها تستند إلى نسخة غير قياسية من مشكلة أسهل (مقارنة بـ SIVP) وهي GapSVP.

نظام التشفير بالمفتاح العام

اقترح ريغيف [ 3 ] نظام تشفير بالمفتاح العام يعتمد على صعوبة مسألة LWE . يُعدّ كلٌّ من نظام التشفير وإثبات أمانه وصحته نظامًا كلاسيكيًا تمامًا. يتميز النظام بما يلي:م،q{\displaystyle m,q}وتوزيع احتماليχ{\displaystyle \chi }علىتي{\displaystyle \mathbb {T} }يتم تحديد المعايير المستخدمة في إثباتات الصحة والأمان.

  • q≥2{\displaystyle q\geq 2}، عادةً ما يكون عددًا أوليًا بينن2{\displaystyle n^{2}}و2ن2{\displaystyle 2n^{2}}.
  • م=(1+ε)(ن+1)سجل⁡q{\displaystyle m=(1+\varepsilon )(n+1)\log q}لثابت اختياريε{\displaystyle \varepsilon }
  • χ=Ψα(ن){\displaystyle \chi =\Psi _{\alpha (n)}}لα(ن)∈o(1/نسجل⁡ن){\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}، أينΨβ{\displaystyle \Psi _{\beta }}هو توزيع احتمالي يتم الحصول عليه عن طريق أخذ عينة من متغير طبيعي بمتوسط0{\displaystyle 0}والتباين المعياريβ2π{\displaystyle {\frac {\beta }{\sqrt {2\pi }}}}وتقليل النتيجة modulo1{\displaystyle 1}.

يتم تعريف نظام التشفير على النحو التالي:

  • المفتاح الخاص : المفتاح الخاص هوs∈Zqن{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}تم اختيارهم بشكل عشوائي ومتساوٍ.
  • المفتاح العام : اخترم{\displaystyle m}المتجهاتأ1،...،أم∈Zqن{\displaystyle \mathbf {a} _{1},\ldots ,\mathbf {a} _{m}\in \mathbb {Z} _{q}^{n}}بشكل موحد ومستقل. اختر إزاحات الخطأهـ1،...،هـم∈تي{\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }بشكل مستقل وفقًا لـχ{\displaystyle \chi }يتكون المفتاح العام من(أأنا،بأنا=⟨أأنا،s⟩/q+هـأنا)أنا=1م{\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}
  • التشفير : تشفير البتx∈{0،1}{\displaystyle x\in \{0,1\}}يتم ذلك عن طريق اختيار مجموعة فرعية عشوائيةS{\displaystyle S}ل[م]{\displaystyle [m]}ثم تحديدغلاف⁡(x){\displaystyle \operatorname {Enc} (x)}مثل
(∑أنا∈Sأأنا،x2+∑أنا∈Sبأنا){\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i},{\frac {x}{2}}+\sum _{i\in S}b_{i}\right)}
  • فك التشفير : فك تشفير(أ،ب){\displaystyle (\mathbf {a} ,b)}يكون0{\displaystyle 0}لوب-⟨أ،s⟩/q{\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}أقرب إلى0{\displaystyle 0}بدلاً من12{\displaystyle {\frac {1}{2}}}، و1{\displaystyle 1}خلاف ذلك.

يُستنتج إثبات صحة الخوارزمية من اختيار المعاملات وبعض التحليلات الاحتمالية. أما إثبات أمانها فيتم عن طريق اختزالها إلى صيغة القرار لخوارزمية LWE : وهي خوارزمية للتمييز بين عمليات التشفير (بالمعاملات المذكورة أعلاه) لـ0{\displaystyle 0}و1{\displaystyle 1}يمكن استخدامها للتمييز بينأs،χ{\displaystyle A_{s,\chi }}والتوزيع المنتظم علىZqن×تي{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }

نظام تشفير آمن من نوع CCA

اقترح بيكرت [ 4 ] نظامًا آمنًا حتى ضد أي هجوم نص مشفر مختار .

تبادل المفاتيح

طُرحت فكرة استخدام LWE وRing LWE لتبادل المفاتيح، وقُدّمت طلب براءة اختراع لها في جامعة سينسيناتي عام 2011 من قِبل جينتاي دينغ. تستند الفكرة إلى خاصية التجميع في ضرب المصفوفات، وتُستخدم الأخطاء لتوفير الأمان. نُشرت الورقة البحثية [ 8 ] عام 2012 بعد تقديم طلب براءة اختراع مؤقتة في العام نفسه.

تم إثبات أمان البروتوكول بناءً على صعوبة حل مشكلة LWE. في عام 2014، قدم بيكرت مخططًا لنقل المفاتيح [ 9 ] يتبع الفكرة الأساسية نفسها لدينغ، حيث تم استخدام فكرة جديدة تتمثل في إرسال إشارة إضافية من بت واحد للتقريب في تصميم دينغ. يستخدم تطبيق "الأمل الجديد" [ 10 ]، الذي تم اختياره لتجربة جوجل ما بعد الكمومية [ 11 ] ، مخطط بيكرت مع اختلاف في توزيع الخطأ.

توقيع التعلم الحلقي مع الأخطاء (RLWE-SIG)

قام ليوباشيفسكي بإنشاء نسخة RLWE من بروتوكول تعريف فيج-فيات-شامير الكلاسيكي وتحويلها إلى توقيع رقمي في عام 2011. وفي عام 2012، قام كل من غونيسيو وليوباشيفسكي وبوبلمان بتوسيع تفاصيل هذا التوقيع ونشرها في بحثهم بعنوان "التشفير العملي القائم على الشبكة - مخطط توقيع للأنظمة المدمجة". وقد أرست هذه الأبحاث الأساس لمجموعة متنوعة من خوارزميات التوقيع الحديثة، بعضها يعتمد مباشرة على مشكلة التعلم الحلقي مع الأخطاء، وبعضها الآخر لا يرتبط بنفس مشاكل RLWE المعقدة.

انظر أيضاً

مراجع

  1. 1 2 ريغيف، أوديد (2009). "حول الشبكات، والتعلم مع الأخطاء، والرموز الخطية العشوائية، والتشفير". مجلة ACM . 56 (6): 1-40 . arXiv : 2401.03703 . doi : 10.1145/1568318.1568324 . S2CID 207156623 . 
  2. ↑ ليوباشيفسكي، فاديم؛ بيكرت، كريس؛ ريجيف، أوديد (نوفمبر 2013). "حول الشبكات المثالية والتعلم مع الأخطاء على الحلقات" . مجلة ACM . 60 (6): 1-35 . doi : 10.1145/2535925 . ISSN 0004-5411 . S2CID 1606347 .  
  3. 1 2 3 4 5 6 7 8 عوديد ريجيف، "حول الشبكات، والتعلم مع الأخطاء، والرموز الخطية العشوائية، والتشفير"، في وقائع الندوة السنوية السابعة والثلاثين لجمعية ACM حول نظرية الحوسبة (بالتيمور، ماريلاند، الولايات المتحدة الأمريكية: ACM، 2005)، 84-93، http://portal.acm.org/citation.cfm?id=1060590.1060603 .
  4. 1 2 3 4 5 6 كريس بيكرت، "أنظمة التشفير بالمفتاح العام من مشكلة أقصر متجه في أسوأ الحالات: ملخص موسع"، في وقائع الندوة السنوية الحادية والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة (بيثيسدا، ماريلاند، الولايات المتحدة الأمريكية: جمعية الحوسبة الآلية، 2009)، 333-342، http://portal.acm.org/citation.cfm?id=1536414.1536461 .
  5. ↑ بيكرت، كريس (2014-10-01). "التشفير الشبكي للإنترنت". في: موسكا، ميشيل (محرر). التشفير ما بعد الكمي . سلسلة محاضرات في علوم الحاسوب. المجلد 8772. دار نشر سبرينغر الدولية. الصفحات 197-219 . CiteSeerX 10.1.1.800.4743 . doi : 10.1007/978-3-319-11659-4_12 . ISBN    978-3-319-11658-7. S2CID 8123895 . 
  6. ↑ كريس بيكرت وبرينت ووترز، "وظائف الباب الخلفي المفقودة وتطبيقاتها"، في وقائع الندوة السنوية الأربعين لجمعية ACM حول نظرية الحوسبة (فيكتوريا، كولومبيا البريطانية، كندا: ACM، 2008)، 187-196، http://portal.acm.org/citation.cfm?id=1374406 .
  7. ↑ كريج جينتري، كريس بيكرت، وفينود فايكونتاناثان، "أبواب خلفية للشبكات الصلبة والتركيبات التشفيرية الجديدة"، في وقائع الندوة السنوية الأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة (فيكتوريا، كولومبيا البريطانية، كندا: جمعية الحوسبة الآلية، 2008)، 197-206، http://portal.acm.org/citation.cfm?id=1374407 .
  8. ↑ لين، جينتاي دينغ، شيانغ شي، شياودونغ (2012-01-01). "مخطط بسيط لتبادل المفاتيح آمن بشكل قابل للإثبات يعتمد على مشكلة التعلم مع الأخطاء" . أرشيف الطباعة الإلكترونية لعلم التشفير .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  9. ↑ بيكرت، كريس (2014-01-01). "التشفير الشبكي للإنترنت" . أرشيف الطباعة الإلكترونية لعلم التشفير .
  10. ↑ ألكيم، إردم؛ دوكاس، ليو؛ بوبلمان، توماس؛ شواب، بيتر (2015-01-01). "تبادل المفاتيح ما بعد الكمومي - أمل جديد" . أرشيف الطباعة الإلكترونية لعلم التشفير .
  11. ↑ "التجريب في التشفير ما بعد الكمي" . مدونة جوجل للأمن الإلكتروني . تم الاطلاع عليه بتاريخ 8 فبراير 2017 .