Журнал "Information Security/ Информационная безопасность" #1, 2018

Говоря неформально, однонаправленная функ- ция – это эффективно вычислимая функция, для обращения которой не существует эффективных алго- ритмов. В качестве модели обратимого преобразования возьмем подстановку на мно- жестве двоичных наборов; в качестве меры сложности того или иного преобразования – сложность минимальной буле- вой схемы, реализующей дан- ное преобразование F и обо- значаемое в дальнейшем через C(F). В качестве модели одно- направленной функции будем рассматривать вычислительно асимметричное преобразова- ние, т.е. такое обратимое пре- образование, сложность кото- рого отличается от сложности обратного преобразования. Такие преобразования извест- ны, их некоторые классы опи- саны в работах [2], [3]. Пытаясь понять природу такой асимметрии, можно задать глупый вопрос: почему схему, реализующую прямое преобразование, нельзя исполь- зовать для вычисления обрат- ного преобразования? Ответ очевиден: потому что логиче- ские элементы, отличные от инверсии, необратимы. Однако уже давно известны обратимые логические элементы [4], при- мерами которых могут служить такие элементы как NOT, CNOT (Controlled NOT), CCNOT (Con- trolled Controlled NOT), пред- ставленные на рисунках 1–3. Эти элементы имеют равное число входов и выходов и, по сути, реализуют подстановки на множестве двоичных набо- ров. На схемах такие элементы принято изображать на парал- лельных горизонтальных линиях, символизирующих про- водники. Входные переменные подаются слева, справа рас- полагаются выходы, расщеп- ление выходов, что допустимо для классических логических элементов, а в случае обрати- мых логических элементов не разрешается. К схеме возмож- но добавление дополнитель- ных линий, на которые подает- ся логический 0, в процессе вычислений они играют роль "памяти". Попытаемся теперь какое- нибудь вычислительно асим- метричное преобразование реализовать схемой из обра- тимых логических элементов. На первый взгляд, в силу обра- тимости используемых логиче- ских элементов схема для обратного преобразования должна состоять из тех же самых элементов и, следова- тельно, иметь ту же сложность, что противоречило бы вычис- лительной асимметричности преобразования. Однако все не так просто. Сложность пря- мого и обратного преобразо- ваний действительно совпада- ет, если минимальная схема не использует "дополнительной памяти". В случае вычисли- тельно асимметричных пре- образований это не так. Проще всего продемонстрировать влияние "дополнительной памя- ти" на примере. Широко известным классом вычислительно асимметричных преобразований являются линейные преобразования 40 • ТЕХНОЛОГИИ Один подход к изучению однонаправленности ля современной криптографии одним из важнейших понятий является однонаправленная функция. Однако, несмотря на многочисленные работы, посвященные этой тематике, строгих доказательств существования или возможности построения таких функций в настоящее время нет. В данной работе будет популярно изложен предложенный автором подход, позволяющий новым образом взглянуть на явление однонаправленности [1]. Д Алексей Жуков, председатель совета директоров ассоциации “РусКрипто”, к.ф.-м.н., доцент, МГТУ им. Н.Э. Баумана Рис. 1. Элемент NOT Рис. 2. Элемент CNOT Рис. 3. Элемент CCNOT Однонаправленная функция – это эффективно вычислимая функция, для обращения которой не существует эффективных алгоритмов.