Black-Box Models of Computation in Cryptology

الگوریتم‌های گروه عمومی مسائل محاسباتی تعریف شده روی گروه‌های جبری را بدون بهره‌برداری از ویژگی‌های یک نمایش خاص از عناصر گروه حل می‌کنند. این با در نظر گرفتن گروه به عنوان یک جعبه سیاه مدل سازی شده است. این واقعیت که یک مشکل محاسباتی را نمی توان با یک کلاس محدود از الگوریتم ها حل کرد، ممکن است به عنوان پشتیبان این حدس تلقی شود که مشکل در مدل ماشین تورینگ کلاسیک نیز سخت است. علاوه بر این، محدودیت پیچیدگی کمتر برای الگوریتم‌های خاص، بینش مفیدی برای جستجوی الگوریتم‌های تحلیل رمزی است.

تیبور جاگر به چندین سؤال اساسی در مورد مدل‌های جعبه سیاه محاسبات جبری می‌پردازد: مدل گروه عمومی و انواع آن یک انتزاع معقول است؟ محدودیت های این مدل ها چیست؟ آیا می‌توانیم این مدل‌ها را آرام کنیم تا آنها را به واقعیت نزدیک‌تر کنیم؟

Generic group algorithms solve computational problems defined over algebraic groups without exploiting properties of a particular representation of group elements. This is modeled by treating the group as a black-box. The fact that a computational problem cannot be solved by a reasonably restricted class of algorithms may be seen as support towards the conjecture that the problem is also hard in the classical Turing machine model. Moreover, a lower complexity bound for certain algorithms is a helpful insight for the search for cryptanalytic algorithms.

Tibor Jager addresses several fundamental questions concerning algebraic black-box models of computation: Are the generic group model and its variants a reasonable abstraction? What are the limitations of these models? Can we relax these models to bring them closer to the reality?