Advances in Cryptology: Proceedings of CRYPTO 84

اخیراً، علاقه زیادی به تولیدکننده‌های اعداد شبه تصادفی «خوب» وجود داشته است [lo, 4, 14, 31. این مولدهای رمزنگاری امن «خوب» هستند به این معنا که همه را پاس می‌کنند. آزمون های آماری زمان چند جمله ای احتمالی با این حال، علی‌رغم این ویژگی‌های خوب، ژنراتورهای ایمن که تاکنون شناخته شده‌اند، از ناکارآمد بودن رنج می‌برند. موثرترین آنها n2 مرحله (یک ضرب مدولار که n طول دانه است) برای تولید یک بیت انجام می دهد. مولدهای اعداد تصادفی شبه که در حال حاضر در عمل استفاده می شوند، n بیت در هر ضرب (n2 مرحله) خروجی می دهند. یک مشکل باز مهم، خروجی حتی دو بیت در هر ضرب به روش رمزنگاری امن بود. این مشکل توسط Blum, Blum & Shub [3] در زمینه ژنراتور z2 mod N بیان شده است. آنها همچنین می پرسند: برای حفظ امنیت رمزنگاری، در هر ضرب چند بیت می توان قرار داد؟ در این مقاله ما یک شرط ساده، شرط XOR را بیان می‌کنیم و نشان می‌دهیم که هر ژنراتوری که این شرط را برآورده کند، می‌تواند بیت‌های ورود را در هر ضرب تولید کند. ما نشان می‌دهیم که شرط XOR توسط بیت‌های کم‌اهمیت lop ژنراتور z2-mod N برآورده می‌شود. امنیت ژنراتور z2 mod N بر اساس باقیمانده درجه دوم [3] بود. این ژنراتور نمونه ای از Trapdoor Generator [13] است و از ویژگی های trapdoor آن در طراحی پروتکل استفاده شده است. ما امنیت این ژنراتور را با اثبات آن به سختی فاکتورگیری تقویت می کنیم.

Recently, there has been a lot of interest in provably "good" pseudo-random number generators [lo, 4, 14, 31. These cryptographically secure generators are "good" in the sense that they pass all probabilistic polynomial time statistical tests. However, despite these nice properties, the secure generators known so far suffer from the han- cap of being inefiicient; the most efiicient of these take n2 steps (one modular multip- cation, n being the length of the seed) to generate one bit. Pseudc-random number g- erators that are currently used in practice output n bits per multiplication (n2 steps). An important open problem was to output even two bits on each multiplication in a cryptographically secure way. This problem was stated by Blum, Blum & Shub [3] in the context of their z2 mod N generator. They further ask: how many bits can be o- put per multiplication, maintaining cryptographic security? In this paper we state a simple condition, the XOR-Condition and show that any generator satisfying this condition can output logn bits on each multiplication. We show that the XOR-Condition is satisfied by the lop least significant bits of the z2-mod N generator. The security of the z2 mod N generator was based on Quadratic Residu- ity [3]. This generator is an example of a Trapdoor Generator [13], and its trapdoor properties have been used in protocol design. We strengthen the security of this gene- tor by proving it as hard as factoring.