Вопрос связан со схемой совместного использования нескольких секретов, описанной в следующем документе:
[FY92] Мэтью К. Франклин, Моти Юнг:
Коммуникационная сложность безопасных вычислений (расширенный реферат). СТОК
1992: 699-710 (Соединять)
Ниже приводится некоторая предыстория. Однако, если вы знакомы с этой статьей, вы можете сразу перейти к основному вопросу ниже (выделен жирным шрифтом в заголовке).
А $(t-k+1,t+1;k,n)$- схема совместного использования нескольких секретов, как определено в [FY92], позволяет дилеру обмениваться $к$ секреты среди $n$ игроков, таких, что любое подмножество $t+1$ игроки или более могут восстановить $к$ секреты и любое подмножество игроков размером до $т-к+1$ не могу узнать никакой информации о $к$ секреты.
Схема совместного использования нескольких секретов в [FY92] использует следующие настройки/системные параметры:
- Позволять $F$ быть конечным полем.
- Позволять $s_1,\cdots,s_n \в F$ быть секреты дилера.
- Позволять $\alpha_1,\cdots,\alpha_n$ и $e_1,\cdots,e_n$ быть предварительно выбранными элементами $F$ которые известны всем сторонам.
- Позволять $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$, куда $q(x) \in_R F[x]$ с $ deg (q (x)) = (tk) $, и
$$L_i(x)= \frac{\prod_{j\neq i}(xe_j)}{\prod_{j\neq i}(e_i-e_j)}$$
Дилер распределяет долю $р(\альфа_я)$ верхний слой $P_i$, за $1\leq i \leq n$.
Любое подмножество игроков размера $\geq т+1$, могут объединить свои доли вместе и восстановить полином $р(х)$, а затем вычислить секреты $s_i = p(e_i)$ за $1\leq i \leq n$.
И наоборот, для любого подмножества $т-к+1$ акций существует единственный полином этих акций и любых $к$ секреты. Следовательно, любое подмножество $т-к+1$ игроки узнают любую информацию о $к$ секреты.
Вычисление долей произведения секретов из долей отдельных секретов
Позволять $(y_1,\cdots,y_n)$ быть множественной долей секретов $(s'_1,\cdots,s'_n)$, и $(z_1,\cdots,z_n)$ быть множественной долей секретов $(s''_1,\cdots,s''_n)$. [FY92] описывает алгоритм вычисления $(v_1,\cdots,v_n)$ продукта секретов $(s'_1 s''_1,\cdots,s'_n s''_n)$ от отдельных мульти-акций $(y_1,\cdots,y_n)$ и $(z_1,\cdots,z_n)$.
Алгоритм работы следующий:
- Каждый игрок $P_i$ вычисляет $w_i = y_i \times z_i$. Это приводит к кортежу $(w_1,\cdots,w_n)$ который кодирует секреты $(s'_1 s''_1,\cdots,s'_n s''_n)$ используя $2т$-полином степени.
- Поскольку общий ресурс с несколькими секретами должен использовать $t$многочлен -степени, кортеж $(w_1,\cdots,w_n)$ не является допустимым множественным обменом секретами. Вместо этого это называется псевдо-мультиакцией.
- Процедура понижения степени необходима для преобразования $(w_1,\cdots,w_n)$ псевдо-мульти-поделиться на действительный мульти-поделиться $(v_1,\cdots,v_n)$, то есть тот, который использует степень-$t$ многочлен вида $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$ как описано выше.
Шаг понижения степени и основная тема/вопрос этого поста
[FY92] дает следующую формулу для расчета $(v_1,\cdots,v_n)$ от псевдо мультишеринга $(w_1,\cdots,w_n)$.
$$(w_1,\cdots,w_n). А = (v_1,\cdots,v_n)$$
куда
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
и
- $B_\ell$ — матрица Вандермонда, $(я,j)$ запись $(\alpha_j - e_\ell)^{i-1}$
- $Chop_{t-k+1}$ матрица проекции на первый ${т-к+1}$ векторы космического базиса.
- $M_\ell$ матрица, чья $(я,j)$ запись $L_\ell(\alpha_i)$ за $я=j$, и ноль везде.
Главный вопрос этого поста
Авторы не объясняют, как они вывели формулу.
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
Может ли кто-нибудь помочь мне вывести эту формулу или доказать ее правильность? [Я не сомневаюсь, что это правильно. Я просто хочу выяснить, как авторы его получили]
Вот некоторые из подходов, которые я пробовал до сих пор.
Во-первых, обратите внимание, что мы можем переписать полином, используемый для разделения, как сумму $к$ условия следующим образом.
$$
\начать{выровнять*}{2}
p(x) &= q(x) \prod_{\ell=1}^{k}(x-e_\ell) + \sum_{\ell=1}^{k} s_\ell L_\ell(x ) \
&= q(x) \frac{1}{k} \sum_{\ell=1}^{k} \left(\prod_{\ell=1}^{k}(x-e_\ell)\ справа) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \
&= q(x) \ \sum_{\ell=1}^{k} \left(\frac{(x-e_\ell)}{k} L_\ell(x) \right) + \sum_{\ ell=1}^{k} s_\ell L_\ell(x) \
&= \sum_{\ell=1}^{k} \left(\frac{q(x)(x-e_\ell)}{k} +s_\ell\right) L_\ell(x) \
&= \sum_{\ell=1}^{k} q'_\ell(x) L_\ell(x)
\end{выравнивание*}
$$
куда $q'_\ell(x)=\frac{1}{k}q(x)(x-e_\ell) +s_\ell$ это $(т-к+1)$-полином степени.
Теперь предположим, что у нас есть два набора секретов. $(s'_1,\cdots,s'_n)$ и $(s''_1,\cdots,s''_n)$ через многочлены $p_1(x)$ и $p_2(x)$. Продукт $P(x)=p_1(x)p_2(x)$ это $2т$-полином степени, который также может быть записан в виде суммы $к$ условия, как показано ниже:
$$
\начать{выровнять*}{2}
Р(х) &= р_1(х) р_2(х) \
&= \sum_{\ell=1}^{k} q'_\ell(x) p_2(x) L_\ell(x)\
&= \sum_{\ell=1}^{k} Q_\ell(x) L_\ell(x)\
&= \sum_{\ell=1}^{k} Q'_\ell(x-e_\ell) L_\ell(x)\
\end{выравнивание*}
$$
куда
- $Q_\ell(x)= q'_\ell(x) \ p_2(x)$ это $(2т-к+1)$-полином такой степени, что $Q_\ell(e_\ell)=s_\ell$ ($s_\ell = s'_\ell s''_\ell$ является продуктом секретов, которые мы хотим вычислить.)
- Полином $Q'_\ell(x)$ получается из $Q_\ell(x)$ заменой переменной так, что $Q'_\ell(x-e_\ell) = Q_\ell(x)$. В частности, $Q'_\ell(0) = Q_\ell(e_\ell) = s_\ell$.
Позволять $H_\ell=(h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0)$ обозначим вектор размера $n$ содержащие коэффициенты $Q'_\ell$. В частности, у нас есть $h_{0,\ell} = s_\ell$.
Позволять $(w_1,\cdots,w_n)$ быть псевдо-множественной долей секретов $(s_1,\cdots,s_n)$. Тогда у нас есть
$$
\начать{выровнять*}{2}
(w_1,\cdots,w_n) &= (P(\alpha_1),\cdots,P(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Б_\элл\ . М_\элл
\end{выравнивание*}
$$
куда $B_\ell$ матрица Вандермонда размера $n$ чья $(я,j)$ запись $(\alpha_j-e_\ell)^{i-1}$, и $M_\ell$ представляет собой квадратную матрицу размера $n$ чья $(я,j)$ запись $L_\ell(\alpha_i)$ за $я=j$, и $0$ где-либо еще.
С другой стороны, пусть $(v_1,\cdots,v_n)$ быть многократным долей секретов $(s_1,\cdots,s_n)$ и разреши $ Р (х) $ быть соответствующей степени-$t$ многочлен. Тогда у нас есть
$$
\начать{выровнять*}{2}
(v_1,\cdots,v_n) &= (R(\alpha_1),\cdots,R(\alpha_n))\
&= \sum_{\ell=1}^{k} H_\ell \ . Chop_{t-k+1} \ . Б_\элл\ . М_\элл
\end{выравнивание*}
$$
Вышеупомянутое верно, потому что многочлен $ Р (х) $ определенное ниже, действительно является степенью-$t$ многочлен такой, что $R(e_\ell) = s_\ell$ для всех $1 \leq \ell \leq k$.
$$
\начать{выровнять*}{2}
R(x) &= \sum_{\ell=1}^{k} Q''_\ell(x-e_\ell) L_\ell(x)\
\end{выравнивание*}
$$
с $Q''_\ell(x-e_\ell)$ а $(т-к+1)$полином такой степени, что $Q''_\ell(0)=s_\ell$ для всех $1 \leq \ell \leq k$.
С $Q''_\ell(0)=Q'_\ell(0)=h_{0,\ell}=s_\ell$ для всех $1 \leq \ell \leq k$, следующий кортеж является допустимым набором коэффициентов для $Q''_\ell(x)$:
$$
\начать{выровнять*}{2}
Ад \ . Chop_{t-k+1} &= (h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0) \ . Chop_{t-k+1}\
&= (h_{0,\ell},\cdots,h_{t-k,\ell},0,\cdots,0)
\end{выравнивание*}
$$
Теперь из двух выражений $(w_1,\cdots,w_n)$ и $(v_1,\cdots,v_n)$ выше, нам нужно добраться до формулы
$$(w_1,\cdots,w_n). А = (v_1,\cdots,v_n)$$ с
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$
Любые мысли или предложения?
