اوراکل تصادفی

در رمزنگاری، اوراکل تصادفی یک اوراکل است که به هر پرس‌وجویی یک جواب کاملاً تصادفی به‌دست می‌دهد، گفته می‌شود. این جواب تصادفی به صورت یکنواخت از دامنه خروجی آن انتخاب می‌شود. اوراکل تصادفی سازگار است به این معنا که به ازای هر ورودی ثابت هر بار یک جواب می‌دهد. در واقع می‌توان به آن به‌عنوان یک تابع کاملاً تصادفی در ریاضیات نگاه کرد. این توابع به صورت کاملاً مجرد در رمزنگاری برای اثبات‌های امنیت استفاده می‌شود و هنوز اثبات نشده است که آیا اوراکل تصادفی وجود دارد یا نه، ولی گمان می‌شود که اوراکل تصادفی به وسیلهٔ شخص ثالث قابل پیاده‌سازی است.

کاربردها

در عمل، اوراکل تصادفی به‌عنوان حالت ایده‌آل تابع درهم ساز رمز نگاری جایگزین می‌شود. برای مثال در جاهایی که به خروجی‌ای نیازمندیم که تصادفی بودن آن قوی باشد.

از اوراکل تصادفی در اثبات‌های رمزنگاری استفاده می‌شود؛ اگر امنیت یک طرح رمزنگاری با استفاده از اوراکل تصادفی در مدل اوراکل تصادفی اثبات شود، نشان می‌دهد که خود طرح نقصی ندارد و اگر نقصی در طرح به وجود می‌آید به خاطر جایگزینی‌ای است که به جای اوراکل تصادفی انجام می‌دهیم (مثلاً به جای اوراکل تصادفی از یک تابع درهم ساز رمز نگاری مثل sha1 استفاده می‌کنیم که ممکن است در مدلی خاص امن نباشد).

همهٔ طرح‌های رمزنگاری نیازی به اوراکل تصادفی ندارند مثلاً جاهایی که فقط یک سری ویژگی‌های خاص را در نظر داریم (برای مثال می‌توان به ویژگی‌های مقاوم در برابر برخورد بودن، مقاوم در برابر تصویر و… اشاره کرد) که این‌ها را می‌توان در مدل استاندارد (ممدل معمولی رمزنگاری) اثبات و استفاده کرد.

یک ویژگی دیگر اوراکل تصادفی این است که عمومی است و همه می‌توانند از آن استفاده کنند ولی کسی از داخل آن خبر ندارد (کد اوراکل را کسی نمی‌داند) ولی برای تابع درهم ساز مثل مرکل-دمگارد، همه کد آن را می‌دانند و بنابراین حمله کننده می‌تواند بهتر به آن حمله کند. این در صورتی است که اوراکل تصادفی مثل یک جعبه جادویی عمل می‌کند و از درون ان بی خبریم.

محدودیت‌ها

یکی از محدودیت‌های اصلی این است که برای پیاده‌سازی اوراکل تصادفی در دنیای واقعی باید آن را با یک تابع درهم ساز «خوب» جایگزین کنیم ولی هم تعریف «خوب» معلوم نیست و هم معلوم نیست که می‌شود چنین کاری را انجام داد یا نه؛ بنابراین مدل‌هایی مثل اوراکل شبه تصادفی هم تعریف شده‌اند.

مشکل دیگر این است که ما چیزی از درون اوراکل نمی‌دانیم ولی برای تابع درهم ساز که به جای اوراکل تصادفی قرار می‌دهیم کد آن را می‌دانیم و می‌توان از این اطلاعات برای حمله به آن استفاده کرد بنابراین پیاده‌سازی اوراکل تصادفی در دنیای واقعی مشکل می‌شود. در واقع طرح‌های رمزنگاری ای وجود دارند که در مدل اوراکل تصادفی امن هستند اما وقتی اوراکل تصادفی را با هر تابع درهم سازی جایگزین می‌کنیم نا امن می‌شوند.

رمز ایده‌آل

رمز ایده‌آل یک اوراکل تصادفی جایگشتی است که یک رمز قالبی ایده‌آل را شبیه‌سازی می‌کند. رمز ایده‌آل را می‌توان به وسیلهٔ اوراکل تصادفی و شبکهٔ فایستل ساخت.

منابع

۱. Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography. CRC Press. ISBN 1-58488-551-3. ۲. CORON, J. S. —DODIS, Y. —MALINAUD, C. —PUNIYA, P. : Merkle-Damg˚ard revisited: How to construct a hash function, in: Advances in Cryptology—CRYPTO ’05, Lecture Notes in Comput. Sci. , Vol. 3621, Springer-Verlag, 2005, pp. 430–448.