Ideal lattice
مجرد ریاضی میں، مثالی جالی جالی کی ایک خاص کلاس اور چکور جالی کی عمومی شکل ہوتی ہے۔ مثالی جالی قدرتی طور پر نمبر تھیوری کے بہت سے حصوں میں، بلکہ دیگر علاقوں میں بھی پائے جاتے ہیں۔ خاص طور پر، ان کا کرپٹوگرافی میں ایک اہم مقام ہے۔ مائکیانشیو نے چکور جالی کی عمومی شکل کو مثالی جالی کے طور پر بیان کیا۔ انہیں کرپٹو سسٹمز میں استعمال کیا جا سکتا ہے تاکہ جالی کو بیان کرنے کے لیے ضروری پیرامیٹرز کی تعداد کو مربع جڑ سے کم کیا جا سکے، جس سے وہ زیادہ موثر ہو جائیں۔ مثالی جالی ایک نیا تصور ہے، لیکن اسی طرح کی جالی کی کلاسیں ایک طویل عرصے سے استعمال ہوتی رہی ہیں۔ مثال کے طور پر، چکور جالی، مثالی جالی کا ایک خاص کیس، این ٹی آر یو این کرپٹ اور این ٹی آر یو سائن میں استعمال ہوتا ہے۔ مثالی جالی بھی کوانٹم کمپیوٹر اٹیک مزاحم کرپٹوگرافی کی بنیاد بناتی ہے جو غلطیوں کے ساتھ رنگ لرننگ پر مبنی ہے۔ یہ خفیہ نظام اس مفروضے کے تحت ثابت طور پر محفوظ ہیں کہ ان مثالی جالی میں مختصر ترین ویکٹر مسئلہ (ایس وی پی) مشکل ہے۔ تعارف عام طور پر، مثالی جالییں ڈگری کے کچھ ناقابل تلافی کثیر الجہتی کے لیے فارم کے رنگوں میں آئیڈیلز سے مطابقت رکھنے والی جالیں ہوتی ہیں۔ سابقہ کام سے آئیڈیل لیٹیسیس کی تمام تعریفیں مندرجہ ذیل عمومی تصور کی مثالیں ہیں: آئیے ایک رنگ بنیں جس کا اضافی گروپ آئسومورفک ہے (یعنی، یہ رینک کا ایک فری-ماڈیول ہے)، اور آئیے ایک جہتی حقیقی ویکٹر اسپیس (مثال کے طور پر) میں کسی لیٹیس کے لیے ایک اضافی آئسومورفزم میپنگ ہو۔ سرایت کے نیچے انگوٹھی کے لیے مثالی جالی کا خاندان تمام جالی کا مجموعہ ہے، جہاں تعریف نوٹیشن میں ایک مثالی ہے۔ نمائندوں کے معیاری سیٹ کا استعمال کرتے ہوئے، اور ویکٹروں کے ساتھ کثیر الجہتی کی شناخت، حصص کی انگوٹی عدد جالی کے لیے آئسومورفک (ایک اضافی گروپ کے طور پر) ہے، اور کوئی بھی آئیڈیل متعلقہ عدد ذیلی جالی کی وضاحت کرتا ہے۔ ایک مثالی جالی ایک عدد جالی ہے جو ڈگری اور مثالی کے کچھ مونیک کثیر الجہتی کے لیے ہوتی ہے۔ متعلقہ خصوصیات یہ پتہ چلتا ہے کہ نتیجے میں ہونے والے فنکشن کے تصادم سے مزاحم ہونے کی متعلقہ خصوصیات یہ ہیں: ناقابل تلافی ہونا چاہیے۔ رنگ کا معیار مقداری معنوں میں کسی بھی کثیر الجہتی سے زیادہ بڑا نہیں ہوتا ہے۔ پہلی خاصیت کا مطلب یہ ہے کہ رنگ کا ہر آئیڈیل ایک مکمل رینک کی جالی کی وضاحت کرتا ہے اور ثبوت میں بنیادی کردار ادا کرتا ہے۔ لیما: کا ہر آئیڈیل، جہاں ڈگری کا ایک مونیک، ناقابل کٹوتی عدد کثیر الجہتی ہے، ایک مکمل رینک والی جالی کے لیے آئسومورفک ہے۔ ڈنگ اور لنڈنر نے اس بات کا ثبوت دیا کہ مثالی جالی کو عام جالی سے ممتاز کرنا کثیر الجہتی وقت میں کیا جا سکتا ہے اور یہ ظاہر کیا کہ عملی طور پر تصادفی طور پر منتخب شدہ جالی کبھی بھی مثالی نہیں ہوتی ہیں۔ انہوں نے صرف اس معاملے پر غور کیا جہاں جالی کا پورا درجہ ہوتا ہے، یعنی۔ بنیاد لکیری آزاد ویکٹروں پر مشتمل ہوتی ہے۔ یہ کوئی بنیادی پابندی نہیں ہے کیونکہ لیوباشیفسکی اور میکیانشیو نے دکھایا ہے کہ اگر کوئی جالی کسی ناقابل تلافی مونیک کثیر الجہتی کے حوالے سے مثالی ہے، تو اس کا مکمل درجہ ہے، جیسا کہ مندرجہ بالا لیما میں دیا گیا ہے۔ الگورتھم: مکمل درجہ کی بنیاد کے ساتھ مثالی جالی کی شناخت ڈیٹا: ایک مکمل درجہ کی بنیاد نتیجہ: درست اور، اگر اس کے حوالے سے ایک مثالی جالی پر پھیلا ہوا ہے، بصورت دیگر غلط۔ ایچ این ایف کیلکولیٹ میں تبدیل کریں، اور پروڈکٹ کا حساب لگائیں اگر صرف پی کا آخری کالم غیر صفر ہے تو اس کالم کو برابر کرنے کے لیے سیٹ کریں ورنہ غلط واپس آئے گا اگر پھر تلاش کرنے کے لیے سی آر ٹی کا استعمال کریں اور پھر غلط واپس آئے گا اگر پھر سچ واپس آئے گا، ورنہ غلط واپس آئے گا جہاں میٹرکس ایم ہے۔ اس الگورتھم کا استعمال کرتے ہوئے، یہ دیکھا جا سکتا ہے کہ بہت سے لیٹیس مثالی لیٹیس نہیں ہیں۔ مثال کے طور پر، چلو اور، پھر مثالی ہے، لیکن نہیں ہے۔ اس کی ایک مثال لیوباشیفسکی اور میکیانشیو نے دی ہے۔ اس پر الگورتھم انجام دینا اور بنیاد کو بی کے طور پر حوالہ دینا، میٹرکس بی پہلے سے ہی ہرمائیٹ نارمل فارم میں ہے لہذا پہلے مرحلے کی ضرورت نہیں ہے۔ تعین کنندہ ہے، ملحقہ میٹرکس اور آخر میں، پروڈکٹ ہے۔ اس مقام پر الگورتھم رک جاتا ہے، کیونکہ اگر کسی مثالی جالی کو پھیلایا جائے تو اس کے آخری کالم کے علاوہ سب کو صفر ہونا پڑتا ہے۔ کرپٹوگرافی میں استعمال مائکیانشیو نے ساختی چکور جالی کی کلاس متعارف کروائی، جو کثیر الجہتی رنگوں میں آئیڈیلز سے مطابقت رکھتی ہے، اور چکور جالی کے لیے پولی (این)-ایس وی پی کی پابندی کی بدترین صورت کی سختی کی بنیاد پر پہلا ثابت محفوظ یک طرفہ فنکشن پیش کیا۔ (مسئلہ γ-SVP کسی دی گئی جالی کے غیر صفر ویکٹر کی گنتی پر مشتمل ہوتا ہے، جس کا معیار مختصر ترین غیر صفر جالی ویکٹر کے معیار سے γ گنا زیادہ بڑا نہیں ہوتا ہے۔) ایک ہی وقت میں، اس کے الجبرائی ڈھانچے کی بدولت، یہ یک طرفہ فنکشن این ٹی آر یو اسکیم کی تشخیص کے وقت اور اسٹوریج لاگت کے مقابلے میں اعلی کارکردگی حاصل کرتا ہے)۔ اس کے بعد، لیوباشیفسکی اور میکیانشیو اور آزادانہ طور پر پیکرٹ اور روزن نے دکھایا کہ کس طرح ایک موثر اور ثابت محفوظ تصادم مزاحم ہیش فنکشن کی تعمیر کے لیے میکیانشیو کے فنکشن میں ترمیم کی جائے۔ اس کے لیے، انہوں نے مثالی جالی کی زیادہ عمومی کلاس متعارف کروائی، جو کثیر الجہتی رنگوں میں آئیڈیل سے مطابقت رکھتی ہیں۔ تصادم کی مزاحمت پولی (این)-ایس وی پی کی مثالی جالی (جسے پولی (این)-آئیڈیل-ایس وی پی کہا جاتا ہے) پر پابندی کی سختی پر منحصر ہے۔ اوسط کیس تصادم تلاش کرنے کا مسئلہ ایک قدرتی کمپیوٹیشنل مسئلہ ہے جسے آئیڈیل-ایس آئی ایس کہا جاتا ہے، جسے آئیڈیل-ایس وی پی کی بدترین صورتوں کی طرح مشکل دکھایا گیا ہے۔ مثالی جالی سے یقینی طور پر محفوظ موثر دستخطی اسکیمیں بھی تجویز کی گئی ہیں، لیکن مثالی جالی سے موثر طور پر محفوظ عوامی کلیدی خفیہ کاری کی تعمیر ایک دلچسپ کھلا مسئلہ تھا۔ کلیدی تبادلے کے لیے ایل ڈبلیو ای اور رنگ ایل ڈبلیو ای کو استعمال کرنے کا بنیادی خیال 2011 میں یونیورسٹی آف سنسناٹی میں جنتای ڈنگ نے تجویز کیا اور دائر کیا اور رنگ ایل ڈبلیو ای کا استعمال کرتے ہوئے کوانٹم مزاحم کلیدی تبادلے کی جدید ترین تفصیل فراہم کی۔ 2012 میں عارضی پیٹنٹ کی درخواست دائر ہونے کے بعد یہ مقالہ 2012 میں شائع ہوا۔ 2014 میں، پیکرٹ نے ڈنگ کے اسی بنیادی خیال پر عمل کرتے ہوئے ایک کلیدی ٹرانسپورٹ اسکیم پیش کی، جہاں ڈنگ کی تعمیر میں گول کرنے کے لیے اضافی سگنل بھیجنے کا نیا خیال بھی استعمال کیا گیا ہے۔ اسی تصورات کا استعمال کرتے ہوئے ایک ڈیجیٹل دستخط کئی سال پہلے وڈم لیوباشیفسکی نے "ٹریپڈورز کے بغیر جالی کے دستخط" میں کیا تھا۔ پیکرٹ اور لیوباشیفسکی کا کام ایک ساتھ مل کر اسی حفاظتی کمی کے ساتھ رنگ-ایل ڈبلیو ای پر مبنی کوانٹم اٹیک مزاحم الگورتھم کا ایک مجموعہ فراہم کرتا ہے۔ موثر تصادم مزاحم ہیش افعال کرپٹوگرافی میں مثالی جالی کی بنیادی افادیت اس حقیقت سے پیدا ہوتی ہے کہ اس طرح کے جالی میں تقریبا مختصر ترین ویکٹر تلاش کرنے کی سختی کی بنیاد پر بہت موثر اور عملی تصادم مزاحم ہیش افعال بنائے جا سکتے ہیں۔ پیکرٹ اور روزن کے ساتھ ساتھ لیوباشیفسکی اور میکیانسو کے ذریعہ آزادانہ طور پر تصادم کے مزاحم ہیش افعال کی تعمیر کی گئی، جو مثالی جالی (چکور جالی کی عمومی شکل) پر مبنی ہے، اور اس نے ایک تیز اور عملی نفاذ فراہم کیا۔ ان نتائج نے شناخت کی اسکیموں اور دستخطوں سمیت دیگر موثر کرپٹوگرافک تعمیرات کی راہ ہموار کی۔ لیوباشیفسکی اور میکیانشیو نے موثر تصادم مزاحم ہیش افعال کی تعمیرات پیش کیں جو مثالی جالی کے لیے مختصر ترین ویکٹر مسئلے کی بدترین صورت کی سختی کی بنیاد پر محفوظ ثابت ہو سکتی ہیں۔ انہوں نے ہیش فنکشن خاندانوں کی تعریف اس طرح کی: ایک رنگ کو دیکھتے ہوئے، جہاں ڈگری کا ایک مونیک، ناقابل تلافی کثیر الجہتی ہے اور تقریبا ترتیب کا ایک عدد ہے، بے ترتیب عناصر پیدا کرتا ہے، جہاں ایک مستقل ہے۔ آرڈرڈ-ٹپل ہیش فنکشن کا تعین کرتا ہے۔ یہ عناصر کا نقشہ بنائے گا، جہاں اسٹریٹجک طور پر منتخب کردہ ذیلی سیٹ ہے۔ کسی عنصر کے لیے، ہیش ہے۔ یہاں کلید (ہیش فنکشن) کا سائز ہے، اور کثیر الجہتی کے مناسب انتخاب کے لیے فاسٹ فورئیر ٹرانسفارم (ایف ایف ٹی) کا استعمال کرکے وقت پر آپریشن کیا جا سکتا ہے۔ چونکہ یہ مستقل ہے، اس لیے ہیشنگ میں وقت درکار ہوتا ہے۔ انہوں نے یہ ثابت کیا کہ ہیش فنکشن فیملی تصادم کے خلاف مزاحم ہے یہ ظاہر کرتے ہوئے کہ اگر کوئی کثیر الجہتی وقت کا الگورتھم ہے جو اس طرح تلاش کرنے میں غیر معمولی امکان کے ساتھ کامیاب ہوتا ہے کہ، تصادفی طور پر منتخب کردہ ہیش فنکشن کے لیے، تو ایک خاص مسئلہ جسے "مختصر ترین ویکٹر مسئلہ" کہا جاتا ہے، رنگ کے ہر آئیڈیل کے لیے کثیر الجہتی وقت میں حل کرنے کے قابل ہے۔ 2006 میں لیوباشیفسکی اور میکیانشیو کے کام کی بنیاد پر، میکیانشیو اور ریجیو نے مثالی جالی کی بنیاد پر ہیش افعال کے درج ذیل الگورتھم کی وضاحت کی: پیرامیٹرز: انٹیجرز ود، اور ویکٹر ایف۔ کلید: ویکٹرز کو آزادانہ طور پر اور یکساں طور پر بے ترتیب طور پر منتخب کیا جاتا ہے۔ ہیش فنکشن: کے ذریعہ دیا گیا۔ یہاں پیرامیٹرز ہیں، f ایک ویکٹر ہے اور ساختی بلاکس کے ساتھ ایک بلاک میٹرکس ہے۔ اوسط پر مختصر ویکٹر تلاش کرنا (یہاں تک کہ صرف الٹا کثیر الجہتی امکان کے ساتھ بھی) اتنا ہی مشکل ہے جتنا کہ مختلف جالی کے مسائل (جیسے کہ تخمینہ ایس وی پی اور ایس آئی وی پی) کو مثالی جالی کے مقابلے میں بدترین صورت میں حل کرنا، بشرطیکہ ویکٹر ایف مندرجہ ذیل دو خصوصیات کو مطمئن کرے: کسی بھی دو یونٹ ویکٹر u، v کے لیے، ویکٹر [F iru] v چھوٹا ہوتا ہے (جیسے، کثیر الجہتی، عام طور پر معمول)۔ کثیر الجہتی انٹیجرز پر ناقابل کٹوتی ہے، یعنی یہ چھوٹی ڈگری کے انٹیجر کثیر الجہتی کے پروڈکٹ میں عنصر نہیں ہے۔ پہلی خاصیت گردش میٹرکس سے مطابقت رکھنے والے ویکٹر سے مطمئن ہوتی ہے، کیونکہ [ایف۔ یو] وی کے تمام نقاط 1 سے بندھے ہوتے ہیں، اور اسی وجہ سے۔ تاہم، اس سے متعلق کثیر الجہتی ناقابل تلافی نہیں ہے کیونکہ اس میں عوامل ہوتے ہیں، اور اسی وجہ سے تصادم کو مؤثر طریقے سے پایا جا سکتا ہے۔ لہذا، تصادم مزاحم ہیش افعال حاصل کرنے کے لیے ایک اچھا انتخاب نہیں ہے، لیکن بہت سے دوسرے انتخاب ممکن ہیں۔ مثال کے طور پر، f کے کچھ انتخاب جن کے لیے دونوں خصوصیات مطمئن ہیں (اور اس وجہ سے، بدترین صورت میں حفاظتی ضمانتوں کے ساتھ تصادم مزاحم ہیش افعال کا نتیجہ) وہ ہیں جہاں پرائم ہے، اور 2 کی طاقت کے برابر ہے۔ ڈیجیٹل دستخطی اسکیمیں سب سے اہم کرپٹوگرافک پرائمیٹوز میں سے ہیں۔ انہیں جالی کے مسائل کی بدترین صورت میں سختی کی بنیاد پر یک طرفہ افعال کا استعمال کرکے حاصل کیا جا سکتا ہے۔ تاہم، وہ ناقابل عمل ہیں۔ غلطیوں کے ساتھ سیکھنے، غلطیوں کے ساتھ رنگ لرننگ اور ٹریپ ڈور لیٹیس پر مبنی متعدد نئی ڈیجیٹل دستخطی اسکیمیں تیار کی گئی ہیں کیونکہ غلطیوں کے ساتھ سیکھنے کے مسئلے کو کرپٹوگرافک سیاق و سباق میں لاگو کیا گیا تھا۔ ڈیجیٹل دستخطوں کی ان کی براہ راست تعمیر مثالی (مثال کے طور پر، چکور) جالی میں مختصر ترین ویکٹر کے قریب ہونے کی پیچیدگی پر مبنی ہے۔ لیوباشیفسکی اور میکیانشیو کی اسکیم میں مثالی جالی کی بنیاد پر بدترین صورت میں حفاظتی ضمانت ہوتی ہے اور یہ آج تک معلوم سب سے زیادہ غیر علامتی طور پر موثر تعمیر ہے، جس سے دستخطی نسل اور تصدیق کے الگورتھم ملتے ہیں جو تقریبا لکیری وقت میں چلتے ہیں۔ ان کے کام کی طرف سے اٹھائے گئے اہم کھلے مسائل میں سے ایک اسی طرح کی کارکردگی کے ساتھ ایک بار کے دستخط کی تعمیر ہے، لیکن یہ ایک کمزور سختی کے مفروضے پر مبنی ہے۔ مثال کے طور پر، سب سے مختصر ویکٹر مسئلہ (ایس وی پی) (مثالی جالی میں) کو ایک عنصر کے اندر قریب کرنے کی سختی کی بنیاد پر سیکیورٹی کے ساتھ ایک بار دستخط فراہم کرنا بہت اچھا ہوگا۔ ان کی تعمیر ایک بار کے دستخطوں سے معیاری تبدیلی پر مبنی ہے (یعنی۔ دستخطیں جو کسی ایک پیغام پر محفوظ طریقے سے دستخط کرنے کی اجازت دیتی ہیں) عام دستخطی اسکیموں کے لیے، ایک جالی پر مبنی ایک وقتی دستخط کی نئی تعمیر کے ساتھ، جس کی سیکیورٹی بالآخر تمام جالی میں سب سے چھوٹے ویکٹر کو لگ بھگ کرنے کی بدترین صورت کی سختی پر مبنی ہوتی ہے۔ کسی بھی ناقابل تلافی کثیر الجہتی کے لیے رنگ میں آئیڈیلز کے مطابق۔ کلیدی نسل الگورتھم: ان پٹ:، ڈگری کا ناقابل تلافی کثیر الجہتی۔ سیٹ کریں،، تمام مثبت کے لیے، سیٹوں کو اس طرح بیان کیا جائے: جیسے کہ یکساں طور پر بے ترتیب سٹرنگ کا انتخاب کریں اگر پھر سیٹ کریں تو سٹرنگ کے آخر میں پہلے 1 کی پوزیشن پر سیٹ کریں اگر آزادانہ طور پر اور یکساں طور پر بے ترتیب سے منتخب کریں اور بالترتیب سائننگ کلید:۔ تصدیق کی کلید: الگورتھم پر دستخط کرنا: ان پٹ: پیغام اس طرح کریں کہ ؛ کلیدی آؤٹ پٹ پر دستخط کرنا: تصدیق کا الگورتھم: ان پٹ: پیغام ؛ دستخط ؛ تصدیق کی کلیدی آؤٹ پٹ: "قبول کریں"، اگر اور "مسترد کریں"، بصورت دیگر۔ ایس ڈبلیو آئی ایف ایف ٹی ہیش فنکشن ہیش فنکشن کافی موثر ہے اور پیچیدہ نمبروں پر فاسٹ فورئیر ٹرانسفارم (ایف ایف ٹی) کا استعمال کرتے ہوئے وقت کے ساتھ غیر علامتی طور پر شمار کیا جا سکتا ہے۔ تاہم، عملی طور پر، اس میں کافی حد تک اوور ہیڈ ہوتا ہے۔ مائیکیانشیو اور ریجیو کے ذریعہ بیان کردہ ہیش افعال کا سویفٹ خاندان بنیادی طور پر (ایف ایف ٹی) کا استعمال کرتے ہوئے اوپر والے ہیش فنکشن کا ایک انتہائی بہتر ورژن ہے۔ ویکٹر f کو 2 کی طاقت کے برابر مقرر کیا گیا ہے، تاکہ متعلقہ کثیر الجہتی ناقابل تلافی ہو۔ ایک پرائم نمبر ہونے دیں جو تقسیم کرتا ہے، اور بعد میں منتخب ہونے کے لیے ایک الٹا میٹرکس ہونے دیں۔ ایس ڈبلیو آئی ایف ایف ٹی ہیش فنکشن ایک کلید کا نقشہ بناتا ہے جس میں یکساں طور پر منتخب کردہ ویکٹروں پر مشتمل ہوتا ہے اور ایک ان پٹ جہاں پہلے کی طرح ہے۔ الٹا میٹرکس کے ذریعے ضرب یکساں طور پر منتخب کردہ نقشہ جات سے یکساں طور پر منتخب کردہ نقشہ جات۔ اس کے علاوہ، اگر اور صرف اگر۔ یہ دونوں حقائق مل کر یہ ثابت کرتے ہیں کہ ایس ڈبلیو آئی ایف ایف ٹی میں تصادم تلاش کرنا بنیادی آئیڈیل لیٹس فنکشن میں تصادم تلاش کرنے کے مترادف ہے، اور ایس ڈبلیو آئی ایف ایف ٹی کی دعوی کردہ تصادم کے خلاف مزاحمت کی خاصیت کو آئیڈیل لیٹس پر بدترین صورت میں لیٹس کے مسائل سے منسلک کیا جاتا ہے۔ ایس ڈبلیو آئی ایف ایف ٹی ہیش فنکشن کا الگورتھم یہ ہے: پیرامیٹرز: انٹیجرز جیسے کہ 2 کی طاقت ہے، پرائم ہے، اور۔ کلید: ویکٹرز کو آزادانہ طور پر اور یکساں طور پر بے ترتیب طور پر منتخب کیا جاتا ہے۔ ان پٹ: ویکٹر۔ آؤٹ پٹ: ویکٹر، جہاں جزو کے لحاظ سے ویکٹر پروڈکٹ ہے۔ غلطیوں کے ساتھ سیکھنا (ایل ڈبلیو ای) رنگ-ایل ڈبلیو ای غلطیوں کے ساتھ سیکھنا (ایل ڈبلیو ای) مسئلہ کو بدترین صورت میں جالی کے مسائل کی طرح مشکل دکھایا گیا ہے اور اس نے بہت سے کرپٹوگرافک ایپلی کیشنز کی بنیاد کے طور پر کام کیا ہے۔ تاہم، یہ ایپلی کیشنز ایل ڈبلیو ای کے استعمال میں ایک موروثی کواڈریٹک اوور ہیڈ کی وجہ سے غیر موثر ہیں۔ واقعی موثر ایل ڈبلیو ای ایپلی کیشنز حاصل کرنے کے لیے، لیوباشیفسکی، پیکرٹ اور ریجیو نے ایل ڈبلیو ای کے مسئلے کے ایک مناسب ورژن کو رنگوں کی ایک وسیع کلاس میں بیان کیا اور ان رنگوں میں مثالی جالی پر بدترین صورت کے مفروضوں کے تحت اس کی سختی کو ثابت کیا۔ انہوں نے اپنے ایل ڈبلیو ای ورژن کو رنگ-ایل ڈبلیو ای کہا۔ فرض کریں، جہاں حفاظتی پیرامیٹر 2 کی طاقت ہے، عقلی پر ناقابل تلافی بناتا ہے۔ (یہ خاص طور پر سائکلوٹومک کثیر الجہتی کے خاندان سے آتا ہے، جو اس کام میں خصوصی کردار ادا کرتے ہیں)۔ فرض کریں کہ یہ انٹیجر پولینومیئلز ماڈیولو کی انگوٹی ہے۔ عناصر (یعنی ریسیڈیوز ماڈیولو) کی نمائندگی عام طور پر ڈگری سے کم کے انٹیجر کثیر الجہتی کے ذریعے کی جاتی ہے۔ ایک کافی بڑا پبلک پرائم ماڈیولس ہونے دیں (ایک کثیر الجہتی سے منسلک)، اور دونوں اور انٹیجر کثیر الجہتی ماڈیولو کی انگوٹی ہونے دیں۔ کے عناصر کی نمائندگی ڈگری سے کم کے کثیر الجہتی سے کی جا سکتی ہے-جن کے گتانک سے ہیں۔ اوپر بیان کردہ رنگ میں، R-LWE مسئلہ کو مندرجہ ذیل طور پر بیان کیا جا سکتا ہے۔ ایک یکساں بے ترتیب رنگ عنصر ہونے دیں، جسے خفیہ رکھا جاتا ہے۔ معیاری ایل ڈبلیو ای کے مطابق، حملہ آور کا مقصد من مانی طور پر بہت سی (آزاد) 'بے ترتیب شور والی رنگ مساوات' کو حقیقی طور پر یکساں مساوات سے ممتاز کرنا ہے۔ مزید خاص طور پر، شور والی مساوات اس شکل کی ہوتی ہیں، جہاں a یکساں طور پر بے ترتیب ہوتا ہے اور پروڈکٹ کو کسی 'چھوٹی' بے ترتیب غلطی کی اصطلاح سے پریشان کیا جاتا ہے، جسے کسی خاص تقسیم سے منتخب کیا جاتا ہے۔ انہوں نے رنگ-ایل ڈبلیو ای کے سرچ ورژن میں مثالی جالی پر لگ بھگ ایس وی پی (بدترین صورت میں) سے کوانٹم کمی دی، جہاں مقصد من مانی طور پر بہت سی شور والی مصنوعات سے راز (کسی کے لیے بھی زیادہ امکان کے ساتھ) کو بازیافت کرنا ہے۔ یہ نتیجہ عام جالی کے لیے ریجیو کی تکراری کوانٹم کمی کے عمومی خاکے کی پیروی کرتا ہے، لیکن مثالی جالی کمی کے 'الجبرائی' اور 'ہندسی' دونوں اجزاء میں کئی نئی تکنیکی رکاوٹیں متعارف کراتی ہیں۔ انہوں نے ان رکاوٹوں پر قابو پانے کے لیے الجبرائی نمبر تھیوری، خاص طور پر، نمبر فیلڈ کی کینونکل ایمبیڈنگ اور چینی ریمینڈر تھیوریم کا استعمال کیا۔ انہیں مندرجہ ذیل نظریہ ملا: نظریہ ڈگری کا ایک صوابدیدی نمبر فیلڈ ہے۔ من مانی ہونے دیں، اور (عقلی) انٹیجر ماڈیولس کو ایسا ہونے دیں۔ جہاں سے-سے-تک ممکنہ کثیر الجہتی وقت کوانٹم میں کمی ہوتی ہے۔ 2013 میں گونیسو، لیوباشیفسکی اور پوپلمین نے غلطیوں کے مسئلے کے ساتھ رنگ لرننگ پر مبنی ایک ڈیجیٹل دستخطی اسکیم کی تجویز پیش کی۔ 2014 میں، پیکرٹ نے اپنے مقالے، "انٹرنیٹ کے لیے لیٹیس کرپٹوگرافی" میں غلطیوں کے کلیدی تبادلے (آر ایل ڈبلیو ای-کے ای ایکس) کے ساتھ رنگ لرننگ پیش کی۔ اسے سنگھ کے کام سے مزید فروغ ملا۔ آئیڈیل-ایل ڈبلیو ای اسٹیہل، اسٹین فیلڈ، تناکا اور زگاوا نے ایل ڈبلیو ای مسئلہ (آئیڈیل-ایل ڈبلیو ای) کے ایک منظم قسم کی وضاحت کی ہے تاکہ مثالی جالی میں لگ بھگ ایس وی پی کی بدترین صورت کی سختی پر مبنی ایک موثر عوامی کلیدی خفیہ کاری اسکیم کو بیان کیا جا سکے۔ یہ پہلی سی پی اے محفوظ عوامی کلیدی خفیہ کاری اسکیم ہے جس کی سیکیورٹی سب ایکسپونینشیل کوانٹم حملوں کے خلاف-آئیڈیل-ایس وی پی کی بدترین صورتوں کی سختی پر منحصر ہے۔ یہ غیر علامتی طور پر زیادہ سے زیادہ کارکردگی حاصل کرتا ہے: عوامی/نجی کلید کی لمبائی بٹس ہوتی ہے اور امورٹائزڈ انکرپشن/ڈکرپشن لاگت بٹ آپریشن فی میسج بٹ ہوتی ہے (بٹس کو ایک ہی وقت میں، قیمت پر انکرپٹ کرنا)۔ یہاں حفاظتی مفروضہ یہ ہے کہ-آئیڈیل-ایس وی پی کو کسی بھی سب ایکسپونینشیل ٹائم کوانٹم الگورتھم کے ذریعے حل نہیں کیا جا سکتا۔ یہ قابل ذکر ہے کہ یہ معیاری عوامی کلیدی کرپٹوگرافی حفاظتی مفروضوں سے زیادہ مضبوط ہے۔ دوسری طرف، زیادہ تر عوامی کلیدی کرپٹوگرافی کے برعکس، جالی پر مبنی کرپٹوگرافی سب ایکسپونینشیل کوانٹم حملوں کے خلاف تحفظ کی اجازت دیتی ہے۔ عام جالی پر مبنی زیادہ تر خفیہ نظام غلطیوں کے ساتھ سیکھنے (ایل ڈبلیو ای) کی اوسط کیس سختی پر انحصار کرتے ہیں۔ ان کی اسکیم ایل ڈبلیو ای کے ایک منظم قسم پر مبنی ہے، جسے وہ آئیڈیل-ایل ڈبلیو ای کہتے ہیں۔ انہیں مثالی جالی کی پابندی سے پیدا ہونے والی دو اہم مشکلات کو روکنے کے لیے کچھ تکنیکیں متعارف کرانے کی ضرورت تھی۔ سب سے پہلے، غیر ساختہ جالی پر مبنی پچھلے کرپٹو سسٹمز باؤنڈ ڈسٹنس ڈیکوڈنگ مسئلہ (بی ڈی ڈی) سے ایل ڈبلیو ای (یہ ایس وی پی سے ایل ڈبلیو ای تک کوانٹم میں کمی کا کلاسیکی قدم ہے) تک ریگیو کے بدترین کیس سے اوسط کیس کلاسیکی کمی کا استعمال کرتے ہیں۔ یہ کمی سمجھی جانے والی جالی کی غیر ساخت کا استحصال کرتی ہے، اور ایسا لگتا ہے کہ مثالی-ایل ڈبلیو ای میں شامل ساختہ جالی تک نہیں پہنچتی ہے۔ خاص طور پر، ایل ڈبلیو ای میٹرکس کی قطاروں کی ممکنہ آزادی ایک ہی قطار پر غور کرنے کی اجازت دیتی ہے۔ دوسرا، پچھلے کرپٹو سسٹمز میں استعمال ہونے والا دوسرا جزو، یعنی ریجیو کا ایل ڈبلیو ای کے کمپیوٹیشنل ورژن سے اس کے فیصلہ کن ورژن میں کمی، بھی آئیڈیل-ایل ڈبلیو ای کے لیے ناکام معلوم ہوتا ہے: یہ ایل ڈبلیو ای میٹرکس کے کالموں کی ممکنہ آزادی پر انحصار کرتا ہے۔ ان مشکلات پر قابو پانے کے لیے، انہوں نے تخفیف کے کلاسیکی قدم سے گریز کیا۔ اس کے بجائے، انہوں نے ایس آئی ایس (اوسط کیس تصادم تلاش کرنے کا مسئلہ) سے ایل ڈبلیو ای میں ایک نئی کوانٹم اوسط کیس کی کمی کی تعمیر کے لیے کوانٹم قدم کا استعمال کیا۔ یہ آئیڈیل-ایس آئی ایس سے لے کر آئیڈیل-ایل ڈبلیو ای تک بھی کام کرتا ہے۔ بدترین کیس آئیڈیل-ایس وی پی سے اوسط کیس آئیڈیل-ایس آئی ایس میں کمی کے ساتھ مل کر، انہوں نے آئیڈیل-ایس وی پی سے آئیڈیل-ایل ڈبلیو ای میں کوانٹم کمی حاصل کی۔ یہ آئیڈیل-ایل ڈبلیو ای کے کمپیوٹیشنل ورژن کی سختی کو ظاہر کرتا ہے۔ چونکہ انہوں نے فیصلہ کن قسم کی سختی حاصل نہیں کی، اس لیے انہوں نے خفیہ کاری کے لیے سڈورینڈم بٹس حاصل کرنے کے لیے ایک عام کٹر فنکشن کا استعمال کیا۔ یہی وجہ ہے کہ انہیں ایس وی پی کی تیز رفتار سختی کو قبول کرنے کی ضرورت تھی۔ مکمل طور پر ہومومورفک خفیہ کاری ایک مکمل طور پر ہومومورفک خفیہ کاری (ایف ایچ ای) اسکیم ہے جو خفیہ کردہ ڈیٹا پر کمپیوٹیشن کی اجازت دیتی ہے، بغیر پہلے ڈکرپٹ کرنے کی ضرورت کے۔ مکمل طور پر ہومومورفک خفیہ کاری اسکیم کی تعمیر کا مسئلہ سب سے پہلے 1978 میں ریویسٹ، ایڈلیمین اور ڈرٹوزوس نے پیش کیا تھا، جو کہ ریویسٹ، ایڈلیمین اور شمیر کے ذریعہ آر ایس اے کی ایجاد کے فورا بعد تھا۔ ایک خفیہ کاری اسکیم سرکٹس کے لیے ہومومورفک ہوتی ہے اگر، کسی بھی سرکٹ کے لیے، دی گئی ہو، اور، یہ اسے برقرار رکھتی ہے۔ مکمل طور پر ہومومورفک ہے اگر یہ سائز کے تمام سرکٹس کے لیے ہومومورفک ہے جہاں اسکیم کا حفاظتی پیرامیٹر ہے۔ 2009 میں، جینٹری نے مکمل طور پر ہومومورفک خفیہ کاری اسکیم کی تعمیر کے مسئلے کا پہلا حل پیش کیا۔ اس کی اسکیم مثالی جالی پر مبنی تھی۔ لیٹیس پر مبنی کرپٹوگرافی ہومومورفک انکرپشن رنگ لرننگ ود ایررز کلیدی تبادلے پوسٹ کوانٹم کرپٹوگرافی مختصر عدد حل مسئلہ حوالہ جات نمبر تھیوری لیٹیس پر مبنی کرپٹوگرافی پوسٹ کوانٹم کرپٹوگرافی بھی دیکھیں۔