أمن مبرهن

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

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

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

تمت كتابة العديد من التفنيدات من قِبل أوديد جولدرايش وأفي ويجديرسون (Avi Wigderson) وغيرهما من الباحثين المتخصصين في هذا المجال. وكتب إيفان دامجارد (Ivan Damgård) لاحقًا بحثا عبر فيه عن رأيه في ICALP 2007 بشأن المشاكل التقنية، وحظي بتوصية سكوت أرونسون (Scott Aaronson) باعتباره بحثًا تفصيليًا.

مراجع 

تعمية