С этим вопросом я имею в виду умножение BGW Дженнаро и др. (PDF здесь).
Умножение описано на 4-й странице.
(Другим источником для меня был «Прагматичное введение в безопасные многосторонние вычисления» п. 43-44)
Краткое изложение процедуры умножения BGW:
Чтобы сделать умножение 2 секретных значений $\альфа$ и $\бета$ каждого игрока $P_i$ должен иметь долю $ f _ {\ альфа} (я) $ и $ f _ {\ бета} (я) $ куда $f_{\alpha}$ и $f_{\бета}$ являются случайными полиномами степени t из секретного обмена Шамира.
Теперь каждый игрок $P_i$ вычисляет $f_{\alpha}(i) \cdot f_{\beta}$ и отправляет доли этого значения $h_i(j)$ созданный со случайным полиномом степени t $h_i$ (так что $h_i(0) = (f_{\alpha} \cdot f_{\beta})(i)$) верхний слой $P_j$ за $1 \le j \le n$.
Далее в приведенной выше статье описывается, как игроки могут получить случайные доли степени t от стоимости $\альфа\cdot\бета$ (чтобы затем они могли восстановить результат умножения с этими долями):
Каждый игрок $P_i$ вычисляет значение $ Н (я) $ из полинома степени t $Ч$ который определяется как:
$$H(x) = \sum_{i=1}^{n} \lambda_i h_i(x)$$
($\lambda_i$s — соответствующие коэффициенты Лагранжа).
$Ч$ является случайным полиномом с
$$H(0) = \sum_{i=1}^{n} \lambda_i h_i(0) = \sum_{i=1}^{n} \lambda_i (f_{\alpha} \cdot f_{\beta })(i) = (f_{\alpha} \cdot f_{\beta})(0) = \alpha \cdot \beta$$
Мой вопрос: Действительно ли H(x) имеет степень t? Не может ли он также быть больше, потому что $n$ точки от разные полиномы степени t $h_i$ за $1 \le i \le n$ используются для интерполяции? Обычно утверждают, что линейные операции над $(т,п)$ общие акции приводят к новым $(т,п)$ акции и потому что $h_i$ функции имеют степень $t$ линейные комбинации значений $h_i{j}$ за $1 \le i \le i$ должно привести к $(т,п)$ также акции. Справедливо ли это и в этом сценарии, поскольку мы всегда комбинируем значения разной степени? $t$ многочлены одновременно $х$ стоимость?
Другой вопрос: Также отмечается, что $t$ должен быть таким, чтобы $2t+1 \le n$. Это действительно необходимо? не будет $t+1 \le n$ достаточно, потому что $Ч(х)$ степень $t$ в любом случае, или информация из 2т+1 акций необходима для правильного построения $Ч(х)$? (Моя гипотеза заключалась в том, что без $2т+1$ Коэффициенты Лагранжа $\лямбда_i$, $Ч(0)$ не будет $\альфа\cdot\бета$)
«Прагматичное вступление» с. 44 говорит, что только с $2t+1 \le n$ у игроков достаточно информации, чтобы определить значение $(f_{\alpha} \cdot f_{\beta})(0)$. Почему это так?
