Один подход к изучению однонаправленности

Говоря неформально, однонаправленная функция – это эффективно вычислимая функция, для обращения которой не существует эффективных алгоритмов. В качестве модели обратимого преобразования возьмем подстановку на множестве двоичных наборов; в качестве меры сложности того или иного преобразования – сложность минимальной булевой схемы, реализующей данное преобразование F и обозначаемое в дальнейшем через C(F). В качестве модели однонаправленной функции будем рассматривать вычислительно асимметричное преобразование, т.е. такое обратимое преобразование, сложность которого отличается от сложности обратного преобразования. Такие преобразования известны, их некоторые классы описаны в работах [2], [3].

Пытаясь понять природу такой асимметрии, можно задать глупый вопрос: почему схему, реализующую прямое преобразование, нельзя использовать для вычисления обратного преобразования? Ответ очевиден: потому что логические элементы, отличные от инверсии, необратимы. Однако уже давно известны обратимые логические элементы [4], примерами которых могут служить такие элементы как NOT, CNOT (Controlled NOT), CCNOT (Controlled Controlled NOT), представленные на рисунках 1–3.

Эти элементы имеют равное число входов и выходов и, по сути, реализуют подстановки на множестве двоичных наборов. На схемах такие элементы принято изображать на параллельных горизонтальных линиях, символизирующих проводники. Входные переменные подаются слева, справа располагаются выходы, расщепление выходов, что допустимо для классических логических элементов, а в случае обратимых логических элементов не разрешается. К схеме возможно добавление дополнительных линий, на которые подается логический 0, в процессе вычислений они играют роль "памяти".

Попытаемся теперь какое-нибудь вычислительно асимметричное преобразование реализовать схемой из обратимых логических элементов. На первый взгляд, в силу обратимости используемых логических элементов схема для обратного преобразования должна состоять из тех же самых элементов и, следовательно, иметь ту же сложность, что противоречило бы вычислительной асимметричности преобразования. Однако все не так просто. Сложность прямого и обратного преобразований действительно совпадает, если минимальная схема не использует "дополнительной памяти". В случае вычислительно асимметричных преобразований это не так. Проще всего продемонстрировать влияние "дополнительной памяти" на примере.

Широко известным классом вычислительно асимметричных преобразований являются линейные преобразования

изученные в работах [2], [3]:

Так

В работе [3] доказано, что при нечетном n ≥ 5 сложности прямого и обратного преобразования равны, соответственно,

С помощью элементов CNOT можно построить минимальную схему (рис. 4), реализующую данное преобразование.

Однако схема, приведенная на рис. 4, хотя и построена из обратимых логических элементов, обратимой не будет. Дело в том, что в процессе вычисления нашего преобразования на выходе схемы появился не только вектор результатов, но и некоторая информация (на выходе дополнительной линии), полученная в процессе вычисления и называемая вычислительным мусором, или просто мусором. Без знания этой информации, а только по выходу (y₁,...,y_n) вход (x₁,...,x_n) получить невозможно.

Для того чтобы получить обратимую схему, понадобится изменить нашу схему таким образом, чтобы на выходе схемы оставался только искомый результат. Такая процедура называется "уборка мусора" и требует использования дополнительных логических элементов (рис. 5).

Теперь схема действительно является обратимой: по входу (x₁,...,x_n) вычисляется (y₁,...,y_n) – значение функции φn, а по (y₁,...,y_n) (и только по нему) – вычисляется прообраз (x₁,...,x_n).

В то же время обратимая схема будет содержать некоторые "лишние" элементы, которые не нужны для реализации, например, прямого преобразования, но нужны для реализации обратного преобразования, и наоборот. Так, для реализации прямого преобразования, когда нас интересует только получение значения функции, нас вполне удовлетворит необратимая схема, приведенная на рис. 4 (т.е. схема, не содержащая элементы, требуемые для "уборки мусора"). В то же время для реализации обратного преобразования совершенно не требуются элементы, стоящие в начале обратимой схемы, и минимальной схемой, реализующей обратное преобразование, будет схема, изображенная на рис. 6. Заметим, что сложности минимальных схем для реализации φn и (φ7)-1 совпадают с теоретическим результатом, приведенным выше.

Проанализировав построенную схему из обратимых элементов, можно выдвинуть следующую гипотезу о структуре вычислительно асимметричных преобразований. В ходе работы прямой схемы вычислительно асимметричного преобразования получается некоторая дополнительная информация ("мусор", с криптографической точки зрения играющий роль "лазейки"), которая необходима для получения результата прямого преобразования.

При попытке непосредственного обращения по такой схеме на ее входы необходимо будет подать этот "мусор", который в общем случае неизвестен. Поэтому, чтобы получить обратимую схему, необходимо добавить в нее дополнительные элементы, которые будут удалять "мусор". В схеме, реализующей обратное преобразование, эти элементы должны быть задействованы, в то же время некоторые элементы из схемы для прямого преобразования в схеме для обратного преобразования не требуются.

Возможно, что схемы из обратимых элементов для вычислительно асимметричных преобразований имеют общую структуру, показанную на рис. 8. У таких схем есть некоторая "общая подсхема", а также подсхемы, отвечающие за удаление "мусора" прямого и обратного преобразований. Из-за разницы в сложностях этих подсхем удаления "мусора" и возникает разница в сложности прямого и обратного преобразований.

Аргументами в пользу сформулированной выше гипотезы служат обратимые схемы, построенные в [6] для таких известных вычислительно асимметричных преобразований, как нелинейные вычислительно асимметричные преобразования [3] и двоичный сумматор/вычитатель [5].

Литература

1. Жуков А.Е. Схемы из обратимых логических элементов: Один подход к изучению однонаправленности. – Труды III Международной конференции "Информационные системы и технологии" (IST’2006). Минск, 2006. – С. 85.
2. Boppana R.B., Lagarias J.C. One-way functions and circuit complexity. Information and Computation, vol. 74 (1987), pp. 226–240.
3. Hiltgen A.P. Cryptographically Relevant Contributions to Combinatorial Complexity Theory. ETH Series in Information Processing, vol. 3 (1993).
4. Toffoli M. Bicontinuous Extensions of Invertible Combinatorial Functions. Math. Syst. Theory, vol. 14 (1981), pp. 13–23.
5. Редькин Н.П. О минимальной реализации двоичного сумматора. Проблемы кибернетики, № 38 (1981). – С. 181–216.
6. Жуков А.Е., Закаблуков Д.В., Засорина Ю.В., Чикин А.А. Вычислительно асимметричные преобразования и схемы из обратимых элементов. – Вопросы кибербезопасности, № 2 (10), 2015. – С. 49–55.