آشنایی با الگوریتم‌های کوانتومی و پساکوانتومی به زبان ساده

الگوریتم کوانتومی چیست؟

الگوریتم کوانتومی الگوریتمی است که بر مدلی واقع گرا از یک کامپیوتر کوانتومی (quantum computer) اجرا می‌شود. پر استفاده‌ترین مدل مدلی است که از جریان کوانتومی (quantum circuit) استفاده می‌کند. الگوریتم کلاسیک روشی است که هر مرحله ان بر روی کامپیوترهای کلاسیک قابل اجرا باشد و در مقابل ان الگوریتم کوانتومی روشی است که هر مرحله ان بر روی کامپیوترهای کوانتومی قابل اجرا باشد. مسئله‌های غیرقابل حل با الگوریتم‌های کلاسیک همچنان با الگوریتم کوانتومی غیرقابل حل است. اما مزیت الگوریتم کوانتومی این است که مسئله‌های قابل حل با زمان کمتری حل می‌شوند. معروف‌ترین الگوریتم‌های کوانتومی الگوریتم شور برای تجزیه به عوامل اول و الگوریتم گرور برای جستجو در یک پایگاه داده نامرتب است. الگوریتم شور به صورت نمایی از بهترین الگوریتم کلاسیکی که تجزیه به عامل اول را انجام می‌دهد بهتر عمل می‌کند و همین‌طور الگوریتم گرور به اندازه رادیکال زمان بهترین الگوریتم کلاسیک با عملکرد مشابه زمان می‌گیرد. در پردازش کوانتومی، تبدیل فوریه کوانتومی یک نگاشت خطی روی کیوبیت‌ها است و مشابه کوانتومی تبدیل فوریه گسسته می‌باشد. تبدیل فوریه کوانتومی جزئی از بسیاری از الگوریتم‌های کوانتومی است، و به خصوص در الگوریتم شر برای فاکتورگیری و محاسبه لگاریتم گسسته، الگوریتم تخمین فاز کوانتومی برای تخمین ویژه‌مقدارهای یک عملگر یکانی و الگوریتم زیرگروه پنهان کاربرد دارد.

رمزنگاری کوانتومی

رمزنگاری کوانتومی استفاده مکانیک کوانتومی به خصوص ارتباطات کوانتومی و محاسبات کوانتومی برای اجرای عملیات رمزنگاری و شکستن سیستم‌های رمزگذاری شده را توصیف می‌کند. استفاده از رمزنگاری کلاسیک (غیر کوانتومی) برای حفاظت در برابر حمله کنندگان کوانتومی نیز به عنوان رمزنگاری کوانتومی در نظر گرفته می‌شود. به این حالت رمز نگاری پست-کوانتومی می‌گویند. نمونه‌هایی از رمزنگاری کوانتومی استفاده از ارتباطات کوانتومی برای رد و بدل کردن مخفیانه کلید (توزیع کلید کوانتومی) یا استفاده از رایانه‌های کوانتومی برای شکستن انواع گوناگون کلیدهای عمومی و امضاهای دیجیتال می‌باشد. (به عنوان مثال سامانه‌های آر اس ای و الجمل) رمزنگاری کوانتومی انجام عملیات گوناگون رمزگذاری را که با تبادلات کلاسیک غیرممکن است میسر می‌سازد که این یکی از مزیت‌های رمز نگاری کوانتومی است. مکانیک کوانتومی تضمین می‌کند که با اندازه‌گیری داده‌های کوانتومی، این اطلاعات از بین می‌روند از این ویژگی می‌توان برای تشخیص مداخله دشمن در یک پیغام استفاده کرد. با این وجود، اگر یک استراق سمع‌کننده اختلالاتی کمتر از آنچه انتظار می‌رود ایجاد کند، ممکن است اطلاعات فاش شوند. مسلماً بهترین کاربرد شناخته شده از رمز نگاری کوانتومی توزیع کلید کوانتومی است. توزیع کلید کوانتومی فرایند استفاده از تبادل کوانتومی را برای ایجاد یک کلید مشترک میان دو نفر (که معمولاً آلیس و باب نامیده می‌شوند) بدون آنکه نفر سوم (ایو) هیچ اطلاعی از کلید به دست آورد را توصیف می‌کند. (حتی در صورتی که بتواند تمام مکالمات بین این دو نفر را شنود نماید) برای رسیدن به این هدف آلیس قبل از فرستادن اطلاعات به باب آن‌ها را به بیت‌های کوانتومی تبدیل می‌کند. در این حالت اگر ایو تلاش کند این بیت‌ها را بخواند، پیغام‌ها مخدوش شده و آلیس و باب متوجه مداخله وی می‌شوند.

توزیع کلید کوانتومی بدون تحمیل هر گونه فرضیات محاسباتی امکان‌پذیر است. (فرضیاتی که بیان می‌کنند بعضی از مسائل محاسباتی مانند تجزیه اعداد بزرگ زمان بسیار طولانی را روی کامپیوتر صرف می‌کنند). توزیع کلید کوانتومی دارای امنیت بدون قید و شرط است. تنها فرضیات پایدار ماندن قوانین مکانیک کوانتومی و وجود یک کانال شناسایی میان آلیس و باب است. داشتن یک کانال شناسایی امن به این معنا است که ایو نتواند خود را به جای آلیس یا باب معرفی نماید زیرا در غیر این صورت، حمله مردی در میان امکان‌پذیر می‌شود. در حال حاضر توزیع کلید کوانتومی تنها نمونه عملی از رمز نگاری کوانتومی است.

الگوریتم امضای ان‌تی‌آریوساین

الگوریتم امضای ان‌تی‌آریوساین NTRUSign یک الگوریتم کلید عمومی رمزنگاری امضای دیجیتال است که بر اساس طرح امضای GGH بنا شده‌است. الگوریتم امضای ان‌تی‌آریوساین NTRUSign یک الگوریتم کلید عمومی رمزنگاری امضای دیجیتال است که بر اساس طرح امضای GGH بنا شده‌است. این موضوع برای اولین بار در جلسه‌ای در Asiacrypt 2001 ارائه شده و به صورت کارشناسی شده در کنفرانس RSA 2003 منتشر شد. انتشاری که سال 2003 انجام شد شامل توصیه‌هایی پارامتری برای امنیت 80 بیتی بود. در نسخه‌های منتشر شده پس از آن 2005 توصیه پارامتر برای امنیت 80 بیتی تجدید نظر شد، و پارامترهایی که سطح امنیتی را تا 112، 128، 160، 192 و 256 بیت بالا بردند معرفی شدند , یک الگوریتم برای استخراج مجموعه پارامتر در هر سطح امنیتی مورد نظر را توصیف کردند. شرکت رمزنگاری NTRU برای ثبت اختراع در الگوریتم مشغول به کار شده‌است. NTRUSign شامل انتقال یک پیام به نقطه تصادفی در فضای 2N بعدی، که N که N یکی از پارامتراهای NTRUSign می‌باشد، و همچنین حل مسئله بردار نزدیک در یک مشبکه بسیار مرتبط با مشبکه NTRUEncrypt می‌باشد. این شبکه دارای خاصیت است که به‌طور 2N بعدی خصوصی برای شبکه را می‌توان با 2 بردار توصیف شده است، که هر کدام با ضریب N شرح داده شده، و به صورت عمومی می‌توان با یک بردار N بعدی تنها توصیف کرد. این موضوع قادر می سازد کلیدهای عمومی در فضای O(N) باشند، به جای O (N2) که به عنوان موردی با دیگر طرح‌های امضا مبتنی بر شبکه است. عملیات O (N2) زمان میگیرد، که با O (N3) برای منحنی رمزنگاری بیضوی و RSA عملیات کلید خصوصی در تضاد است. بنابراین NTRUSign سریع تر از الگوریتمهای در سطوح امنیتی کم، و به‌طور قابل توجهی سریع تر در سطوح امنیتی بالا می‌باشد. NTRUSign تحت بررسی استاندارد توسط گروه کاری IEEE P1363 می‌باشد.

NTRUSign یک طرح امضای بدون دانش نیست و رونوشتهای امضا اطلاعاتی در مورد کلید خصوصی را فاش کیممند که اولین بار توسط Gentry و Szydlo مشاهده شد. در سال 2006 Nguyen و Regev نشان دادند که برای پارامتر هموار اصلی NTRUSign، مجموعه نفوذگرها (هکرها) می‌توانند کلید خصوصی با کمتر از 400 امضا بیابند. پیشنهادهای کنونی استفاده از آشفتگی برای افزایش طول رونوشت مورد نیاز برای بهبود دادن کلید خصوصی می‌باشد: صاحب امضا نکته‌ای که معرف پیام است را با یک مقدار محرمانه کوچک که قبل از امضای خود محاسبه می‌شود را جایگزین میکند. NTRU ادعا می‌کند که حداقل 30^2 امضا و احتمالاً به‌طور قابل توجهی بیشتر نیاز است، تا قبل از رونوشت امضاهای آشفته تا هر گونه حمله مفید را قادر سازد. در سال 2012 یک حمله به طرح با آشفتگی ارائه شد که تنها نیاز به چند هزار امضا برای پارامترهای امنیتی استاندارد داشت.

رمزنگاری ان‌تی‌آریو

NTRU Encrypt یک سیستم رمزگذاری کلمات عمومی، که بیشتر به عنوان الگوریتم رمزنگاری NTRU شناخته می‌شود، بر پایه شبکه‌های رمزنگاری نامتقارن که مرتبط با RSA و ECC است که برای حل کردن مشکل بردارهای کوچک در سیستم‌های شبکه‌ای ارائه شده‌است. (مشکل مورد نظر این است که رمزهایی ساخته شود تا به وسیله رایانه‌های کوانتومی شکسته نشود) عملیات این الگوریتم بر اساس، عوامل ضرب چندجمله‌ای‌های همراه با ضرب پیچیده به گونه‌ای که همه چندجمله‌ای‌های موجود در حلقه با ضرایب صحیح و توان حداکثر N-1 باشند. NTRU در واقع از خانواده Parameterised سیستم‌های رمزنگاری می‌باشد به گونه‌ای که، هر سیستم توسط سه پارامتر صحیح (N,p،q) مشخص شده، که به ترتیب نشان دهنده بیشترین درجه برای همه چندجمله‌ای‌ها در حلقه R و کمترین و بیشترین پیمانه است، با این شرایط که همواره N عدد اول، q بزرگتر از p و q و p نسبت به هم اول هستند. همچنین برای قرار دادن چندجمله‌ای‌ که قسمتی از کلید خصوصی است، چندجمله‌ای که برای ساخ یک کلید عمومی استفاده می شود، پیام و مقدار مخفی شده و چندجمله‌ای متناظر لازم است درجه به درجه آن‌ها دقت شود. این عمل، بستگی به انتخاب درجه سختی فاکتورگیری از چندجمله‌ای‌های خاص موجود در حلقه و تبدیل آن به دو چندجمله‌ای با ضرایب بسیار کوچک دارد. شکستن رمز به مقدار زیادی با مشکلات موجود در کاهش شبکه (به منظور حل مشکلات برداری کوچک) ارتباط مستقیم دارد. دقت در انتخاب پارامترهای مناسب برای خنثی کردن حملات بسیار مهم و ضروری می‌باشد. از آنجایی که هم قسمت رمزگذاری و هم قسمت رمزگشایی از ساده‌ترین ضرب چندجمله‌ای‌ها استفاده می‌کند، بنابراین این عملیات در مقایسه با دیگر سیستم‌های رمزگذاری نامتقارن، مانند RSA، ElGamal و Elliptic curve cryptography بسیار سریع تر عمل می‌کند. با این وجود هنوز این سیستم رمزگذاری توسط معیارهای دقیق رمزنگاری رتبه دهی نشده‌است.

سیستم رمزنگاری کلیدهای عمومی مربوط به سیستم رمزنگاری جدید می‌باشد. اولین ورژن از این سیستم، که به‌طور اختصار NTRU صدا زده می‌شد، در حدود سال ۱۹۹۶ توسط سه دانشمند ریاضی (ج. هافستین، ج. پیفر، ج. سیلورمن) ساخته شد. در سال ۱۹۹۶ این ریاضیدانان در کنار هم و با کمک د. لیمن توانستند الگوریتم رمزگذاری NTRU را بدست آورند و حق امتیاز ثبت اختراع را در سیستم رمزنگاری بدست آورند. در ابتدا سیستم رمزنگاری، در مواقعی پیام کد شده را، حتی با وجود این که پیام به‌طور صحیح و کامل رمزگذاری شده بود، به‌طور ناقص به پیام اصلی تبدیل می‌کرد و در مواردی به‌طور کل ناتوان بود و به هیچ وجه پیام اصلی به وجود نمی‌آمد؛ بنابراین سازندگان این روش تصمیم گرفتند که از این الگوریتم برای رمزنگاری کلیدهای عمومی استفاده کنند و قسمت امنیت این سیستم را بر اساس این فرضیه که این الگوریتم برای رمزنگاری کلیدهای عمومی ساخته شده، بنا کردند. در ده سال گذشته افراد زیادی برای ارتقای سیستم رمزنگاری تلاش کردند تا زمانی که در اولین کنفرانس رسمی در مورد رمزنگاری تغییراتی برای افزایش کیفیت عملکرد خود سیستم و قسمت امنیت آن ایجاد شد. بیشتر تغییرات ایجاد شده در قسمت عملکرد، بیشتر بر روی افزایش سرعت رمزنگاری بود تا حل کردن مشکل رمزگشایی این سیستم. تا اینکه در سال ۲۰۰۵ مطبوعات توانستند مشکل این الگوریتم را در در رمزگشایی کشف و بیان کنند. به دلایل امنیتی، از زمان ارائه اولین ورژن این الگوریتم رمزنگاری، پارامترهای جدیدی تعیین شد که به نظر می‌رسید در برابر همه حملاتی که امروزه ما با آن‌ها آشنا هستیم مقاوم و امن هستند و باعث افزایش قدرت محاسبات نیز می‌شوند؛ ولی اکنون این سیستم به‌طور کامل توسط استانداردهای IEEE P1363 که برای رمزنگاری کلمات عمومی بر پایه شبکه به وجود آمده بود تأیید شده‌است. به دلیل سرعت بالای این روش در رمزنگاری کلیدهای عمومی و استفاده حافظه کمتر، می‌توان آن را در دستگاه‌های همراه و کارت‌های هوشمند به کار برد. در آوریل ۲۰۱۱، NTRUEncrypt به عنوان استاندارد X9.98 پذیرفته شد به گونه‌ای که اکنون می‌توان از آن در صنعت خدمات مالی مانند بانک‌ها استفاده کرد.

الگوریتم شور

الگوریتم شور (Shor's Algorithm) یک الگوریتم کوانتومی، برای تجزیه عددها به عوامل اول در زمان چندجمله‌ای (Polynomial time) است. نام این الگوریتم که به افتخار پیتر شر نام‌گذاری شده است، در سال ۱۹۹۴ فرمول‌بندی شد.

الگوریتم گرور

الگوریتم گرور (Grover's algorithm) یک الگوریتم کوانتومی برای جستجو در یک پایگاه داده نامرتب دارای N عضو، در زمانِ (O(N۱/۲ و در فضای ذخیره‌سازی (O(log N است. لُو گرور این الگوریتم را در سال ۱۹۹۶ مطرح کرد. بر روی یک رایانه کلاسیک، جستجو در یک پایگاه داده نامرتب نمی‌تواند در زمان کمتر از زمان خطی یا (O(n، یعنی با بررسی تک تک ورودی‌ها انجام گیرد. الگوریتم گرُوِر بیان می‌کند که روی یک رایانه کوانتومی این عمل با پیچیدگی زمانی (O(N۱/۲ قابل انجام است و به‌طور حدی، سریع‌ترین الگوریتم قابل پیاده‌سازی برای جستجوی پایگاه دادهٔ نامرتب روی یک رایانه کوانتومی است. با وجود اینکه که الگوریتم‌های کوانتومی معمولاً افزایش سرعتی نمایی نسبت به الگوریتم‌های کلاسیک دارند ٬این الگوریتم افزایش سرعتی از توان ۰٫۵ در پی دارد که البته برای Nهای بزرگ بسیار قابل توجه است.