Есть функция
![$g\colon (A \to B) \times S \to C$ $g\colon (A \to B) \times S \to C$](https://dxdy-03.korotkov.co.uk/f/a/0/a/a0a49d6ffad86df9875b312d667e008c82.png)
, проделывающая некоторое вычисление, использующее функцию
![$f\colon A \to B$ $f\colon A \to B$](https://dxdy-02.korotkov.co.uk/f/d/8/6/d86070709106787e203da9d2b86067eb82.png)
и некий дополнительный аргумент
![$s$ $s$](https://dxdy-03.korotkov.co.uk/f/6/f/9/6f9bad7347b91ceebebd3ad7e6f6f2d182.png)
. Можно ли иметь функцию
![$g'\colon (A \to B) \times S \times X \to C \times Y$ $g'\colon (A \to B) \times S \times X \to C \times Y$](https://dxdy-02.korotkov.co.uk/f/9/3/1/931b17d7ab522a66dd22f64558c9b06f82.png)
такую*, что
![$g'(f, s, x) = (g(f, s),\ldots)$ $g'(f, s, x) = (g(f, s),\ldots)$](https://dxdy-01.korotkov.co.uk/f/4/9/7/497f2ed1efa77501d24de0c5379a81a282.png)
и такую, что просто проверить, что
![$(c, y)$ $(c, y)$](https://dxdy-01.korotkov.co.uk/f/8/7/f/87f78d086f7a001d1b812083c6b0f0af82.png)
— это действительно скорее всего результат применения
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
к некоторым известным нам аргументам (а не результат применения какой-то подкрученной злоумышленником
![$g''$ $g''$](https://dxdy-04.korotkov.co.uk/f/7/7/3/773753cd3a84733a271e27836e05230282.png)
) — проще, чем посчитать
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
.
* И чтобы, разумеется, она вообще была практически реализуема на тьюринг-ограниченной архитектуре, если реализуема
.Дополнительно, у нас может не быть возможности самим посчитать
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
, потому что вместо конкретной
![$f = f_0$ $f = f_0$](https://dxdy-03.korotkov.co.uk/f/a/9/4/a94d4110a902a44cc102cfe24cf7d78782.png)
нам дан некоторый хеш
![$h(\mathtt f_0)$ $h(\mathtt f_0)$](https://dxdy-01.korotkov.co.uk/f/c/d/8/cd844b4e11e78f74846107c0959f4d0f82.png)
её кода
![$\mathtt f_0$ $\mathtt f_0$](https://dxdy-01.korotkov.co.uk/f/8/1/1/8113c908611ddb63fac2444989edb6d682.png)
(будем считать, что у
![$f_0$ $f_0$](https://dxdy-01.korotkov.co.uk/f/8/5/e/85e88daa56884880b8a3141b22f439bc82.png)
только одна реализация
![$\mathtt f_0$ $\mathtt f_0$](https://dxdy-01.korotkov.co.uk/f/8/1/1/8113c908611ddb63fac2444989edb6d682.png)
и потому ей соответствует только один хеш), где
![$h$ $h$](https://dxdy-03.korotkov.co.uk/f/2/a/d/2ad9d098b937e46f9f58968551adac5782.png)
известная функция — но нам всё равно хотелось бы иметь какие-то гарантии, что (при известных всем
![$h(\mathtt f_0), s, x$ $h(\mathtt f_0), s, x$](https://dxdy-04.korotkov.co.uk/f/f/f/3/ff329c9535b06022aaba38ed3021dae882.png)
) переданное нам
![$(c, y)$ $(c, y)$](https://dxdy-01.korotkov.co.uk/f/8/7/f/87f78d086f7a001d1b812083c6b0f0af82.png)
— это
![$g'(f_0, s, x)$ $g'(f_0, s, x)$](https://dxdy-01.korotkov.co.uk/f/8/9/c/89cfc02bff5f8aef890756a14beea08382.png)
.
Это описывает такую ситуацию:
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
симулирует какую-то систему, полностью задаваемую параметрами
![$s$ $s$](https://dxdy-03.korotkov.co.uk/f/6/f/9/6f9bad7347b91ceebebd3ad7e6f6f2d182.png)
, и оценивает управление
![$f$ $f$](https://dxdy-02.korotkov.co.uk/f/1/9/0/190083ef7a1625fbc75f243cffb9c96d82.png)
для неё. Хочется довести
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
до какой-то затем публично известной
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
, которую каждый проверяющий свою
![$f_0$ $f_0$](https://dxdy-01.korotkov.co.uk/f/8/5/e/85e88daa56884880b8a3141b22f439bc82.png)
мог бы запустить у себя сам и надеяться, что результаты запуска (вместе с параметрами) позволят другим считать, что он действительно воспользовался
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
и ничего не менял в её коде, не пользовался никакими уязвимостями в процессе выполнения и т. п., и притом было бы хорошо, если бы ему не надо было показывать сам код своей функции, вместо того дав что-то безобидное типа
![$h(\mathtt f_0)$ $h(\mathtt f_0)$](https://dxdy-01.korotkov.co.uk/f/c/d/8/cd844b4e11e78f74846107c0959f4d0f82.png)
.
Как я понимаю, задача почти исключительно требует очень жёстко впутать вычисление
![$h(\mathtt f_0)$ $h(\mathtt f_0)$](https://dxdy-01.korotkov.co.uk/f/c/d/8/cd844b4e11e78f74846107c0959f4d0f82.png)
в каждый шаг симуляции в
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
, значимый для получения результатов? (Это выглядит ужасно нереализуемым; но если это не предполагать, то мы вроде очень легко сможем написать
![$g''$ $g''$](https://dxdy-04.korotkov.co.uk/f/7/7/3/773753cd3a84733a271e27836e05230282.png)
, делающую что нам захочется, так как код
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
по условию всем известен.) Или можно что-то попроще? Я вообще в криптографии не разбираюсь, знаю только некоторые идеи и что у неё можно типично просить.
-- Вс фев 28, 2021 18:15:02 --Если больше разных результатов выполнения
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
дают большую гарантию, предполагается, что можно варьировать параметр
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
как душе угодно (и это вынужденно скажется на
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
из результата).
-- Вс фев 28, 2021 18:33:44 --Было бы вообще прекрасно, если бы существовала
![$j\colon X \times C \times Y \times H \to S$ $j\colon X \times C \times Y \times H \to S$](https://dxdy-04.korotkov.co.uk/f/b/1/d/b1d721e83e44c325c8316fc0220097f182.png)
, такая что
![$g'([\![ \mathtt f ]\!], j(x, c, y, h(\mathtt f)), x) = (c, y)$ $g'([\![ \mathtt f ]\!], j(x, c, y, h(\mathtt f)), x) = (c, y)$](https://dxdy-04.korotkov.co.uk/f/f/5/8/f58584ec37efd803bcaaf5cb8e8da8c482.png)
для всех
![$s, c, x, y, \mathtt f$ $s, c, x, y, \mathtt f$](https://dxdy-04.korotkov.co.uk/f/b/f/7/bf7a19623590b406b184fb4758a5adab82.png)
(и когда определены подвыражения
![$[\![ \mathtt f ]\!], j(\ldots)$ $[\![ \mathtt f ]\!], j(\ldots)$](https://dxdy-01.korotkov.co.uk/f/4/2/d/42d0f079d3ec791de5954d47229d8b7982.png)
— не любой код задаёт подходящую
![$f$ $f$](https://dxdy-02.korotkov.co.uk/f/1/9/0/190083ef7a1625fbc75f243cffb9c96d82.png)
и не всегда
![$(c, y) \in \operatorname{cod} g'$ $(c, y) \in \operatorname{cod} g'$](https://dxdy-01.korotkov.co.uk/f/8/e/e/8ee932e7f56913d9d7f3e5ccc2cafdfd82.png)
), вычислимая проще
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
. Но я думаю, это невозможно или искать подходящую
![$g'$ $g'$](https://dxdy-03.korotkov.co.uk/f/a/c/3/ac31c2a831e69e0608b9e2cc6c98249e82.png)
, когда
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
достаточно хитра, просто нецелесообразно.
Выше
![$H$ $H$](https://dxdy-04.korotkov.co.uk/f/7/b/9/7b9a0316a2fcd7f01cfd556eedf72e9682.png)
— тип значений
![$h$ $h$](https://dxdy-03.korotkov.co.uk/f/2/a/d/2ad9d098b937e46f9f58968551adac5782.png)
,
![$[\![ \mathtt f_0 ]\!] = f_0$ $[\![ \mathtt f_0 ]\!] = f_0$](https://dxdy-03.korotkov.co.uk/f/2/6/c/26ca68be49191a8fb68f3fe1bd074d0082.png)
— получение функции по её коду.
-- Вс фев 28, 2021 18:38:00 --(Существование
![$j$ $j$](https://dxdy-04.korotkov.co.uk/f/3/6/b/36b5afebdba34564d884d347484ac0c782.png)
, разумеется, требует, чтобы в
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
входил в какой-то мере протокол работы
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
. Уже потому это сомнительная затея, если ожидать, что
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
на каждом шаге не делает ничего особо сложного, что мне стоило наверно добавить к описанию наверху.)