افتراض صعوبة الحساب

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

في نظرية التعقيد الحسابي ، يُفترض أن مشكلة معينة لا يمكن حلها بكفاءة (حيث تعني الكفاءة عادةً "في وقت متعدد الحدود "). ولا يُعرف كيفية إثبات الصعوبة (غير المشروطة) لأي مشكلة مفيدة. بدلاً من ذلك، يعتمد علماء الحاسوب على الاختزالات لربط صعوبة مشكلة جديدة أو معقدة بشكل رسمي بافتراض صعوبة حسابية لمشكلة أخرى مفهومة بشكل أفضل.

تُعدّ افتراضات صعوبة الحساب ذات أهمية بالغة في علم التشفير . يتمثل أحد الأهداف الرئيسية في هذا العلم في ابتكار أدوات تشفيرية ذات أمان قابل للإثبات . في بعض الحالات، تُكتشف بروتوكولات تشفيرية تتمتع بأمان نظري للمعلومات ؛ وتُعدّ لوحة المفاتيح لمرة واحدة مثالًا شائعًا على ذلك. مع ذلك، لا يمكن دائمًا تحقيق الأمان النظري للمعلومات؛ في مثل هذه الحالات، يلجأ خبراء التشفير إلى الأمان الحسابي. بعبارة أخرى، يعني هذا أن هذه الأنظمة آمنة بافتراض أن قدرة أي مُهاجم محدودة حسابيًا ، كما هو الحال مع جميع المُهاجمين في الواقع.

تُعد افتراضات الصعوبة الحسابية مفيدة أيضًا لتوجيه مصممي الخوارزميات : فمن غير المرجح أن تدحض خوارزمية بسيطة افتراضًا مدروسًا جيدًا للصعوبة الحسابية مثل P ≠ NP .

مقارنة افتراضات الصلابة

يستخدم علماء الحاسوب طرقًا مختلفة لتقييم أي افتراضات الصعوبة أكثر موثوقية.

قوة افتراضات الصلابة

نقول هذا الافتراضأ{\displaystyle A}أقوى من الافتراضب{\displaystyle B}متىأ{\displaystyle A}يشير إلىب{\displaystyle B}(والعكس خاطئ أو غير معروف). بعبارة أخرى، حتى لو كان الافتراضأ{\displaystyle A}كانت افتراضات خاطئةب{\displaystyle B}قد يظل هذا صحيحًا، والبروتوكولات التشفيرية القائمة على الافتراضاتب{\displaystyle B}قد يظل استخدامها آمناً. لذا، عند تصميم بروتوكولات التشفير، يأمل المرء في إثبات الأمان باستخدام أضعف الافتراضات الممكنة.

افتراضات الحالة المتوسطة مقابل افتراضات أسوأ الحالات

يفترض افتراض الحالة المتوسطة أن مشكلة معينة صعبة في معظم الحالات وفقًا لتوزيع محدد، بينما يفترض افتراض الحالة الأسوأ أن المشكلة صعبة في بعض الحالات فقط. بالنسبة لمشكلة معينة، فإن صعوبة الحالة المتوسطة تعني صعوبة الحالة الأسوأ، لذا فإن افتراض صعوبة الحالة المتوسطة أقوى من افتراض صعوبة الحالة الأسوأ لنفس المشكلة. علاوة على ذلك، حتى بالنسبة للمشكلات غير القابلة للمقارنة، غالبًا ما يُعتبر افتراض مثل فرضية الزمن الأسي أفضل من افتراض الحالة المتوسطة مثل تخمين الزمرة المزروعة . [ 1 ] مع ذلك، بالنسبة للتطبيقات التشفيرية، فإن معرفة أن مشكلة ما لها بعض الحالات الصعبة (أي أن المشكلة صعبة في أسوأ الحالات) غير مجدية لأنها لا توفر لنا طريقة لتوليد حالات صعبة. [ 2 ] لحسن الحظ، يمكن بناء العديد من افتراضات الحالة المتوسطة المستخدمة في التشفير (بما في ذلك RSA ، واللوغاريتم المنفصل ، وبعض مسائل الشبكة ) على افتراضات الحالة الأسوأ من خلال اختزال الحالة الأسوأ إلى الحالة المتوسطة. [ 3 ]

قابلية التكذيب

من الخصائص المرغوبة لفرضية صعوبة الحساب إمكانية دحضها ، أي أنه إذا كانت الفرضية خاطئة، فسيكون من الممكن إثباتها. على وجه الخصوص، قدم ناور (2003) مفهومًا رسميًا لإمكانية دحض التشفير. [ 4 ] باختصار، يُقال إن فرضية صعوبة الحساب قابلة للدحض إذا أمكن صياغتها في شكل تحدٍّ: بروتوكول تفاعلي بين خصم ومُدقِّق كفء، حيث يستطيع الخصم الكفء إقناع المُدقِّق بالقبول إذا وفقط إذا كانت الفرضية خاطئة.

الافتراضات الشائعة حول صعوبة التشفير

توجد العديد من افتراضات الصلابة التشفيرية المستخدمة. فيما يلي قائمة ببعض أكثرها شيوعاً، وبعض بروتوكولات التشفير التي تستخدمها.

تحليل الأعداد الصحيحة إلى عواملها الأولية

بفرض عدد صحيح مركبن{\displaystyle n}وعلى وجه الخصوص، العدد الذي هو ناتج ضرب عددين أوليين كبيرينن=ص⋅q{\displaystyle n=p\cdot q}تتمثل مشكلة تحليل الأعداد الصحيحة إلى عواملها الأولية في إيجادص{\displaystyle p}وq{\displaystyle q}(بشكل عام، ابحث عن الأعداد الأولية)ص1،...،صك{\displaystyle p_{1},\dots ,p_{k}}بحيثن=∏أناصأنا{\displaystyle n=\prod _{i}p_{i}}). يُعدّ إيجاد خوارزمية لتحليل الأعداد الصحيحة إلى عواملها الأولية، والتي تعمل في وقت متعدد الحدود بالنسبة لحجم التمثيل، مشكلة مفتوحة رئيسية (سجل⁡ن{\displaystyle \log n}تعتمد أمان العديد من بروتوكولات التشفير على افتراض أن تحليل الأعداد الصحيحة إلى عواملها الأولية أمر صعب (أي لا يمكن حله في وقت متعدد الحدود). تشمل أنظمة التشفير التي يكافئ أمانها هذا الافتراض توقيع رابين ونظام تشفير أوكاموتو-أوتشياما . وتعتمد أنظمة تشفير أخرى كثيرة على افتراضات أقوى مثل RSA ، ومسائل البواقي ، وإخفاء فاي .

مشكلة RSA

بالنظر إلى عدد مركبن{\displaystyle n}، الأسهـ{\displaystyle e}والرقمج:=مهـ(مoدن){\displaystyle c:=m^{e}(\mathrm {mod} \;n)}تكمن مشكلة RSA في إيجادم{\displaystyle m}يُفترض أن المشكلة صعبة، لكنها تصبح سهلة بالنظر إلى تحليل المعادلة.ن{\displaystyle n}في نظام التشفير RSA ،(ن،هـ){\displaystyle (n,e)}هو المفتاح العام ،ج{\displaystyle c}تشفير الرسالةم{\displaystyle m}، وتحليلن{\displaystyle n}هو المفتاح السري المستخدم لفك التشفير.

مشاكل البقايا

بالنظر إلى عدد مركبن{\displaystyle n}والأعداد الصحيحةy،د{\displaystyle y,d}تتمثل مشكلة الباقي في تحديد ما إذا كان هناك (أو بدلاً من ذلك، إيجاد)x{\displaystyle x}بحيث

xد≡y(مودن).{\displaystyle x^{d}\equiv y{\pmod {n}}.}

تشمل الحالات الخاصة المهمة مشكلة البقايا التربيعية ومشكلة البقايا المركبة القرارية . وكما هو الحال في RSA، يُفترض أن هذه المشكلة (وحالاتها الخاصة) صعبة، ولكنها تصبح سهلة بالنظر إلى تحليلها إلى عوامل.ن{\displaystyle n}تتضمن بعض أنظمة التشفير التي تعتمد على صعوبة حل مشاكل البقايا ما يلي:

افتراض إخفاء فاي

بالنسبة للعدد المركبم{\displaystyle m}ليس من المعروف كيفية حساب دالة أويلر الخاصة بها بكفاءةϕ(م){\displaystyle \phi (m)}يفترض افتراض إخفاء فاي أنه من الصعب حسابϕ(م){\displaystyle \phi (m)}وعلاوة على ذلك، حتى حساب أي عوامل أولية لـϕ(م){\displaystyle \phi (m)}يُعدّ هذا الأمر صعباً. ويُستخدم هذا الافتراض في بروتوكول Cachin–Micali–Stadler PIR . [ 5 ]

مشكلة اللوغاريتم المنفصل (DLP)

العناصر المعطاةأ{\displaystyle a}وب{\displaystyle b}من مجموعةجي{\displaystyle G}تتطلب مسألة اللوغاريتم المنفصل عددًا صحيحًاك{\displaystyle k}بحيثأ=بك{\displaystyle a=b^{k}}. من غير المعروف أن مشكلة اللوغاريتم المنفصل قابلة للمقارنة مع تحليل الأعداد الصحيحة إلى عواملها الأولية، ولكن تعقيداتهما الحسابية مرتبطة ارتباطًا وثيقًا .

تعتمد معظم بروتوكولات التشفير المتعلقة بمشكلة اللوغاريتم المنفصل في الواقع على فرضية ديفي-هيلمان الأقوى : بالنظر إلى عناصر المجموعةز،زأ،زب{\displaystyle g,g^{a},g^{b}}، أينز{\displaystyle g}هو مولد وأ،ب{\displaystyle a,b}هي أعداد صحيحة عشوائية، ومن الصعب العثور عليهازأ⋅ب{\displaystyle g^{a\cdot b}}. تشمل أمثلة البروتوكولات التي تستخدم هذا الافتراض تبادل مفاتيح ديفي-هيلمان الأصلي ، بالإضافة إلى تشفير ElGamal (الذي يعتمد على متغير ديفي-هيلمان القراري (DDH) الأقوى ).

الخرائط متعددة الخطوط

الخريطة متعددة الخطية هي دالةهـ:جي1،...،جين→جيتي{\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}(أينجي1،...،جين،جيتي{\displaystyle G_{1},\dots ,G_{n},G_{T}}هي مجموعات ) بحيث لأيز1،...،زن∈جي1،...جين{\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}وأ1،...،أن{\displaystyle a_{1},\dots ,a_{n}}،

هـ(ز1أ1،...،زنأن)=هـ(ز1،...،زن)أ1⋯أن{\displaystyle e(g_{1}^{a_{1}},\dots ,g_{n}^{a_{n}})=e(g_{1},\dots ,g_{n})^{a_{1}\cdots a_{n}}}.

في التطبيقات التشفيرية، يرغب المرء في إنشاء مجموعاتجي1،...،جين،جيتي{\displaystyle G_{1},\dots ,G_{n},G_{T}}وخريطةهـ{\displaystyle e}بحيث تكون الخريطة وعمليات المجموعة علىجي1،...،جين،جيتي{\displaystyle G_{1},\dots ,G_{n},G_{T}}يمكن حسابها بكفاءة، لكن مشكلة اللوغاريتم المنفصل علىجي1،...،جين{\displaystyle G_{1},\dots ,G_{n}}لا يزال الأمر صعباً. [ 6 ] تتطلب بعض التطبيقات افتراضات أقوى، على سبيل المثال، النظائر متعددة الخطية لافتراضات ديفي-هيلمان.

في الحالة الخاصة لـن=2{\displaystyle n=2}تم إنشاء خرائط ثنائية الخطية ذات أمان موثوق باستخدام اقتران ويل واقتران تيت . [ 7 ] لـن>2{\displaystyle n>2}تم اقتراح العديد من الإنشاءات في السنوات الأخيرة، ولكن تم هدم العديد منها أيضاً، ولا يوجد حالياً إجماع حول مرشح آمن. [ 8 ]

تتضمن بعض أنظمة التشفير التي تعتمد على افتراضات الصعوبة متعددة الخطية ما يلي:

مشاكل الشبكة

تُعدّ مسألة أقصر متجه (SVP) أهمّ مشكلة حسابية أساسية على الشبكات : بالنظر إلى شبكةل{\displaystyle L}أوجد أقصر متجه غير صفريv∈ل{\displaystyle v\in L}تتطلب معظم أنظمة التشفير افتراضات أقوى بشأن متغيرات مسألة المتجهات المستقلة القصيرة (SVP)، مثل مسألة المتجهات المستقلة القصيرة (SIVP) ، ومسألة المتجهات المستقلة القصيرة ذات الفجوة (GapSVP )، [ 10 ] أو مسألة المتجهات المستقلة القصيرة الفريدة (Unique-SVP). [ 11 ]

يُعدّ افتراض صلابة الشبكة الأكثر فائدة في علم التشفير هو لمشكلة التعلّم مع الأخطاء (LWE): بالنظر إلى العينات لـ(x،y){\displaystyle (x,y)}، أينy=و(x){\displaystyle y=f(x)}لبعض الدوال الخطيةو(⋅){\displaystyle f(\cdot )}من السهل تعلمهو(⋅){\displaystyle f(\cdot )}باستخدام الجبر الخطي . في مسألة LWE، تحتوي مدخلات الخوارزمية على أخطاء، أي لكل زوجy≠و(x){\displaystyle y\neq f(x)}باحتمالية ضئيلة . يُعتقد أن الأخطاء تجعل المشكلة غير قابلة للحل (بالنسبة للمعاملات المناسبة)؛ على وجه الخصوص، هناك اختزالات معروفة من أسوأ الحالات إلى متوسط ​​الحالات من متغيرات SVP. [ 12 ]

بالنسبة للحواسيب الكمومية ، تُعدّ مسائل التحليل إلى عوامل أولية واللوغاريتمات المنفصلة سهلة، لكن يُعتقد أن مسائل الشبكة صعبة. [ 13 ] وهذا يجعل بعض أنظمة التشفير القائمة على الشبكة مرشحة للتشفير ما بعد الكمومي .

تتضمن بعض أنظمة التشفير التي تعتمد على صعوبة مشاكل الشبكة ما يلي:

افتراضات الصلابة غير المشفرة

إلى جانب تطبيقاتها في التشفير، تُستخدم افتراضات الصعوبة في نظرية التعقيد الحسابي لتقديم أدلة على صحة العبارات الرياضية التي يصعب إثباتها بشكل مطلق. في هذه التطبيقات، يُثبت أن افتراض الصعوبة يستلزم عبارة معينة مرغوبة في نظرية التعقيد، بدلاً من إثبات صحة العبارة نفسها. أشهر هذه الافتراضات هو افتراض أن P ≠ NP ، [ 14 ] ، ومن الأمثلة الأخرى فرضية الزمن الأسي ، [ 15 ] وتخمين الزمرة المزروعة ، وتخمين الألعاب الفريدة . [ 16 ]

مسائل صعبة من الفئة ج

من المعروف أن العديد من مسائل الحساب في أسوأ الحالات صعبة أو حتى كاملة بالنسبة لبعض فئات التعقيد.ج{\displaystyle C}وخاصةً المسائل الصعبة من فئة NP (ولكنها غالبًا ما تكون أيضًا صعبة من فئة PSPACE ، وصعبة من فئة PPAD ، وما إلى ذلك). وهذا يعني أنها على الأقل بنفس صعوبة أي مسألة في هذه الفئة.ج{\displaystyle C}إذا كانت المشكلةج{\displaystyle C}إذا كانت المسألة صعبة (بالنسبة للاختزالات متعددة الحدود)، فلا يمكن حلها بواسطة خوارزمية متعددة الحدود إلا إذا تم افتراض صعوبة الحساب.P≠ج{\displaystyle P\neq C}هذا غير صحيح.

فرضية الزمن الأسي (ETH) ومتغيراتها

تُعدّ فرضية الزمن الأسي (ETH) تعزيزًا لـP≠شمالP{\displaystyle P\neq NP}يفترض هذا الافتراض صعوبة حل مشكلة الإرضاء المنطقي (SAT)، والتي تفترض أن هذه المشكلة لا تملك خوارزمية ذات وقت متعدد الحدود فحسب، بل تتطلب أيضًا وقتًا أُسّيًا (2Ω(ن){\displaystyle 2^{\أوميغا (ن)}}[ 17 ] وهناك افتراض أقوى، يُعرف باسم فرضية الزمن الأسي القوي (SETH) ، يفترض أنك{\displaystyle k}يتطلب اختبار SAT2(1-εك)ن{\displaystyle 2^{(1-\varepsilon _{k})n}}الوقت، أينليمك→∞εك=0{\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}تسمح افتراضات صعوبة الحساب ETH وSETH وما يتصل بها باستنتاج نتائج دقيقة حول التعقيد، مثل النتائج التي تميز بين الوقت متعدد الحدود والوقت شبه متعدد الحدود ، [ 1 ] أو حتىن1.99{\displaystyle n^{1.99}}عكسن2{\displaystyle n^{2}}[ 18 ] هذه الافتراضات مفيدة أيضًا في التعقيد المُعَلم . [ 19 ]

افتراضات الصلابة في الحالة المتوسطة

تُفترض بعض المسائل الحسابية صعبة في المتوسط ​​على توزيع معين من الحالات. على سبيل المثال، في مسألة الزمرة المزروعة ، يكون المدخل عبارة عن رسم بياني عشوائي تم اختياره عن طريق أخذ عينة من رسم بياني عشوائي من نوع إردوش-ريني ، ثم "زرع" رسم بياني عشوائي آخر.ك{\displaystyle k}-clique، أي ربطك{\displaystyle k}عقد عشوائية بشكل منتظم (حيث2سجل2⁡ن≪ك≪ن{\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}والهدف هو العثور على المزروعك{\displaystyle k}-clique (وهي فريدة من نوعها). [ 20 ] مثال آخر مهم هو فرضية فيج ، وهي فرضية صعوبة حسابية تتعلق بحالات عشوائية من 3-SAT (يتم أخذ عينات منها للحفاظ على نسبة محددة من البنود إلى المتغيرات). [ 21 ] تُعد فرضيات الصعوبة الحسابية في الحالة المتوسطة مفيدة لإثبات صعوبة الحالة المتوسطة في تطبيقات مثل الإحصاء، حيث يوجد توزيع طبيعي على المدخلات. [ 22 ] بالإضافة إلى ذلك، تم استخدام فرضية صعوبة الزمرة المزروعة أيضًا للتمييز بين تعقيد الوقت في أسوأ الحالات متعدد الحدود وشبه متعدد الحدود لمسائل أخرى، [ 23 ] على غرار فرضية الوقت الأسي .

ألعاب فريدة

تُعدّ مشكلة غطاء الملصق الفريد مشكلة إرضاء قيود، حيث كل قيدج{\displaystyle C}يتضمن متغيرينx،y{\displaystyle x,y}ولكل قيمة منx{\displaystyle x}هناك قيمة فريدة لـy{\displaystyle y}ذلك يرضيج{\displaystyle C}يُعد تحديد ما إذا كان من الممكن تلبية جميع القيود أمرًا سهلاً، لكن فرضية اللعبة الفريدة (UGC) تفترض أن تحديد ما إذا كان من الممكن تلبية جميع القيود تقريبًا ((1-ε){\displaystyle (1-\varepsilon )}-كسر، لأي ثابتε>0{\displaystyle \varepsilon >0}) يمكن إرضاؤها أو لا يمكن إرضاؤها تقريبًا (ε{\displaystyle \varepsilon }يُعدّ حلّ مسألة (الكسر) التي يمكن تحقيقها مسألةً صعبةً من نوع NP. [ 16 ] من المعروف أن مسائل التقريب غالبًا ما تكون صعبةً من نوع NP بافتراض UGC؛ وتُعرف هذه المسائل باسم مسائل UG-hard. على وجه الخصوص، بافتراض UGC، توجد خوارزمية برمجة شبه محددة تحقق ضمانات تقريب مثالية للعديد من المسائل المهمة. [ 24 ]

توسعة المجموعة الصغيرة

ترتبط مشكلة توسيع المجموعة الصغيرة (SSE) ارتباطًا وثيقًا بمشكلة تغطية التسميات الفريدة : بالنظر إلى رسم بيانيجي=(V،هـ){\displaystyle G=(V,E)}، ابحث عن مجموعة صغيرة من الرؤوس (بحجمن/سجل⁡(ن){\displaystyle n/\log(n)}) التي يكون توسع حوافها في حده الأدنى. من المعروف أنه إذا كان تقريب SSE صعبًا، فإن تغطية التسميات الفريدة تكون صعبة أيضًا. لذا، فإن فرضية توسع المجموعة الصغيرة ، التي تفترض صعوبة تقريب SSE، هي فرضية أقوى (وإن كانت وثيقة الصلة) من تخمين اللعبة الفريدة. [ 25 ] من المعروف أن بعض مسائل التقريب صعبة من نوع SSE [ 26 ] (أي أنها على الأقل بنفس صعوبة تقريب SSE).

تخمين المجموع الثلاثي

بالنظر إلى مجموعة منن{\displaystyle n}في مسألة مجموع ثلاثة أعداد (3SUM)، يُطرح السؤال عما إذا كان هناك ثلاثة أعداد مجموعها يساوي صفرًا. توجد خوارزمية لحل 3SUM بزمن تربيعي ، ويُفترض أنه لا توجد خوارزمية قادرة على حل 3SUM بزمن "أقل من التربيعي فعليًا": ويُفترض في فرضية 3SUM صعوبة الحساب، أي أنه لا يوجديا(ن2-ε){\displaystyle O(n^{2-\varepsilon })}خوارزميات زمنية لـ 3SUM (لأي ثابت)ε>0{\displaystyle \varepsilon >0}). هذه الفرضية مفيدة لإثبات الحدود الدنيا شبه التربيعية للعديد من المسائل، وخاصة من الهندسة الحسابية . [ 27 ]

انظر أيضاً

مراجع

  1. 1 2 برافرمان، مارك ؛ كو، يونغ كون؛ وينشتاين، عمري (2015). "تقريب أفضل توازن ناش فينo(سجل⁡(ن)){\displaystyle n^{o(\log(n))}}"الزمن يكسر فرضية الزمن الأسي". ندوة حول الخوارزميات المنفصلة (SODA) . جمعية الرياضيات الصناعية والتطبيقية . الصفحات 970-982 . doi : 10.1137/1.9781611973730.66 . ISBN  978-1-61197-374-7.
  2. ↑ J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/CRC Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
  3. ↑ غولدواسير، شافي ؛ كالاي، يائيل تاومان (2016). "الافتراضات التشفيرية: ورقة موقف". مؤتمر نظرية التشفير (TCC) 2016. سلسلة محاضرات في علوم الحاسوب. المجلد 9562. سبرينغر. الصفحات 505-522 . doi : 10.1007/978-3-662-49096-9_21 . ISBN   978-3-662-49095-2.
  4. ↑ ناور، موني (2003). "حول الافتراضات والتحديات المتعلقة بالتشفير". في: بونيه، دان (محرر). التطورات في علم التشفير - CRYPTO 2003: المؤتمر الدولي السنوي الثالث والعشرون لعلم التشفير، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 17-21 أغسطس 2003، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد 2729. برلين: سبرينغر. الصفحات 96-109 . doi : 10.1007/978-3-540-45146-4_6 . ISBN   978-3-540-40674-7MR 2093188 .​ 
  5. ↑ كاشين، كريستيان؛ ميكالي، سيلفيو؛ ستادلر، ماركوس (1999). "استرجاع المعلومات الخاص حسابيًا باستخدام الاتصال متعدد اللوغاريتمات". في: ستيرن، جاك (محرر). التطورات في علم التشفير - يورو كريبت 99. سلسلة محاضرات في علوم الحاسوب. المجلد 1592. سبرينغر. الصفحات 402-414 . doi : 10.1007/3-540-48910-X_28 . ISBN   978-3-540-65889-4. S2CID 29690672 . 
  6. ↑ بونيه، دان ؛ سيلفربيرغ، أليس (2002). "تطبيقات الأشكال متعددة الخطية في علم التشفير" . أرشيف الطباعة الإلكترونية لعلم التشفير .
  7. ^ دوتا، راتنا؛ باروا، رنا؛ ساركار، بالاش (2004). "بروتوكولات التشفير القائمة على الاقتران : دراسة استقصائية" . أرشيف الطباعة الإلكترونية لعلم التشفير . 
  8. ↑ ألبريشت، مارتن ر. "هل تم كسر نظام التشفير المتدرج بعد؟" . تم الاسترجاع في 22 مارس 2018 .
  9. ↑ غارغ، سانجام؛ جينتري، كريغ؛ هاليفي، شاي؛ رايكوفا، ماريانا؛ ساهي، أميت؛ ووترز، برنت (2016). "إخفاء عدم التمييز بين المرشحين والتشفير الوظيفي لجميع الدوائر" (ملف PDF) . مجلة SIAM للحوسبة . 45 (3). SIAM: 882-929 . doi : 10.1137/14095772X .
  10. ↑ بيكرت، كريس (2009). "أنظمة التشفير بالمفتاح العام من مشكلة أقصر متجه في أسوأ الحالات: ملخص موسع". وقائع الندوة السنوية الحادية والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC) . الصفحات 333-342 . doi : 10.1145/1536414.1536461 . 
  11. ↑ أجتاي، ميكلوس ؛ دورك، سينثيا (1997). "نظام تشفير بالمفتاح العام مع تكافؤ أسوأ الحالات/متوسط ​​الحالات". وقائع الندوة السنوية التاسعة والعشرين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC) . الصفحات 284-293 . doi : 10.1145/258533.258604 . ISBN  0-89791-888-6.
  12. ↑ ريغيف، أوديد (2010). "مشكلة التعلم مع الأخطاء (دراسة استقصائية مدعوة)". مؤتمر التعقيد الحسابي (CCC) 2010. ص 191-204 . doi : 10.1109 /CCC.2010.26 . ISBN  978-1-4244-7214-7.
  13. ↑ بيكرت، كريس (2016). "عقد من التشفير الشبكي" . أسس واتجاهات في علوم الحاسوب النظرية . 10 (4): 283-424 . doi : 10.1561/0400000074 .
  14. ↑ فورتناو، لانس (2009). "وضع مشكلة P مقابل NP" (ملف PDF) . مجلة اتصالات ACM . 52 (9): 78-86 . doi : 10.1145/1562164.1562186 . S2CID 5969255. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 24 فبراير 2011. .
  15. ↑ ووجينجر، جيرهارد (2003). "الخوارزميات الدقيقة للمسائل الصعبة من نوع NP: دراسة استقصائية". التحسين التوافقي - يوريكا، أنت تتقلص! سلسلة محاضرات في علوم الحاسوب. المجلد 2570. سبرينغر-فيرلاغ. الصفحات 185-207 . doi : 10.1007/3-540-36478-1_17 . ISBN   978-3-540-00580-3. S2CID 289357 . .
  16. 1 2 خوت، سوبهاش (2010). "حول تخمين الألعاب الفريدة". وقائع المؤتمر الخامس والعشرين لمعهد مهندسي الكهرباء والإلكترونيات حول التعقيد الحسابي (ملف PDF) . الصفحات 99-121 . doi : 10.1109/CCC.2010.19 . .
  17. ↑ إمباغليازو، راسل ؛ باتوري، راماموهان (1999). "تعقيد k-SAT". وقائع المؤتمر الرابع عشر لمعهد مهندسي الكهرباء والإلكترونيات حول التعقيد الحسابي . الصفحات 237-240 . doi : 10.1109/CCC.1999.766282 . ISBN  0-7695-0075-7.
  18. ↑ عبود، أمير؛ فاسيلفسكا-ويليامز، فيرجينيا ؛ وايمان، أورين (2014). "نتائج محاذاة التسلسلات بشكل أسرع". الأوتوماتا واللغات والبرمجة - الندوة الدولية الحادية والأربعون، ICALP 2014. سلسلة محاضرات في علوم الحاسوب. المجلد 8572. الصفحات 39-51 . doi : 10.1007/978-3-662-43948-7_4 . ISBN   978-3-662-43947-0.
  19. ↑ لوكشتانوف، دانيال؛ ماركس، دانيال؛ سوراب، ساكيت (2011). "الحدود الدنيا القائمة على فرضية الزمن الأسي" . نشرة الجمعية الأوروبية لعلوم الحاسوب التطبيقية . 105 : 41-72 .
  20. ↑ أرورا، سانجيف ؛ باراك، بواز (2009). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج. ص 362-363 . ISBN  9780521424264..
  21. ↑ فيج، أورييل (2002). "العلاقات بين تعقيد الحالة المتوسطة وتعقيد التقريب". وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC) . الصفحات 534-543 . doi : 10.1145/509907.509985 . ISBN  1-58113-495-9.
  22. ↑ بيرتيه، كوينتين؛ ريغوليه، فيليب (2013). "الحدود الدنيا لنظرية التعقيد للكشف عن المكونات الرئيسية المتفرقة". COLT 2013. ص 1046-1066 . 
  23. ↑ هازان، إيلاد؛ كراوثغامر، روبرت (2011). "ما مدى صعوبة تقريب أفضل توازن ناش؟". مجلة SIAM للحوسبة . 40 (1): 79-91 . CiteSeerX 10.1.1.139.7326 . doi : 10.1137/090766991 . 
  24. ↑ راغافيندرا، براساد (2008). "الخوارزميات المثلى ونتائج عدم التقريب لكل مسألة إرضاء القيود؟". المؤتمر السنوي الأربعون لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC) 2008. الصفحات 245-254 . doi : 10.1145/1374376.1374414 . ISBN  978-1-60558-047-0.
  25. ↑ راغافيندرا، براساد؛ ستويرر، ديفيد (2010). "توسيع الرسم البياني وتخمين الألعاب الفريدة". المؤتمر السنوي الثاني والأربعون لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC) 2010. الصفحات 755-764 . doi : 10.1145/1806689.1806792 . ISBN  978-1-4503-0050-6.
  26. ↑ وو، يو؛ أوسترين، بير؛ بيتاسي، تونيان؛ ليو، ديفيد (2014). "عدم إمكانية تقريب عرض الشجرة والمشاكل ذات الصلة" . مجلة أبحاث الذكاء الاصطناعي . 49 : 569-600 . doi : 10.1613/jair.4030 .
  27. ↑ فاسيلفسكا ويليامز، فيرجينيا (2018). "حول بعض المسائل الدقيقة في الخوارزميات والتعقيد". المؤتمر الدولي للحسابات المعقدة 2018 (ملف PDF) .