Naor–Reingold pseudorandom function
1997 সালে, মনি নওর এবং ওমর রেইনগোল্ড ব্যক্তিগত কী এবং পাবলিক-কী ক্রিপ্টোগ্রাফিতে বিভিন্ন ক্রিপ্টোগ্রাফিক প্রিমিটিভের জন্য দক্ষ নির্মাণের বর্ণনা দিয়েছেন। তাদের ফলাফল হল একটি দক্ষ সিউডোরান্ডম ফাংশন নির্মাণ। ধরা যাক p এবং l হল মৌলিক সংখ্যা যার l |p −1। তারপর প্রতিটি (n + 1)-মাত্রিক ভেক্টর a = (a0, a1,., an)-এর জন্য তারা ফাংশনটি সংজ্ঞায়িত করে যেখানে x = x1। xn হল পূর্ণসংখ্যা x, 0 ≤ x ≤ 2n − 1-এর বিট উপস্থাপনা, প্রয়োজনে কিছু অতিরিক্ত নেতৃস্থানীয় শূন্য সহ। উদাহরণস্বরূপ ধরা যাক p = 7 এবং l = 3; সুতরাং l |p −1। গুণনীয়ক ক্রম 3-এর g = 4 ω নির্বাচন করুন (যেহেতু 43 = 64 ω1 মোড 7)। n = 3, a = (1,1,2,1) এবং x = 5 (5 এর বিট উপস্থাপনা 101) এর জন্য, আমরা নিম্নরূপ গণনা করতে পারিঃ দক্ষতা নাওর-রিঙ্গোল্ড গঠনে ফাংশনের মূল্যায়ন খুব দক্ষতার সাথে করা যেতে পারে। যে কোনও বিন্দুতে ফাংশনের মান গণনা করা একটি মডুলার সূচক এবং এন-মডুলার গুণনের সাথে তুলনীয়। এই ফাংশনটি সীমাবদ্ধ গভীরতা এবং বহুপদী আকারের প্রান্তিক বর্তনী দ্বারা সমান্তরালে গণনা করা যেতে পারে। নাওর-রিঙ্গোল্ড ফাংশনটি প্রতিসম এনক্রিপশন, প্রমাণীকরণ এবং ডিজিটাল স্বাক্ষর সহ অনেক ক্রিপ্টোগ্রাফিক স্কিমের ভিত্তি হিসাবে ব্যবহার করা যেতে পারে। ফাংশনের নিরাপত্তা ধরে নিন যে একজন আক্রমণকারী ফাংশনের বেশ কয়েকটি আউটপুট দেখেন, যেমন। , এবং গণনা করতে চায়। সরলতার জন্য ধরে নিন যে x1 = 0, তারপর আক্রমণকারীকে এবং পাওয়ার মধ্যে গণনামূলক ডিফি-হেলম্যান (সিডিএইচ) সমাধান করতে হবে। সাধারণভাবে, k থেকে k + 1-এ যাওয়া বিট প্যাটার্ন পরিবর্তন করে এবং যদি k + 1 2-এর ঘাত না হয় তবে কেউ সূচককে বিভক্ত করতে পারে যাতে গণনাটি আগের দুটি ফলাফলের মধ্যে ডিফি-হেলম্যান কী গণনা করার সাথে মিলে যায়। এই আক্রমণকারী পরবর্তী ক্রম উপাদানটির পূর্বাভাস দিতে চায়। এই ধরনের আক্রমণ খুব খারাপ হবে-তবে কঠিন ডিফি-হেলম্যান সমস্যা (ডিএইচপি) সহ গোষ্ঠীতে কাজ করে এর বিরুদ্ধে লড়াই করাও সম্ভব। উদাহরণস্বরূপঃ একজন আক্রমণকারী ফাংশনের বেশ কয়েকটি আউটপুট দেখেন যেমন। , যেমন পূর্ববর্তী উদাহরণে, এবং। তারপর, আক্রমণকারী এই ফাংশনের পরবর্তী ক্রম উপাদানটির পূর্বাভাস দিতে চায়। যাইহোক, আক্রমণকারী জ্ঞান এবং জ্ঞান থেকে ফলাফলের পূর্বাভাস দিতে পারে না। অন্যান্য আক্রমণ রয়েছে যা একটি সিউডোর্যান্ডম নম্বর জেনারেটরের জন্য খুব খারাপ হবেঃ ব্যবহারকারী আউটপুট থেকে এলোমেলো সংখ্যা পাওয়ার আশা করে, তাই অবশ্যই স্ট্রিমটি অনুমানযোগ্য হওয়া উচিত নয়, তবে আরও বেশি, এটি একটি এলোমেলো স্ট্রিং থেকে অবিচ্ছেদ্য হওয়া উচিত। ফাংশনটি মূল্যায়নের জন্য একটি ওরাকলে অ্যাক্সেস সহ অ্যালগরিদমটি নির্দেশ করা যাক। মনে করুন সিদ্ধান্তমূলক ডিফি-হেলম্যান অনুমানটি ধরে রাখে, নাওর এবং রেইনগোল্ড দেখান যে প্রতিটি সম্ভাবনাময় বহুপদী সময় অ্যালগরিদমের জন্য এবং যথেষ্ট বড় এন নগণ্য। প্রথম সম্ভাব্যতা বীজ s = (p, g, a)-এর পছন্দের উপর নেওয়া হয় এবং দ্বিতীয় সম্ভাব্যতাটি p, g দ্বারা, ইনস্ট্যান্স জেনারেটরের উপর প্ররোচিত এলোমেলো বিতরণ এবং সমস্ত ফাংশনের সেটের মধ্যে ফাংশনের এলোমেলো পছন্দের উপর নেওয়া হয়। রৈখিক জটিলতা ক্রিপ্টোগ্রাফিক উদ্দেশ্যে একটি ক্রম কতটা কার্যকর হতে পারে তার একটি প্রাকৃতিক পরিমাপ হল তার রৈখিক জটিলতার আকার। একটি বলয়ের উপর একটি n-উপাদান ক্রম W (x), x = 0,1,2,., n-1-এর রৈখিক জটিলতা হল সংক্ষিপ্ততম রৈখিক পুনরাবৃত্তি সম্পর্ক W (x + l) = Al−1W (x + l−1) +. + A0W (x), x = 0,1,2,., n-l−1 সঙ্গে A0,., Al−1 ω, যা এই ক্রম দ্বারা সন্তুষ্ট হয়। কিছু> 0 এর জন্য, n ≤ (1 +), যে কোনও, যথেষ্ট বড় l এর জন্য, অনুক্রমের রৈখিক জটিলতা, 0 ≤ x ≤ 2n-1, দ্বারা চিহ্নিত করা হয়, সম্ভবত বেশিরভাগ ভেক্টর ব্যতীত সকলের জন্য সন্তোষজনক। এই কাজের সীমার অসুবিধাগুলি রয়েছে, যথা এটি খুব আকর্ষণীয় ক্ষেত্রে প্রযোজ্য নয় বিতরণের অভিন্নতা এর পরিসংখ্যানগত বিতরণ প্রায় সমস্ত ভেক্টরের জন্য অভিন্ন বিতরণের কাছাকাছি। সেটের অসঙ্গতি ধরা যাক। সুতরাং, যদি p-এর বিট দৈর্ঘ্য হয় তবে সমস্ত ভেক্টরের জন্য a ω বাউন্ড ধারণ করে, যেখানে এবং যদিও এই বৈশিষ্ট্যটির কোনও তাত্ক্ষণিক ক্রিপ্টোগ্রাফিক প্রভাব আছে বলে মনে হয় না, বিপরীত সত্য, যথা অ-অভিন্ন বিতরণ, যদি সত্য হয় তবে এই ফাংশনের প্রয়োগের জন্য বিপর্যয়কর পরিণতি ঘটবে। উপবৃত্তাকার বক্ররেখার ক্রম এই ফাংশনের উপবৃত্তাকার বক্ররেখার সংস্করণটিও আকর্ষণীয়। বিশেষ করে, এটি সংশ্লিষ্ট সিস্টেমের ক্রিপ্টোগ্রাফিক নিরাপত্তা উন্নত করতে সাহায্য করতে পারে। ধরা যাক p> 3 মৌলিক এবং E একটি উপবৃত্তাকার বক্ররেখা, তারপর প্রতিটি ভেক্টর a উপগোষ্ঠীতে একটি সীমাবদ্ধ ক্রমকে সংজ্ঞায়িত করেঃ যেখানে পূর্ণসংখ্যার বিট উপস্থাপনা। নাওর-রিঙ্গোল্ড উপবৃত্তাকার বক্ররেখা ক্রমকে এইভাবে সংজ্ঞায়িত করা হয় যে, যদি সিদ্ধান্তমূলক ডিফি-হেলম্যান অনুমানটি ধরে থাকে, তবে সূচক কে বহুপদী সময়ে গণনা করার জন্য যথেষ্ট নয়, এমনকি যদি কোনও আক্রমণকারী এলোমেলোভাবে <আইডি1:// এন. উইকিপিডিয়া. ওআরজি/উইকি/উপবৃত্তাকার বক্ররেখার সাথে বহুপদীভাবে অনেক প্রশ্ন সম্পাদন করে। ছদ্মবেশী সংখ্যা জেনারেটর ক্রিপ্টোগ্রাফি