Существуют ли криптографические методы $f,g,h$ с $f(g(h(x)))=h(g(f(x)))=g(h(f(x)))$) и нахождение $ x$ для данного $c=f^ig^jh^k(x)$ сложнее, чем $O(i+j+k)$?

Позволять $N$ быть произведением двух больших сильных простых чисел, т.е. $N=pq$, $p=2r+1$, $д=2с+1$ с $р$, $q$, $г$ и $s$ все премьер. Мы также требуем, чтобы требовалось 3 числа, которые являются примитивными корнями для обоих $г$ и $s$ (учитывая мод первобытных корней $г$ объявление $s$ мы можем сделать это с помощью китайской теоремы об остатках). Мы возьмем эти три числа как 3, 5 и 7 ниже. Мы предполагаем, что $N$ трудно разложить на множители и решить дискретные логарифмы по модулю $N$ тоже тяжело.

Позволять $х$ быть любой квадрат в $\mathbb Z/N\mathbb Z$ (например, выберите случайный элемент и возведите его в квадрат). Теперь пусть $f(x)=x^3\mod N$, $ г (х) = х ^ 5 \ мод N $ и $ ч (х) = х ^ 7 \ мод N $. Запись $f(g(h(x))=x^{105}\mod N$ и то же самое для других заказов. Существует аналогичная взаимосвязь инверсий (хотя вычисление инверсии так же сложно, как и расшифровка RSA).

Быстрое вычисление $f^ig^jh^k(x)$ позволит нам использовать гигантское шифрование RSA, которое считается сложным, если мы не знаем факторов $N$.

Наконец итерированные приложения $f$, $г$ и $ч$ произвести цикл длины $\mathrm{lcm}((r-1),(s-1))$ пока не $х$ либо $г$й или $s$модуль мощности $N$ (что исчезающе маловероятно).