تابع یک‌طرفه
تابع یک‌طرفه در علوم رایانه، به تابعی گفته می‌شود که برای هر ورودی، خروجی تابع به راحتی قابل محاسبه است، امّا به‌دست آوردنِ پیش‌تصویرِ خروجیِ متناظر با یک ورودیِ تصادفی، دشوار می‌باشد. منظور از راحتی و دشواری محاسبه، آسانی یا سختی محاسبه از لحاظ پیچیدگی محاسبه است. محاسبه در زمانِ چندجمله‌ایِ قطعی را آسان و عدم توانایی محاسبه در زمان چندجمله‌ای قطعی را پیچیده می‌گوییم. توجّه داشته باشید که برای یک‌طرفه بودن تابع، نیازی به یک‌به‌یک بودن آن نیست.
وجود توابع یک‌طرفه در علوم رایانه، هنوز به عنوان یک مسئلهٔ حل نشدهٔ پژوهشی مطرح می‌باشد. در واقع وجود چنین توابعی نشانگر نابرابری کلاس‌های P و NP است که به تبع آن مهم‌ترین مسئلهٔ حل‌نشدهٔ علوم رایانهٔ نظری ثابت می‌شود. عکس گزارهٔ گفته شده درست نیست، بدین معنی که نابرابری کلاس‌های P و NP، وجود توابع یک‌طرفه را به‌طور مستقیم نتیجه نمی‌دهد.
در موارد کاربردی منظور از آسانی و پیچیدگی معمولاً به دستگاه محاسبهٔ مورد نظر برمی‌گردد. توابع یک‌طرفه، ابزارهای بنیادی در رمزنگاری، احراز هویّت، اصالت‌سنجی و دیگر کاربردهای امنیّت داده می‌باشند. گرچه مسئلهٔ وجود توابع یک‌طرفه هنوز مسئله‌ای باز است، امّا نامزدهای متعدّدی برای این توابع جهت استفاده در مخابرات و سامانه‌های تجارت الکترونیک در طول دهه‌های گذشته در نظر گرفته شده‌است. تابع formula_1 یک‌طرفه است هرگاه f توسّط یک الگوریتم چندجمله‌ای قابل محاسبه باشد، برای هر الگوریتم تصادفی که در زمان چندجمله‌ای از طول ورودی اجرا می‌شود و برای هر چندجمله‌ای formula_2 و برای مقادیر بزرگ formula_3 داشته باشیم:
formula_4
به‌طوری که انتخاب formula_5 به‌طور یکنواخت روی formula_6 است.  توجّه داشته باشید که طبق تعریف، به‌دست آوردن پیش‌تصویر یک عنصر باید در حالت میانگین سخت باشد و لزومی ندارد که در بدترین حالت هم سخت باشد.
جایگشت یک‌طرفه تابع یک‌طرفه‌ای است که خود تابع یک جایگشت است. به‌طور دقیق‌تر، تابع یک‌طرفه‌ای را که یک‌به‌یک و پوشا باشد، یک جایگشت یک‌طرفه می‌نامند. جایگشت‌های یک‌طرفه ابزارهای بنیادی مهمّی در رمزنگاری هستند. اینکه وجود جایگشت یک‌طرفه، وجود تابع یک‌طرفه را نتیجه می‌دهد، هنوز به عنوان مسئله‌ای حل نشده باقی‌مانده است. تابع چکیده‌ساز مقاوم در برابر برخورد formula_7 تابع یک‌طرفه‌ای است که مقاوم در برابر برخورد نیز می‌باشد. بدین معنی که هیچ الگوریتم تصادفی در زمان چندجمله‌ای نمی‌تواند مقادیر متمایز formula_5 و formula_9 را با احتمال غیر ناچیز پیدا کند به‌طوری‌که formula_10 باشد.
تابع formula_7 که عدد اوّل formula_12 و عدد صحیح formula_5 بین صفر و formula_14 را می‌گیرد و باقی‌ماندهٔ formula_15 را بر formula_12 برمی‌گرداند، توان گسسته نامیده می‌شود. توان گسسته در زمان formula_17 قابل محاسبه است به‌طوری‌که formula_3 تعداد بیت‌های formula_12 می‌باشد. محاسبهٔ معکوس این تابع نیازمند محاسبهٔ لگاریتم گسستهٔ به پیمانهٔ formula_12 است. به‌طور خلاصه مسئلهٔ لگاریتم گسسته به این صورت است که به ازای عدد اوّل formula_12 و عدد صحیح formula_9 که formula_23، هدف پیدا کردن عدد formula_5 است به‌طوری که formula_25 باشد. برای این مسئله، هیچ الگوریتمی وجود ندارد که در زمان چندجمله‌ای اجرا شود. سیستم رمز الگمال بر مبنای لگاریتم گسسته طرّاحی شده‌است.
تعدادی تابع چکیده‌ساز رمزنگاری مانند SHA-256 وجود دارند که در زمان کمی قابل محاسبه می‌باشند. تعدادی از نسخه‌های ساده از تحلیل‌های امنیّتی با موفقیّت عبور نکردند، امّا نسخه‌های قوی‌تر همچنان راه‌حل‌های عملی برای محاسبهٔ یک‌طرفه می‌باشند.
خم‌های بیضوی مجموعه اعداد صحیحی هستند که در معادلهٔ formula_26 صدق می‌کنند. تعریف جمع برای نقاط دوبعدی رو خم‌ها و ضرب اسکالر برای آن‌ها به صورت دنباله‌ای از عمل جمع، منجر به معادلهٔ formula_27 برای نقاط می‌شود که با داشتن formula_28 و formula_29 محاسبهٔ formula_30 آسان است، امّا در صورتی که formula_28 و formula_30 معلوم باشند محاسبهٔ formula_29 از لحاظ محاسباتی دشوار است.
نامزدهای دیگری برای توابع یک‌طرفه وجود دارند که مبتنی بر سختی کدگشایی کدهای خطّی تصادفی، مسئلهٔ مجموع زیرمجموعه‌ها و مسائل دیگری می‌باشند.
تابع صریح formula_7 وجود دارد که اگر تابع یک‌طرفه وجود داشته باشد، formula_7 نیز یک‌طرفه خواهد بود. به عبارت دیگر، در صورتی که هر تابع یک‌طرفه باشد، formula_7 نیز یک‌طرفه خواهد بود. چون این تابع، اوّلین تابعِ ترکیبیاتیِ یک‌طرفه‌یِ کاملی است که ارائه شده‌است، به عنوان تابع یک‌طرفهٔ جهانی شناخته می‌شود. در نتیجه، مسئلهٔ پیدا کردن تابع یک‌طرفه، به مسئلهٔ اثبات یک‌طرفه بودن تابع formula_7 تحویل می‌شود.