সেলিব্রেটেড ক্রিপ্টোগ্রাফি অ্যালগরিদম একটি আপগ্রেড পায় | কোয়ান্টা ম্যাগাজিন

আমাদের ক্রমবর্ধমান ডিজিটাল জীবনে, নিরাপত্তা ক্রিপ্টোগ্রাফির উপর নির্ভর করে। একটি ব্যক্তিগত বার্তা পাঠান বা অনলাইনে একটি বিল পরিশোধ করুন এবং আপনি আপনার ডেটা গোপন রাখার জন্য ডিজাইন করা অ্যালগরিদমের উপর নির্ভর করছেন। স্বাভাবিকভাবেই, কিছু লোক সেই গোপনীয়তাগুলি উন্মোচন করতে চায় — তাই গবেষকরা এই সিস্টেমগুলির শক্তি পরীক্ষা করার জন্য কাজ করে তা নিশ্চিত করার জন্য যে তারা কোনও চতুর আক্রমণকারীর হাতে ভেঙে পড়বে না।

এই কাজের একটি গুরুত্বপূর্ণ হাতিয়ার হল এলএলএল অ্যালগরিদম, যার নাম গবেষকদের নামে এটা প্রকাশিত 1982 সালে — আর্জেন লেনস্ট্রা, হেনড্রিক লেনস্ট্রা জুনিয়র এবং লাসজলো লোভাসজ। এলএলএল, তার অনেক বংশধরদের সাথে, কিছু ক্ষেত্রে ক্রিপ্টোগ্রাফিক স্কিমগুলি ভাঙতে পারে; তারা কীভাবে আচরণ করে তা অধ্যয়ন করা গবেষকদের এমন সিস্টেম ডিজাইন করতে সাহায্য করে যা আক্রমণের জন্য কম ঝুঁকিপূর্ণ। এবং অ্যালগরিদমের প্রতিভা ক্রিপ্টোগ্রাফির বাইরেও প্রসারিত: এটি গণিত সংখ্যা তত্ত্বের মতো উন্নত গাণিতিক অঙ্গনেও একটি দরকারী টুল।

বছরের পর বছর ধরে, গবেষকরা পদ্ধতিটিকে আরও ব্যবহারিক করার জন্য LLL এর রূপগুলিকে সম্মানিত করেছেন — তবে শুধুমাত্র একটি বিন্দু পর্যন্ত। এখন, একজোড়া ক্রিপ্টোগ্রাফার একটি নতুন LLL-শৈলীর অ্যালগরিদম তৈরি করেছে যার দক্ষতা উল্লেখযোগ্যভাবে বৃদ্ধি পেয়েছে। নতুন কৌশল যা জিতেছে সেরা কাগজের পুরস্কার এ 2023 আন্তর্জাতিক ক্রিপ্টোলজি সম্মেলন, পরিস্থিতির পরিসরকে প্রশস্ত করে যেখানে কম্পিউটার বিজ্ঞানী এবং গণিতবিদরা সম্ভাব্যভাবে LLL-এর মতো পদ্ধতি ব্যবহার করতে পারেন।

"এটা সত্যিই উত্তেজনাপূর্ণ ছিল," বলেন ক্রিস পিকার্ট, মিশিগান বিশ্ববিদ্যালয়ের একজন ক্রিপ্টোগ্রাফার যিনি কাগজে জড়িত ছিলেন না। টুলটি কয়েক দশক ধরে অধ্যয়নের কেন্দ্রবিন্দু হয়েছে, তিনি বলেন। "এটা সবসময়ই ভালো লাগে যখন একটি টার্গেট যা এতদিন ধরে কাজ করা হয়েছে … দেখায় যে এখনও বিস্ময় খুঁজে পাওয়া যাচ্ছে।"

LLL-টাইপ অ্যালগরিদমগুলি জালির জগতে কাজ করে: নিয়মিত ব্যবধানযুক্ত বিন্দুর অসীম সংগ্রহ। এটি কল্পনা করার একটি উপায় হিসাবে, কল্পনা করুন যে আপনি একটি মেঝে টাইলিং করছেন। আপনি এটিকে বর্গাকার টাইলস দিয়ে ঢেকে দিতে পারেন এবং সেই টাইলের কোণগুলি একটি জালি তৈরি করবে। বিকল্পভাবে, আপনি একটি ভিন্ন জালি তৈরি করতে একটি ভিন্ন টালি আকৃতি বেছে নিতে পারেন — বলুন, একটি দীর্ঘ সমান্তরালগ্রাম —।

একটি জালিকে তার "ভিত্তি" ব্যবহার করে বর্ণনা করা যেতে পারে। এটি ভেক্টরের একটি সেট (মূলত, সংখ্যার তালিকা) যা আপনি জালির প্রতিটি বিন্দু পেতে বিভিন্ন উপায়ে একত্রিত করতে পারেন। আসুন দুটি ভেক্টর সমন্বিত ভিত্তি সহ একটি জালি কল্পনা করি: [3, 2] এবং [1, 4]। জালি হল সেই সমস্ত পয়েন্ট যা আপনি সেই ভেক্টরগুলির কপি যোগ এবং বিয়োগ করে পৌঁছাতে পারেন।

ভেক্টরের এই জোড়াটি জালির একমাত্র ভিত্তি নয়। কমপক্ষে দুটি মাত্রা সহ প্রতিটি জালির অসীমভাবে অনেকগুলি সম্ভাব্য ভিত্তি রয়েছে। কিন্তু সব ঘাঁটি সমান তৈরি করা হয় না। একটি ভিত্তি যার ভেক্টরগুলি একে অপরের সাথে সমকোণে ছোট এবং কাছাকাছি থাকে তার সাথে কাজ করা সাধারণত সহজ এবং কিছু গণনাগত সমস্যা সমাধানের জন্য আরও দরকারী, তাই গবেষকরা সেই ঘাঁটিগুলিকে "ভাল" বলে। এর একটি উদাহরণ হল নীচের চিত্রে নীল ভেক্টরের জোড়া। লম্বা এবং কম অর্থোগোনাল ভেক্টর নিয়ে গঠিত বেস - যেমন লাল ভেক্টর - "খারাপ" হিসাবে বিবেচিত হতে পারে।

এটি এলএলএল-এর জন্য একটি কাজ: এটিকে (বা এর ভাইদের) একটি বহুমাত্রিক জালির ভিত্তি দিন এবং এটি আরও ভাল একটি থুথু ফেলবে। এই প্রক্রিয়াটি জালি ভিত্তিতে হ্রাস হিসাবে পরিচিত।

এই সব ক্রিপ্টোগ্রাফি সঙ্গে কি করতে হবে? এটা দেখা যাচ্ছে যে একটি ক্রিপ্টোগ্রাফিক সিস্টেম ভাঙ্গার কাজটি, কিছু ক্ষেত্রে, আরেকটি সমস্যা হিসাবে পুনর্নির্মাণ করা যেতে পারে: একটি জালিতে একটি অপেক্ষাকৃত ছোট ভেক্টর খুঁজে পাওয়া। এবং কখনও কখনও, সেই ভেক্টরটিকে একটি LLL-শৈলী অ্যালগরিদম দ্বারা উত্পন্ন হ্রাসকৃত ভিত্তি থেকে বাদ দেওয়া যেতে পারে। এই কৌশলটি গবেষকদের এমন সিস্টেমগুলিকে টপকে যেতে সাহায্য করেছে যেগুলি, পৃষ্ঠে, জালির সাথে খুব কম সম্পর্ক রয়েছে বলে মনে হয়।

তাত্ত্বিক অর্থে, আসল এলএলএল অ্যালগরিদম দ্রুত চলে: এটি চালানোর জন্য যে সময় লাগে তা ইনপুটের আকারের সাথে তাত্পর্যপূর্ণভাবে স্কেল করে না - অর্থাৎ, জালির মাত্রা এবং সংখ্যাগুলির আকার (বিটে) ভিত্তি ভেক্টর। কিন্তু এটি একটি বহুপদী ফাংশন হিসাবে বৃদ্ধি পায়, এবং "যদি আপনি আসলে এটি করতে চান, বহুপদী সময় সবসময় এতটা সম্ভব নয়," বলেন লিও ডুকাস, নেদারল্যান্ডসের জাতীয় গবেষণা ইনস্টিটিউট CWI-এর একজন ক্রিপ্টোগ্রাফার।

অনুশীলনে, এর মানে হল যে আসল LLL অ্যালগরিদম খুব বড় ইনপুটগুলি পরিচালনা করতে পারে না। "গণিতবিদ এবং ক্রিপ্টোগ্রাফাররা আরও কিছু করার ক্ষমতা চেয়েছিলেন," বলেছেন কিগান রায়ান, ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের একজন ডক্টরাল ছাত্র, সান দিয়েগো। গবেষকরা LLL-শৈলীর অ্যালগরিদমগুলিকে অপ্টিমাইজ করার জন্য কাজ করেছেন বড় ইনপুটগুলিকে মিটমাট করার জন্য, প্রায়শই ভাল কর্মক্ষমতা অর্জন করে৷ তারপরও কিছু কাজ নাগালের বাইরে থেকে গেছে।

রায়ান এবং তার উপদেষ্টা দ্বারা রচিত নতুন কাগজ, নাদিয়া হেনিঙ্গার, এর LLL-শৈলী অ্যালগরিদমের দক্ষতা উন্নত করতে একাধিক কৌশল একত্রিত করে। একটি জিনিসের জন্য, কৌশলটি একটি পুনরাবৃত্ত কাঠামো ব্যবহার করে যা কাজটিকে ছোট ছোট অংশে ভেঙে দেয়। অন্যটির জন্য, অ্যালগরিদমটি সাবধানতার সাথে জড়িত সংখ্যাগুলির নির্ভুলতা পরিচালনা করে, গতি এবং একটি সঠিক ফলাফলের মধ্যে ভারসাম্য খুঁজে পায়। নতুন কাজটি গবেষকদের জন্য হাজার হাজার মাত্রা সহ জালির ঘাঁটি হ্রাস করা সম্ভবপর করে তোলে।

অতীত কাজ একই পদ্ধতি অনুসরণ করেছে: A 2021 কাগজ বৃহৎ জালির দ্রুত কাজ করার জন্য পুনরাবৃত্তি এবং নির্ভুলতা ব্যবস্থাপনাকেও একত্রিত করে, কিন্তু এটি শুধুমাত্র নির্দিষ্ট ধরণের জালির জন্য কাজ করে, এবং ক্রিপ্টোগ্রাফিতে গুরুত্বপূর্ণ নয়। নতুন অ্যালগরিদম অনেক বিস্তৃত পরিসরে ভাল আচরণ করে। "আমি সত্যিই খুশি যে কেউ এটা করেছে," বলেছেন টমাস এসপিটাউ, PQShield কোম্পানির একজন ক্রিপ্টোগ্রাফি গবেষক এবং 2021 সংস্করণের একজন লেখক। তার দলের কাজ একটি "ধারণার প্রমাণ," তিনি বলেন; নতুন ফলাফল দেখায় যে "আপনি একটি শব্দ উপায়ে খুব দ্রুত জাল হ্রাস করতে পারেন।"

নতুন কৌশল ইতিমধ্যে কার্যকর প্রমাণিত হতে শুরু করেছে। অরেল পেজ, ফরাসি জাতীয় গবেষণা ইনস্টিটিউট ইনরিয়ার একজন গণিতবিদ বলেছেন যে তিনি এবং তার দল কিছু গণনীয় সংখ্যা তত্ত্বের কাজগুলিতে কাজ করার জন্য অ্যালগরিদমের একটি অভিযোজন তৈরি করেছেন।

LLL-শৈলীর অ্যালগরিদমগুলি ডিজাইন করা জালি-ভিত্তিক ক্রিপ্টোগ্রাফি সিস্টেমের সাথে সম্পর্কিত গবেষণায় ভূমিকা পালন করতে পারে নিরাপদ থাকুন এমনকি ভবিষ্যতে শক্তিশালী কোয়ান্টাম কম্পিউটার সহ। এগুলি এই জাতীয় সিস্টেমগুলির জন্য কোনও হুমকি তৈরি করে না, যেহেতু তাদের নামিয়ে নেওয়ার জন্য এই অ্যালগরিদমগুলি অর্জন করতে পারে তার চেয়ে ছোট ভেক্টর খুঁজে বের করতে হবে। তবে সেরা আক্রমণ গবেষকরা "বেসিক বিল্ডিং ব্লক" হিসাবে একটি এলএলএল-স্টাইল অ্যালগরিদম ব্যবহার করতে জানেন। ওয়েসেল ভ্যান ওয়ার্ডেন, বোর্দো বিশ্ববিদ্যালয়ের একজন ক্রিপ্টোগ্রাফার। এই আক্রমণগুলি অধ্যয়ন করার জন্য ব্যবহারিক পরীক্ষায়, সেই বিল্ডিং ব্লক সবকিছুকে ধীর করে দিতে পারে। নতুন টুল ব্যবহার করে, গবেষকরা আক্রমণের অ্যালগরিদমগুলিতে চালানো পরীক্ষাগুলির পরিসর প্রসারিত করতে সক্ষম হতে পারে, তারা কীভাবে কার্য সম্পাদন করে তার একটি পরিষ্কার চিত্র অফার করে।

কোয়ান্টা আমাদের শ্রোতাদের আরও ভালভাবে পরিবেশন করার জন্য সমীক্ষার একটি সিরিজ পরিচালনা করছে। আমাদের নিন কম্পিউটার বিজ্ঞান পাঠক জরিপ এবং আপনি বিনামূল্যে জিততে প্রবেশ করা হবে কোয়ান্টা পণ্যদ্রব্য.