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

, изученные в работах [2], [3]: Так , . В работе [3] доказано, что при нечетном n ≥ 5 сложности прямого и обратного преобра- зования равны, соответственно, С помощью элементов CNOT можно построить минимальную схему (рис. 4), реализующую данное преобразование. Однако схема, приведенная на рис. 4, хотя и построена из обратимых логических элемен- тов, обратимой не будет. Дело в том, что в процессе вычисле- ния нашего преобразования на выходе схемы появился не толь- ко вектор результатов, но и некоторая информация (на выходе дополнительной линии), полученная в процессе вычис- ления и называемая вычисли- тельным мусором, или просто мусором. Без знания этой информации, а только по выхо- ду (y 1 ,...,y n ) вход (x 1 ,...,x n ) полу- чить невозможно. Для того чтобы получить обратимую схему, понадобится изменить нашу схему таким образом, чтобы на выходе схемы оставался только иско- мый результат. Такая процеду- ра называется "уборка мусора" и требует использования допол- нительных логических элемен- тов (рис. 5). Теперь схема действительно является обратимой: по входу (x 1 ,...,x n ) вычисляется (y 1 ,...,y n ) – значение функции φ n, а по (y 1 ,...,y n ) (и только по нему) – вычисляется прообраз (x 1 ,...,x n ). В то же время обратимая схема будет содержать некото- рые "лишние" элементы, кото- рые не нужны для реализации, например, прямого преобразо- вания, но нужны для реализа- ции обратного преобразования, и наоборот. Так, для реализа- ции прямого преобразования, когда нас интересует только получение значения функции, нас вполне удовлетворит необратимая схема, приведен- ная на рис. 4 (т.е. схема, не содержащая элементы, требуе- мые для "уборки мусора"). В то же время для реализации обратного преобразования совершенно не требуются эле- менты, стоящие в начале обра- тимой схемы, и минимальной схемой, реализующей обратное преобразование, будет схема, изображенная на рис. 6. Заме- 42 • ТЕХНОЛОГИИ Рис. 4. Минимальная схема, построенная из элементов CNOT и реализующая вычислительно асимметричное преобразование 7 Рис. 5. Обратимая схема, построенная из элементов CNOT и реализующая вычислительно асимметричное преобразование 7 Рис. 6. Минимальная схема, построенная из элементов CNOT и реализующая преобразование ( φ 7 ) -1