Кіріспе
Компьютерлік криптографияда қолданылатын функция. Компьютерлік ғылымда бір жолды функция – кез келген мәлімет бойынша есептеу оңай, бірақ кездейсоқ мәліметтің нәтижесі берілгенде, оны кері қайтару қиын. Мұндағы "оңай" және "қиын" терминдері есептеу күрделілігі теориясы, атап айтқанда полиномдық уақыт проблемалары теориясы тұрғысынан түсінілуі керек. Функция бір-бірге сәйкес болмауы, оны бір жолды функция деп атау үшін жеткілікті емес (төмендегі теориялық анықтаманы қараңыз). Мұндай бір жолды функциялардың бар екендігі әлі де ашық болжам болып табылады. Олардың бар екендігі P және NP күрделілік сыныптарының тең емес екенін дәлелдейді, осылайша теориялық компьютерлік ғылымның ең шешілмеген маңызды мәселесін шешеді. Керісінше, P ≠ NP екенін дәлелдеу, бір жолды функциялардың бар екендігін тікелей білдірмейді. Қолданбалы контексте "оңай" және "қиын" терминдері әдетте нақты есептеу жүргізетін тұлғаға қатысты түсіндіріледі; әдетте "заңды пайдаланушылар үшін жеткілікті арзан" және "жаман ниетті агенттер үшін тым қымбат". Осы мағынада бір жолды функциялар криптография, жеке сәйкестендіру, аутентификация және басқа да деректерді қорғау құралдары болып табылады. Бұл мағынадағы бір жолды функциялардың бар екендігі де ашық болжам болып табылады, бірақ ондаған жылдар бойы қатаң тексеруден өткен бірнеше үміткерлер бар. Олардың кейбіреулері әлемдегі телекоммуникация, электрондық сауда және электрондық банк жүйелерінің маңызды құрамдас бөліктері болып табылады.
In computer science, a one way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one to one is not considered sufficient for a function to be called one way (see Theoretical definition, below). The existence of such one way functions is still an open conjecture. Their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science. The converse is not known to be true, i. e. the existence of a proof that P ≠ NP would not directly imply the existence of one way functions. In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any malicious agents". One way functions, in this sense, are fundamental tools for cryptography, personal identification, authentication, and other data security applications. While the existence of one way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most telecommunications, e commerce, and e banking systems around the world.
Теориялық анықтама
F функциясы: {0, 1}* → {0, 1}* – егер f функциясы полиномиалдық уақыт алгоритмімен есептелуге мүмкін болса, бірақ f үшін псевдо-инверсті есептеуге тырысатын кез келген полиномиалдық уақыт рандомизацияланған алгоритмі, елеусіз ықтималдықпен ғана табысқа жетеді. (* Клейн жұлдызы – қайталанулардың кез келген санын білдіреді.) Яғни, барлық рандомизацияланған алгоритмдер үшін , барлық оң бүтін сандар c және барлық жеткілікті үлкен n = length(x) үшін,
мұндағы ықтималдық {0, 1}ⁿ жиынындағы дискретті біркелкі таралым бойынша x-ті таңдауға және рандомизацияға байланысты. Бұл анықтама бойынша, функция орташа жағдайда «кері қайтару қиын» болуы керек, ең нашар жағдайда емес. Бұл күрделілік теориясының көп бөлігінен (мысалы, NP қиындығы) өзгеше, онда «қиын» термині ең нашар жағдайда қолданылады. Сондықтан, егер бір жолды функцияларға (төменде сипатталған) кандидаттардың кейбіреуі NP-толық екені белгілі болса да, бұл олардың бір жолды екенін білдірмейді. Соңғы қасиет тек мәселені шешуге белгілі алгоритмдердің болмауына негізделген. Бір жолды функция болу үшін функцияны «жоғалтушы» (бірін-біріне сәйкес емес) ету жеткіліксіз. Атап айтқанда, n ұзындығы бар кез келген кіріс үшін n нөлден тұратын тізбекті шығаратын функция бір жолды функция емес, себебі сол шығысқа әкелетін кірісті табу оңай. Нақтырақ айтқанда: жай ғана нөлдер тізбесін шығаратын мұндай функция үшін, f(x) кірісінде кез келген n ұзындығындағы тізбекті шығаратын F алгоритмі, шығыстың дұрыс алдын ала бейнесін «табады», тіпті ол бастапқыда шығыс тізбесін табу үшін қолданылған кіріс болмаса да.
Note that, by this definition, the function must be "hard to invert" in the average case, rather than worst case sense. This is different from much of complexity theory (e. g., NP hardness), where the term "hard" is meant in the worst case. That is why even if some candidates for one way functions (described below) are known to be NP complete, it does not imply their one wayness. The latter property is only based on the lack of known algorithms to solve the problem. It is not sufficient to make a function "lossy" (not one to one) to have a one way function. In particular, the function that outputs the string of n zeros on any input of length n is not a one way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm F that just outputs any string of length n on input f(x) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.
Қарым-қатынас ұғымдары
Бір жолды пермутация – бұл бір жолды функция, сонымен қатар пермутация, яғни биективті функция. Бір жолды пермутациялар маңызды криптографиялық құрал болып табылады, және олардың болуы бір жолды функциялардың болуынан туындай ма, жоқ па, әзірге белгісіз. Тұзақ есігі бар бір жолды функция немесе тұзақ есігі бар пермутация – бұл бір жолды функцияның ерекше түрі. Мұндай функцияны тұзақ есігі деп аталатын құпия ақпарат болмаса, кері қайтару өте қиын. Соқтығысудан сақталған хэш-функция f – бұл соқтығысуға төзімді бір жолды функция; яғни, кездейсоқ полиномиалдық уақыт алгоритмі екі түрлі мәндер x, y үшін f(x) = f(y) болатындай соқтығысуды елеулі емес ықтималдықпен таба алмайды.
Бір бағыттағы функцияларға үміткерлер
Келесілер бір бағытты функцияларға үміткерлер (2009 жылғы сәуір айының мәліметі бойынша). Бұл функциялардың шынымен бір бағытты екені белгісіз, бірақ осы уақытқа дейін жасалған кең ауқымды зерттеулердің ешқайсысы олардың біреуі үшін тиімді кері алгоритм табуға қол жеткізбеді.
these functions are indeed one way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.
Көбейту және факторлау
F функциясы екілік форматта берілген екі жай сан p және q-ны кіріс ретінде қабылдайды және олардың көбейтіндісін қайтарады. Бұл функция O(b²) уақытында "оңай" есептелінеді, мұнда b – кіріс биттерінің жалпы саны. Бұл функцияны кері қайтару үшін, берілген бүтін сан N-нің бөлгіштерін табу қажет. Қазіргі кезде белгілі ең жақсы бөлгіш алгоритмдері уақыт бойынша жүреді, мұнда b – N-ді көрсетуге қажетті бит саны.
Бұл функцияны p және q-ға қолайлы жартылай жай сандар жиынында кеңейту арқылы жалпылауға болады. F функциясы кездейсоқ таңдалған p, q > 1 бүтін сандары үшін бір бағытты емес екенін ескеріңіз, өйткені көбейтіндіде 2 саны 3/4 ықтималдығымен бөлгіш болады (себебі кез келген p-нің тақ болу ықтималдығы 1/2, және q үшін де солай, егер олар тәуелсіз түрде таңдалса, екеуінің де тақ болу ықтималдығы 1/4; демек, p немесе q-ның жұп болу ықтималдығы 1 = 1 − 1/4 = 3/4).
Рабин функциясы (модульдік квадраттау)
Рабин функциясы, яғни кез келген функция бір бағытты болса, онда f функциясы да бір бағытты болады. Бұл функция алғаш рет комбинаторлық тұрғыдан толыққанды бір бағытты функция ретінде көрсетілгендіктен, ол "жалпылама бір бағытты функция" деп аталады. Сондықтан, бір бағытты функция табу мәселесі, мүмкін конструктивті емес, мұндай функцияның бар екенін дәлелдеуге дейін тоғысып келеді.