ћашина “ьюр≥нга

риптограф≥чн≥ односторонн≥ функц≥њ

ƒл¤ забезпеченн¤ ст≥йкост≥ криптограф≥чних схем, побудованих на основ≥ односторонн≥х функц≥й, необх≥дно, щоб останн≥ складно ≥нвертувалис¤. “обто, потр≥бно використовувати ≥ншу м≥ру складност≥ - складн≥сть "в середньому".

Ќеформально, така односторонн¤ функц≥¤ може бути визначена наступними умовами:

функц≥¤ ефективно обраховуЇтьс¤;
будь-¤кий ефективний алгоритм ≥нвертуЇ цю функц≥ю лише на дуже малому в≥др≥зку значень.

ѕерейдемо до формальних визначень. Ќехай $\ Sigma = \ (0,1 \) *$ , $\ Sigma ^ n = \ (0,1 \) ^ n$ .Ќижче будемо припускати, що множина $\ Sigma$ Ї областю визначенн¤ вс≥х розгл¤нутих функц≥й. ƒовжину слова будемо позначати через $\ Vert x \ vert$ . ƒл¤ де¤кого под≥њ $\ Alpha$ через $\ Pr (\ alpha)$ будемо позначати ймов≥рн≥сть ц≥Їњ под≥њ.

Ќасамперед зазначимо, що функц≥¤ може складно ≥нвертуватис¤ лише тому, що вона занадто сильно "стискаЇ" вх≥дн≥ значенн¤. ясно, що н≥¤коњ пол≥ном≥альний алгоритм не може њњ ≥нвертувати, оск≥льки за пол≥ном≥альною (в≥д довжини значенн¤ функц≥њ) час в≥н не встигне виписати знайдене значенн¤ з прообразу. ÷ей випадок нец≥кавий виключаЇтьс¤ за допомогою вимоги так званоњ чесност≥.

¬изначенн¤ 1. ‘ункц≥¤ називаЇтьс¤ чесною, ¤кщо ≥снуЇ пол≥ном такий, що $\ Vert x \ vert <p (\ vert f (x) \ vert)$ дл¤ будь-¤кого $X \ in \ Sigma$ .

¬изначенн¤ 2. „есна функц≥¤ називаЇтьс¤ односторонн≥й в сильному сенс≥, ¤кщо

≥снуЇ пол≥ном≥альна машина “ьюринга , ўо на будь-¤кому вход≥ $X \ in \ Sigma$ обчислюЇ ;
дл¤ будь-¤кого пол≥ном≥альною алгоритму справедливо наступне. Ќехай $X \ in_ (\ mbox (\ tiny \ rm R)) \ Sigma ^ n$ ≥ слово подано на вх≥д алгоритму . “од≥ дл¤ будь-¤кого пол≥нома ≥ дл¤ вс≥х досить великих

$\ displaystyle \ Pr (f (A (y)) = y) <1 / p (n).$

≤мов≥рн≥сть беретьс¤ за вибором значенн¤ з $\ Sigma ^ n$ ≥, ¤кщо - ÷е ймов≥рн≥сна машина “ьюринга, - по створеними нею випадковим величинам.

якщо у визначенн≥ 2 обмеженн¤ на ймов≥рн≥сть зам≥нити наступним б≥льш слабким умовою:

$\ displaystyle \ \ Pr (f (A (y)) = y) <1-1 / p (n)$

дл¤ де¤кого ф≥ксованого пол≥нома , “о отримаЇмо визначенн¤ функц≥њ, односторонн≥й в слабкому сенс≥. √овор¤чи неформально, така функц≥¤ складно ≥нвертуЇтьс¤ принаймн≥ на пол≥ном≥альн≥й частц≥ значень. « результат≥в яо [Yao] ≥ √ольдрайха та ≥н [Getal] випливаЇ, що функц≥њ, односторонн≥ в сильному сенс≥ ≥снуЇ тод≥ ≥ т≥льки тод≥, коли ≥снують функц≥њ, односторонн≥ в слабкому сенс≥. “ака "ст≥йк≥сть" св≥дчить, що знайдена адекватна формал≥зац≥¤ ≥нтуњтивного пон¤тт¤ одноб≥чноњ функц≥њ.

Ќеобх≥дно в≥дзначити, що односторонн¤ функц≥¤ - г≥потетичний об'Їкт, тому називати конкретн≥ функц≥њ (¤к, наприклад, дискретний логарифм) односторонн≥ми математично некоректно. ќчевидно, що з припущенн¤ про ≥снуванн¤ односторонн≥х функц≥й випливаЇ, що P $() \ Ne ()$ NP. ѕитанн¤ про те, чи Ї це умова одночасно ≥ достатньою, залишаЇтьс¤ в≥дкритим. Ѕ≥льш того, н≥¤ких нетрив≥альних достатн≥х умов ≥снуванн¤ односторонн≥х функц≥й на даний момент не в≥домо.