Diffie–Hellman problem
ডিফি-হেলম্যান সমস্যা (ডিএইচপি) একটি গাণিতিক সমস্যা যা হুইটফিল্ড ডিফি এবং মার্টিন হেলম্যান ক্রিপ্টোগ্রাফির প্রসঙ্গে প্রথম প্রস্তাব করেছিলেন। এই সমস্যার প্রেরণা হল যে অনেক নিরাপত্তা ব্যবস্থা একমুখী ফাংশন ব্যবহার করেঃ গাণিতিক ক্রিয়াকলাপ যা গণনা করা দ্রুত, কিন্তু বিপরীত করা কঠিন। উদাহরণস্বরূপ, তারা একটি বার্তা এনক্রিপ্ট করতে সক্ষম করে, তবে এনক্রিপশনটি বিপরীত করা কঠিন। যদি ডিএইচপি সমাধান করা সহজ হত, তবে এই ব্যবস্থাগুলি সহজেই ভেঙে যেত। সমস্যার বিবরণ ডিফি-হেলম্যান সমস্যাটি অনানুষ্ঠানিকভাবে নিম্নরূপ বর্ণনা করা হয়েছেঃ একটি উপাদান জি এবং জিএক্স এবং জিআই-এর মান দেওয়া হলে, জিএক্সআই-এর মান কত? আনুষ্ঠানিকভাবে, g হল কিছু গোষ্ঠীর একটি উৎপাদক (সাধারণত একটি সসীম ক্ষেত্রের গুণিতক গোষ্ঠী বা একটি উপবৃত্তাকার বক্ররেখা গোষ্ঠী) এবং x এবং y এলোমেলোভাবে নির্বাচিত পূর্ণসংখ্যা। উদাহরণস্বরূপ, ডিফি-হেলম্যান কী এক্সচেঞ্জ-এ, একটি ইভস্ড্রপার প্রোটোকলের অংশ হিসাবে জিএক্স এবং জিএক্স বিনিময় পর্যবেক্ষণ করে এবং উভয় পক্ষই ভাগ করা কী জিএক্সআই গণনা করে। ডিএইচপি সমাধানের একটি দ্রুত উপায় ডিফি-হেলম্যান কী এক্সচেঞ্জ এবং এলগ্যামাল এনক্রিপশন সহ এর অনেকগুলি রূপের গোপনীয়তা লঙ্ঘন করার অনুমতি দেবে। গণনামূলক জটিলতা ক্রিপ্টোগ্রাফিতে, নির্দিষ্ট গোষ্ঠীর জন্য, এটি ধরে নেওয়া হয় যে ডিএইচপি কঠিন, এবং এটিকে প্রায়শই ডিফি-হেলম্যান অনুমান বলা হয়। সমস্যাটি কয়েক দশক ধরে তদন্তাধীন রয়েছে এবং কোনও "সহজ" সমাধান এখনও প্রচারিত হয়নি। 2006 সালের হিসাবে, ডিএইচপি সমাধানের জন্য সবচেয়ে কার্যকর উপায় হল বিচ্ছিন্ন লগারিদম সমস্যা (ডিএলপি) সমাধান করা, যা হল x প্রদত্ত g এবং gx খুঁজে বের করা। প্রকৃতপক্ষে, উল্লেখযোগ্য অগ্রগতি (ডেন বোয়ার, মৌরার, ওল্ফ, বোনহ এবং লিপটন দ্বারা) দেখানো হয়েছে যে অনেক গোষ্ঠীতে ডিএইচপি প্রায় ডিএলপির মতোই কঠিন। সাধারণ গোষ্ঠী (নেচায়েভ এবং শুপ দ্বারা) ব্যতীত, ডিএইচপি বা ডিএলপি একটি কঠিন সমস্যা বলে আজ অবধি কোনও প্রমাণ নেই। একটি প্রমাণ যে উভয় সমস্যাই কঠিন, তা বোঝায় যে পি ষ্ণ এনপি। অন্যান্য রূপগুলি ডিফি-হেলম্যান সমস্যার অনেক রূপ বিবেচনা করা হয়েছে। সবচেয়ে উল্লেখযোগ্য বৈকল্পিক হল ডিসিশনাল ডিফি-হেলম্যান প্রবলেম (ডিডিএইচপি), যা জি, জিএক্স এবং জি দেওয়া একটি র্যান্ডম গ্রুপ উপাদান থেকে জিএক্সআইকে আলাদা করে। কখনও কখনও ডি. এইচ. পি-কে ডি. ডি. এইচ. পি থেকে আরও স্পষ্টভাবে আলাদা করার জন্য গণনামূলক ডিফি-হেলম্যান সমস্যা (সি. ডি. এইচ. পি) বলা হয়। সম্প্রতি পেয়ারিং সহ গ্রুপগুলি জনপ্রিয় হয়ে উঠেছে এবং এই গ্রুপগুলিতে ডিডিএইচপি সহজ, তবুও ডিএইচপি এখনও কঠিন বলে মনে করা হয়। ডিএইচপি-র কম উল্লেখযোগ্য রূপগুলির জন্য রেফারেন্সগুলি দেখুন। রেফারেন্স বি. ডেন বোয়ার, ডিফি-হেলম্যান অ্যাডভান্সস ইন ক্রিপ্টোলজি-ক্রিপটো 88, লেকচার নোটস ইন কম্পিউটার সায়েন্স 403, স্প্রিংগার, পৃ. 530,1988-এ নির্দিষ্ট মৌলিক সংখ্যার জন্য বিচ্ছিন্ন লগের মতোই শক্তিশালী। ইউ. এম. মৌরার এবং এস. ওল্ফ, ডিফি-হেলম্যান ওরাকল ইন অ্যাডভান্সস ইন ক্রিপ্টোলজি-ক্রিপটো 96, (এন. কোব্লিটজ, সংস্করণ। ), লেকচার নোটস ইন কম্পিউটার সায়েন্স 1070, স্প্রিঙ্গার, পিপি। 268-282,1996। ডি. বোনেহ এবং আর. জে. লিপটন, অ্যালগরিদমস ফর ব্ল্যাক-বক্স ফিল্ডস অ্যান্ড দেয়ার অ্যাপ্লিকেশন টু ক্রিপ্টোটোগ্রাফি ইন অ্যাডভান্সস ইন ক্রিপ্টোলজি-ক্রিপটো 96, (এন. কোব্লিটজ, সংস্করণ। ), লেকচার নোটস ইন কম্পিউটার সায়েন্স 1070, স্প্রিঙ্গার, পিপি। 283-297,1996। এ. মুজেরো, এন. পি. স্মার্ট এবং এফ. ভারকাউটেরান, ব্যবহারিক প্রয়োগগুলিতে ব্যবহৃত উপবৃত্তাকার বক্ররেখার জন্য ডি. এইচ. পি এবং ডি. এল. পি-র মধ্যে সমতুল্যতা, এল. এম. এস. জে. কম্পিউট। গণিত., 7, পৃ. 50-72,2004। [www.lms.ac.uk] দেখুন। ডি. আর. এল. ব্রাউন এবং আর. পি. গ্যালান্ট, দ্য স্ট্যাটিক ডিফি-হেলম্যান প্রবলেম, আইএসিআর ইপ্রিন্ট 2004/306। ভি. আই. নেচায়েভ, বিচ্ছিন্ন লগারিদমের জন্য একটি নির্ধারিত অ্যালগরিদমের জটিলতা, গাণিতিক নোটস, 55 (2), পৃ। 165-172,1994। ভি. শুপ, লোয়ার বাউন্ডস ফর ডিসক্রিট লগারিদমস অ্যান্ড রিলেটেড প্রবলেম ইন অ্যাডভান্সস ইন ক্রিপ্টোলজি-ইইউআরওসিআরওয়াইপিটি 97, (ডব্লিউ. ফুমি, সংস্করণ। ), লেকচার নোটস ইন কম্পিউটার সায়েন্স 1233, স্প্রিঙ্গার, পিপি। 256-266,1997। গণনামূলক কঠোরতা অনুমান সীমাবদ্ধ ক্ষেত্র