МЕНЮ

Каталог

ЗАДАЧА О ВЫЧИСЛЕНИИ ОПРЕДЕЛИТЕЛЯ Протокол DС
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

Постановка задачи

Пусть $ A$ - квадратная матрица большого порядка, $ d$ - вещественное число. $ P$ утверждает, что $ detA=d$ (т.е. обладает достаточными вычислительными ресурсами, чтобы вычислить $ detA$), $ V$ не может самостоятельно вычислить $ detA$ (не обладает достаточными ресурсами). $ P$ хочет убедить $ V$ в истинности этого утверждения, не раскрывая вычислений (по разным причинам), а $ V$ хочет быть уверенным, что число $ d$ действительно является значением $ detA$.
Описание протокола

1-ый вариант. 

Общий вход: $ A$ - квадратная матрица большого порядка, вещественное число $ d$. 

1) Первый шаг проверяющего: $ V$ преобразовывает $ A$ так, чтобы $ detA$ не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу $ A_1$ такую, что $ detA_1=detA$. Затем преобразовывает $ A$ так, чтобы $ detA$изменился, т.е. получает $ A_2$ такую, что $ detA_2 eq detA$. $ V$ отправляет $ A_1$ и $ A_2$доказывающему и просит его вычислить их определители. 

2) Первый шаг доказывающего: $ P$ вычисляет определители полученных матриц и отправляет их значения проверяющему. 

3) Второй шаг проверяющего: $ V$ проверяет, если $ detA_1 eq d$ или $ detA_2= d$, то останавливает проверку и отвергает доказательство. 

$ P$ и $ V$ повторяют шаги 1) и 3) $ m$ раз. 

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 3). В противном случае, отвергает. 

2-ой вариант. 

Общий вход: $ A$ - квадратная матрица большого порядка, вещественное число $ d$. 

1) Первый шаг проверяющего: $ V$ наугад выбирает бит $ alpha in {{0,1}}$. Если $ alpha=1$, то $ V$преобразовывает $ A$ так, чтобы $ detA$ не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу $ A_1$ такую, что $ detA_1=detA$. Если $ alpha=0$, то $ V$ преобразовывает $ A$ так, чтобы $ detA$ изменился, т.е. получает $ A_0$ такую, что $ detA_0 eq detA$. $ V$ отправляет $ A_alpha$ доказывающему и просит его вычислить определитель матрицы $ A_alpha$. 

2) Первый шаг доказывающего: $ P$ вычисляет определитель полученной матрицы и отправляет его значение проверяющему. 

3) Второй шаг проверяющего: $ V$ проверяет, если $ detA_1 eq d$ или $ detA_2= d$, то останавливает проверку и отвергает доказательство. 

$ P$ и $ V$ повторяют шаги 1) и 3) $ m$ раз. 

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 3). В противном случае, отвергает.

 

Основные сведения

 
Ссылки
  1. Бекенов М.И., Оспанов Р.М. Пример протокола интерактивного доказательства. Международная конференция "МАЛЬЦЕВСКИЕ ЧТЕНИЯ" (Новосибирск, 11–15 ноября 2013 г.) Тезисы докладов. С.28