Вот идея, которая, казалось бы, отвечает всем вашим заявленным требованиям. Теперь он не соответствует другим разумным криптографическим требованиям; однако вы никогда не просили их.
Вот идея: мы работаем в группе эллиптической кривой соответствующего размера (скажем, P224) с размером группы $q$ (что является простым) и выберите три генератора $Ф, Г, Н$ (с неизвестными отношениями; возможно, сгенерировано с использованием метода Hash2Curve); и:
$$f(X) = F + X$$
$$g(X) = G + X$$
$$h(X) = H + X$$
Очевидно, что эти операции коммутируют, и мы имеем $f^i(g^j(h^k(X))) = iF + jG + kH + X$.
Прохождение ваших требований:
Если сейчас $ф,г,ч$, применены $i,j,k$-раз на вход $х$ поиск/вычисление $х$ для данного $ c = f ^ i (g ^ j (h ^ k (x))) $ должно быть максимально жестким и при этом занимать более $O(|i|+|j|+|k|)$ шаги.
Я предполагаю, что в этом требовании злоумышленник не знает значения $я, дж,к$ (он знает относительный диапазон). В этом случае лучший поиск, который я могу найти, чтобы проверить значение $с$ берет $O( \sqrt{i \cdot j \cdot k } )$ время (при условии $i \cdot j \cdot k < q$, очевидно); это больше, чем $О(я + j + к)$. Этот поиск осуществляется с помощью $0F, 1F, ..., iF$, $0G, 1G, ..., jG$, $0H, 1H, ..., кГ$, разделив их на два списка, где сумма любых трех элементов в трех списках может быть выражена как сумма двух элементов в списке, а затем применив алгоритм стиля «большой шаг/маленький шаг».
Кроме того, методы $ф,г,ч$ сохраняют формат: $X \стрелка вправо X$, так что каждый выход может служить новым входом.
Пока ты в порядке с $Х$ будучи набором точек эллиптической кривой, мы хорошо здесь.
Максимальный размер должен быть: $|Х|<2^{256}$
С Р-224 это правда.
Вычисления $ф,г,ч$ и их обратные должны занимать одинаковое время для каждого входа (независимо от $i,j,k$).
нам здесь хорошо
более того $ф,г,ч$ нужно создать цикл вроде $f(f(....f(x)...))=x$ с размером $F,G,H$ с $F \приблизительно G \приблизительно H \gg 1$
Истинный; $ф, г, ч$ у всех порядок $q$, что намного больше 1
Вы можете легко выбрать диапазоны для $я, дж,к$ чтобы целевая безопасность была соблюдена.
Единственное, чего эта идея не дает, это то, что, учитывая $с, х$ с $ c = f ^ i (g ^ j (h ^ k (x))) $, вычислить несложно $c' = f^i(g^j(h^k(x')))$. Однако вы никогда не просили, чтобы это было тяжело...
