আপনি কিভাবে একটি গোপন প্রমাণ করবেন?

কল্পনা করুন যে আপনার কাছে কিছু দরকারী জ্ঞান ছিল - হতে পারে একটি গোপন রেসিপি, বা একটি সাইফারের চাবিকাঠি। আপনি কি একজন বন্ধুর কাছে প্রমাণ করতে পারেন যে আপনার কাছে সেই জ্ঞান ছিল, এটি সম্পর্কে কিছু প্রকাশ না করে? কম্পিউটার বিজ্ঞানীরা 30 বছরেরও বেশি আগে প্রমাণ করেছেন যে আপনি যদি শূন্য-জ্ঞান প্রমাণ বলে তা ব্যবহার করেন।

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

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

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

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

মিকালি এবং গোল্ডওয়াসার — তখন ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের স্নাতক ছাত্র, বার্কলে — যখন একটি নেটওয়ার্কে জুজু খেলার রসদ নিয়ে বিভ্রান্ত হয়েছিল তখন মিথস্ক্রিয়াগুলির এই ধারণাটি এসেছিল৷ কীভাবে সমস্ত খেলোয়াড় যাচাই করতে পারে যে তাদের মধ্যে একজন যখন ভার্চুয়াল ডেক থেকে একটি কার্ড পায়, ফলাফলটি এলোমেলো হয়? ইন্টারেক্টিভ প্রমাণ পথ হতে পারে. কিন্তু তারপরে, খেলোয়াড়রা কীভাবে যাচাই করতে পারে যে পুরো প্রোটোকল - নিয়মগুলির সম্পূর্ণ সেট - সঠিকভাবে অনুসরণ করা হয়েছিল, পথে প্রতিটি খেলোয়াড়ের হাত প্রকাশ না করে?

এই লক্ষ্য অর্জনের জন্য, মিকালি এবং গোল্ডওয়াসার একটি ইন্টারেক্টিভ প্রমাণের জন্য প্রয়োজনীয় দুটির সাথে একটি তৃতীয় বৈশিষ্ট্য যুক্ত করেছেন: প্রমাণটি জ্ঞান সম্পর্কে কিছুই প্রকাশ করবে না, শুধুমাত্র বিবৃতির সত্যতা। "একটি প্রোটোকলের মধ্য দিয়ে যাওয়ার একটি ধারণা রয়েছে, যার শেষে আপনি বিশ্বাস করেন যে [জুজু খেলোয়াড়রা] তাদের যা জানা উচিত তার চেয়ে বেশি কিছু জানেন না," গোল্ডওয়াসার বলেছেন।

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

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

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

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

এবং 1988 সালে, মিকালি এবং অন্যান্য দেখিয়েছেন যে যদি একজন পরীক্ষক এবং একজন যাচাইকারী এলোমেলো বিটগুলির একটি ছোট স্ট্রিং ভাগ করে, কোন মিথস্ক্রিয়া প্রয়োজন হয় না। এটি তাত্ত্বিকভাবে বোঝায় যে শূন্য-জ্ঞানের প্রমাণগুলি ইন্টারেক্টিভ হতে হবে না, যা বোঝায় যে দুটি পক্ষের মধ্যে ধ্রুবক যোগাযোগের প্রয়োজন নেই। এটি তাদের গবেষকদের জন্য অনেক বেশি উপযোগী করে তুলবে, কিন্তু 21 শতকের পালা পর্যন্ত এই ধরনের প্রমাণগুলি বন্ধ হয়ে যায় নি।

"2000 এর দশকের শেষের দিকে, আমরা শূন্য-জ্ঞান প্রমাণ তৈরির জন্য দক্ষ কৌশলগুলির বিবর্তন দেখতে শুরু করেছি," বলেন ম্যাথিউ ডি গ্রিন, জন হপকিন্স বিশ্ববিদ্যালয়ের একজন ক্রিপ্টোগ্রাফার। "আমরা এমন পর্যায়ে পৌঁছেছি যেখানে আমরা বুঝতে পেরেছি, 'এক সেকেন্ড অপেক্ষা করুন, বাস্তবে এটি ব্যবহার করার একটি উপায় থাকতে পারে।'"

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

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

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

সম্পাদকের দ্রষ্টব্য: শফি গোল্ডওয়াসার সাইমনস ফাউন্ডেশন থেকে তহবিল পেয়েছে, যা এটির জন্য অর্থায়ন করে সম্পাদকীয়ভাবে স্বাধীন প্রকাশনা. সিমন্স ফাউন্ডেশন ফান্ডিং সিদ্ধান্ত আমাদের কভারেজের উপর কোন প্রভাব ফেলে না।