هل توجد خوارزميات تشفير للمفتاح العام يصعب هزيمتها باستخدام NP؟[مغلق]

Question

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

يحرر:

يرجى مراجعة قسم "الحوسبة الكمومية في نظرية التعقيد الحسابي" فيمقالة ويكي عن الحواسيب الكمومية. ويشير إلى أن فئة المشكلات التي يمكن لأجهزة الكمبيوتر الكمومية الإجابة عليها (BQP) يُعتقد أنها أسهل تمامًا من NP-Complete.

تحرير 2:

تعد عبارة "استنادًا إلى NP-Complete" طريقة سيئة للتعبير عما أهتم به.

ما كنت أنوي طرحه هو خوارزمية تشفير المفتاح العام مع خاصية أنه يمكن أيضًا استخدام أي طريقة لكسر التشفير لكسر مشكلة NP-Complete الأساسية.وهذا يعني أن كسر التشفير يثبت P=NP.

Answer 1

أرد على هذا الموضوع القديم لأنه سؤال شائع ومهم للغاية، وجميع الإجابات هنا غير دقيقة.

الإجابة المختصرة على السؤال الأصلي هي "لا" بشكل لا لبس فيه.لا توجد أنظمة تشفير معروفة (ناهيك عن أنظمة المفتاح العام) تعتمد على مشكلة NP-Complete (وبالتالي جميعها، في ظل تخفيضات زمنية متعددة الحدود).ومع ذلك، فإن بعضها "أقرب" من البعض الآخر، لذا اسمحوا لي أن أوضح ذلك.

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

ومع ذلك، لا يوجد لدى أنظمة التشفير مثل هذا الدليل.إذا نظرت إلى الأدبيات، مع استثناءات قليلة جدًا (انظر أدناه)، فإن النظريات الأمنية تقرأ كما يلي:

نظرية: مخطط التشفير هذا آمن بشكل كبير ، على افتراض أنه لا توجد خوارزمية متعددة الحدود حل الحالات العشوائية لبعض المشاكل X.

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

مشكلة "الحالات العشوائية" مقابل "أسوأ الحالات" هي ما أعاق العديد من المستجيبين أعلاه.تعتمد أنظمة التشفير من نوع McEliece على إصدار عشوائي خاص جدًا من فك الرموز الخطية - وليس على الإصدار الفعلي لأسوأ الحالات وهو NP-Complete.

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

Answer 2

تم اقتراح بعض أنظمة التشفير المعتمدة على مشاكل NP-hard (مثل ميركل هيلمان نظام التشفير على أساس مشكلة المجموع الفرعي، و نظام التشفير الظهري ناكاش-ستيرن بناءً على مشكلة الحقيبة)، لكنها جميعها مكسورة.لماذا هذا؟المحاضرة 16 لسكوت آرونسون أفكار عظيمة في علوم الكمبيوتر النظرية يقول شيئًا عن هذا، والذي أعتقد أنه يجب عليك اعتباره نهائيًا.ما يقوله هو ما يلي:

من الناحية المثالية، نود إنشاء [مولد تشفير عشوائي زائف] أو نظام تشفير يعتمد أمانه على مشكلة NP-Complete.لسوء الحظ، فإن مشكلات NP-Complete تكون دائمًا في أسوأ الحالات.في التشفير، هذا من شأنه أن يترجم إلى عبارة مثل "هناك". موجود رسالة يصعب فك تشفيرها"، وهذا ليس ضمانًا جيدًا لنظام التشفير!يجب أن يكون من الصعب فك تشفير الرسالة باحتمالية ساحقة.على الرغم من عقود من الجهود، لم يتم اكتشاف طريقة حتى الآن لربط الحالة الأسوأ بالحالة المتوسطة لمشكلات NP الكاملة.ولهذا السبب، إذا أردنا أنظمة تشفير آمنة حسابيًا، فنحن بحاجة إلى وضع افتراضات أقوى من P≠NP.

Answer 3

وكان هذا سؤال مفتوح في عام 1998:

حول إمكانية إسناد تشفير على افتراض أن P! = NP بواسطة أوديد غولدريخ، رحوفوت إسرائيل، شافي غولدفاسر

ومن المجرد: "استنتاجنا هو أن السؤال لا يزال مفتوحا"

-؟ وأتساءل عما إذا كان هذا الذي تغير في العقد الماضي

وتحرير:

وبقدر ما استطيع ان اقول السؤال لا يزال مفتوحا، مع التقدم الذي أحرز مؤخرا نحو جوابا من أي من هذه الخوارزمية موجودا.

نشرت

وعدي Akavia، أوديد غولدريخ، شافي غولدفاسر، ودانا Moshkovitz هذه الورقة في ACM في عام 2006: <لأ href = "http://portal.acm.org/citation.cfm؟doid=1132516.1132614" يختلط = " noreferrer "> في إسناد الوظائف في اتجاه واحد على NP-صلابة " النتائج الرئيسية لدينا هي كما يلي اثنين من نتائج سلبية "

وستانفورد الموقع التعقيد حديقة حيوان يساعد في decripting ما تعنيه تلك النتائج السلبية اثنين.

Answer 4

وحين تم كسر أشكالا عديدة، تحقق من ميركيل-هيلمان ، استنادا إلى شكل من أشكال NP-كاملة "الحقيبة مشكلة".

Answer 5

يقدم التشفير الشبكي رسالة معممة مفادها أنه في الواقع يمكن للمرء تصميم أنظمة تشفير حيث يكون كسر الحالة المتوسطة أمرًا صعبًا مثل حل مشكلة NP-hard معينة (عادةً مشكلة أقصر ناقل أو أقرب مشكلة ناقل).

يمكنني أن أوصي بقراءة قسم المقدمة من http://eprint.iacr.org/2008/521 ومن ثم مطاردة الإشارات إلى أنظمة التشفير.

وراجع أيضا مذكرة المحاضرات في http://www.cs.ucsd.edu/~daniele/CSE207C/, ، ومطاردة روابط لكتاب إذا كنت تريد.

Answer 6

وغوغلينغ لNP-كاملة ومفتاح التشفير العام يجد ايجابيات كاذبة ... التي هي آمنة فعلا. هذا الشعبي الكرتوني يبدو لاظهار والعامة خوارزمية encyption رئيسية على أساس minimium مجموعة الهيمنة مشكلة . مزيد من القراءة عليه ثم يعترف الكذب أن الخوارزمية هي آمنة ... المشكلة الأساسية هي NP-اكتمال ولكن من استخدامها في الخوارزمية PK لا يحافظ صعوبة.

وآخر الكاذبة الإيجابية جوجل تجد: تحليل الشفرات للتشفير Goldreich-غولدفاسر-هاليفي من تشفير " 97 . من الناحية النظرية:

وفي تشفير '97، اقترح Goldreich، غولدفاسر وهاليفي نظام تشفير المفتاح العام استنادا إلى أقرب مشكلة ناقلات في شعرية، والذي يعرف لتكون NP-الثابت. وتبين لنا أن هناك خللا كبيرا في تصميم المخطط الذي فقد اثنين من الآثار: أي معلومات النص المشفر تسرب على النص الأصلي، ومشكلة فك شفرة ciphertexts يمكن تخفيضها إلى أقرب مشكلة خاصة ناقلات الذي هو أسهل بكثير من مشكلة عامة .

Answer 7

وهناك موقع على شبكة الإنترنت التي قد تكون ذات صلة لاهتماماتك: بعد الكم تشفير

Answer 8

وهنا هو بلدي المنطق. تصحيح لي إذا كنت مخطئا.

و(ط) `` كسر '' نظام تشفير هو بالضرورة مشكلة في NP وشارك في NP. (كسر نظام تشفير ينطوي على عكس وظيفة التشفير، التي تعد واحدة الى واحد ومحسوب في الوقت متعدد الحدود. لذلك، وبالنظر إلى النص المشفر، النص الأصلي هو الشهادة التي يمكن التحقق منها في الوقت متعدد الحدود. وهكذا الاستعلام عن نص عادي على أساس المشفر في NP وبالتعاون-NP).

و(ب) إذا كان هناك مشكلة NP-الصلبة في NP وشارك في NP، ثم NP = شارك في NP. (هذه المشكلة سيكون NP-كاملة وبالتعاون-NP منذ أي لغة NP هي تقليص لهذه اللغة المشتركة-NP، NP هي مجموعة فرعية من شارك في NP الآن استخدام التماثل: أي لغة L بالتعاون-NP ديه -L (مجاملة لها) في NP، من حيث -L في المشترك NP --- هذا هو L = --L في NP).

و(ج) I <م> التفكير التي يعتقد عموما أن NP! = شارك في NP، وإلا هناك أدلة كثيرة الحدود الحجم التي الصيغ المنطقية ليست ستيسفيبل.

والخلاصة: التخمين التعقيد نظري يعني أن نظم الترميز NP-الصلبة لا وجود لها

(وإلا، لديك مشكلة NP-الصلبة في NP وشارك في NP، من حيث NP = شارك في NP --- التي يعتقد أنها كاذبة).

Answer 9

وبينما تستند RSA وغيرها من خوارزميات التشفير المستخدمة على نطاق واسع على صعوبة التعميل عدد صحيح (الذي لا يعرف أن يكون NP-كاملة)، وهناك بعض العامة خوارزميات التشفير رئيسية على أساس مشاكل NP-كاملة أيضا. جوجل للبحث عن "المفتاح العمومي" و "NP-الكامل" سوف تكشف عن بعض منها.

و(قلت بشكل غير صحيح قبل أن أجهزة الكمبيوتر الكم من شأنه تسريع مشاكل NP-كاملة، ولكن هذا ليس صحيحا. أقف تصحيحه.)

Answer 10

كما أشار العديد من الملصقات الأخرى، من الممكن أن يعتمد التشفير على مسائل NP-hard أو NP-Complete.

ومع ذلك، فإن الطرق الشائعة للتشفير ستعتمد على الرياضيات الصعبة (أي التي يصعب حلها).الحقيقة هي أنه من الأسهل إجراء تسلسل للأرقام كمفتاح تقليدي بدلاً من إنشاء سلسلة موحدة تحل مشكلة NP الصعبة.لذلك، يعتمد التشفير العملي على مشكلات رياضية لم يثبت بعد أنها NP-hard أو NP-Complete (لذلك فمن الممكن أن تكون بعض هذه المشكلات موجودة في P).

في تشفير الجمل أو RSA، يتطلب كسره كسر اللوغاريتم المنفصل، فانظر إلى هذا ويكيبيديا شرط.

لا توجد خوارزمية فعالة لحساب اللوغاريتمات المنفصلة العامة logbg.الخوارزمية الساذجة هي رفع b إلى قوى أعلى وأعلى k حتى يتم العثور على g المطلوب؛وهذا ما يسمى أحيانًا الضرب التجريبي.تتطلب هذه الخوارزمية تشغيل زمن خطي في حجم المجموعة G وبالتالي أسي في عدد الأرقام في حجم المجموعة.توجد خوارزمية كمومية فعالة بسبب بيتر شور (http://arxiv.org/abs/quant-ph/9508027).

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

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

الاعتقاد السائد هو أن هذه هي NP كاملة، ولكن ربما لا يمكن إثبات ذلك.لاحظ أن أجهزة الكمبيوتر الكمومية قد تكسر التشفير بكفاءة!

Answer 11

ومنذ لا أحد أجاب حقا السؤال لدي لتعطيك تلميح: "McEliece". القيام ببعض عمليات البحث على ذلك. في ثبت خوارزمية التشفير NP-الصلب. انها تحتاج O (ن ^ 2) التشفير ووقت فك التشفير. كان لديه المفتاح العمومي O حجم (ن ^ 2) أيضا، وهو أمر سيء. ولكن هناك تحسينات التي خفض كل هذه الحدود.