2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Есть ли способ получить гарантии для такого
Сообщение28.02.2021, 16:12 
Заслуженный участник


27/04/09
28128
Есть функция $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$ на каждом шаге не делает ничего особо сложного, что мне стоило наверно добавить к описанию наверху.)

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение09.03.2021, 22:34 
Аватара пользователя


07/03/16

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

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение09.03.2021, 23:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение10.03.2021, 21:50 


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

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение10.03.2021, 22:35 
Заслуженный участник


27/04/09
28128
ipgmvq в сообщении #1508609 писал(а):
А не хочет делиться исходной системой
А хочет — но не хочет, чтобы результаты работы системы фальсифицировали.

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

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

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение11.03.2021, 21:00 


27/06/20
330
arseniiv в сообщении #1508619 писал(а):
а хотят удостовериться с меньшими затратами

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

 Профиль  
                  
 
 Re: Есть ли способ получить гарантии для такого
Сообщение11.03.2021, 21:17 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group