آیا می توانید آن را حل کنید؟ ریاضیات دیوانه رمزنگاری | علوم پایه

معمای امروز بر اساس یک مفهوم پیشگامانه ریاضی استوار است که هفته گذشته یکی از پیشگامان خود را برنده جایزه آبل کرد ، جایزه نوبل ریاضیات.

مفهوم اثبات دانش صفر، و در رمزنگاری دیجیتال کاربردهای زیادی دارد. بگذارید مختصر توضیح دهم.

معمولاً در ریاضیات – و در زندگی – وقتی می خواهید صحت گفته ها را ثابت کنید ، باید پشتیبان ادعای خود باشید. با این حال ، با اثبات دانش صفر ، می توان بدون افشای هیچ اطلاعات پشتیبانی ، صحت یک گزاره را اثبات کرد.

به عنوان مثال ، فقط بگویید من یک سودوکو بسیار سخت را حل کرده ام و می خواهم به شما ثابت کنم که آن را حل کرده ام. یک مدرک دانش صفر شما را متقاعد می کند که من آن را حل کرده ام بدون اینکه چیزی درمورد راه حل خودم فاش کنم.

سردرگم، گیج، مات مبهوت؟ شما در شرکت خوبی هستید. هنگامی که اثبات دانش صفر برای اولین بار در دهه 1980 ظاهر شد ، جامعه ریاضی گسترده تر بود. کل ایده عجیب و ضد شهودی به نظر می رسید. با این حال ، در نهایت ، این یک انقلاب مفهومی در چگونگی فکر ریاضیدانان در مورد اثبات است و برنامه های خارق العاده ای را در ارزهای رمزپایه و سیستم های رمزنگاری پیدا کرده است ، جایی که کاربران می خواهند اعتماد ایجاد کنند اما اطلاعات مهم را محرمانه نگه دارند.

بیایید به معما برویم ، و بعداً بحث را ادامه دهیم.

گیره کاغذی دزدیده شده

شما در یک دفتر 100 نفره کار می کنید. یک روز گیره کاغذ مورد علاقه شما به سرقت رفته است. شما کاملاً خوب می دانید چه کسی این کار را انجام داده است. همکار شما آنابل به شما می گوید که او ایده خوبی هم دارد.

شما می خواهید با آنابل بررسی کنید که هر دوی شما به یک فرد یکسان مشکوک هستید ، اما هیچ یک از شما حاضر نیستید مظنون خود را شناسایی کنید در صورتی که به افراد مختلف فکر می کنید. (به دلیل سیاست های اداری ، هیچ کس نمی خواهد انگشت بگذارد.)

به روشی فکر کنید که به شما و آنابل اجازه می دهد فرد مظنون و مظنون او را یک نفر بررسی کنید ، بدون اینکه هیچ یک از شما اطلاعاتی درباره مظنون خود فاش کنید.

آنچه این معما می پرسد این است: آیا شما و آنابل می توانید در مورد روشی برای مقایسه اطلاعات خود بدون دادن چیزی به توافق برسید؟ در پایان “مقایسه” خود یا خواهید فهمید که مظنونان شما یک شخص هستند ، یا خواهید فهمید که آنها نیستند. در حالت دوم ، شما هیچ اطلاعاتی به آنابل فاش نخواهید کرد ، و یا او چیزی به شما فاش نخواهد کرد. بنابراین روال راستی آزمایی “دانش صفر” است ، زیرا هیچ دانشی از حقیقت ، یا کذب ، خود راستی آزمایی آشکار نمی شود.

موافقم ، غیر ممکن به نظر می رسد!

در اینجا یک کاری وجود دارد که نمی توانید انجام دهید: شما نمی توانید چیزی را با آنابل به اشتراک بگذارید که مشکوک شما را شناسایی کند. به عنوان مثال نمی توانید بگویید: “مظنون من اواخر روز دوشنبه است” ، زیرا برخی از اطلاعات مربوط به آن شخص را نشان می دهد.

معمولاً در ستون می گویم NO SPOILERS (با حروف بزرگ!). اما امروز فرق می کند زیرا من از شما می خواهم مغز خود را به شکلی که احتمالاً قبلاً هرگز آنرا مخدوش نکرده اید ، انحراف دهید. و راه حل های بسیاری وجود دارد که هرکدام دارای نقاط قوت و ضعف هستند.

یکی از اینها: تصور کنید که شما و آنابل یک دوست خوب دن دارید که هر دو به او اعتماد دارید. در اینجا روشی وجود دارد که شامل Dan می باشد:

  • مرحله 1 شما و آنابل در مورد روش اختصاص یک عدد از 1 تا 100 به همه افراد در دفتر توافق می کنید.

  • مرحله 2 شماره شخصی را که مظنون هستید روی یک کاغذ یادداشت کنید. آنابل نیز همین کار را می کند.

  • مرحله 3 شما دو قطعه کاغذ را به دان تحویل می دهید و از او می خواهید که به شما بگوید که هر دو قطعه تعداد یکسانی دارند.

اگر دن بگوید که اعداد یکسان هستند ، می دانید که مظنونان یکسان هستند. اگر اعداد متفاوت باشد ، مظنونان متفاوت هستند و نه شما و نه آنابل در مورد اینکه فرد مقابل چه مشکوکی دارد ، خردمندتر نیستید. کار تمام شد!

با این وجود گزینه Dan کامل نیست. اولاً ، این به وجود Dan متکی است ، یعنی یک تأیید کننده مستقل و صادق ، که ممکن است همیشه اینگونه نباشد. از همه مهمتر ، هر دوی شما برخی اطلاعات را برای دان فاش می کنید. هدف کلی این تمرین این است که هرگز چیزی را برای کسی فاش نکنید. آیا راهی وجود دارد که شخص دیگری را درگیر نکند؟

در صورت تمایل در مورد چگونگی برخورد با این مشکل در زیر خط پیشنهاداتی ارائه دهید. لطفاً اگر راه حل کاملی می دانید ، راه حل کامل ندهید، اما به یکدیگر کمک کنید و در گروه کار کنید!

من در ساعت 5 عصر بریتانیا با یک راه حل و بحث بیشتر برمی گردم.

در بالا اشاره کردم که جایزه آبل 2021 از یکی از پیشگامان اثبات دانش صفر افتخار کرد. نام وی آوی ویگدرسون ، 64 ساله است و به همراه لازلو لووا ، 73 ساله به دلیل “نقش اصلی آنها در شکل دادن [theoretical computer science and discrete mathematics] به بخشهای اصلی ریاضیات مدرن تبدیل شوند. “

در دهه 1980 ، ویگدرسون ، به همراه اود گلدریچ و سیلویو میکالی ، نشان دادند که هر گزاره ریاضی واقعی دارای اثبات دانش صفر است. در آن زمان ، این نتیجه یک پیشرفت کاملاً تئوریک بود ، اما در سال های اخیر اثبات دانش صفر کاربردهای مهمی در امنیت دیجیتال ، به ویژه در ارزهای رمزپایه و سیستم های احراز هویت پیدا کرده است. اثبات دانش صفر به دو نفر اجازه می دهد تا اعتماد را ثابت کنند در حالی که هیچ چیز را فاش نمی کنند.

اگر شما علاقه مندید درباره کار افتخارآمیز جایزه آبل 2021 بیشتر بدانید ، ممکن است از این فیلم کوتاه که برای جایزه آبل ساخته ام و در جریان مراسم اعلام پخش شد لذت ببرید. این خلاصه ای غیر روحانی از کارهای Lovász و Wigderson را ارائه می دهد و (از 4 دقیقه) مثالی از اثبات دانش صفر را می آورد (که ممکن است در تلاش برای حل معمای امروز مفید باشد.)

توضیح اثبات دانش صفر از 4 دقیقه است

من هر دو هفته یکشنبه یک معما تنظیم می کنم. من همیشه به دنبال معماهای عالی هستم. اگر می خواهید یکی را پیشنهاد دهید ، برای من ایمیل بزنید.

من نویسنده چندین کتاب معمایی هستم که اخیراً کتاب معمای زبان عاشق است.

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *