আধুনিক ক্রিপ্টোগ্রাফি প্রাচীনকালের কেবল সংকেত তৈরি বা কোড ভাঙার কলাকৌশল নয়; এটি মূলত ডিসক্রিট গণিত এবং তাত্ত্বিক কম্পিউটেশনাল জটিলতা বিজ্ঞানের (Computational Complexity Theory) এক অনন্য শাখা। কোনো অ্যালগরিদম শুধু “ভেঙে ফেলা কঠিন” বলে চালানোর দিন শেষ—আধুনিক নিরাপত্তা ব্যবস্থায় প্রতিটি স্কিমের নিরাপত্তা গাণিতিক রিডাকশনের মাধ্যমে মৌলিক গাণিতিক কাঠামোর ওপর প্রমাণ করা হয়। এই সমগ্র কাঠামোর ভিত্তিপ্রস্তর হলো একমুখী ফাংশন (One-Way Functions – OWFs), যার বাস্তব অস্তিত্ব সরাসরি নির্দেশ করে (P
eq NP)।
১. একমুখী ফাংশনের (OWF) গাণিতিক সংজ্ঞা
একটি বহুপদী-সময়ে হিসাবযোগ্য ফাংশন (f: {0,1}^* o {0,1}^*)-কে তখনই একটি শক্তিশালী একমুখী ফাংশন (Strong One-Way Function) বলা হয় যখন তা দুটি কঠোর গাণিতিক শর্ত পূরণ করে:
- গণনায় সহজ (Easy to compute): একটি ডিটারমিনিস্টিক পলিনোমিয়াল-টাইম অ্যালগরিদম (M) থাকবে যা যেকোনো ইনপুট (x)-এর জন্য দ্রুত (f(x)) নির্ণয় করতে পারে।
- বিপরীতকরণে কঠিন (Hard to invert): যেকোনো প্রোবাবিলিস্টিক পলিনোমিয়াল-টাইম (PPT) আক্রমণকারী (mathcal{A}), যেকোনো ধনাত্মক বহুপদী (p(n)), এবং পর্যাপ্ত বৃহৎ সিকিউরিটি প্যারামিটার (n)-এর জন্য:
[
Pr_{x leftarrow {0,1}^n} left[ mathcal{A}(1^n, f(x)) in f^{-1}(f(x))
ight] le rac{1}{p(n)} = ext{negl}(n)
]
যেখানে সম্ভাব্যতা হিসাব করা হয় ইনপুট (x)-এর সমবণ্টন এবং আক্রমণকারীর নিজস্ব অভ্যন্তরীণ র্যান্ডমনেসের ওপর ভিত্তি করে।
যদি তাত্ত্বিকভাবে (P = NP) প্রমাণিত হয়, তবে নন-ডিটারমিনিস্টিক বহুপদী যাচাইকারী দ্বারা যেকোনো সমীকরণ (f(x) = y) মুহূর্তের মধ্যে বহুপদী সময়ে সমাধান করা সম্ভব হবে, ফলে মহাবিশ্বে কোনো একমুখী ফাংশনের অস্তিত্ব থাকবে না। অর্থাৎ একমুখী ফাংশন থাকার পূর্বশর্তই হলো (P
eq NP)।
২. হার্ড-কোর প্রেডিকেট ও গোল্ডরাইখ-লেভিন উপপাদ্য
একটি ফাংশন একমুখী হলেও তার আউটপুট (f(x)) থেকে ইনপুট (x)-এর কিছু আংশিক তথ্য (যেমন প্যারিটি বিট বা প্রথম কয়েকটি ডিজিট) অনুমান করা সম্ভব হতে পারে। ক্রিপ্টোগ্রাফিক সুরক্ষার জন্য এমন একটি একক বিট প্রয়োজন যা আউটপুট জানার পরও অনুমান করা একটি সাধারণ কয়েন টসের চেয়ে ভালো হবে না। একে বলা হয় হার্ড-কোর প্রেডিকেট (Hard-Core Predicate):
[
Pr_{x leftarrow {0,1}^n} left[ mathcal{A}(1^n, f(x)) = B(x)
ight] le rac{1}{2} + ext{negl}(n)
]
১৯৮৯ সালে ওদেদ গোল্ডরাইখ এবং লিওনিড লেভিন তাদের বিশ্ববিখ্যাত উপপাদ্যে প্রমাণ করেন যে, প্রতিটি একমুখী ফাংশন থেকেই একটি সার্বজনীন হার্ড-কোর প্রেডিকেট তৈরি করা যায়। যদি (|x| = |r| = n) হয় এবং (g(x, r) = (f(x), r)) সংজ্ঞায়িত করা হয়, তবে মডুলো ২ ইনার প্রোডাক্ট:
[
B(x, r) = langle x, r
angle = bigoplus_{i=1}^n x_i r_i pmod 2
]
ফাংশন (g)-এর একটি নিশ্চিত হার্ড-কোর প্রেডিকেট। হাদামার্দ কোড এবং ফুরিয়ার বিশ্লেষণের সাহায্যে এটি প্রমাণ করা হয় যে, এই একক বিটটি যদি কোনো অ্যালগরিদম (rac{1}{2} + psilon) সুবিধায় অনুমান করতে পারে, তবে সে পুরো (x)-কেই (mathcal{O}(n^2 psilon^{-2})) সময়ে পুনরুদ্ধার করতে সক্ষম হবে।
৩. সিউডোর্যান্ডম জেনারেটর (PRG) ও হিল (HILL) উপপাদ্য
একটিমাত্র একমুখী ফাংশন এবং তার হার্ড-কোর প্রেডিকেট ব্যবহার করে একটি সিউডোর্যান্ডম জেনারেটর (PRG) তৈরি করা যায়। এটি এমন একটি ডিটারমিনিস্টিক ফাংশন (G: {0,1}^n o {0,1}^{n + ll(n)}), যা একটি ছোট এলোমেলো বীজকে (seed) প্রসারিত করে এমন একটি দীর্ঘ স্ট্রিং তৈরি করে যা কোনো বহুপদী-সময়ের অ্যালগরিদমের কাছে প্রকৃত র্যান্ডম স্ট্রিং থেকে আলাদা করা অসম্ভব:
[
left| Pr_{s leftarrow U_n} [D(G(s)) = 1] – Pr_{y leftarrow U_{n+ll}} [D(y) = 1]
ight| le ext{negl}(n)
]
১৯৯৯ সালের ঐতিহাসিক HILL থিওরেম প্রমাণ করে যে: সিউডোর্যান্ডম জেনারেটরের অস্তিত্ব একমুখী ফাংশনের অস্তিত্বের সমতুল্য। সেখান থেকে GGM ট্রির মাধ্যমে তৈরি হয় সিউডোর্যান্ডম ফাংশন (PRF), যা আজকের ব্লক সাইফার এবং আধুনিক সিমেট্রিক এনক্রিপশনের মূল ভিত্তি।
৪. র্যান্ডম ওরাকল মডেল (ROM) বনাম স্ট্যান্ডার্ড মডেল
ক্রিপ্টোগ্রাফিক প্রোটোকল প্রমাণের দুটি প্রধান পরিমণ্ডল রয়েছে:
- স্ট্যান্ডার্ড মডেল (Standard Model): আক্রমণকারী কেবল পলিনোমিয়াল সময় ও স্মৃতির সীমার মধ্যে থাকে এবং গাণিতিক অনুমান (যেমন LWE বা ডিসক্রিট লগ) সত্য ধরে সরাসরি প্রমাণ করা হয়।
- র্যান্ডম ওরাকল মডেল (Random Oracle Model – ROM): বেলার ও রোগাওয়ের মডেল অনুযায়ী, ক্রিপ্টোগ্রাফিক হ্যাশ ফাংশনকে একটি উন্মুক্ত কাল্পনিক ব্ল্যাক-বক্স (mathcal{H}) হিসেবে ধরা হয় যা প্রতিটি নতুন ইনপুটের জন্য একটি সম্পূর্ণ অপরিবর্তনীয় ও স্বাধীন র্যান্ডম আউটপুট প্রদান করে।
যদিও ক্যানেত্তি, গোল্ডরাইখ ও হালেভি প্রমাণ করেছেন যে এমন কিছু বিশেষ সার্কিট তৈরি করা সম্ভব যা ROM-এ নিরাপদ কিন্তু বাস্তব জীবনে কোনো বাস্তব হ্যাশ ফাংশন দিয়েই নিরাপদ করা যায় না, তবুও ব্যবহারিক জীবনে অতি দ্রুত ও নিরাপদ ক্রিপ্টোগ্রাফিক সিস্টেম (যেমন ফিয়াট-শামির ট্রান্সফর্ম এবং আধুনিক zk-SNARKs) নির্মাণে র্যান্ডম ওরাকল মডেল এক অপরিহার্য আদর্শ হাতিয়ার।
