Есть ли способ получить гарантии для такого

[arseniiv]

Есть функция $g\colon (A \to B) \times S \to C$, проделывающая некоторое вычисление, использующее функцию $f\colon A \to B$ и некий дополнительный аргумент $s$. Можно ли иметь функцию $g'\colon (A \to B) \times S \times X \to C \times Y$ такую*, что $g'(f, s, x) = (g(f, s),\ldots)$ и такую, что просто проверить, что $(c, y)$ — это действительно скорее всего результат применения $g'$ к некоторым известным нам аргументам (а не результат применения какой-то подкрученной злоумышленником $g''$) — проще, чем посчитать $g'$.

* И чтобы, разумеется, она вообще была практически реализуема на тьюринг-ограниченной архитектуре, если реализуема $g$.

Дополнительно, у нас может не быть возможности самим посчитать $g'$, потому что вместо конкретной $f = f_0$ нам дан некоторый хеш $h(\mathtt f_0)$ её кода $\mathtt f_0$ (будем считать, что у $f_0$ только одна реализация $\mathtt f_0$ и потому ей соответствует только один хеш), где $h$ известная функция — но нам всё равно хотелось бы иметь какие-то гарантии, что (при известных всем $h(\mathtt f_0), s, x$) переданное нам $(c, y)$ — это $g'(f_0, s, x)$.

Это описывает такую ситуацию: $g$ симулирует какую-то систему, полностью задаваемую параметрами $s$, и оценивает управление $f$ для неё. Хочется довести $g$ до какой-то затем публично известной $g'$, которую каждый проверяющий свою $f_0$ мог бы запустить у себя сам и надеяться, что результаты запуска (вместе с параметрами) позволят другим считать, что он действительно воспользовался $g'$ и ничего не менял в её коде, не пользовался никакими уязвимостями в процессе выполнения и т. п., и притом было бы хорошо, если бы ему не надо было показывать сам код своей функции, вместо того дав что-то безобидное типа $h(\mathtt f_0)$.

Как я понимаю, задача почти исключительно требует очень жёстко впутать вычисление $h(\mathtt f_0)$ в каждый шаг симуляции в $g'$, значимый для получения результатов? (Это выглядит ужасно нереализуемым; но если это не предполагать, то мы вроде очень легко сможем написать $g''$, делающую что нам захочется, так как код $g'$ по условию всем известен.) Или можно что-то попроще? Я вообще в криптографии не разбираюсь, знаю только некоторые идеи и что у неё можно типично просить.

-- Вс фев 28, 2021 18:15:02 --

Если больше разных результатов выполнения $g'$ дают большую гарантию, предполагается, что можно варьировать параметр $x$ как душе угодно (и это вынужденно скажется на $y$ из результата).

-- Вс фев 28, 2021 18:33:44 --

Было бы вообще прекрасно, если бы существовала $j\colon X \times C \times Y \times H \to S$, такая что $g'([\![ \mathtt f ]\!], j(x, c, y, h(\mathtt f)), x) = (c, y)$ для всех $s, c, x, y, \mathtt f$ (и когда определены подвыражения $[\![ \mathtt f ]\!], j(\ldots)$ — не любой код задаёт подходящую $f$ и не всегда $(c, y) \in \operatorname{cod} g'$), вычислимая проще $g'$. Но я думаю, это невозможно или искать подходящую $g'$, когда $g$ достаточно хитра, просто нецелесообразно.

Выше $H$ — тип значений $h$, $[\![ \mathtt f_0 ]\!] = f_0$ — получение функции по её коду.

-- Вс фев 28, 2021 18:38:00 --

(Существование $j$, разумеется, требует, чтобы в $y$ входил в какой-то мере протокол работы $g$. Уже потому это сомнительная затея, если ожидать, что $g$ на каждом шаге не делает ничего особо сложного, что мне стоило наверно добавить к описанию наверху.)

[Emergency]

Почти ничего не понял, но кажется речь об этом Криптосистема с открытым ключом.
Извините, если не так.

[arseniiv]

Не, просто асимметричное шифрование само по себе здесь ничего не решит.

[ipgmvq]

arseniiv
Да, на первый вгляд это кажется невозможным.
А какую примерно практическую задачу поможет решить такая система?
Я понял, что есть две стороны А и Б.
У А есть система, у Б функция для неё.
А не хочет делиться исходной системой, а Б функцией.
Мне не совсем ясно следующее:
Известны ли публично X? Сколько этого X для теста функции? Постоянны ли X для всех пользователей производной системы или X меняются со временем? Выбирает ли сторона Б сами X, или они поставляются стороной А?

[arseniiv]

ipgmvq в сообщении #1508609 писал(а):

А не хочет делиться исходной системой

А хочет — но не хочет, чтобы результаты работы системы фальсифицировали.

Ну и для простой постановки можно считать, что Б тоже вполне готов делиться функцией, но всё же что другие не хотят запускать её на системе А у себя сами, а хотят удостовериться с меньшими затратами.

ipgmvq в сообщении #1508609 писал(а):

Мне не совсем ясно следующее:
Известны ли публично X? Сколько этого X для теста функции? Постоянны ли X для всех пользователей производной системы или X меняются со временем? Выбирает ли сторона Б сами X, или они поставляются стороной А?

Конкретные $X$ может выбирать и Б, но можно представить ситуацию, когда ему могут их предлагать.

[ipgmvq]

arseniiv в сообщении #1508619 писал(а):

а хотят удостовериться с меньшими затратами

Мне кажется, что если для запуска $g'$ с целью верификации препятствием является только вычислительная сложность $g'$, то вариантом будет только наличие certification authority с большими вычислительными мощностями, которая за плату (себестоимость плюс разумная маржа) будет запускать вычисления с использованием предоставленной и подписанной приватным сертификатом заказчика функции с дальнейшей подписью хэша функции и результата симуляции приватным сертификатом certification authority.
Если заказчик предпочитает сохранять функцию в секрете, то этап, вовлекающей эту функцию, можно реализовать через API от certification authority, где соединение с заказчиком будет удостоверенно сертификатом последнего, путем последовательной интерактивной пересылки аргументов заказчику и получением обратно результатов для продолжения симуляции. Опять же заказчик предоставляет подписанный своим приватным сертификатом хэш функции, и его и результаты симуляции подписывает certification authority своим приватным сертификатом, которому все доверяют.

[arseniiv]

Эх! Точнее не эх, мне эта задача интересна была большей частью абстрактно, но если бы вдруг решение оказалось простым, я бы его себе закодил.