Quantum Programming

آیا کامپیوترهای کوانتومی رمزنگاری RSA2048 را در سال 2023 خواهند شکست؟

در روزهای پایانی سال 2022 مقاله تحت عنوان زیر توسط محققان چینی منتشر شد.
Factoring integers with sublinear resources on a superconducting quantum processor
با توجه به الگوریتم شور، یک کامپیوتر کوانتومی قادر است عامل‌های اول یک عدد صحیح بسیار بزرگ (که مبنای رمزنگاری هست) را بصورت N=p×q در زمان چندجمله‌ای پیدا کند. اما برای پیاده سازی الگوریتم شور به میلیون‌ها کیوبیت فیزیکی نیاز است. منظور از کیوبیت فیزیکی، کیوبیتی است که در آزمایشگاه ساخته می‌شود. می دانیم در حال حاضر 400-300 کیوبیت در دسترس است و از این رو پیاده‌سازی این الگوریتم بطور موثر امکان پذیر نیست. محققان چینی با معرفی روشی جدید ادعاد کرده‌اند که برای شکستن رمزنگاری RSA2048 تنها 372 کیوبیت فیزیکی لازم است. آنها همچنین یافتن عامل‌های اول یک عدد 48 بیتی را با 10 کیوبیت ابررسانا انجام داده‌اند. اگر این ادعا درست باشد با توجه به در اختیار بودن تعداد کافی از کیوبیت‌های فیزیکی همچون کیوبیت‌های ابررسانا شرکت IBM، رمزنگاری RSA2048 در سال 2023 خواهد شکست. قبل از آنکه به صحت کارکرد الگوریتم معرفی شده بپردازیم به نحوی کارکرد آن نگاهی بیاندازیم. این الگوریتم در دسته الگوریتم‌های ترکیبی کوانتومی و کلاسیک قرار دارد. ابتدا مسئله یافتن عامل‌های اول بصورت مسئله نزدیک ترین بردار (CVP) روی یک صفحه در نظرگرفته می‌شود. این مسئله با الگوریتمBabai حل می‌شود. سپس نتایج به کامپیوتر ارسال می‌شود تا به عنوان بهینه ساز نزدیک‌ترین بردار بهینه را پیدا کند، بدین منظور الگوریتم ترکیبی QAOA بکار گرفته می‌شود. نتایج بهینه‌سازی به الگوریتم اشنور فرستاده می‌شود تا عامل‌های اول p و q به دست آید. در حالت کلی این الگوریتم ترکیب الگوریتم اشنور با الگوریتم QAOA است. الگوریتم اشنور با استفاده از محاسبات کلاسیک عامل‌های اول عدد را محاسبه می‌کند. به دلایل زیر باید با احتیاط در باره صحت کارکرد این الگوریتم صحبت کرد.
دلیل اول: محققان چینی برای تعداد کیوبیت فیزیکی کم الگوریتم را پیاده کرده‌اند از این رو در اندازه‌های بزرگ باید انتظار خطا زیادی داشت.
دلیل دوم: قسمت مهم الگوریتم استفاده از بهینه‌سازی کوانتومی است که ایده مهم الگوریتم است اما در پیاده سازی بهینه سازی کوانتومی هنوز شک وجود دارد چرا که الگوریتم QAOA یک الگوریتم ترکیبی است بطور همزمان از پردازنده کلاسیک و کوانتومی استفاده می‌کند و پیاده‌سازی آن بطور بهینه برای حل این مسئله از چالش‌هاست.
دلیل سوم: قسمت نتیجه‌گیری مقاله نویسندگان گفته‌اند که با توجه به مبهم بودن همگرایی الگوریتم QAOAسرعت الگوریتم واضح نیست و راه یادی تا شکستن RSA باقی است.
با این حال این مقاله گامی است در کاربردی کردن محاسبات کوانتومی و از این جهت حائز اهمیت است.
🆔@QuantumProgramming
🆔http://instagram.com/Quantum.Programming

www.tgoop.com/QuantumProgramming/396

1.74K viewsJan 20, 2023 at 09:47

آیا کامپیوترهای کوانتومی رمزنگاری RSA2048 را در سال 2023 خواهند شکست؟

در روزهای پایانی سال 2022 مقاله تحت عنوان زیر توسط محققان چینی منتشر شد.
Factoring integers with sublinear resources on a superconducting quantum processor
با توجه به الگوریتم شور، یک کامپیوتر کوانتومی قادر است عامل‌های اول یک عدد صحیح بسیار بزرگ (که مبنای رمزنگاری هست) را بصورت N=p×q در زمان چندجمله‌ای پیدا کند. اما برای پیاده سازی الگوریتم شور به میلیون‌ها کیوبیت فیزیکی نیاز است. منظور از کیوبیت فیزیکی، کیوبیتی است که در آزمایشگاه ساخته می‌شود. می دانیم در حال حاضر 400-300 کیوبیت در دسترس است و از این رو پیاده‌سازی این الگوریتم بطور موثر امکان پذیر نیست. محققان چینی با معرفی روشی جدید ادعاد کرده‌اند که برای شکستن رمزنگاری RSA2048 تنها 372 کیوبیت فیزیکی لازم است. آنها همچنین یافتن عامل‌های اول یک عدد 48 بیتی را با 10 کیوبیت ابررسانا انجام داده‌اند. اگر این ادعا درست باشد با توجه به در اختیار بودن تعداد کافی از کیوبیت‌های فیزیکی همچون کیوبیت‌های ابررسانا شرکت IBM، رمزنگاری RSA2048 در سال 2023 خواهد شکست. قبل از آنکه به صحت کارکرد الگوریتم معرفی شده بپردازیم به نحوی کارکرد آن نگاهی بیاندازیم. این الگوریتم در دسته الگوریتم‌های ترکیبی کوانتومی و کلاسیک قرار دارد. ابتدا مسئله یافتن عامل‌های اول بصورت مسئله نزدیک ترین بردار (CVP) روی یک صفحه در نظرگرفته می‌شود. این مسئله با الگوریتمBabai حل می‌شود. سپس نتایج به کامپیوتر ارسال می‌شود تا به عنوان بهینه ساز نزدیک‌ترین بردار بهینه را پیدا کند، بدین منظور الگوریتم ترکیبی QAOA بکار گرفته می‌شود. نتایج بهینه‌سازی به الگوریتم اشنور فرستاده می‌شود تا عامل‌های اول p و q به دست آید. در حالت کلی این الگوریتم ترکیب الگوریتم اشنور با الگوریتم QAOA است. الگوریتم اشنور با استفاده از محاسبات کلاسیک عامل‌های اول عدد را محاسبه می‌کند. به دلایل زیر باید با احتیاط در باره صحت کارکرد این الگوریتم صحبت کرد.
دلیل اول: محققان چینی برای تعداد کیوبیت فیزیکی کم الگوریتم را پیاده کرده‌اند از این رو در اندازه‌های بزرگ باید انتظار خطا زیادی داشت.
دلیل دوم: قسمت مهم الگوریتم استفاده از بهینه‌سازی کوانتومی است که ایده مهم الگوریتم است اما در پیاده سازی بهینه سازی کوانتومی هنوز شک وجود دارد چرا که الگوریتم QAOA یک الگوریتم ترکیبی است بطور همزمان از پردازنده کلاسیک و کوانتومی استفاده می‌کند و پیاده‌سازی آن بطور بهینه برای حل این مسئله از چالش‌هاست.
دلیل سوم: قسمت نتیجه‌گیری مقاله نویسندگان گفته‌اند که با توجه به مبهم بودن همگرایی الگوریتم QAOAسرعت الگوریتم واضح نیست و راه یادی تا شکستن RSA باقی است.
با این حال این مقاله گامی است در کاربردی کردن محاسبات کوانتومی و از این جهت حائز اهمیت است.
🆔@QuantumProgramming
🆔http://instagram.com/Quantum.Programming

BY Quantum Programming