Оценка трудоёмкости восстановления секрета

Естественным образом возникает вопрос о том, насколько надежно защищает предложенный способ разделения секрета от восстановления секрета на основе знания данных предоставляемых поставщикам облачных вычислений (CP). Представляется возможным использовать строго доказуемую неединственность решения. Или единственность с точностью до широкого класса функций, как инструмент в защите информации при решении краевых задач с привлечением неконтролируемых вычислительных ресурсов.

Формализация задачи

Указанный тезис можно пояснить на простейшем примере. Рассмотрим две односвязные области: и задачу Дирихле для уравнения Лапласа:

Решение это задачи существует и единственно при достаточно слабых условиях на границы и рассматриваемые классы граничных функций. Предположим, что задача решается численно с помощью альтернирующего метода Шварца, где итерации последовательно проводятся на двух подобластях представляющие из себя вложенные кольца. Кольцо примыкает к и контролируется вычислительным устройством А, а остальная часть контролируется вычислительным устройством В. Возникает вопрос, можно ли обладая информацией о решении в области получить информацию о границе и значениях функции или ее производных на ? Если решение такой задачи будет неединственно или единственно с точностью до широкого класса функций, то подобную схему можно использовать для вычислений с арендой мощных вычислительных устройств и с гарантией сохранения секрета.

Простой случай

Рассмотрим три краевые задачи для уравнения Лапласа и покажем, насколько трудоемким является восстановление границы неизвестной области и значений функции на ней, в том случае, когда известно решение на некоторой области топологически эквивалентной кольцу. Тем обстоятельством, что функция сеточная и условной корректностью рассматриваемых задач, будем пренебрегать. Покажем, что решение в каждом из этих случаев неединственно.

Рассмотрим задачу Коши для уравнения Лапласа:

где односвязная область, строго включена в и ее граница не пересекается с границей . Заданы:

Задача заключается в нахождении неизвестных функции , и области :

.

Если выполнятся условия Неймана: , то область может быть пустым множеством, точнее, если сужение решения задачи Неймана на границу равно заданному значению: . Но оно может быть и не пустым, а любым, включенным в . Таким образом, в этом, самом простом случае решение неединственно. Очевидно, что в случае выполнения условия Неймана, выполнения условий согласования между граничными значениями функции и ее нормальной производной область определяется неединственным образом. Т.е вырезая из области любое , не касающееся границы мы никак не влияем на решение вне и граничные условия.

Более сложный случай

Как поступать в более сложном случае, когда согласования между граничными условиями нет? Рассмотрим логарифмический потенциал по неизвестной площади и два нелинейных уравнения, выполняющихся на границе , обозначим их уравнения А:

где это неизвестная константа. Второе уравнение при выборе конкретного хорошо известно, это обратная задача гравиметрии определения формы области. Предположим, что решение второго уравнения единственно. Тогда, подставляя решение в первое уравнение, мы в общем случае не получим равенство. Надо будет подобрать такое и соответствующее ему решение, например, методом деления пополам так, что оба уравнения обратятся в тождество. Таким образом, мы можем найти область и функцию . Но обратим внимание на то, что рассматривая разложения: , где слагаемые с индексом 1 отвечают согласованным краевым условиям задачи Неймана. Мы можем получить решение в виде , где индекс 1 отвечает решению ранее рассмотренной задачи Неймана, а индекс 2 отвечает решению задачи с помощью логарифмического потенциала. Рассматривая в качестве любую область , такую, что мы получим функцию удовлетворяющую уравнению Лапласа в и заданным краевым условиям, что доказывает неединственность решения задачи.

Задача продолжения функции

Рассмотрим задачу продолжения функции, заданной на некоторой области гомеоморфной кольцу через внутреннюю границу в область считая, что , где односвязная область, включена в и ее граница не пересекается с границей . Значения функции в кольце известны .

Задача заключается в нахождении неизвестной области и неизвестной нормальной производной на границе этой области:

с условием .

Функция задает гармоническую функцию вне границы удовлетворяющую условию Неймана на границе: .

Для любых двух замкнутых кривых в , окаймляющих , можно составить два интегральных уравнения первого рода, связывающие известные значений и значения, индуцированные логарифмическим потенциалом простого слоя. Предположим, что решение этих уравнений существует и единственно вне зависимости от выбора кривых. Рассмотрим область . Функция задает нормальную производную с помощью которой можно также построить функцию гармоническую функцию вне и внутри . В самом деле, из-за отсутствия источников и в качестве плотности можно взять . Внутри кольца и вне его функция совпадает с индуцированной ранее, т.к. их разность является гармонической функцией с нулевыми условиями Дирихле и Неймана на границе . В итоге мы получим неединственность , при принятом допущении, что решение системы интегральных уравнений единственно задает .

Условие непротекания

Предположим, что на границе задано условие непротекания . В этом случае построение потенциала с помощью логарифмического потенциала простого слоя, как в предыдущем случае, невозможно. Как поступить в этом случае? Рассмотрим решение смешанной задаче Неймана в кольце :

,

и покажем, что выбор неединственен. Функции можно поставить в соответствие сопряженную гармоническую функцию так, что будет голоморфной. Если мы отступим от и выберем некоторую точку ,лежащую во внутренности , то через нее проходит , линия уровня . На этой линии также будет выполняться условие непротекания. Область, ограниченную можно рассматривать как , и будет гармонической функцией в .

Таким образом, практическая задача сводится только к методу подбора, который можно организовать, обладая некоторой априорной информацией, и выбирая вид так, чтобы на внешней границе происходила наиболее гладкая склейка с известным вне решением и его производными. Оценим трудоемкость такого подхода. Если, например, сетка в подобласти представляет собой образ прямоугольной сетки размера где число шагов сетки по нормали от , а число шагов сетки по поверхности, то число выборов «гладкой функции» описывающей будет равно . Отсюда следует, что уже при возникает комбинаторный взрыв. Решение задачи продолжения методом подбора невозможно на современной и перспективной вычислительной технике.

Обратим также внимание на то, что неизвестными (секретом) являются не только и или но и параметры сгущения или организации сетки внутри области . А это не только полностью исключает возможность решения задачи за приемлемое время, а ставит вопрос об алгоритмической неразрешимости задачи В.