Являются ли доли секрета Шамира равномерно распределенными случайными числами?

Позволять $t$ быть порогом в схеме обмена секретами Shamir (SSS).

Предположим, мы знаем $t'<t$ акции. Предположим, что нам даны некоторые случайные значения, равномерно выбранные из того же поля, что и поле, используемое в SSS.

Вопрос: можем ли мы отличить случайные значения от долей с незначительной вероятностью?

Каждое значение степени $t-1$ полный полином SSS $P$ оценивается в любой $х$ в конечном поле $F$ она определена над равномерно распределена в $F$. Видеть этот ответ Например.

Теперь предположим $tâ<t$ акции раскрываются, говорят, что они $Sâ=\{(x_1,P(x_1)),\ldots,(x_{tâ},P(x_{tâ}))\}.$

Если первоначальный набор акций был $S$ непустое множество $T=S\setminus Sâ$ теперь однозначно определяет действительный интерполяционный полином Лагранжа степени $t-tâ-1$ учитывая любой $ т-т $ точки $х$ в $K \setminus \{x_1,\ldots,x_{tâ}\}$.

Алгоритм различения: Позволять $к>т-т$ и пусть заявленные доли $$C=\{(x_j,y_j):1\leq j \leq k\}$$ быть данным. Если это подлинные акции $ т-т $ из них даст тот же интерполяционный многочлен Лагранжа, что и любое другое такое подмножество того же размера. Если $y_j$ случайны, две разные интерполяции Лагранжа говорят, что две поддерживаются на $$A=\{x_1,\ldots,x_{t-tâ}\}$$ и дальше $$Aâ=\{x_2,\ldots,x_{t-tâ},x_{t-tâ+1}\}$$ дам разные Интерполяционные полиномы Лагранжа с вероятностью $$1-\frac{1}{q}$$ куда $q$ размер поля, которое мы используем.

На самом деле, даже если только одна акция в $A \bigcup Aâ$ является случайным, это свойство будет сохраняться, поскольку по крайней мере одна из интерполяций даст случайный многочлен.

Предположим, мы знаем $t'<t$ акции. Предположим, что нам даны некоторые случайные значения, равномерно выбранные из того же поля, что и поле, используемое в SSS.

Вопрос: можем ли мы отличить случайные значения от долей с незначительной вероятностью?

Это зависит.

Теперь есть два возможных способа интерпретировать ваш вопрос (и хотя ответ одинаков для обоих, логика немного отличается). Вот способы, которые я вижу:

• Эти $г$ «случайные значения» следует рассматривать все сразу как потенциальные доли; то есть противнику было дано всего $т'+г$ акции, $t'$ из которых являются истинными долями, и $г$ из которых могут быть случайными значениями или (с точки зрения противника) также могут быть истинными долями. Если это так, следуйте приведенной ниже логике.

• Эти $г$ «случайные значения» — это все возможности отсутствующей доли. Это, $r-1$ из них являются случайными значениями (и противник это знает), это последнее значение также может быть случайным значением, а может быть истинным значением - противник не знает, какое, и он также не знает, какое может быть истинным значением. истинное значение. Если это так, следуйте приведенной ниже логике, но с $г=1$, и перебрать различные возможности честной доли.

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

В том случае, если $t'+r<t$, то противник ничего не может определить; все эти доли выглядят случайными. То есть для любых значений известных долей и любого значения общего секрета существуют возможные коэффициенты к неизвестному многочлену, которые привели бы к наблюдаемым значениям (и оказывается, что существует равное количество возможностей, не зависящих от наблюдаемые значения, следовательно, противник не может получить даже никакой вероятностной информации).

С другой стороны, если $t'+r\get$, то у противника есть подход; он может взять имеющиеся у него акции (как заведомо хорошие, так и с сомнительным провидением) и реконструировать, какую общую тайну они подразумевают; Затем он проверит, возможен ли этот общий секрет. Если это не одно из возможных значений, он знает, что некоторые доли, которые он использовал, были неправильными.

Нет, мы не можем.Мы знаем, что SSS совершенен, что означает, что знание (t-1) или меньшего количества долей не дает информации о s - следовательно, о других долях-