Naor–Reingold pseudorandom function
1997 میں، مونی نور اور عمر رینگولڈ نے نجی کلید کے ساتھ ساتھ عوامی کلیدی خفیہ نگاری میں مختلف خفیہ نگاری کے ابتدائی حصوں کے لیے موثر تعمیرات بیان کیں۔ ان کا نتیجہ ایک موثر سڈورینڈم فنکشن کی تعمیر ہے۔ فرض کریں کہ p اور l، l |p −1 کے ساتھ پرائم نمبر ہوں۔ ضرب ترتیب l کا ایک عنصر g ω منتخب کریں۔ پھر ہر ایک (n + 1) جہتی ویکٹر a = (a0, a1,., an) ω کے لیے وہ اس فنکشن کی وضاحت کرتے ہیں جہاں x = x1 ہے۔ xn عدد x کی بٹ نمائندگی ہے، 0 ≤ x ≤ 2n − 1، اگر ضروری ہو تو کچھ اضافی لیڈنگ زیرو کے ساتھ۔ مثال کے طور پر فرض کریں کہ p = 7 اور l = 3 ؛ تو l |p −1۔ ضرب ترتیب 3 کا g = 4 bul منتخب کریں (چونکہ 43 = 64 ष्ण 1 موڈ 7)۔ n = 3، a = (1، 1، 2، 1) اور x = 5 (5 کی بٹ نمائندگی 101 ہے) کے لیے، ہم مندرجہ ذیل حساب لگا سکتے ہیں: کارکردگی ناور-رنگولڈ کی تعمیر میں فنکشن کی تشخیص بہت مؤثر طریقے سے کی جا سکتی ہے۔ کسی بھی نقطہ پر فنکشن کی قدر کا حساب لگانا ایک ماڈیولر ایکسپوینٹیشن اور این-ماڈیولر ضرب کے ساتھ موازنہ ہے۔ اس فنکشن کا حساب متوازی طور پر باؤنڈڈ ڈیپتھ اور پولینومیل سائز کے تھریشولڈ سرکٹس کے ذریعے کیا جا سکتا ہے۔ ناور-رنگولڈ فنکشن کو بہت سی کرپٹوگرافک اسکیموں کی بنیاد کے طور پر استعمال کیا جا سکتا ہے جن میں سمیٹرک انکرپشن، تصدیق اور ڈیجیٹل دستخط شامل ہیں۔ فنکشن کی سیکیورٹی فرض کریں کہ حملہ آور فنکشن کے کئی آؤٹ پٹ دیکھتا ہے، جیسے۔ ، اور حساب لگانا چاہتا ہے۔ سادگی کے لیے فرض کریں کہ x1 = 0، پھر حملہ آور کو اور حاصل کرنے کے لیے کمپیوٹیشنل ڈفی ہیلمین (سی ڈی ایچ) کو حل کرنے کی ضرورت ہے۔ عام طور پر، k سے k + 1 پر منتقل ہونے سے بٹ پیٹرن میں تبدیلی آتی ہے اور جب تک کہ k + 1 2 کی طاقت نہ ہو تب تک ایکسپونینٹ کو اس میں تقسیم کیا جا سکتا ہے تاکہ کمپیوٹیشن پہلے کے دو نتائج کے درمیان ڈفی ہیلمین کلید کی کمپیوٹنگ سے مطابقت رکھتی ہے۔ یہ حملہ آور اگلے ترتیب والے عنصر کی پیش گوئی کرنا چاہتا ہے۔ اس طرح کا حملہ بہت برا ہوگا-لیکن سخت ڈفی ہیلمین مسئلہ (ڈی ایچ پی) والے گروپوں میں کام کرکے اس سے لڑنا بھی ممکن ہے۔ مثال: حملہ آور فنکشن کے کئی آؤٹ پٹ دیکھتا ہے۔ ، جیسا کہ پچھلی مثال میں، اور۔ پھر، حملہ آور اس فنکشن کے اگلے ترتیب عنصر کی پیش گوئی کرنا چاہتا ہے۔ تاہم، حملہ آور جان کر اور کے نتیجے کی پیش گوئی نہیں کر سکتا۔ دوسرے حملے بھی ہیں جو سڈورینڈم نمبر جنریٹر کے لیے بہت خراب ہوں گے: صارف آؤٹ پٹ سے بے ترتیب نمبر حاصل کرنے کی توقع کرتا ہے، اس لیے یقینا اسٹریم کی پیش گوئی نہیں کی جانی چاہیے، لیکن اس سے بھی زیادہ، یہ بے ترتیب سٹرنگ سے ناقابل شناخت ہونا چاہیے۔ فنکشن کا اندازہ کرنے کے لیے اوریکل تک رسائی کے ساتھ الگورتھم کی نشاندہی کریں۔ فرض کریں کہ فیصلہ کن ڈفی ہیلمین کا مفروضہ اس کے لیے ہے، نور اور رینگولڈ ظاہر کرتے ہیں کہ ہر ممکنہ کثیر الجہتی وقت کے الگورتھم کے لیے اور کافی حد تک بڑا n نہ ہونے کے برابر ہے۔ پہلا امکان بیج s = (p، g، a) کے انتخاب پر لیا جاتا ہے اور دوسرا امکان p، g بائی، انسٹنس جنریٹر، اور تمام افعال کے سیٹ کے درمیان فنکشن کے بے ترتیب انتخاب پر مبنی بے ترتیب تقسیم پر لیا جاتا ہے۔ لکیری پیچیدگی کرپٹوگرافک مقاصد کے لیے ایک ترتیب کتنی مفید ہو سکتی ہے اس کی ایک قدرتی پیمائش اس کی لکیری پیچیدگی کا سائز ہے۔ کسی n-عنصر کی ترتیب W (x)، x = 0,1,2،.، n-1 کی لکیری پیچیدگی، کسی رنگ کے اوپر، مختصر ترین لکیری تکرار تعلق W (x + l) = Al−1W (x + l−1) +. + A0W (x)، x = 0,1,2،.، n-l−1 کے ساتھ A0،.، Al−1 ω کی لمبائی ہے، جو اس ترتیب سے مطمئن ہے۔ کچھ> 0 کے لیے، n ≤ (1 +)، کسی بھی، کافی بڑے l کے لیے، ترتیب کی لکیری پیچیدگی، 0 ≤ x ≤ 2n-1، ممکنہ طور پر زیادہ تر ویکٹروں کے علاوہ سب کے لیے تسلی بخش ہوتی ہے۔ اس کام کے باؤنڈ کے نقصانات ہیں، یعنی یہ بہت دلچسپ کیس پر لاگو نہیں ہوتا ہے تقسیم کی یکسانیت کی شماریاتی تقسیم تقریبا تمام ویکٹر a ω کے لیے یکساں تقسیم کے قریب ہے۔ سیٹ کی تضاد ہونے دیں۔ اس طرح، اگر p کی بٹ لمبائی ہے تو تمام ویکٹروں کے لیے a bul باؤنڈ ہولڈز، جہاں اور اگرچہ اس پراپرٹی کے کوئی فوری کرپٹوگرافک مضمرات نہیں لگتے ہیں، الٹا حقیقت، یعنی غیر یکساں تقسیم، اگر سچ ہے تو اس فنکشن کے استعمال کے لیے تباہ کن نتائج برآمد ہوں گے۔ الپٹک وکر میں ترتیب اس فنکشن کا الپٹک وکر ورژن بھی دلچسپی کا باعث ہے۔ خاص طور پر، یہ متعلقہ نظام کی کرپٹوگرافک سیکیورٹی کو بہتر بنانے میں مدد کر سکتا ہے۔ فرض کریں کہ p> 3 پرائم ہے اور E کو ایک الپٹک وکر ہونے دیں، پھر ہر ویکٹر a ذیلی گروپ میں ایک محدود ترتیب کی وضاحت کرتا ہے: جہاں انٹیجر کی بٹ نمائندگی ہے۔ نور-رنگولڈ ایلیپٹک وکر سیکوینس کی تعریف اس طرح کی گئی ہے کہ اگر فیصلہ کن ڈفی-ہیلمین مفروضہ برقرار رہتا ہے، تو انڈیکس k کثیر الجہتی وقت میں حساب کرنے کے لیے کافی نہیں ہے، چاہے حملہ آور بے ترتیب <ID1:// en. وکیپیڈیا. org/وکی/ایلیپٹک _ وکر پر کثیر الجہتی طور پر بہت سے سوالات انجام دے۔ فیصلہ کن ڈفی-ہیلمین مفروضہ محدود فیلڈ الٹا ہم آہنگ جنریٹر عمومی الٹا ہم آہنگ سڈورینڈم نمبر نوٹ حوالہ جات۔ سیوڈورانڈم نمبر جنریٹر کرپٹوگرافی