تابع یک طرفه

در علوم رایانه، تابع یک طرفه به تابعی گفته می شود که برای هر ورودی، خروجی تابع به راحتی قابل محاسبه است، امّا به دست آوردنِ پیش تصویرِ خروجیِ متناظر با یک ورودیِ تصادفی، دشوار می باشد. منظور از راحتی و دشواری محاسبه، آسانی یا سختی محاسبه از لحاظ پیچیدگی محاسبه است. محاسبه در زمانِ چندجمله ایِ قطعی را آسان و عدم توانایی محاسبه در زمان چندجمله ای قطعی را سخت می گوییم. توجّه داشته باشید که برای یک طرفه بودن تابع، نیازی به یک به یک بودن آن نیست.
وجود توابع یک طرفه در علوم رایانه، هنوز به عنوان یک مسئلۀ حل نشدۀ پژوهشی مطرح می باشد. در واقع وجود چنین توابعی نشانگر نابرابری کلاس های P و NP است که به تبع آن مهم ترین مسئلۀ حل نشدۀ علوم رایانۀ نظری ثابت می شود. عکس گزارۀ گفته شده درست نیست، بدین معنی که نابرابری کلاس های P و NP، وجود توابع یک طرفه را به طور مستقیم نتیجه نمی دهد.
در موارد کاربردی منظور از آسانی و سختی معمولاً به دستگاه محاسبۀ مورد نظر برمی گردد. توابع یک طرفه، ابزارهای بنیادی در رمزنگاری، احراز هویّت، اصالت سنجی و دیگر کاربردهای امنیّت داده می باشند. گرچه مسئلۀ وجود توابع یک طرفه هنوز مسئله ای باز است، امّا نامزدهای متعدّدی برای این توابع جهت استفاده در مخابرات و سامانه های تجارت الکترونیک در طول دهه های گذشته در نظر گرفته شده است.
تابع f : { 0 , 1 } ∗ → { 0 , 1 } ∗ {\displaystyle f:\{0,1\}^{*}\rightarrow \{0,1\}^{*}}   یک طرفه است هرگاه f توسّط یک الگوریتم چندجمله ای قابل محاسبه باشد، برای هر الگوریتم تصادفی که در زمان چندجمله ای از طول ورودی اجرا می شود و برای هر چندجمله ای p ( n ) {\displaystyle p(n)}   و برای مقادیر بزرگ n {\displaystyle n}   داشته باشیم: