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

тим, что сложности минималь- ных схем для реализации φ 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 Combi- natorial Complexity Theory. ETH Series in Information Processing, vol. 3 (1993). 4. Toffoli M. Bicontinuous Exten- sions of Invertible Combinatorial Functions. Math. Syst. Theory, vol. 14 (1981), pp. 13–23. 5. Редькин Н.П. О мини- мальной реализации двоич- ного сумматора. Проблемы кибернетики, № 38 (1981). – С. 181–216. 6. Жуков А.Е., Закаблуков Д.В., Засорина Ю.В., Чикин А.А. Вычислительно асимметричные преобразования и схемы из обратимых элементов. – Вопро- сы кибербезопасности, № 2 (10), 2015. – С. 49–55. l • 43 КРИПТОГРАФИЯ www.itsec.ru Рис. 7. Обратимая схема, реализующая вычислительно асимметричное преобразование 7 с выделенными подсхемами для "уборки мусора" Рис. 8. Возможная структура вычислительно асимметричных преобразований Ваше мнение и вопросы присылайте по адресу is@groteck.ru