تابع یک طرفه
دانشنامه عمومی
وجود توابع یک طرفه در علوم رایانه، هنوز به عنوان یک مسئلهٔ حل نشدهٔ پژوهشی مطرح می باشد. در واقع وجود چنین توابعی نشانگر نابرابری کلاس های P و NP است که به تبع آن مهم ترین مسئلهٔ حل نشدهٔ علوم رایانهٔ نظری ثابت می شود. عکس گزارهٔ گفته شده درست نیست، بدین معنی که نابرابری کلاس های P و NP، وجود توابع یک طرفه را به طور مستقیم نتیجه نمی دهد.
در موارد کاربردی منظور از آسانی و پیچیدگی معمولاً به دستگاه محاسبهٔ مورد نظر برمی گردد. توابع یک طرفه، ابزارهای بنیادی در رمزنگاری، احراز هویّت، اصالت سنجی و دیگر کاربردهای امنیّت داده می باشند. گرچه مسئلهٔ وجود توابع یک طرفه هنوز مسئله ای باز است، امّا نامزدهای متعدّدی برای این توابع جهت استفاده در مخابرات و سامانه های تجارت الکترونیک در طول دهه های گذشته در نظر گرفته شده است.
تابع f : { 0 , 1 } ∗ → { 0 , 1 } ∗ یک طرفه است هرگاه f توسّط یک الگوریتم چندجمله ای قابل محاسبه باشد، برای هر الگوریتم تصادفی که در زمان چندجمله ای از طول ورودی اجرا می شود و برای هر چندجمله ای p ( n ) و برای مقادیر بزرگ n داشته باشیم:
Pr < 1 p ( n )
به طوری که انتخاب x به طور یکنواخت روی { 0 , 1 } n است. توجّه داشته باشید که طبق تعریف، به دست آوردن پیش تصویر یک عنصر باید در حالت میانگین سخت باشد و لزومی ندارد که در بدترین حالت هم سخت باشد.
جایگشت یک طرفه تابع یک طرفه ای است که خود تابع یک جایگشت است. به طور دقیق تر، تابع یک طرفه ای را که یک به یک و پوشا باشد، یک جایگشت یک طرفه می نامند. جایگشت های یک طرفه ابزارهای بنیادی مهمّی در رمزنگاری هستند. اینکه وجود جایگشت یک طرفه، وجود تابع یک طرفه را نتیجه می دهد، هنوز به عنوان مسئله ای حل نشده باقی مانده است. تابع چکیده ساز مقاوم در برابر برخورد f تابع یک طرفه ای است که مقاوم در برابر برخورد نیز می باشد. بدین معنی که هیچ الگوریتم تصادفی در زمان چندجمله ای نمی تواند مقادیر متمایز x و y را با احتمال غیر ناچیز پیدا کند به طوری که f ( x ) = f ( y ) باشد.
